> For the complete documentation index, see [llms.txt](https://ankit-apdc.gitbook.io/python-1/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ankit-apdc.gitbook.io/python-1/data-structure/linkedlist.md).
# LinkedList
## Singly LinkedList
### What is it?
* LinkedList is like a game of treasure-hunt where each point contains the clue for the next point
* We need to start somewhere for the next point (node), therefore we are given with first node call head
* A node contains 2 information (a node is a class object, from an implementation point of view):
* value of the current node
* pointing to the second node (address or class object)
```python
# Here is how a single node for single LinkedList is defined, Node object (class)
class Node:
def __init__(self, data):
self.data = data
self.next = None
```
* The power of LinkedList comes from, ability to break the chain and rejoin it
* Hence, unlike a list. we don't need to shift all the items after insertion, rather we can insert anywhere
* Here is a disadvantage as well, index access is not efficient; we need to iterate from head till we reach the index to access it. Arbitrary access needs iteration from head to the point/index
* **Various Operations**
|
Operation
| Worst case | Average case |
| ----------------------- | ---------- | ------------ |
| **Search** | O(n) | O(n) |
| **Insert at the start** | O(1) | O(1) |
| **Deletion at the end** | O(1) | O(1) |
### Implementation
Different Operations:
* **Insertion**: at the start, in the end, in the middle
* **Traversing** (accessing all the elements or search for a specific number)
* **Deletion**: starting node
* **Delete key**: find the key in LinkedList and delete the first found
* **Display**: display the LinkedList
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self, head=None):
self.head = head
def insertion(self, data):
new_node = Node(data)
if self.head == None:
self.head = new_node
else:
next_node = self.head
self.head = new_node
self.head.next = next_node
return True
def deletion(self):
if self.head:
self.head = self.head.next
return -1
else:
return 'empty'
def display(self):
this_node = self.head
while this_node:
print(this_node.data, end = ' -> ')
this_node = this_node.next
print()
def search(self, data):
this_node = self.head
count = 0
while this_node:
if this_node.data == data:
return count
else:
count+=1
this_node = this_node.next
return -1
def delete_key(self, data):
this_node = self.head
if not this_node:
return False
if this_node.data == data:
self.head = this_node.next
return True
prev_node = this_node
this_node = this_node.next
while this_node:
if this_node.data == data:
if this_node.next:
prev_node.next = this_node.next
else:
prev_node.next = None
return True
prev_node = this_node
this_node = this_node.next
return False
```
## Doubly LinkedList
### what is it?
* In doubly LinkedList, we can move in either direction
* A node has three parts in a doubly LinkedList
* Data for the node
* pointer to the next node
* pointer to the previous node
```python
# Here is how a single node for doubly LinkedList is defined, Node object (class)
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
```
* We are given with start and end node in the case of LinkedList
* We can travel in both forward or backward direction
* Time complexity point of view: No difference if adding and deleting from start or end
### Implementation
```python
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self, head = None, tail = None):
self.head = head
self.tail = tail
def head_insertion(self, data):
new_node = Node(data)
if self.head:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
else:
self.head = new_node
self.tail = new_node
def tail_insertion(self, data):
new_node = Node(data)
if self.tail:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
else:
self.head = new_node
self.tail = new_node
def head_deletion(self):
if self.head == self.tail:
self.head = None
self.tail = None
elif self.head:
self.head = self.head.next
self.head.prev = None
def tail_deletion(self):
if self.tail == self.head:
self.head = None
self.tail = None
elif self.tail:
self.tail = self.tail.prev
self.tail.next = None
def key_deletion(self, data):
this_node = self.head
if not this_node:
return False
if this_node.data == data:
if this_node.next:
self.head = this_node.next
self.head.prev = None
else:
self.head = None
self.tail = None
return True
prev_node = this_node
this_node = this_node.next
while this_node:
if this_node.data == data:
if this_node.next:
this_node.next.prev = prev_node
prev_node.next = this_node.next
else:
prev_node.next = None
self.tail = prev_node
return True
prev_node = this_node
this_node = this_node.next
return False
def display(self):
this_node = self.head
while this_node:
print(this_node.data, end= ' -> ')
this_node = this_node.next
print()
def search(self, data):
this_node = self.head
count = 0
while this_node:
if this_node.data == data:
return count
else:
count+=1
this_node = this_node.next
return -1
```
## Circular LinkedList
### What is it?
* A circular LinkedList is a variation of a linked list in which the last element is linked to the first element. This forms a circular loop
* It can be implemented using singly LinkedList or doubly LinkedList
* for a singly LinkedList, the next pointer of the last item points to the first item
* In the doubly LinkedList, prev pointer of the first item points to the last item as well
* The NULL assignment is not required because a node always points to another node.
* The starting point can be set to any node.
* Traversal from the first node to the last node is quick
### Implementation
#### Circular LinkedList using Singly LinkedList
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class CircularSinglyLinkedList:
def __init__(self, last=None):
self.last = last
def insertion(self, data):
new_node = Node(data)
if not self.last:
self.last = new_node
self.last.next = self.last
else:
new_node.next = self.last.next
self.last.next = new_node
def deletion(self):
if not self.last:
return True
elif self.last and not self.last.next:
self.last = None
return True
elif self.last and self.last.next:
self.last.next = self.last.next.next
return True
else:
return False
def display(self):
this_node = self.last
if self.last:
this_node = this_node.next
while this_node != self.last:
print(this_node.data, end = ' -> ')
this_node = this_node.next
print(this_node.data)
```
#### Circular LinkedList using Doubly LinkedList
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class CircularDoublyLinkedList:
def __init__(self, head=None):
self.head = head
def head_insertion(self, data):
new_node = Node(data)
if not self.head:
new_node.prev = new_node
new_node.next = new_node
self.head = new_node
else:
temp = self.head
new_node.next = self.head
new_node.prev = self.head.prev
self.head.prev = new_node
new_node.prev.next = new_node
self.head = new_node
def head_deletion(self):
if not self.head or not self.head.next:
self.head = None
return True
else:
self.head.prev.next = self.head.next
self.head.next.prev = self.head.prev
self.head = self.head.next
return True
def display(self):
this_node = self.head
if this_node:
print(this_node.data, end = ' -> ')
this_node = this_node.next
while this_node != self.head:
print(this_node.data, end = ' -> ')
this_node = this_node.next
print()
```
## LinkedList Data Structure Uses
* [Implemented in the stack](/python-1/data-structure/stack.md#using-linkedlist)
* **Implemented in the queue** - [regular queue - implementation using LinkedList](/python-1/data-structure/queue.md#normal-queue-1)
* **Dynamic memory allocation** -
* **In undo functionality**, it is more like a use case of queue using LinkedList
* **In Hash tables** - When there is a collision of hash (two different values have the same hash then they are arranged as LinkedList within a hash)
* **In Tree** -
* **In Graphs** -
## Miscellaneous
### Difference Between the Array and LinkedList?
## Reference for Further Reading
{% embed url="" %}