Linked list deletion algorithm

Table of Contents
  • Traverse a Linked List
    • Algorithm: Traverse
  • Inserting Elements to a Linked List
    • Insert a Node at the beginning of a Linked list
      • Algorithm: InsertAtBeginning
    • Insert a Node at the end of a Linked list
      • Algorithm: InsertAtEnd
    • Insert a Node after a given Node in a Linked list
      • Algorithm: InsertAfterAnElement
  • Deleting Elements from a Linked List
    • Delete a Node from the beginning of a Linked list
      • Algorithm: DeleteFromBeginning
    • Delete last Node from a Linked list
      • Algorithm: DeleteFromEnd
    • Delete the Node after a given Node in a Linked list
      • Algorithm: DeleteAfterANode
  • Search
    • Algorithm: Search

A singly linked list is the most simple type of linked list, with each node containing some data as well as a pointer to the next node. That is a singly linked list allows traversal of data only in one way. There are several linked list operations that allow us to perform different tasks.

The basic linked list operations are:

  • Traversal Access the nodes of the list.
  • Insertion Adds a new node to an existing linked list.
  • Deletion Removes a node from an existing linked list.
  • Search Finds a particular element in the linked list.

Traverse a Linked List

Accessing the nodes of a linked list in order to process it is called traversing a linked list. Normally we use the traverse operation to display the contents or to search for an element in the linked list. The algorithm for traversing a linked list is given below.

Algorithm: Traverse

Step 1: [INITIALIZE] SET PTR = HEAD 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
  • We first initialize PTR with the address of HEAD. Now the PTR points to the first node of the linked list.
  • A while loop is executed, and the operation is continued until PTR reaches the last node (PTR = NULL).
  • Apply the process(display) to the current node.
  • Move to the next node by making the value of PTR to the address of next node.

The following block of code prints all elements in a linked list in C.

struct node *ptr = head; printf("Elements in the linked list are : "); while (ptr != NULL) { printf("%d ", ptr->data); ptr = ptr->next; }

Inserting Elements to a Linked List

We will see how a new node can be added to an existing linked list in the following cases.

  1. The new node is inserted at the beginning.
  2. The new node is inserted at the end.
  3. The new node is inserted after a given node.

Insert a Node at the beginning of a Linked list

Consider the linked list shown in the figure. Suppose we want to create a new node with data 24 and add it as the first node of the list. The linked list will be modified as follows.

Linked list deletion algorithm
Linked list deletion algorithm
  • Allocate memory for new node and initialize its DATA part to 24.
  • Add the new node as the first node of the list by pointing the NEXT part of the new node to HEAD.
  • Make HEAD to point to the first node of the list.

Algorithm: InsertAtBeginning

Step 1: IF AVAIL = NULL 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 = HEAD Step 6: SET HEAD = NEW_NODE Step 7: EXIT

Note that the first step of the algorithm checks if there is enough memory available to create a new node. The second, and third steps allocate memory for the new node.

This algorithm can be implemented in C as follows:

struct node *new_node; new_node = (struct node*) malloc(sizeof(struct node)); new_node->data = 24; new_node->next = head; head = new_node;

Insert a Node at the end of a Linked list

Take a look at the linked list in the figure. Suppose we want to add a new node with data 24 as the last node of the list. Then the linked list will be modified as follows.

Linked list deletion algorithm
Linked list deletion algorithm
  • Allocate memory for new node and initialize its DATA part to 24.
  • Traverse to last node.
  • Point the NEXT part of the last node to the newly created node.
  • Make the value of next part of last node to NULL.

Algorithm: InsertAtEnd

Step 1: IF AVAIL = NULL 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 = HEAD 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

This can be implemented in C as follows,

struct node *new_node; new_node = (struct node*) malloc(sizeof(struct node)); new_node->data = 24; new_node->next = NULL; struct node *ptr = head; while(ptr->next != NULL){ ptr = ptr->next; } ptr->next = new_node;

Insert a Node after a given Node in a Linked list

The last case is when we want to add a new node after a given node. Suppose we want to add a new node with value 24 after the node having data 9. These changes will be done in the linked list.

Linked list deletion algorithm
Linked list deletion algorithm
  • Allocate memory for new node and initialize its DATA part to 24.
  • Traverse the list until the specified node is reached.
  • Change NEXT pointers accordingly.

Algorithm: InsertAfterAnElement

Step 1: IF AVAIL = NULL 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 = HEAD Step 6: SET PREPTR = PTR Step 7: Repeat Steps 8 and 9 while PREPTR -> DATA != NUM Step 8: SET PREPTR = PTR Step 9: SET PTR = PTR -> NEXT [END OF LOOP] Step 1 : PREPTR -> NEXT = NEW_NODE Step 11: SET NEW_NODE -> NEXT = PTR Step 12: EXIT

Deleting Elements from a Linked List

Lets discuss how a node can be deleted from a linked listed in the following cases.

  1. The first node is deleted.
  2. The last node is deleted.
  3. The node after a given node is deleted.

Delete a Node from the beginning of a Linked list

Suppose we want to delete a node from the beginning of the linked list. The list has to be modified as follows:

Linked list deletion algorithm
Linked list deletion algorithm
  • Check if the linked list is empty or not. Exit if the list is empty.
  • Make HEAD points to the second node.
  • Free the first node from memory.

Algorithm: DeleteFromBeginning

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

This can be implemented in C as follows,

if(head == NULL) { printf("Underflow"); } else { ptr = head; head = head -> next; free(ptr); }

Delete last Node from a Linked list

Suppose we want to delete the last node from the linked list. The linked list has to be modified as follows:

Linked list deletion algorithm
Linked list deletion algorithm
  • Traverse to the end of the list.
  • Change value of next pointer of second last node to NULL.
  • Free last node from memory.

Algorithm: DeleteFromEnd

Step 1: IF HEAD = NULL Write UNDERFLOW Go to Step 8 [END OF IF] Step 2: SET PTR = HEAD Step 3: Repeat Steps 4 and 5 while PTR -> NEXT != NULL Step 4: SET PREPTR = PTR Step 5: SET PTR = PTR -> NEXT [END OF LOOP] Step 6: SET PREPTR -> NEXT = NULL Step 7: FREE PTR Step 8: EXIT

Here we use two pointers PTR and PREPTR to access the last node and the second last node. This can be implemented in C as follows,

if(head == NULL) { printf("Underflow"); } else { struct node* ptr = head; struct node* preptr = NULL; while(ptr->next!=NULL){ preptr = ptr; ptr = ptr->next; } preptr->next = NULL; free(ptr); }

Delete the Node after a given Node in a Linked list

Suppose we want to delete the that comes after the node which contains data 9.

Linked list deletion algorithm
Linked list deletion algorithm
  • Traverse the list upto the specified node.
  • Change value of next pointer of previous node(9) to next pointer of current node(10).

Algorithm: DeleteAfterANode

Step 1: IF HEAD = NULL Write UNDERFLOW Go to Step 10 [END OF IF] Step 2: SET PTR = HEAD Step 3: SET PREPTR = PTR Step 4: Repeat Steps 5 and 6 while PREPTR -> DATA != NUM Step 5: SET PREPTR = PTR Step 6: SET PTR = PTR -> NEXT [END OF LOOP] Step 7: SET TEMP = PTR Step 8: SET PREPTR -> NEXT = PTR -> NEXT Step 9: FREE TEMP Step 10 : EXIT

Implementation in C takes the following form:

if(head == NULL) { printf("Underflow"); } else { struct node* ptr = head; struct node* preptr = ptr; while(ptr->data!=num){ preptr = ptr; ptr = ptr->next; } struct node* temp = ptr; preptr -> next = ptr -> next; free(temp); }

Search

Finding an element is similar to a traversal operation. Instead of displaying data, we have to check whether the data matches with the item to find.

  • Initialize PTR with the address of HEAD. Now the PTR points to the first node of the linked list.
  • A while loop is executed which will compare data of every node with item.
  • If item has been found then control goes to last step.

Algorithm: Search

Step 1: [INITIALIZE] SET PTR = HEAD Step 2: Repeat Steps 3 and 4 while PTR != NULL Step 3: If ITEM = 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

Search operation can be implemented in C as follows:

struct node* ptr = head; struct node* pos = NULL; while (ptr != NULL) { if (ptr->data == item) pos = ptr printf("Element Found"); break; else ptr = ptr -> next; }
Advertisements

Tải thêm tài liệu liên quan đến bài viết Linked list deletion algorithm