Operations in Linked List

Generally, "linked list" are referred to a singly linked list. This list contains of a number of nodes in which each node has a next pointer to the following element. The link of the last node in the list is NULL and indicates the end of the list.

Basic Operations on a linked list

• Traversing the list
• Inserting an item in the list
• Deleting an item from the list

Traversing the list

Let us assume the head points to the first node of the list. To traverse the list, we do the following:

• Follow the pointers
• Display the contents of the nodes (or count) as they are traversed
• Stop when the next pointer points to NULL.

The listLength() function takes a linked list as input and counts the number of nodes in the list. It can be used for printing the list data with extra print function:

int listLength(struct Node* head){

struct Node* current = head;

int count = 0;

while(current != NULL){

printf(current -> value);

count ++;

current = current -> next;

}

return count;

}

Singly linked list Insertion

It has three cases:

• Inserting a new node before the head (at the beginning)
• Inserting a new node after the tail (at the end)
• Inserting a new node in the middle of the list (random location)

Insertion at the beginning

In this case, a new node is inserted before the current head nodne. Only one next pointer needs to be modified (new node's next pointer) and it can be done in two steps:

• Update the next pointer of the new node, to point to the current head.

• Update the head pointer to point to the new node

Insertion at the End

In this case, we need to modify two next pointers (last node's next pointer and new node's next pointer).

• New node's next pointer points to NULL

• Last node's next pointer points to the new node

Insertion in the Middle

Let us assume that we are given a position where we want to insert the new node. In this case also, we need to modify two next pointers.

• If we want to add an element at position 6 then we stop at position 5. That means we traverse 5 nodes and insert the new node. For simplicity, let us assume the fifth is called position node New node points to the next node of the position where we want to add this node.

• Position node's next pointer now points to the new node.

Let us now write the C code for the insertion for all three cases:

void insertInLinkedList(struct Node **head, int data, int position){

int k = 1;

struct Node *p, *q, *newNode;

newNode = (Node*)malloc(sizeof(struct Node));

if(!newNode){ //Check for memory errors

printf("Memory Error");

return;

}

newNode -> value = data;

p = *head;

if(position == 1) { // Insertion at the beginning

newNode -> next = p;

*head = newNode;

}

else { //Traverse the list until position-1

while ((p != NULL && ( k

k ++;

q = p;

p = p -> next;

}

if ( p == NULL) { // Insertion at the end

q -> next = newNode;

newNode -> next = NULL;

}

else { //Insertion in the middle

q -> next = newNode;

newNode -> next = p;

}

}

}

Singly Linked List Deletion

Similar to insertion, deletion also has three cases:

• Deleting the first node
• Deleting the last node
• Deleting an intermediate node

Deleting the First Node

First node (current node head) is removed from the list in two steps:

• Create a temporary node which will point to the same node as that of the head.

• Now, move the head node's pointer to the next node and dispose the temporary node.

Deleting the last node

In this case, the last node is removed from the list. This operation is a bit trickier than removing the first node, because algorithm should find anode, which is previous to the tail first. It can be done in three steps:

• Traverse the list and whle traversing maintain the previous node address also. By the time we reach the end of list, we will have two pointers, one pointing to the tail node and the other pointing to the node before the tail node.

• Update previous node's next pointer with NULL

• Dispose the tail node

Deleting an Intermediate Node

In this case, node to be removed is always located between two nodes. Head and tail links are not updated in this case. Such removal can be done in two steps:

• As similar to the previous case, maintain previous node while traversing the list. Once we find the node to be deleted, change the previous node's next pointer to next pointer of the node to be deleted.

• Dispose the current node to be deleted

Code:

void deleteNodeFromLinkedList(struct Node **head, int position) {

int k = 1;

struct Node *p, *q;

if (*head == NULL) {

printf("List Empty");

return;

}

p = *head;

if (position == 1) { //From the beginning

p = *head;

*head = *head -> next;

free (p);

return;

}

else { //Traverse the list until the position from which we want to delete

while ((p!=NULL) && (k<position-1)) {

k++;

q = p;

p = p -> next;

}

if (p == NULL) { //At the end

printf("Position doesn't exist");

}

else { //From the middle

q -> next = p -> next;

free(p);

}

}

}

References

1. Karumanchi, N. "Data Structures and Algorithms Made Easy"

2. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

3. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”