---
# System prepended metadata

title: Linked List
tags: [GeeksforGeeks]

---

# 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)
![image](https://hackmd.io/_uploads/SyKMXAIz0.png)
- 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
![image](https://hackmd.io/_uploads/r1JywC8z0.png)
- we have multiple sorted sequences we need to merge them frequently
![image](https://hackmd.io/_uploads/B128OALMC.png)
    - no need for auxillary space during merging 
- embeded devices with low memory 
    - where long continues memory is hard to get

### Concepts
![image](https://hackmd.io/_uploads/r1raqCIz0.png)
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
![image](https://hackmd.io/_uploads/S1ITy1wMC.png)
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
![image](https://hackmd.io/_uploads/S1O0FZvMA.png)
    - 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
![image](https://hackmd.io/_uploads/BykItcWm0.png)

![image](https://hackmd.io/_uploads/BJa659ZX0.png)


``` 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
![image](https://hackmd.io/_uploads/S1BI3cZX0.png)
``` 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
![image](https://hackmd.io/_uploads/rkmb6cb7C.png)
``` 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
![image](https://hackmd.io/_uploads/Hy051jW7A.png)
``` 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
![image](https://hackmd.io/_uploads/r10izjbXR.png)
``` 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
![image](https://hackmd.io/_uploads/S1A6QsZQA.png)
``` 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
![image](https://hackmd.io/_uploads/HyDYsi9Q0.png)
![image](https://hackmd.io/_uploads/rJRB3iqXA.png)
Iterate though all nodes and swap previous and next pointers
![image](https://hackmd.io/_uploads/B1SpRjcXC.png)

``` 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
![image](https://hackmd.io/_uploads/SJwIUhqm0.png)
``` 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
