# Linked List - Operations

on 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.

## 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) {
return;
}

}
``````

Here goes the explanation.

1. First, we created a new node `newNode` with the data passed to the function.
2. 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.
3. 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) {
return;
}

Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}

temp->next = newNode;
}
``````

Here goes the explanation.

1. First, we created a new node `newNode` with the data passed to the function.
2. 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`.
3. 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.
4. 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) {
return;
}

if (position == 1) {
return;
}

Node* temp = head;
for (int i = 1; i < position - 1; i++) {
temp = temp->next;
}

newNode->next = temp->next;
temp->next = newNode;
}
``````

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.

1. First, we created a new node `temp` and assigned the `head` variable of the Linked List to it.
2. Then, we traversed the Linked List until we reached the last node.
3. 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.
4. 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.

1. First, we created a new node `temp` and assigned the `head` variable of the Linked List to it.
2. Then, we traversed the Linked List until we reached the last node.
3. 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;
delete temp;
}
``````

Here goes the explanation.

1. First, we checked if the Linked List is empty or not. If the Linked List is empty, we returned from the function.
2. 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;`.
3. 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) {
return;
}

Node* temp = head;
while (temp->next->next != NULL) {
temp = temp->next;
}

delete temp->next;
temp->next = NULL;
}
``````

Here goes the explanation.

1. First, we checked if the Linked List is empty or not. If the Linked List is empty, we returned from the function.
2. 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.
3. 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.
4. 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;
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.

1. First, we checked if the Linked List is empty or not. If the Linked List is empty, we returned from the function.
2. 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.
3. 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.
4. 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;`.
5. 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;
}
};

public:

}

void insertAtPosition(int data, int position) {
Node* newNode = new Node(data);

if (head == NULL) {
return;
}

if (position == 0) {
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;
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() {

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.