How will you insert and delete from a linked list?

Linked List | Set 2 (Inserting a node)

We have introduced Linked Lists in the previous post. We also created a simple linked list with 3 nodes and discussed linked list traversal.
All programs discussed in this post consider the following representations of linked list.

Table of Contents Show

Linked List | Set 2 (Inserting a node)
Linked List | Set 3 (Deleting a node)
Traverse a Linked List
Inserting Elements to a Linked List
Insert a Node at the beginning of a Linked list
Insert a Node at the end of a Linked list
Insert a Node after a given Node in a Linked list
Traverse a Linked List

C++

// A linked list node 

class Node
{ 

public:

int data;

Node *next;
}; 
// This code is contributed by rathbhupendra

// A linked list node

struct Node
{

int data;

struct Node *next;
};

Java

// Linked List Class

class LinkedList
{

Node head; // head of list

/* Node Class */

class Node

{

int data;

Node next;

// Constructor to create a new node

Node(int d) {data = d; next = null; }

}
}

Python

# Node class

class Node:

# Function to initialize the node object

def __init__(self, data):

self.data = data # Assign data

self.next = None # Initialize next as null
# Linked List class

class LinkedList:

# Function to initialize the Linked List object

def __init__(self):

self.head = None

/* Linked list Node*/

public class Node
{

public int data;

public Node next;

public Node(int d) {data = d; next = null; }
}

Javascript

<script>
// Linked List Class

var head; // head of list

/* Node Class */

class Node {

// Constructor to create a new node

constructor(d) {

this.data = d;

this.next = null;

}

}
// This code is contributed by todaysgaurav 
</script>

In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways
1) At the front of the linked list
2) After a given node.
3) At the end of the linked list.

Linked List | Set 3 (Deleting a node)

We have discussed Linked List Introduction and Linked List Insertion in previous posts on a singly linked list.
Let us formulate the problem statement to understand the deletion process. Given a ‘key’, delete the first occurrence of this key in the linked list.

Iterative Method:
To delete a node from the linked list, we need to do the following steps.
1) Find the previous node of the node to be deleted.
2) Change the next of the previous node.
3) Free memory for the node to be deleted.

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.

The new node is inserted at the beginning.
The new node is inserted at the end.
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.

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.

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.

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

Traverse a Linked List

Traversing through a linked list is very easy. It requires creating a temp node pointing to the head of the list. If the temp node is not null, display its content and move to the next node using temp next. Repeat the process till the temp node becomes null. If the temp node is empty at the start, then the list contains no item.

//C++ Code //Display the content of the list void PrintList() { //1. create a temp node pointing to head Node* temp = head; //2. if the temp node is not null continue // displaying the content and move to the // next node till the temp becomes null if(temp != NULL) { cout<<"\nThe list contains: "; while(temp != NULL) { cout<data<<" "; temp = temp->next; } } else { //3. If the temp node is null at the start, // the list is empty cout<<"\nThe list is empty."; } }