Progress

# Linked Lists Data Structures with Algorithm and Examples Linked lists are non-primitive linear data structures with several benefits. It stores the nodes at different memory locations and each node has reference to the next node in the memory.

They are the best alternatives to the array when the length of data items is unknown.

The linked lists are one of the most important data structures which have a lot of applications. Some other performance-optimized data structures such as tree and graphs use a linked list.

## What is a Linked List Data Structure?

Linked list data structures are the collection of nodes which are connected to each other.

The nodes contain two parts, data and reference to the next node in the memory.

The data part holds the actual data which we use and the reference pointer is to go at the next node.

Here are different types of linked lists which are suitable for specific sitation. We need to know them in depth to understand them.

Singly linked lists are those in which nodes contain reference to only next node.

It means the traversal of singly linked list is only one way. We can only traverse forward and not backward because there is no reference to previous node.

Whenever we simply say linked list it means we refer to the singly linked list because it is used most of the time.

Here is a pseudo code for the node of singly linked list.

``````class Node{
Object data;
Node nextNode;
}``````

The data can be of any type, it means we can also store own custom object in the linked list. The `nextNode` is of type `Node` which refers to the next node.

Here is python program implementation of singly linked list.

Note: This program is only to uderstand the concept, we do not link nodes manually in real life uses.

Copy
``````class Node:
#Constructor
def __init__(self, data):
self.nextNode = None
self.data = data

node1 = Node(5)
node2 = Node(9)
node3 = Node(13)
node4 = Node(17)

#Connect them manually (just for understanding)
node1.nextNode = node2
node2.nextNode = node3
node3.nextNode = node4

#Verify they are connected
pointer = node1
#Traverse until last node (last node has nextNode=None)
while(1):
print(pointer.data, sep="", end="")
# If pointer is on last node break while loop and exit
if(pointer.nextNode is None):
break
#for Visual Formatting only
print("", end=" => ")
#Move pointer to next node
pointer = pointer.nextNode``````
Output
`5 => 9 => 13 => 17`

As we see that singly linked list has a disadvantage that it can only traverse in the forward direction.

Doubly linked lists contain nodes which contain three parts, reference to previous node, data and reference to next node.

Here is a pseudo code for the node of doubly linked list.

``````class Node{
Node previousNode;
Object data;
Node nextNode;
}``````

This is the reason that it is possible to traverse the doubly linked list in forward as well as backward direction.

The previous node reference of the first node is set to `NULL` that represents it is the starting node. Similarly, the next node reference of the last node is also `NULL` which represent the end of the linked list.

Here is a python program just for a clear understanding of doubly linked list data structure.

Copy
``````class Node:
#Constructor
def __init__(self, data):
self.previousNode = None
self.data = data
self.nextNode = None

node1 = Node(5)
node2 = Node(9)
node3 = Node(13)
node4 = Node(17)

#Connect them manually (just for understanding)
node1.nextNode = node2
node2.previousNode = node1
node2.nextNode = node3
node3.previousNode = node2
node3.nextNode = node4
node4.previousNode = node3

#Verify they are connected
pointer = node1
#Traverse until last node (last node has nextNode=None)
while(1):
print(pointer.data, sep="", end="")
# If pointer is on last node break while loop and exit
if(pointer.nextNode is None):
break
#for Visual Formatting only
print("", end=" => ")
#Move pointer to next node
pointer = pointer.nextNode
print("\nTraverse in Reverse")
#Reverse Traverse
while(1):
print(pointer.data, sep="", end="")
# If pointer is on last node break while loop and exit
if(pointer.previousNode is None):
break
#for Visual Formatting only
print("", end=" <= ")
#Move pointer to next node
pointer = pointer.previousNode``````
Output
```5 => 9 => 13 => 17
Traverse in Reverse
17 <= 13 <= 9 <= 5```

Circular linked lists are similar to singly linked list except the last node is connected to the first node because the next node reference of the last node refers to the first node (see the picture). It forms a circular path.

Doubly linked lists can also be circular. Here is the picture that demonstrate the concept.

It means the `previous node` reference of the first node points to the last node of the linked list and the `next node` reference of the last node points to the first node.

Here is a Python program for implementation of doubly circular linked list data structure.

doublyCircularLL.py
Copy
``````class Node:
#Constructor
def __init__(self, data):
self.previousNode = None
self.data = data
self.nextNode = None

node1 = Node(5)
node2 = Node(9)
node3 = Node(13)
node4 = Node(17)

#Connect them manually (just for understanding)
node1.previousNode = node4
node1.nextNode = node2
node2.previousNode = node1
node2.nextNode = node3
node3.previousNode = node2
node3.nextNode = node4
node4.nextNode = node1
node4.previousNode = node3

#Verify they are connected
n=20
pointer = node1
while(n is not 0):
print(pointer.data, end="=>")
pointer = pointer.nextNode
n = n-1``````
Output
`5=>9=>13=>17=>5=>9=>13=>17=>5=>9=>13=>17=>5=>9=>13=>17=>5=>9=>13=>17=>`

### Dynamic Size

Whenever we need to add new data we can simply add a new node. The length of the linked list is not fixed, it is dynamic.

This is an advantage over array because in array we need to define length and it is not easy to change it.

### No wastage of Memory

Because the length is not fixed, there is no wastage of memory. We add new node only when we need to store some data.

We can relate this with an array, the length of the array is fixed which means it occupies that space in memory. If we do not use that, the array will still hold it and it will go waste.

### Efficient Insertion and Deletion

Insertion and deletion only require to change the reference of next node (and previous node) to the new node.

In array the insertion and deletion is much more costly because all the elements need to shift from their original position.

### Accessing Element

The linked list do not support indexing. We cannot get data by their index position.

Each time we need to traverse the linked list and reach to the certain position to extract the data.

### Extra Memory Requirement

Some extra memory is requires with each node to hold the reference of the next node and previous node in case of doubly and circular linked list.

## When to use Linked Lists?

Linked lists are very helpful in the situations when we need to add and remove data frequently. It is also used as an alternative of the array when the length of data is unknown.

Here are some example use cases which use linked list data structure.

Browser Previous and next button: It will be efficient to use a linked list to implement a back and forward button in a doubly-linked list as we can easily access the previous and next node.

Songs in Playlist: The user can frequently add and remove songs from his playlist. It will be efficient to implement linked list because insertion and deletion are less costly.

Undo and Redo functionality: Linked lists can also be used to implement undo and redo functionality in any program.

## Summary

It was all about linked list. Here is a quich summary of the most important points described above.

• A linked list is a good alternative to the array when the length of data is unknown.
• Linked lists are made up of nodes which contain the data and reference to the next node.
• Linked list are of three types: