Programming
in C
CHAPTER -11
LINKED LISTS
LINKED LIST
• A linked list in simple terms is a linear collection of data elements. These data elements are called
nodes.
• Linked list is a data structure which in turn can be used to implement other data structures. Thus, it acts
as building block to implement data structures like stacks, queues and their variations.
• A linked list can be perceived as a train or a sequence of nodes in which each node contain one or more
data fields and a pointer to the next node.
START
1 2 3 4 5 6 7 X
In the above linked list, every node contains two parts- one integer and the other a pointer to the
next node. The left part of the node which contains data may include a simple data type, an array or
a structure. The right part of the node contains a pointer to the next node (or address of the next
node in sequence). The last node will have no next node connected to it, so it will store a special
value called NULL.
LINKED LIST contd.
• Linked list contains a pointer variable, START which stores the address of the first node in the list.
• We can traverse the entire list using a single pointer variable START. The START node will contain the address of
the first node; the next part of the first node will in turn store the address of its succeeding node.
• Using this technique the individual nodes of the list will form a chain of nodes. If START = NULL, this means that the
linked list is empty and contains no nodes.
• In C, we will implement a linked list using the following code:
• struct node
• {
• int data;
• struct node *next;
• };
START
If we want to add a node to an already existing linked list in the
1
DATA NEXT memory, we will first find any free space in the memory and then use
1 H 4 it to store the information.
2
The operating system maintains a free pool which is a linked list of a
3
E 7
of all free memory cells. It maintains a pointer variable AVAIL which
4
5
stores the address of the first free space.
6
When you delete a node from the linked list, the operating system
7 L 8
adds the freed memory to the free pool.
8 L 10
AVAIL
9 The operating system will perform this operation whenever it finds
9
10 O -1 the CPU idle or whenever the programs are falling short of memory.
The operating system scans through all the memory cells and mark
the cells that are being used by some or the other program. Then, it
START pointing to the collects all those cells which are not being used and add their
first element of the
linked list in memory address to the free pool so that it can be reused by the programs.
This process is called garbage collection. The whole process of
collecting unused memory cells (garbage collection) is transparent to
the programmer.
LINKED LIST VERSUS ARRAYS
• An array is linear collection of data elements and a linked list is a linear collection of nodes. But unlike an
array, a linked list does not store its nodes in consecutive memory locations.
• Another point of difference between an array and a linked list is that a linked list does not allow random
access of data. Nodes in a linked list can be accessed only in a sequential manner.
• But like an array, insertions and deletions can be done at any point in the list.
• Another advantage of linked list over an array is that, we can add any number of elements in the list.
This is not possible in case of an array. For example, if we declare an array as int marks[10], then the
array can store maximum ten data elements but not even a single more than that. There is no such
restriction in case of a linked list.
• Thus linked lists provide an efficient way of storing related data and perform basic operations such as
insertion, deletion and updating of information at the cost of extra space required for storing address of
the next node.
SINGLY LINKED LIST
• A singly linked list is the simplest type of linked list in which every node contains some data and a
pointer to the next node of the same data type. By saying that the node contains a pointer to the next
node we mean that the node stores the address of the next node in sequence.
START
1 2 3 4 5 6 7 X
Algorithm for traversing a linked list
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Apply Process to PTR->DATA
Step 4: SET PTR = PTR->NEXT
[END OF LOOP]
Step 5: EXIT
SINGLY LINKED LIST
Algorithm to print the information stored in each node of the
linked list
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Write PTR->DATA
Step 4: SET PTR = PTR->NEXT
[END OF LOOP]
Step 5: EXIT
Algorithm to print the number of nodes in the linked list
Step 1: [INITIALIZE] SET Count = 0
Step 2: [INITIALIZE] SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR != NULL
Step 4: SET Count = Count + 1
Step 5: SET PTR = PTR->NEXT
[END OF LOOP]
Step 6: EXIT
Algorithm to search an unsorted linked list
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 while PTR != NULL
Step 3: IF VAL = PTR->DATA
SET POS = PTR
Go To Step 5
ELSE
SET PTR = PTR->NEXT
[END OF IF]
[END OF LOOP]
Step 4: SET POS = NULL
Step 5: EXIT
1 7 3 4 2 6 5 X
1 7 3 4 2 6 5 X
1 7 3 4 2 6 5 X
1 7 3 4 2 6 5 X
1 7 3 4 2 6 5 X
START
9 1 7 3 4 2 6 5 X
START
Algorithm to insert a new node in the beginning of the linked list
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET New_Node->Next = START
Step 6: SET START = New_Node
Step 7: EXIT
1 7 3 4 2 6 5 X
START, PTR
1 7 3 4 2 6 5 9 X
START PTR
Algorithm to insert a new node at the end of the linked list
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 10
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET New_Node->Next = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR->NEXT != NULL
Step 8: SET PTR = PTR ->NEXT
[END OF LOOP]
Step 9: SET PTR->NEXT = New_Node
Step 10: EXIT
Algorithm to insert a new node after a node that has value NUM
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Step 8 and 9 while PREPTR->DATA != NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR->NEXT
[END OF LOOP]
Step 10: PREPTR->NEXT = New_Node
Step 11: SET New_Node->NEXT = PTR
Step 12: EXIT
1 7 3 4 2 6 5 X
START, PTR, PREPTR
1 7 3 4 2 6 5 X
START PREPTR PTR
1 7 3 9 4 2 6 5 X
START
Algorithm to delete the first node from the linked list
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 5
[END OF IF]
Step 2: SET PTR = START
Step 3: SET START = START->NEXT
Step 4: FREE PTR
Step 5: EXIT
1 7 3 4 2 6 5 X
7 3 4 2 6 5 X
Algorithm to delete the last node of the linked list
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
START
Step 3: Repeat Step 4 and 5 while PTR->NEXT != NULL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR->NEXT
[END OF LOOP]
START
Step 6: SET PREPTR->NEXT = NULL
Step 7: FREE PTR
Step 8: EXIT
Algorithm to delete the node after a given node from the linked list
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 10
[END OF IF]
Step 2: SET PTR = START
Step 3: SET PREPTR = PTR
Step 4: Repeat Step 5 and 6 while PRETR->DATA != NUM
Step 5: SET PREPTR = PTR
Step 6: SET PTR = PTR->NEXT
[END OF LOOP]
Step7: SET TEMP = PTR->NEXT
Step 8: SET PREPTR->NEXT = TEMP->NEXT
Step 9: FREE TEMP
Step 10: EXIT
1 7 3 4 2 6 5 X
START, PREPTR, PTR
1 7 3 4 2 6 5 X
START PREPTR PTR
1 7 3 4 2 6 5 X
START
1 7 3 4 6 5 X
START
CIRCULAR LINKED LIST
• In a circular linked list, the last node contains a pointer to the first node of the list. We can have a
circular singly listed list as well as circular doubly linked list. While traversing a circular linked list, we can
begin at any node and traverse the list in any direction forward or backward until we reach the same
node where we had started. Thus, a circular linked list has no beginning and no ending.
START
1 2 3 4 5 6 7
DOUBLY LINKED LIST
A doubly linked list or a two way linked list is a more complex type of linked list which contains a
pointer to the next as well as previous node in the sequence. Therefore, it consists of three parts
and not just two. The three parts are data, a pointer to the next node and a pointer to the previous
node
START
X 1 1 2 3 4 X
In C language, the structure of a doubly linked list is given as,
struct node
{ struct node *prev;
int data;
struct node *next;
};
The prev field of the first node and the next field of the last node will contain NULL. The
prev field is used to store the address of the preceding node. This would enable to traverse
the list in the backward direction as well.
CIRCULAR DOUBLY LINKED LIST
• A circular doubly linked list or a circular two way linked list is a more complex type of linked list
which contains a pointer to the next as well as previous node in the sequence.
• The difference between a doubly linked and a circular doubly linked list is same as that exists
between a singly linked list and a circular linked list. The circular doubly linked list does not contain
NULL in the previous field of the first node and the next field of the last node. Rather, the next field
of the last node stores the address of the first node of the list, i.e; START. Similarly, the previous field
of the first field stores the address of the last node.
• Since a circular doubly linked list contains three parts in its structure, it calls for more space per node
and for more expensive basic operations. However, it provides the ease to manipulate the elements
of the list as it maintains pointers to nodes in both the directions . The main advantage of using a
circular doubly linked list is that it makes searches twice as efficient.
START
1 1 2 3 4
HEADER LINKED LIST
• A header linked list is a special type of linked list which contains a header node at the beginning of
the list. So, in a header linked list START will not point to the first node of the list but START will
contain the address of the header node. There are basically two variants of a header linked list-
• Grounded header linked list which stores NULL in the next field of the last node
• Circular header linked list which stores the address of the header node in the next field of the last
node. Here, the header node will denote the end of the list.
START
4
1 2 3 5 6 X
Header Node
4
START 1 2 3 5 6
Header Node
