# 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**

| <p><br>Operation</p>    | 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](../stack#using-linkedlist)
* **Implemented in the queue** - [regular queue - implementation using LinkedList](../queue#normal-queue-1)
* **Dynamic memory allocation** -&#x20;
* **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** -&#x20;
* **In Graphs** -&#x20;

## Miscellaneous

### Difference Between the Array and LinkedList?

## Reference for Further Reading

{% embed url="https://medium.com/javarevisited/top-20-linked-list-coding-problems-from-technical-interviews-90b64d2df093" %}



