INTRODUCTION –It is a sequence of items (objects) where every item is linked to the next. They are linked to one another through pointers. There are two parts in each node: the first part contains the data, and the second part contains the address of the next node in the linked list. Address part of the node which is connected to next is also called a link. The following Fig. 1. shows a typical example of a node.

Fig. 2. shows a schematic diagram of a linked list. Each node is pictured with two parts. The left part of each node contains the data, and the right part represents the address of the next node. There is an arrow that shows that the first node is connected to the next node. 

IMPLEMENTATION OF LINKED LIST

When we say linked list, we are talking about a singly linked list. There are various types of linked lists which we will discuss below, but here we are going to implement a singly linked list. There is a concept of pointer and structure, what structure data type is in C++ language, also, how to access the structure members using that structure variable and pointer.

First of all, see the logical view of a linked list in Fig. 3, which shows the linked list having three nodes.

First, we have to create a node. 

Creating a node using a user-defined data type, i.e. structure :

Also Read: Function overloading in C++

TYPES OF LINKED LIST

 We can divide the linked list into the following three types mainly:

1. Singly-linked list
2. Doubly linked list
3. Circular linked list

1. Singly Linked List or One-Way Chain

In a singly linked list, all the nodes are arranged sequentially. A node in the singly linked list consists of two parts: the data part and the link/address part. The data part of the node stores actual information that is to be represented by the node, while the link or the address part of the node stores the address of its immediate successor.

A one-way chain or singly linked list can be traversed in one direction only; that is why it is known as a one-way chain. Fig. 4. shows the linked list.  

2. Doubly Linked List

In a singly linked list, as each node contains the next node’s address, it doesn’t have any record of its previous node. However, a doubly-linked list will apply in place of a singly linked list. As we also know, each node of the list contains the address of its previous node of the linked list, so we can find all the details about the previous node by using the previous address stored inside the previous part of each node in a linked list.

   Every node in the doubly linked list has three fields that are Left_Pointer, Right_Pointer and Data. Fig.5 shows a doubly linked list.

the point will point to the node on the left side (or previous node) that will hold the previous node’s address in a doubly-linked list. RPoint will point the right side (or next node) to the next node’s address in a linked list. Data will store the information of the node.

Representation of Doubly Linked List

3. Circular Linked List

A circular linked list is one where there is no beginning and no end. A singly linked list can be made a circular linked list by simply storing the address of the first node in the linked field of the last node in a linked list. A circular linked list is shown in Fig. 6

We can traverse a circular linked list until we reach the same node from where we started.

There is no null value present in any of the nodes in a circular linked list.

OPERATIONS ON LINKED LIST

The operations performed on the Linked List are as follows:

1. Creation
2. Insertion 
3. Deletion 
4. Traversing
5. Searching 
6. Concatenation

Creation operation is used to create a node or linked list. When a linked list is created with one node, an insertion operation is used to add more elements to the node.

Insertion operation is used to insert a new node at any location in the linked list. A new node may be inserted:

1. At the beginning of the linked list
2. At the end of the linked list
3. At any position in a linked list

Deletion operation is used to delete or remove a node from the linked list. A node may be deleted from the

1. Beginning of a linked list 
2. End of a linked list
3. Specified location of the linked list

Traversing is the process of going through each node from one end to another end of a linked list. In a singly linked list, we can visit from left to right, forward traversing, but we can not go from right to left. In a doubly-linked list, both side traversing is possible.

Concatenation is the process of appending the second list to the end of the first list in a linked list. Let us consider a list A having n nodes and B with m nodes. Then the concatenation will place the 1^st node of B in the (n+1)th node in list A. After concatenation, A will contain (n+m) nodes in the list.

EXAMPLES:

OPERATIONS ON SINGLY LINKED LIST

                 Some operations can be performed on a singly linked list. A list of all the operations is   given below.

Node Creation

INSERTION 

1. Insertion in a singly linked list: 

There are the following steps to insert a new node in the list. 

• Allocate the space for the new node and store data into the data part of the node in the singly linked list. 

• ptr = (struct node *) malloc(sizeof(struct node *)); o ptr → data = item 

• Now, link part of the new node pointing to the first node of the list. 

 • ptr->next = head; 

• Now, at last, we need to make the new node the first node of the list 

 • head = ptr; 

Algorithm 

STEP-1: IF PTR = NULL 

Write OVERFLOW

 Go to STEP-7

ELSE

STEP-2: SET NEW_NODE = PTR 

STEP-3: SET PTR = PTR → NEXT 

STEP-4: SET NEW_NODE → DATA = VAL 

STEP-5: SET NEW_NODE → NEXT = HEAD

 STEP-6: SET HEAD = NEW_NODE 

STEP-7: EXIT

DELETION 

Deletion in a singly linked list:

Deleting a node from the beginning of the list is the simplest operation of all the operations. Since the first node of the list is to be deleted, we have to make the head and point to the next of the head.

 • ptr = head;

 • head = ptr->next; 

 • The pointer ptr pointing to the head node is now free.  

 • free(ptr)

Algorithm 

STEP-1: IF HEAD = NULL

 Write UNDERFLOW

 Go to STEP-5 [END OF IF] 

STEP-2: SET PTR = HEAD 

STEP-3: SET HEAD = HEAD -> NEXT 

STEP-4: FREE PTR 

STEP-5: EXIT

Traversing in a singly linked list 

Traversing means visiting each node of the list when we perform operations on that. 

 ptr = head;

 while (ptr!=NULL)

 {

 ptr = ptr -> next;

 }

 Algorithm

 STEP-1: SET PTR = HEAD 

STEP-2: IF PTR = NULL 

WRITE “EMPTY LIST” 

GOTO STEP-7 

END OF IF 

STEP-4: REPEAT STEP-5 AND 6 UNTIL PTR == NULL 

STEP-5: PRINT PTR→ DATA 

STEP-6: PTR = PTR → NEXT 

[END OF LOOP] 

STEP-7: EXIT

Searching in a singly linked list 

Searching is used to find the location of a particular item in the list. The searching operation needs traversing through the list. 

Algorithm

 STEP-1: SET PTR = HEAD 

STEP-2: Set I = 0 

STEP-3: IF PTR = NULL 

WRITE “EMPTY LIST” 

GOTO STEP-8 

END OF IF 

STEP-4: REPEAT STEP-5 TO 7 UNTIL PTR == NULL 

STEP-5: if ptr → data = item write i+1 End of IF 

STEP-6: I = I + 1 

STEP-7: PTR = PTR → NEXT 

[END OF LOOP] 

STEP-8: EXIT

OPERATIONS ON DOUBLY LINKED LIST:

Node Creation

INSERTION

Insertion in a doubly-linked list:

 In the doubly linked list, each node of the list contains double pointers.

Algorithm

STEP-1: IF ptr = NULL Write OVERFLOW

Go to STEP-9 [END OF IF]

STEP-2: SET NEW_NODE = ptr

STEP-3: SET ptr = ptr -> NEXT

STEP-4: SET NEW_NODE -> DATA = VAL

STEP-5: SET NEW_NODE -> PREV = NULL STEP-6: SET NEW_NODE -> NEXT = START STEP-7: SET head -> PREV = NEW_NODE

STEP-8: SET head = NEW_NODE

STEP-9: EXIT

DELETION

Deletion in a doubly-linked list

• For deletion in doubly linked lists, we have to copy the head pointer to pointer ptr. We also have to shift the head pointer to its next.
  • Ptr = head;
  • head = head → next;
• now make the prev of this new head node point to NULL(prev=NULL). 
  • head → prev = NULL

Algorithm 

STEP-1: IF HEAD = NULL 

WRITE UNDERFLOW 

GOTO STEP-6 

STEP-2: SET PTR = HEAD 

STEP-3: SET HEAD = HEAD → NEXT 

STEP-4: SET HEAD → PREV = NULL 

STEP-5: FREE PTR 

STEP-6: EXIT

Traversing in a doubly-linked list

• Copy the head pointer in any of the temporary pointers, here we will be using ptr.
  • Ptr = head
• then traverse through the list. Keep shifting the value of the pointer variable ptr

until we find the last node of the list. The last node contains null.

• while(ptr != NULL)
• {
  • printf(“%dn”,ptr->data);
• ptr=ptr->next;
• }

Algorithm 

STEP-1: IF HEAD == NULL 

WRITE “UNDERFLOW” 

GOTO STEP-6 

[END OF IF] 

STEP-2: Set PTR = HEAD 

STEP-3: Repeat STEP-4 and 5 while (PTR == NULL) 

STEP-4: Write PTR → data 

STEP-5: PTR = PTR → next 

STEP-6: Exit

Searching in Doubly Linked List

• Copy head pointer into a temporary pointer variable, here we use ptr.
  • ptr = head
• declare a local variable I for assigning its value as 0.
  • i=0
• Traverse the list until the pointer becomes null(ptr==NULL). Keep shifting pointer to its next and increasing I by +1.
• Compare each element of the list with the other items which are to be searched.

Algorithm 

STEP-1: IF HEAD == NULL 

WRITE “UNDERFLOW” 

GOTO STEP-8 

[END OF IF] 

STEP-2: Set PTR = HEAD 

STEP-3: Set i = 0 

STEP-4: Repeat STEP-5 to 7 while (PTR == NULL) 

STEP-5: IF PTR → data = item return i 

[END OF IF] 

STEP-6: i = i + 1 

STEP-7: PTR = PTR → next

 STEP-8: Exit

OPERATION ON CIRCULAR SINGLY LINKED LIST:

INSERTION

Insertion into the circular singly linked list:

• In the first case, the condition head == NULL will be true. Since we know that, we are inserting the node is a circular singly linked list, so the node of the list will point to itself only. 
  • if(head == NULL)
  • {
    • head = ptr;
  • ptr -> next = head;
  • }
•  The condition head == NULL will become false, this means that there is at least one node in the list. Here, we have to traverse the list for reaching that point.
  • temp = head;
  • while(temp->next != head)
    • temp = temp->next;
• We have to make the next pointer of the last node point to the head node of the list.
  • temp -> next = ptr;
• the next pointer of temp will point to the existing head node of the list.
  • ptr->next = head;
• Make the new node ptr, which is a new head node of the circular singly linked list.
  • head = ptr;
• In this way, we inserted the node ptr into the circular singly linked list.

Algorithm 

STEP-1: IF PTR = NULL

 Write OVERFLOW 

Go to STEP-11 

[END OF IF] 

STEP-2: SET NEW_NODE = PTR 

STEP-3: SET PTR = PTR -> NEXT 

STEP-4: SET NEW_NODE -> DATA = VAL 

STEP-5: SET TEMP = HEAD

 STEP-6: Repeat STEP-8 while TEMP -> NEXT== HEAD 

STEP-7: SET TEMP = TEMP -> NEXT 

[END OF LOOP] 

STEP-8: SET NEW_NODE -> NEXT = HEAD 

STEP-9: SET TEMP → NEXT = NEW_NODE 

STEP-10: SET HEAD = NEW_NODE 

STEP-11: EXIT

DELETION

Deletion in a circular singly linked list:

To delete a node in a circular singly linked list, we have to make a few pointers for adjustments. 

Case 1: (The list is Empty)

If the condition head == NULL will become true, which means the list is empty, in this case, we just need to print underflow.

if(head  ==  NULL)

{

printf(“nUNDERFLOW”);

return;

}

Case 2: (The list contains a single node)

If the condition head → next == head will become true. This means the list contains a single node. In this case, we have to delete the entire list. 

if(head->next  ==  head)

{

head  =  NULL; free(head);

}

Case 3: (The list contains more than one node)

If there is more than one node in the list, then, in that case, we have to traverse the list by using the pointer ptr.

ptr  =  head;

while(ptr  ->  next  !=  head) ptr  =  ptr  ->  next;

End of the loop, the pointer points to the last node. As the last node of the list points to the head node. Now, the last node point to the next of the head node. 

o ptr->next = head->next; 

• Now, by using the free() method in the C language, free the head pointer.

 o free(head);

o head = ptr->next; 

• By this way, the node deletion from the circular singly linked list will be successful.

Algorithm

 STEP-1: IF HEAD = NULL 

Write UNDERFLOW

 Go to STEP-8

 [END OF IF] 

STEP-2: SET PTR = HEAD

 STEP-3: Repeat STEP-4 while PTR → NEXT == HEAD 

STEP-4: SET PTR = PTR → next 

[END OF LOOP] 

STEP-5: SET PTR → NEXT 

 HEAD → NEXT

 STEP-6: FREE HEAD 

STEP-7: SET HEAD = PTR → NEXT 

STEP-8: EXIT

Traversing in Circular Singly linked list

Traversing in a circular singly linked list can be possible by using a loop. Initialize the temporary pointer variable, which is temp, and it points to the head pointer and runs the while loop.

Algorithm 

STEP-1: SET PTR = HEAD 

STEP-2: IF PTR = NULL 

WRITE “EMPTY LIST” 

GOTO STEP-8 

END OF IF 

STEP-3: REPEAT STEP-4 AND 5 UNTIL PTR → NEXT != HEAD 

STEP-4: PRINT PTR → DATA 

STEP-5: PTR = PTR → NEXT 

[END OF LOOP] 

STEP-6: PRINT PTR→ DATA

 STEP-7: EXIT

Searching in a circular singly linked list

Searching in a circular singly linked list needs traversing. The item we want to search in the list is matched with each node data of the list once, if the match is found then the location of that item is returned otherwise -1 is returned.

Algorithm 

STEP-1: SET PTR = HEAD 

STEP-2: Set I = 0 

STEP-3: IF PTR = NULL 

WRITE “EMPTY LIST” 

GOTO STEP-8

 [END OF IF] 

STEP-4: IF HEAD → DATA = ITEM WRITE i+1 RETURN 

[END OF IF] 

STEP-5: REPEAT STEP-5 TO 7 UNTIL PTR->next == head 

STEP-6: if ptr → data = item write i+1 RETURN 

End of IF

 STEP-7: I = I + 1 

STEP-8: PTR = PTR → NEXT 

[END OF LOOP] 

STEP-9: EXIT

OPERATION ON CIRCULAR DOUBLY LINKED LIST

INSERTION 

Insertion in circular doubly linked list:

ptr  =  (struct  node  *)malloc(sizeof(struct  node));

• If the condition head == NULL becomes true then, the node will be added as the first node in the circular doubly linked list. 
  • head = ptr;
  • ptr -> next = head;
  • ptr -> prev = head;
• In the second scenario, the condition head == NULL becomes false. Then, we have to make a few pointers for adjustments. We have to reach the last node of the list by traversing through the list.
• temp = head;

while(temp -> next != head)

{

temp = temp -> next;

}

• Now at the end of the loop, the pointer temp would point to the last node of the list. 

• temp -> next = ptr;
• ptr -> prev = temp;
• head -> prev = ptr;
• ptr -> next = head;
• head = ptr;

Algorithm 

STEP-1: IF PTR = NULL 

Write OVERFLOW 

Go to STEP-13 

[END OF IF] 

STEP-2: SET NEW_NODE = PTR 

STEP-3: SET PTR = PTR -> NEXT 

STEP-4: SET NEW_NODE -> DATA = VAL 

STEP-5: SET TEMP = HEAD 

STEP-6: Repeat STEP-7 while TEMP -> NEXT == HEAD

 STEP-7: SET TEMP = TEMP -> NEXT 

[END OF LOOP] 

STEP-8: SET TEMP -> NEXT = NEW_NODE 

STEP-9: SET NEW_NODE -> PREV = TEMP 

STEP-10 : SET NEW_NODE -> NEXT = HEAD 

STEP-11: SET HEAD -> PREV = NEW_NODE

 STEP-12: SET HEAD = NEW_NODE 

STEP-13: EXIT

DELETION

Deletion in a Circular doubly linked list:

• The conditioning head → next == head will become true, then the list needs to be completely deleted.
• Assign head pointer of the list to null(head==NULL).
  • head = NULL;
  • free(head);
• The list contains more than one element in the list, then the condition head → next == head will become false
  • temp = head;
  • while(temp -> next != head)
  • {
  • temp = temp -> next;
  • }
• temp will point to the last node. 
  • temp -> next = head -> next;
• The new head node 
  • head -> next -> prev = temp;
• Now, free the head pointer and make its next pointer.
  • free(head);
  • head = temp -> next;

Algorithm 

Step-1: IF HEAD = NULL 

Write UNDERFLOW 

Go to STEP-8 

[END OF IF] 

Step-2: SET TEMP = HEAD 

Step-3: Repeat STEP-4 while TEMP –> NEXT == HEAD 

Step-4: SET TEMP = TEMP -> NEXT 

[END OF LOOP] 

Step-5: SET TEMP -> NEXT 

 HEAD -> NEXT 

Step-6: SET HEAD -> NEXT –> PREV = TEMP 

Step-7: FREE HEAD 

Step-8: SET HEAD = TEMP -> NEXT

Step-9: EXIT

ADVANTAGES AND DISADVANTAGES

ADVANTAGES

• Linked Lists are dynamic data structure. 
• Efficient memory utilization. Memory is allocated whenever it is required. 
• Insertion and deletion are easier and efficient as compilers to others.

DISADVANTAGES

• Memory is required to store an integer number is more. 
• It is time-consuming.

REAL/ PRACTICAL APPLICATIONS OF LINKED LIST:-

There is much real-life example of linked lists like- Train cars/coach, traffic light, chains etc. If we decide it category wise then-
1) For a Singly linked list

• Child brain (eg. In case a child recited a poem, if you ask him the last line then, he will have to read from the first line of the poem again as he cannot remember the last line directly).
  
• Traffic light (there are three signals – red, yellow and green). If we are at a stop position in the traffic light, we will first see the red and the green signal. After green, we see the yellow signal for a few seconds, and we cannot go directly to the red signal.

2) Doubly linked list

• DNA double-helix structure 
• Train coaches 
• Roller chain of bicycle/bike
• Undo functionality in photoshop or word

3) Circular linked list

• The time-sharing problem used in the operating system.
•  Boardgame (Multiple players)
•  Used to repeat the songs in a playlist
• Audio-video streaming

Conclusion- These operations are functional in many real/ practical applications. We learned how to traverse, append, insert and delete nodes from the linked list. Suppose we take the example of a PowerPoint presentation, where nodes are slides that are serially linked with one another. Many other applications may require thinking of the function of the list, where the list can easily be maintained.