Data Structures Data Structures References

# Linked List Operations - Traverse, Insert and Delete

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

//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<<temp->data<<" ";
temp = temp->next;
}
} else {

//3. If the temp node is null at the start,
//   the list is empty
cout<<"\nThe list is empty.";
}
}
```

## Insert a new node in Linked List

A new node can be inserted into a list in three ways:

• Insert a node at the start
• Insert a node at the given position
• Insert a node at the end

### Insert a new node at the start

In this method, a new node is inserted at the beginning of the linked list. For example - if the given list is 10->20->30 and a new element 100 is added at the start, the list becomes 100->10->20->30.

Inserting a new node at the beginning of the Linked List is very easy. First, a new node with given element is created. It is then added before the head of the given list that makes the newly added node to new head of the list by changing the head pointer to point to the new node.

```//C++ Code
//Inserts a new node at the start
void push_front(int newElement) {

//1. allocate a new node
Node* newNode = new Node();

//2. assign data element
newNode->data = newElement;

//3. make next node of new node as head

//4. make new node as head
}
```

### Insert a new node at the given position

In this method, a new element is inserted at the specified position in the linked list. For example - if the given list is 10->20->30 and a new element 100 is added at position 2, the list becomes 10->100->20->30.

First, a new node with given element is created. If the insert position is 1, then the new node is made to head. Otherwise, traverse to the node that is previous to the insert position and check if it is null or not. In case of null, the specified position does not exist. In other case, assign next of the new node as next of the previous node and next of previous node as new node.

```//C++ Code
//Inserts a new node at the given position
void push_at(int newElement, int position) {

//1. allocate node to new element
Node* newNode = new Node();
newNode->data = newElement;
newNode->next = NULL;

//2. check if the position is > 0
if(position < 1) {
cout<<"\nposition should be >= 1.";
} else if (position == 1) {

//3. if the position is 1, make next of the
} else {

//4. Else, make a temp node and traverse to the
//   node previous to the position
for(int i = 1; i < position-1; i++) {
if(temp != NULL) {
temp = temp->next;
}
}

//5. If the previous node is not null, make
//   newNode next as temp next and temp next
//   as newNode.
if(temp != NULL) {
newNode->next = temp->next;
temp->next = newNode;
} else {

//6. When the previous node is null
cout<<"\nThe previous node is null.";
}
}
}
```

### Insert a new node at the end

In this method, a new node is inserted at the end of the linked list. For example - if the given list is 10->20->30 and a new element 100 is added at the end, the list becomes 10->20->30->100.

Inserting a new node at the end of the Linked List is very easy. First, a new node with given element is created. It is then added at the end of the list by linking the last node to the new node.

```//C++ Code
//Inserts a new node at the end
void push_back(int newElement) {

//1. allocate node
Node* newNode = new Node();

//2. assign data element
newNode->data = newElement;

//3. assign null to the next of new node
newNode->next = NULL;

//4. Check the list is empty or not,
//   if empty make the new node as head
} else {

//5. Else, traverse to the last node
while(temp->next != NULL)
temp = temp->next;

//6. Change the next of last node to new node
temp->next = newNode;
}
}
```

## Delete a Node from Linked List

A node can be deleted from a list in three ways:

• Delete the first node
• Delete the node at given position
• Delete the last node

### Delete the first node

In this method, the first node of the linked list is deleted. For example - if the given list is 10->20->30->40 and the first node is deleted, the list becomes 20->30->40.

Deleting the first node of the linked list is very easy. If the head is not null then create a temp node pointing to head and move head to the next of head. Then delete the temp node.

```//C++ Code
//Deletes the first node
void pop_front() {

//1. if head is not null, create a
//   temp node pointing to head

//3. delete temp node
free(temp);
}
}
```

### Delete a node from middle

In this method, a node at the specified position in the linked list is deleted. For example - if the given list is 10->20->30 and the 2nd node is deleted, the list becomes 10->20.

First, the specified position must be greater than equal to 1. If the specified position is 1 and head is not null, then make the head to head next. Else, traverse to the node that is previous to the specified position. If the specified node and previous to the specified node are not null then adjust the link and delete the node at specified position. In other case, the specified node will be already null.

```//C++ Code
//Deletes the node at given position
void pop_at(int position) {

//1. check if the position is > 0
if(position < 1) {
cout<<"\nposition should be >= 1.";
} else if (position == 1 && head != NULL) {

//2. if the position is 1 and head is not null,
free(nodeToDelete);
} else {

//3. Else, make a temp node and traverse to the
//   node previous to the position
for(int i = 1; i < position-1; i++) {
if(temp != NULL) {
temp = temp->next;
}
}

//4. If the previous node and next of the previous
if(temp != NULL && temp->next != NULL) {
Node* nodeToDelete = temp->next;
temp->next = temp->next->next;
free(nodeToDelete);
} else {

//5. Else the given node will be empty.
}
}
}
```

### Delete the last node

In this method, the last node of the linked list is deleted. For example - if the given list is 10->20->30->40 and the last node is deleted, the list becomes 10->20->30.

Deleting the last node of the Linked List involves checking the head for empty. If it is not empty, then check the head next for empty. If the head next is empty, then release the head, else traverse to the second last node of the list. Then, link the next of second last node to NULL and delete the last node.

```//C++ Code
//Deletes the last node
void pop_back() {

//   is null, release the head
} else {

//2. Else, traverse to the second last
//   element of the list
while(temp->next->next != NULL)
temp = temp->next;

//3. Change the next of the second
//   last node to null and delete the
//   last node
Node* lastNode = temp->next;
temp->next = NULL;
free(lastNode);
}
}
}
```

5