 # Linked List Operations with Algorithms

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.

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.

• 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;

### Insert a Node at the end of a Linkedlist

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;

while(ptr->next != NULL){
ptr = ptr->next;
}

ptr->next = new_node;```

### Insert a Node after a given Node in a Linkedlist

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```

## Deleting Elements from a Linked List

Let’s 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:

• 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 4: FREE PTR
Step 5: EXIT```

This can be implemented in C as follows,

```if(head == NULL)
{
printf("Underflow");
}
else
{
free(ptr);
}```

### Delete last Node from a Linkedlist

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

• 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* 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 Linkedlist

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

• 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* preptr = ptr;
while(ptr->data!=num){
preptr = ptr;
ptr = ptr->next;
}
struct node* temp = ptr;
preptr -> next = ptr -> next;
free(temp);
}```

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.
```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;
}```

Subscribe
Notify of 