# Linked List Operations - Traverse, Insert and Delete

In the previous section, we had discussed about structure of linked list. In this section, we will learn about basic operations of a linked list.

## 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<<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 newNode->next = head; //4. make new node as head head = newNode; }

### 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 // new node as head and new node as head newNode->next = head; head = newNode; } else { //4. Else, make a temp node and traverse to the // node previous to the position Node* temp = head; 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 if(head == NULL) { head = newNode; } else { //5. Else, traverse to the last node Node* temp = head; 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() { if(head != NULL) { //1. if head is not null, create a // temp node pointing to head Node* temp = head; //2. move head to next of head head = head->next; //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 2^{nd} 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, // make head to head next and delete the // previous head Node* nodeToDelete = head; head = head->next; free(nodeToDelete); } else { //3. Else, make a temp node and traverse to the // node previous to the position Node* temp = head; for(int i = 1; i < position-1; i++) { if(temp != NULL) { temp = temp->next; } } //4. If the previous node and next of the previous // is not null, adjust links 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. cout<<"\nThe node is already null."; } } }

### 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() { if(head != NULL) { //1. if head in not null and next of head // is null, release the head if(head->next == NULL) { head = NULL; } else { //2. Else, traverse to the second last // element of the list Node* temp = head; 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); } } }