# 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](https://ankit-apdc.gitbook.io/python-1/stack#using-linkedlist)
* **Implemented in the queue** - [regular queue - implementation using LinkedList](https://ankit-apdc.gitbook.io/python-1/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>" %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ankit-apdc.gitbook.io/python-1/data-structure/linkedlist.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.