# Linked List
- Linear data structure
- not cache frendly
- memory need not have to be contiguous (unlike array data structure)
### Problems with Arrays
- Either Size is fixed (fixed sized arrays) or Preallocated (vectors)
- worst case insertion at end is O(n) - after amotization and average case is O(1)
- Insert into middle or begining takes O(n)
- Delete into middle or begining takes O(n)
- Implementation of other data strucures such as queue and deque are complex with arrays
- stack insertion and deletion happends at one end
- insertion and deletion happends at both ends
- Hard to implement round robin scheduling (and its easy with circular linked list)
- Given a sequence of items. whenever we see a item an item x in the sequence, we need to replace it with 5 instances of another item y
- we have multiple sorted sequences we need to merge them frequently
- no need for auxillary space during merging
- embeded devices with low memory
- where long continues memory is hard to get
### Concepts
It forms a chain or sequence
### Terminology
- Head
- Node
- Value or data
- Reference or pointer to next node
- Null reference
### Structures
- Singly Linked List
- keep track of head
- tail node will next pointer points to null
- Doubly Linked List
- Circular Linked List
#### Singly Linked List
``` python
class Node:
def __init__(self, data, next = None):
self.data=data
self.next=next
```
#### Doubly Linked List
``` python
class Node:
def __init__(self,data, next = None, prev = None):
self.data=data
self.next=next
self.prev=prev
```
#### Doubly linked list vs Single
- Advantages
- Can be traversed in both directions
- a given delete a node in O(1) time with given referencer to it
- Insert/delete before a given node
- Insert/delete from both ends is O(1) by maintaining tail
- Disadvantages
- Extra space for prev
- code becomes complex
#### Circular linked list (single)
- Advantages
- we can traverse the whole list from any node
- implementation of algorithms like round robin
- we can insert at the begining and end by just maintining one tail reference/pointer (instead of head)
- Disadvantages
- Implementation of operations become complex
### Memory Allocation
Addtional memory is needed to store the next pointer for each node
- data -> 4 bytes
- address -> 4 bytes
### Applications
- worst case insertion at the end and begin are O(1)
- worst case deletion from begining is O(1)
- Insertions and deletions in the middle are O(1) if we have reference to the previous node
- Round robin implementation
- merging two sorted linked lists is faster and space efficent
- Implementation of simple memeory manager need to link free blocks
- Other data structues such as stacks and Queues can be implimented with linked list much easier then with arrays
### Problems
- impliment single linked list
``` python
class Node:
def __init__(self, data, next = None):
self.data=data
self.next=next
head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
```
- traverse single linked list
- iterative
``` python
# TC: O(n)
# SC: O(1)
def traverse(head):
if head is None:
print('NULL')
current = head
while current is not None:
print(current.data, end=' ')
current = current.next
print(' ')
```
- recursive
``` python
# TC: O(n)
# SC: O(n)
def traverse(node):
if node is None:
print('NULL')
return
print(node.data, end=' ')
traverse(node.next)
```
- count items in single linked list
- iterative
``` python
# TC: O(n)
# SC: O(1)
def count(node):
size = 0
current = node
while current != None:
size += 1
current = current.next
return size
```
- recursive
``` python
# TC: O(n)
# SC: O(n)
def count(node):
if node is None:
return 0
return 1 + count(node.next)
```
- insert at begin
- return the head pointer
``` python
# TC: O(1)
# SC: O(1)
def insert_begin(node, data):
return Node(data, node)
```
- insert at end
``` python
def insert_end(head, data):
temp = Node(data)
if head is None:
return temp
node = head
while node.next is not None:
node = node.next
node.next = temp
return head
```
- insert at given position of single linked list
Note: position is provided as 1 based index
``` python
# TC: O(n)
# SC: O(1)
def insert_nth(head, data, pos):
temp = Node(data)
# insert at begining
if pos == 1:
temp.next = head
return temp
current = head
for _ in range(1, pos - 1):
if current is None:
return head
current = current.next
# if end is reached skip inserting and exit
if current is None:
return head
# swap pointers
temp.next = current.next
current.next = temp
return head
```
- delete first node of single linked list
``` python
# TC: O(1)
# SC: O(1)
def delete_first(head):
if head is None:
return None
return head.next
```
- delete last node of single linked list
``` python
# TC: O(1)
# SC: O(1)
def delete_last(head):
if head is None or head.next is None:
return None
current = head
while current.next.next is not None:
current = current.next
# deleting the last node
current.next = None
return head
```
- search in single linked list
- iterative
``` python
# TC: O(n)
# SC: O(1)
def search(head, data):
current = head
while current is not None:
if current.data == data:
return True
current = current.next
return False
```
- recursive
``` python
# TC: O(n)
# SC: O(n)
def search(node, data):
if node is None:
return False
if node.data == data:
return True
return search(node.next, data)
```
- Doubly linked list
``` python
class Node:
def __init__(self,data, next = None, prev = None):
self.data=data
self.next=next
self.prev=prev
head = Node(10)
node1 = Node(20)
node2 = Node(30)
head.next = node1
node1.prev = head
node1.next = node2
node2.prev = node1
```
- Insert in begining of doubly linked list
``` python
# TC: O(1)
# SC: O(1)
def insert_begin(head, data):
temp = Node(data)
if head is None:
return temp
temp.next = head
head.prev = temp
return temp
```
- Insert in end of doubly linked list
``` python
# TC: O(n)
# SC: O(1)
def insert_end(head, data):
temp = Node(data)
if head is None:
return temp
current = head
while current.next is not None:
current = current.next
current.next = temp
temp.prev = current
return head
```
- reverse a doubly linked list
Iterate though all nodes and swap previous and next pointers
``` python
# TC: O(n)
# SC: O(1)
def reverse(head):
if head is None or head.next is None:
return head
prev = None
current = head
while current is not None:
prev = current.prev
current.prev = current.next
current.next = prev
current = current.prev
return prev.prev
```
- delete head of doubly linked list
``` python
# TC: O(1)
# SC: O(1)
def delete_first(head):
if head is None or head.next is None:
return None
current_head = head.next
current_head.prev = None
# cleanup
head.next = None
return current_head
```
- delete tail of doubly linked list
``` python
# TC: O(n)
# SC: O(1)
def delete_last(head):
if head is None or head.next is None:
return None
current = head
while current.next is not None:
current = current.next
current.prev.next = None
# cleanup
current.prev = None
return head
```
- Circular linked list
``` python
class Node:
def __init__(self, data, next = None):
self.data=data
self.next=next
# case 1
head = None
# case 2
head = Node(10)
head.next = head
# case 3
tail = Node(5)
head = Node(1, Node(2, Node(3, Node(4, tail))))
tail.next = head
```
- circular linked list traversal
``` python
def traverse(head):
if head is None:
print ('NULL')
return
current = head
while current.next != head:
print(current.data, end = ' -> ')
current = current.next
print(current.data)
```
- insert at begin of circular linked list
- insert at the end of circular linked list
- sorted insert in a single linked list
- middle of linked list
``` python
# TC: O(n)
# SC: O(1)
def middle(head):
fast = head
slow = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow.data
```
- nth node from end of linked list
``` python
# TC: O(n)
# SC: O(1)
def nth_from_end(head, pos):
fast = head
slow = head
while pos > 0:
fast = fast.next
pos -= 1
while fast is not None:
fast = fast.next
slow = slow.next
return slow.data
```
- reverse a linked list
- iterative
- recursive
- removed duplicates from sorted singly linked list
- reverse a linked list in groups of size k
- detect loop
- detect loop using floyd cycle detection
- detect and remove loop in linked list
- delete node with only pointers given to it
- segragate even and odd nodes
- intersection of two linked list
- pairwise swap nodes of linked list
- clone a linked list with random pointer
- LRU cache design
- merge two sorted linked list
- palindrome linked list
- XOR linked list
- Circular linked lists
Sign in with Wallet
Connect another wallet