## Linked List

Linked List is a linear data structure where each element is a separate object called node. Each node contains the data and a pointer to the next node.

To learn more about Linked List, read the article Linked List.

## Operations on Linked List

Don't you want to do some crazy stuff with your Linked List? Well, you can do that. Let's have a look at some of the operations that can be performed on a Linked List.

### Insertion at the beginning

You have a Linked List and you want to insert a new node at the beginning of the Linked List. How will you do that? Let's have a look at the code.

```
void insertAtBeginning(int data) {
Node* newNode = new Node(data);
if (head == NULL) {
head = newNode;
return;
}
newNode->next = head;
head = newNode;
}
```

Here goes the explanation.

- First, we created a new node
`newNode`

with the data passed to the function. - Then, we checked if the Linked List is empty or not. If the Linked List is empty, we assigned the
`newNode`

to the`head`

variable of the Linked List and returned from the function. - If the Linked List is not empty, we assigned the
`head`

variable of the Linked List to the`next`

variable of the`newNode`

, that is`newNode->next = head;`

. Then, we assigned the`newNode`

to the`head`

variable of the Linked List to make the`newNode`

the first node of the Linked List.

### Insertion at the end

You want to insert a new node at the end of the Linked List too. How will you do that? Let's have a look at the code.

```
void insertAtEnd(int data) {
Node* newNode = new Node(data);
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
```

Here goes the explanation.

- First, we created a new node
`newNode`

with the data passed to the function. - Again we checked if the Linked List is empty or not. If the Linked List is empty, we assigned the
`newNode`

to the`head`

variable of the Linked List and returned from the function. The`newNode`

will be the end node. Because, the only node present in the Linked List is the`newNode`

. - If the Linked List is not empty, we created a new node
`temp`

and assigned the`head`

variable of the Linked List to it. Then, we traversed the Linked List until we reached the last node. - Then, we assigned the
`newNode`

to the`next`

variable of the last node, that is`temp->next = newNode;`

.

### Insertion at a given position

But, I guess you want to insert a new node at any position in the Linked List. How will you do that? Let's have a look at the code.

```
void insertAtPosition(int data, int position) {
Node* newNode = new Node(data);
if (head == NULL) {
head = newNode;
return;
}
if (position == 1) {
newNode->next = head;
head = newNode;
return;
}
Node* temp = head;
for (int i = 1; i < position - 1; i++) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
```

### Search

You have got a Linked List and you want to search for a node with a given data. How will you do that? Let's have a look at the code.

```
bool search(int data) {
Node* temp = head;
while (temp != NULL) {
if (temp->data == data) {
return true;
}
temp = temp->next;
}
return false;
}
```

Here goes the explanation.

- First, we created a new node
`temp`

and assigned the`head`

variable of the Linked List to it. - Then, we traversed the Linked List until we reached the last node.
- Then, we checked if the data of the current node is equal to the data passed to the function. If it is, we returned
`true`

from the function. If not, we moved to the next node. - If we reached the last node of the Linked List and still the data is not found, we returned
`false`

from the function.

### Traversal

Now you know how to search for a node with a given data. But, you want to print the data of all the nodes in the Linked List. How will you do that? Let's go through it.

```
void traverse() {
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
```

Here goes the explanation.

- First, we created a new node
`temp`

and assigned the`head`

variable of the Linked List to it. - Then, we traversed the Linked List until we reached the last node.
- Then, we printed the data of the current node and moved to the next node.

### Deletion at the beginning

You got all your data in a Linked List. But the first node does not seems to be useful. You want to delete the first node. How will you do that? Let's have a look at the code.

```
void deleteAtBeginning() {
if (head == NULL) {
return;
}
Node* temp = head;
head = head->next;
delete temp;
}
```

Here goes the explanation.

- First, we checked if the Linked List is empty or not. If the Linked List is empty, we returned from the function.
- Then, we created a new node
`temp`

and assigned the`head`

variable of the Linked List to it. After that, we assigned the`next`

variable of the`head`

to the`head`

variable by`head = head->next;`

. - Then, we deleted the
`temp`

node from the memory.

### Deletion at the end

Now it seems like the last node is not useful too. You want to delete the last node. Let's remove it.

```
void deleteAtEnd() {
if (head == NULL) {
return;
}
if (head->next == NULL) {
delete head;
head = NULL;
return;
}
Node* temp = head;
while (temp->next->next != NULL) {
temp = temp->next;
}
delete temp->next;
temp->next = NULL;
}
```

Here goes the explanation.

- First, we checked if the Linked List is empty or not. If the Linked List is empty, we returned from the function.
- Then, we checked if the Linked List has only one node. If the Linked List has only one node, we deleted the
`head`

node from the memory and assigned`NULL`

to the`head`

variable of the Linked List. - If the Linked List has more than one node, we created a new node
`temp`

and assigned the`head`

variable of the Linked List to it. Then, we traversed the Linked List until we reached the second last node. - Then, we deleted the last node from the memory and assigned
`NULL`

to the`next`

variable of the second last node.

### Deletion at a given position

If all seems fine. But, for your curiosity, you want to delete a node at a given position. How will you do that? Let's have a look at the code.

```
void deleteAtPosition(int position) {
if (head == NULL) {
return;
}
if (position == 0) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* temp = head;
for (int i = 1; i < position; i++) {
temp = temp->next;
}
Node* toDelete = temp->next;
temp->next = temp->next->next;
delete toDelete;
}
```

Here goes the explanation.

- First, we checked if the Linked List is empty or not. If the Linked List is empty, we returned from the function.
- Then, we checked if the position is
`0`

. If the position is`0`

, we deleted the`head`

node from the memory and assigned`NULL`

to the`head`

variable of the Linked List. - If the position is not
`0`

, we created a new node`temp`

and assigned the`head`

variable of the Linked List to it. Then, we traversed the Linked List until we reached the node at the given position. - Then, we created a new node
`toDelete`

and assigned the`next`

variable of the`temp`

node to it. After that, we assigned the`next`

variable of the`toDelete`

node to the`next`

variable of the`temp`

node by`temp->next = temp->next->next;`

. - Then, we deleted the
`toDelete`

node from the memory.

At last, we have completed the implementation of the Linked List. Now, let's have a look at the complete code.

To make the code length not too long, I have included the major functions only.

```
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = NULL;
}
};
class LinkedList {
public:
Node* head;
LinkedList() {
head = NULL;
}
void insertAtPosition(int data, int position) {
Node* newNode = new Node(data);
if (head == NULL) {
head = newNode;
return;
}
if (position == 0) {
newNode->next = head;
head = newNode;
return;
}
Node* temp = head;
for (int i = 1; i < position; i++) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
void traverse() {
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
bool search(int data) {
Node* temp = head;
while (temp != NULL) {
if (temp->data == data) {
return true;
}
temp = temp->next;
}
return false;
}
void deleteAtPosition(int position) {
if (head == NULL) {
return;
}
if (position == 0) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* temp = head;
for (int i = 1; i < position; i++) {
temp = temp->next;
}
Node* toDelete = temp->next;
temp->next = temp->next->next;
delete toDelete;
}
};
int main() {
LinkedList* ll = new LinkedList();
ll->insertAtPosition(10, 0);
ll->insertAtPosition(20, 1);
ll->insertAtPosition(30, 2);
ll->insertAtPosition(40, 3);
ll->traverse();
cout << ll->search(30) << endl;
cout << ll->search(50) << endl;
ll->deleteAtPosition(2);
ll->traverse();
}
```

Now I hope you have understood the Linked List. If you have any doubts, please contact me. I will be happy to help you.

## References

- "Linked list - Wikipedia" En, https://en.wikipedia.org/wiki/Linked_list.
- "Linked List Data Structure - GeeksforGeeks" Geeksforgeeks, 18 Jun. 2002, https://www.geeksforgeeks.org/data-structures/linked-list/.
- "Linked List Operations: Traverse, Insert and Delete" Programiz, https://www.programiz.com/dsa/linked-list-operations.