Linked lists are data structures that store data in such a way that each element has a reference to another element in the list.

#### Operations

Any linked list invariant must support some basic operations:

- Insertion
- Search (find)
- Deletion

#### Invariants

There are numerous linked lists invariants. We will take a look at two of the most used ones: *Singly Linked List* and *Doubly Linked List*.

#### Singly Linked List

This is the most basic invariant of linked lists.

Keep track of the first node (head) and last node (tail).

Each node points to the next nod in the list.

Before diving into details, let’s define `class Node`

that will hold elements of our list.

We want our node class to be flexible enough to store data of any type, so we use `class template`

.

template class Node { public: Node(const T &value) : data(value), next(NULL){} ~Node(void){} T data; Node *next; };

This class has two members: `data`

to store our data, and `next`

which is a pointer to the next node in the list, if any. The constructor initializes `data`

with the `value`

parameter and sets `next`

to `NULL`

.

Let’s think about the linked list class we’re about to write. We need to keep track of our head node; so we’ll do so using a pointer. We’ll create a member pointer and call it `head`

. Also, let’s create another pointer while we’re at it to keep track of the tail. Now, we need methods to add nodes to our list. Let’s create a method to add nodes at the `head`

. Let’s call it `addToHead()`

. Also, we’d want to add another method to delete or remove items from `head`

and it shall be called… `deleteFromHead()`

. Since we have a `tail`

, let’s create `addToTail()`

and `deleteFromTail()`

.

##### Do Not Lose The List

As you might have thought, we’ll be moving `next`

and `head`

or `tail`

to add or delete new nodes to the list. The key guideline here is: Not to lose the list! We have to make sure that our pointers are in check and valid.

Now, let’s take a look at the class.

template class List { public: List(void){ head = tail = NULL;} ~List(void){} bool isEmpty() { return head == NULL; } void addToHead(T value); T deleteFromHead(); void addToTail(T value); T deleteFromTail(); bool find(T value); bool deleteNode(T value); private: Node *head, *tail; };

##### Insertion

Let’s implement `void addToHead()`

:

template void List::addToHead(T value) { Node *node = new Node(value); if (head) node->next = head; head = node; if (!tail) tail = head; }

Let’s walk through the code above. First, we created a Node object using the value passed into addToHead() method. Then we check to see if `head`

is `NULL`

. So, if exists a head then make our new `node->next`

point to the current head. Then we make our head point to the new node. So we added the new node in front of the old head.

Finally, if the tail pointer is null, we make point to the new head. That means we only have one item in the list.

There is no dependency in this method on the size of the list. So, the time complexity for this method is O(1) or it runs in constant time.

Now let’s take a look at `deleteFromHead()`

.

template T List::deleteFromHead() { T value = head->data; Node *temp = head; if (head == tail) // One node in list head = tail = NULL; else head = head->next; delete temp; return value; }

In the code above, we extract the information from the head node in `value`

. Then, we create a temporary pointer to point to point to the head node. If we have only one node in the list, we nullify head and tail pointers. If we have more than one node in the list, we make the head pointer points to the next node. Then we delete the temporary pointer to free up memory, otherwise we’ll have a memory leak. Finally, we return `value`

to caller.

Like `addToHead()`

, there is no dependency in this method on the size of the list. So, it runs in constant time O(1);

Similar to `addToHead()`

, we implement `addToTail()`

.

template void List::addToTail(T value) { Node *node = new Node(value); if (tail) tail->next = node; tail = node; if (!head) head = tail; }

Here, the tail pointer is key, obviously. First we create a new `Node`

to store our `value`

. Then if tail is not null, we make `tail->next`

point to the new node. Now we can have `tail`

point to `node`

, which is now the last node in the list. If `head`

is null then our list has only one node, so make `head`

point to `tail`

.

Again, since there is no dependency on the size of the list, this method runs in constant time O(n).

`deleteFromTail()`

will be a little different. Let’s take a look.

template T List::deleteFromTail() { T value = tail->data; if (head == tail) { delete head; head = tail = NULL; } else { Node *temp; // loop to the node before last for (temp = head; temp->next != tail; temp = temp->next); delete tail; tail = temp; // node previous to tail is now tail tail->next = NULL; } return value; }

Firstly, we make record of the data we want to return in `value`

. Here, we have two main branches:

- There is only one node in the list, then delete that node and nullify
`head`

and`tail`

pointers.

- There are several nodes in the list. Then we’ll create a pointer
`temp`

to point at`head`

then loop over all the nodes in the list until we reach the node before last, in other words, until we reach the node that will become the new tail. At this point it is safe to free memory occupied by the last node. Since`temp`

is now pointing to the new tail node, we make`tail`

point to this node. Finally, we make sure to nullify`tail->next`

.

In the above method, since we loop from head to tail, there is a dependency on the size of the list. Our time complexity here is linear or O(N).

##### Find

Now let’s implement `find()`

.

template Node List::find(T value) { for (Node *i = head; i != NULL; i = i->next) if (i->data == value) return true; return false; }

As you see above, there is no fast way to find items in a linked list. We have to loop over items in list until we find what we’re looking for. The find() method returns true if the item is found and false otherwise.

Time complexity of `find()`

is proportional to the size of the list *n*, or it is O(n).

##### Deletion By Value

In order to delete a node by its value (could be somewhere between head and tail), we need to know the previous node so we keep track of the two parts of the list after deleting our node. But, we have a couple of special cases:

- If head is to be deleted.
- If head is to be deleted and it is the only node in the list.

So, here is the code:

template bool List::deleteNode(T value) { if (head->data == value) { if (head == tail) { delete head; return true; } else { Node *temp = head; head = head->next; delete temp; return true; } } else { if (head == tail) return false; for ( Node *prev = head, Node *i = head->next; i->next != NULL; prev = prev->next, i = i->next; ) { if (i->data == value) { prev->next = i->next; if (i == tail) tail = prev; delete i; return true; } } } return false; }

As you can tell, the time complexity is linear for `deleteNode()`

or we can say it is O(n).

##### Conclusion

Operations on a linked lists are best done at head and tail are done in constant time. Other operations performed on other nodes in the middle of the list depend on the size of the list n. Other algorithms are developed to improve search operations on the list.

#### Notes

##### Linked Lists Vs. Arrays

- Linked lists dynamically allocate memory as needed for new items (nodes), and free memory as nodes are removed from the list.
- Arrays are statically allocated on the
if the array is declared locally or on the**stack**if declared globally. Arrays cannot be resized once declared.**Data Segment**

- Linked lists items are not randomly accessed. An iterative process is required to access items in a list without having a direct reference to each item.
- Array items can be access randomly giving that we know the index of the item we want (i.e.
`arr[4] = 2;`

).