## What is a Linked List

A Linked List is a data structure in which each `Node`

points to the next to create a dynamic list. Linked Lists are also called dynamic lists. It works similar to an array but has some advantages compared to a static list.

```
struct Node {
Node* next;
int value;
};
```

## Why do we use Linked Lists

The main problems with arrays are insertion and deletion of an element. Each time you delete an element you are forced to shift all the elements above it one cell down. This operation costs Θ(n). Nevertheless, when we use a linked list instead these operations have a cost of Θ(1), we just need to change the pointer of the element before the deleted node to point to the element after the deleted node.

When we need to insert an element we are facing the same problem. An array has a predefined static size: it means we need to create another greater array in order to insert a new element into it (that is how C++ `vector`

works). This is not an issue if we use a linked list because its size is dynamic.

The problem with linked list is that each time we need to select a specific node we need to cycle to the entire list to find it because we only store a reference to the `head`

node. This operation is Θ(n). Therefore, linked list is not efficient with searching operations.

## Linked List C++ Implementation

I have developed a C++ class that implements linked list. All the source code is free and open source, you can download it on my Github page LassSandro/LinkedList. I am going to explain how some functions of the class work.

#### insertNode(int)

```
// Push node at the end of the list
void LinkedList::insertNode(int value) {
Node* temp = createEmptyNode(value);
// If list is empty
// Set tail and head to the new temp node
if (isEmpty()) {
setHead(temp);
setTail(temp);
increaseLength();
return;
}
// Append new node at the end and set tail
getTail()->next = temp;
setTail(temp);
increaseLength();
}
```

With `insertNode(int)`

we can insert a new node at the end of the list. We simply create a new node with the given value and attach it at the end of the list by making the previous last node point to the new node created. If the list is empty the new node is the only one in the list (it is both the head and the tail).

#### searchValue(int)

```
// Return node index if find value
// Return -1 if not find
int LinkedList::searchValue(int value) {
Node* curr = getHead();
int currIndex = 0;
while(curr != nullptr) {
if (curr->value == value) {
return currIndex;
}
curr = curr->next;
++currIndex;
}
return -1;
}
```

As we said the main problem with linked list is searching. In order to find a value, we need to start from the head and cycle through the whole list until we find the requested value. If the value is in the list we return the index of the node we found, otherwise we return -1.

#### insertNode(unsigned, int)

```
// Insert node in a specific position
void LinkedList::insertNode(unsigned index, int value) {
// Check position index
if (index > length) {
positionError(index);
return;
}
// Insert head (index == 0)
if (index == 0) {
insertHead(value);
return;
}
Node* temp = createEmptyNode(value);
Node* curr = getHead();
// Set current index to position '1'
unsigned currIndex = 1;
// Reach node at requested position
while (currIndex != index) {
curr = curr->next;
++currIndex;
}
// If last position requested
if (currIndex == length) {
insertNode(value);
return;
}
// Change pointers to insert node in
temp->next = curr->next;
curr->next = temp;
increaseLength();
}
```

If we want to insert a new node in a specific position the process is nearly the same. This time we need to find the node in the specified position. To do that we cycle from the head each node until we reach the `index`

inserted. Then we check if the node selected is the tail, in this case we call the `insertNode(int)`

function. If not, we just need to make the current node point to the new node and the new node point to the `next`

of the current one.

#### deleteNode(unsigned)

```
// Delete node in specific position
void LinkedList::deleteNode(unsigned index) {
// Check position index
if (index >= length) {
positionError(index);
return;
}
// Delete head (index == 0)
if (index == 0) {
deleteHead();
return;
}
// Set curr node (head)
Node* curr = getHead();
unsigned currIndex = 1;
// Stop when reach position OR the last element
while (currIndex != index || currIndex != (length - 1)) {
curr = curr->next;
++currIndex;
}
// Change tail if reached last element
if (currIndex == (length - 1)) {
setTail(curr);
curr->next = nullptr;
decreaseLength();
return;
}
// Change next to remove element from list
curr->next = curr->next->next;
decreaseLength();
}
```

The process to find the requested node to delete is the same as the `insertNode(unsigned, int)`

function above but this time we are looking for the node before the `index`

's one. Once we find that node we just need to make it point to the node next to the node that we want to delete.

These are the main functions of our C++ Linked List class implementation. We will update the repository with some more functionalities in the near future. Feel free to contribute yourself to the project. Stay tuned for future updates, sign up to our newsletter to not miss any new article.