# LinkedList

## Linked list

<details>

<summary>Implementation of Linked list</summary>

[Java impl of Linked List](https://www.geeksforgeeks.org/implementing-a-linked-list-in-java-using-class/) ([Github](https://github.com/amartyushov/Experiments/blob/d228b895c63a737feb121a936b9dfe906c5e4609/java/algo/src/main/java/io/mart/data/structures/LinkedList.java))

{% code fullWidth="true" %}
```java
public class LinkedList {
	Node head;

	public static LinkedList insertToTail(LinkedList list, int data) {
		Node newNode = new Node(data);
		
		if (list.head == null) { // if list is empty
			list.head = newNode;
		} else {
			// traverse till the last node and insert new node there
			Node currentNode = list.head;
			while (currentNode.next != null) {
				currentNode = currentNode.next;
			}
			currentNode.next = newNode;
		}
		return list;
	}
	
	public static LinkedList deleteNode(LinkedList list, int key) {
		Node currentNode = list.head;
		Node prevNode = null;
		
		// CASE 1:
		// If head node itself holds the key to be deleted
		if (currentNode != null && currentNode.data == key) {
			list.head = currentNode.next;
			System.out.println(key + " found and deleted");
			return list;
		}
		
		// CASE 2:
		// If the key is somewhere other than at head
		
		// Search for the key to be deleted,
		// keep track of the previous node
		// as it is needed to change currNode.next
		while (currentNode != null && currentNode.data != key) {
			prevNode = currentNode;
			currentNode = currentNode.next;
		}
		
		// If the key was present, it should be at currentNode
		// Therefore the currentNode shall not be null
		if (currentNode != null) {
			// Since the key is at currentNode
			// Unlink currentNode from linked list
			prevNode.next = currentNode.next;
			
			// Display the message
			System.out.println(key + " found and deleted");
		}
		
		// CASE 3: The key is not present
		
		// If key was not present in linked list
		// currentNode should be null
		if (currentNode == null) {
			// Display the message
			System.out.println(key + " not found");
		}
		return list;
	}
	
	public static LinkedList deleteAtPosition(LinkedList list, int index) {
		Node currentNode = list.head;
		Node prevNode = null;
		
		// CASE 1:
		// If index is 0, then head node itself is to be deleted
		if (index == 0 && currentNode != null) {
			list.head = currentNode.next;
			System.out.println(index + " position element deleted");
			return list;
		}
		
		// If the index is greater than 0 but less than the size of LinkedList
		int counter = 0;
		
		// Count for the index to be deleted,
		// keep track of the previous node as it is needed to change currNode.next
		while (currentNode != null) {
			if (counter == index) {
				// Since the currentNode is the required
				// position Unlink currNode from linked list
				prevNode.next = currentNode.next;
				
				System.out.println(index + " position element deleted");
				break;
			} else {
				// If current position is not the index continue to next node
				prevNode = currentNode;
				currentNode = currentNode.next;
				counter++;
			}
		}
		
		// CASE 3: The index is greater than the size of the LinkedList
		// In this case, the currNode should be null
		if (currentNode == null) {
			System.out.println(index + " position element not found");
		}
		return list;
	}
	
	public static void printList(LinkedList list) {
		Node currentNode = list.head;
		System.out.print(" List: ");
		
		while (currentNode != null) {
			System.out.print(currentNode.data + " ");
			currentNode = currentNode.next;
		}
	}
	
	/**
	 * <a href="https://www.geeksforgeeks.org/rotate-a-linked-list/">source</a>
	 * Input: linked list = 10->20->30->40->50->60, k = 4
	 * Output: 50->60->10->20->30->40.
	 * Explanation: k is smaller than the count of nodes in a linked list so (k+1 )th node i.e. 50 becomes the head node and 60’s next points to 10
	 */
	public static LinkedList rotateCounterClockwise(LinkedList list, int k) {
		if (list.head == null) {
			System.out.println("List is empty");
			return list;
		}
		if (k == 0) return list;
		
		// Let us understand the below code for example k =
		// 4 and list = 10->20->30->40->50->60.
		Node currentNode = list.head;
		
		int counter = 1;
		// current will either point to kth or NULL after
		// this loop. current will point to node 40 in the
		// above example
		while (currentNode != null && counter < k) {
			currentNode = currentNode.next;
			counter++;
		}
		
		// If current is NULL, k is greater than or equal to
		// count of nodes in linked list. Don't change the
		// list in this case
		if (currentNode == null) {
			System.out.println(k + " is bigger than list size");
			return list;
		}
		
		// current points to kth node. Store it in a
		// variable. kthNode points to node 40 in the above example
		Node kNode = currentNode;
		
		// current will point to last node after this loop
		// current will point to node 60 in the above
		// example
		while (currentNode.next != null) {
			currentNode = currentNode.next;
		}
		
		// Change next of last node to previous head
		// Next of 60 is now changed to node 10
		currentNode.next = list.head;
		
		// Change head to (k+1)th node
		// head is now changed to node 50
		list.head = kNode.next;
		
		// change next of kth node to null
		kNode.next = null;
		return list;
	}
	
	static class Node {
		int data;
		Node next; // by default it is null
		
		Node(int value) { data = value; }
	}
	
	// Driver code
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		for (int i = 1; i < 9; i++) {
			list = insertToTail(list, i);
		}
		
		deleteAtPosition(list, 7);
		printList(list);
	}
}
```
{% endcode %}

</details>

<details>

<summary>Rotate counter clockwise Linked list</summary>

```java
package io.mart.data.structures;

public class LinkedList {
	Node head;

	public static LinkedList insertToTail(LinkedList list, int data) {
		Node newNode = new Node(data);
		
		if (list.head == null) { // if list is empty
			list.head = newNode;
		} else {
			// traverse till the last node and insert new node there
			Node currentNode = list.head;
			while (currentNode.next != null) {
				currentNode = currentNode.next;
			}
			currentNode.next = newNode;
		}
		return list;
	}
	
	public static void printList(LinkedList list) {
		Node currentNode = list.head;
		System.out.print(" List: ");
		
		while (currentNode != null) {
			System.out.print(currentNode.data + " ");
			currentNode = currentNode.next;
		}
		System.out.println();
	}
	
	static class Node {
		int data;
		Node next; // by default it is null
		
		Node(int value) { data = value; }
	}
	
	/**
	 * <a href="https://www.geeksforgeeks.org/rotate-a-linked-list/">source</a>
	 * Input: linked list = 10->20->30->40->50->60, k = 4
	 * Output: 50->60->10->20->30->40.
	 * Explanation: k is smaller than the count of nodes in a linked list so (k+1 )th node i.e. 50 becomes the head node and 60’s next points to 10
	 */
	public static LinkedList rotateCounterClockwise(LinkedList list, int k) {
		if (list.head == null) {
			System.out.println("List is empty");
			return list;
		}
		if (k == 0) return list;
		
		// Let us understand the below code for example k =
		// 4 and list = 10->20->30->40->50->60.
		Node currentNode = list.head;
		
		int counter = 1;
		// current will either point to kth or NULL after
		// this loop. current will point to node 40 in the
		// above example
		while (currentNode != null && counter < k) {
			currentNode = currentNode.next;
			counter++;
		}
		
		// If current is NULL, k is greater than or equal to
		// count of nodes in linked list. Don't change the
		// list in this case
		if (currentNode == null) {
			System.out.println(k + " is bigger than list size");
			return list;
		}
		
		// current points to kth node. Store it in a
		// variable. kthNode points to node 40 in the above example
		Node kNode = currentNode;
		
		// current will point to last node after this loop
		// current will point to node 60 in the above
		// example
		while (currentNode.next != null) {
			currentNode = currentNode.next;
		}
		
		// Change next of last node to previous head
		// Next of 60 is now changed to node 10
		currentNode.next = list.head;
		
		// Change head to (k+1)th node
		// head is now changed to node 50
		list.head = kNode.next;
		
		// change next of kth node to null
		kNode.next = null;
		return list;
	}
	
	public static void main(String[] args) {
		LinkedList list3 = new LinkedList();
		for (int i = 1; i < 9; i++) {
			insertToTail(list3, i);
		}
		printList(list3);
		rotateCounterClockwise(list3, 4);
		printList(list3);
	}
}
// List: 1 2 3 4 5 6 7 8 
// List: 5 6 7 8 1 2 3 4 
```

</details>

<details>

<summary>Reverse LinkedList</summary>

```java
package io.mart.data.structures;

public class LinkedList {
	Node head;

	public static LinkedList insertToTail(LinkedList list, int data) {
		Node newNode = new Node(data);
		
		if (list.head == null) { // if list is empty
			list.head = newNode;
		} else {
			// traverse till the last node and insert new node there
			Node currentNode = list.head;
			while (currentNode.next != null) {
				currentNode = currentNode.next;
			}
			currentNode.next = newNode;
		}
		return list;
	}
	
	public static void printList(LinkedList list) {
		Node currentNode = list.head;
		System.out.print(" List: ");
		
		while (currentNode != null) {
			System.out.print(currentNode.data + " ");
			currentNode = currentNode.next;
		}
		System.out.println();
	}
	
	static class Node {
		int data;
		Node next; // by default it is null
		
		Node(int value) { data = value; }
	}
	
	public static LinkedList reverseList(LinkedList list) {
		Node current = list.head;
		Node previous = null;
		
		while (current != null) {
			Node nextNode = current.next;
			
			current.next = previous;
			
			previous = current;
			current = nextNode;
		}
		list.head = previous;
		return list;
	}
	
	public static void main(String[] args) {
		LinkedList list3 = new LinkedList();
		for (int i = 1; i < 9; i++) {
			insertToTail(list3, i);
		}
		printList(list3);
		LinkedList reverseList = reverseList(list3);
		printList(reverseList);
	}
}

// List: 1 2 3 4 5 6 7 8 
// List: 8 7 6 5 4 3 2 1 
```

</details>

<details>

<summary>Print LinkedList values in reverse order (recursive solution)</summary>

```java
/*
https://www.youtube.com/watch?v=IR2X5Mw3StY&t=2s
1 -> 2 -> 3
Solution 1:
* reverse LinkedList
* iterate over the list again and print values

Pros:
+ does not take additional space

Cons:
- modifies linked LinkedList
- iterate over list twice (though time complexity is still O(n)

Solution 2:
Recursively print n.next

Pros:
+ does not modify initial LinkedList

Cons:
- it will take additional memory for recurvice method calls (method stack)
*/
public void printInReverseOrder(Node n) {
    // base case
    if (n == null) return;
    printInReverseOrder(n.next);
    System.out.println(n.value);
}

/*
Testing the solution (method stack displayed):
n = 1 ; n = 1 ; n = 1 ; n = 1
        n = 2   n = 2   n = 2 
                n = 3   n = 3
                        n = null   (base case returns here)                              
*/
```

</details>

<details>

<summary>find Nth last element</summary>

[https://www.byte-by-byte.com/nthtolastelement/](https://www.byte-by-byte.com/nthtolastelement/)

Given the list and n = 2, we have to return 3 (because 2nd node from the end is 3).

1 -> 2 -> 3 -> 4 -> 5 -> null

**Straightforward solution** is to:

1. Iterate over list and count its length (n)
2. Needed element position will be n - N
3. Iterate over list again and find element with a position n-N

it takes O(2\*n), which is O(n)

There is **alternative solution**:

Lets have two pointers _current_ and _follower_.&#x20;

1 -> 2 -> 3 -> 4 -> 5 -> null

&#x20;              ^

current

^&#x20;

follower

1. Advance current pointer to the N steps forward (e.g. n = 2)
2. Then synchronously move both pointers until current reaches the last element
3. Once reached, follower pointer will be on the Nth to the last position

```java
public Node (Node node, int n) {
    Node current = node;
    Node follower = node;
    
    // step 1
    for (int i = 0; i < n; i++) {
        if (current == null) return null;
        current = current.next;
    }
    
    // it means that n is equal to the list size. This is an edge case => return null
    if (current == null) return null;
    
    // step 3
    while (current.next != null) {
        current = current.next;
        follower = follower.next;
    }
    return follower;
}
```

</details>

<details>

<summary>Split LinkedList in half</summary>

```java
/* 
https://www.youtube.com/watch?v=lMxYBLqt1Mg
Given a linked list, write a function to split the list into two equal halves.

eg.

divide(1 -> 2 -> 3 -> 4) = 1 -> 2, 3 -> 4
divide(1 -> 2 -> 3 -> 4 -> 5) = 1 -> 2 -> 3, 4 -> 5

Topic: slow and fast pointers
Even number of elements in list:
1 -> 2 -> 3 -> 4
     ^
runner
^
pointer
1 -> 2 -> 3 -> 4
               ^
runner
     ^
pointer



Odd number of elements in list:
1 -> 2 -> 3 -> 4 -> 5
     ^
runner
^
pointer
1 -> 2 -> 3 -> 4 -> 5
               ^
runner
     ^
pointer
1 -> 2 -> 3 -> 4 -> 5 -> null
                          ^
runner
          ^
pointer

*/
public Node splitListInHalf (Node list) {
     if (list == null) return list;
     Node runner = list.next;
     
     while (runner != null) {
          runner = runner.next;
          if (runner == null) break;
          runner = runner.next;
          list = list.next;
     }
     Node toReturn = list.next;
     list.next = null; // split the list
     
     return toReturn;
}
```

</details>

<details>

<summary>Find duplicates in LinkedList</summary>

```java
/* https://www.youtube.com/watch?v=2X9cdj6Ng0w
Time complexity: O(N)
Space complexity: O(N) in case all values in list are unique
*/
public void dedup(Node n) {
    if (n == null) return;
    Set<Integer> nodes = new HashSet<>();
    Node prev = null;
    
    while (n != null) {
        if (nodes.contains(n.val)) {
            prev.next = n.next;
        } else {
            nodes.add(n.val);
            prev = n;
        }
        n = n.next;
    }
}

/*
https://www.youtube.com/watch?v=2X9cdj6Ng0w&t=573s
Time complexity: O(N^2)
Space complexity: O(1)
*/
public void dedup(Node n) {
    while (n != null) {
        Node curr = n;
        while (curr.next != null) {
            if (curr.next.val == n.val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
        n = n.next;
    }
}
```

</details>

<details>

<summary>Check LinkedList contains cycles</summary>

```java
/*
https://www.youtube.com/watch?v=dvOilHNRzZs
1 -> 2 -> 3 -> 4
     ^         |
     |_________|
*/

/*
First solution is pretty simple, using Set
Time complexity: O(N)
Space complexity: O(N)
*/
public boolean containsCycle(Node n) {
     if (n == null) return null;
     Set<Node> visited = new HashSet<>();
     
     for (Node curr = n; curr != null; curr = curr.next) {
          if (visited.contains(curr)) return true;
          visited.add(curr);     
     }
     return false;
}

/*
Second solution is based on Floyd's algorithm.
Explanation: https://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work
There is a slow and fast pointer. In case there is a cycle, then fast pointer 
finally catch up with slow pointer. Otherwise fast pointer will just reach
the end of the list.
*/
public boolean containsCycle(Node n) {
     if (n == null) return false;
     Node slow = n;
     Node fast = n.next;
     
     while (fast != null && fast.next !=null) {
          if (slow == fast) return true;
          slow = slow.next;
          fast = fast.next.next;
     }
     return false;
}
```

</details>

![](http://www.plantuml.com/plantuml/svg/SoWkIImgAStDuKhEIImkLYXBp2bDDLIevb9Go4kjAB7YgkL2bZ72AMECAfEHcPAga9jQaf6VKim5DLJN3ce85uI22nXpGOtGrT1Ko2lDoU5oICrB0JeA0000)

### Linked list insertion of element

![linked list insertion](http://www.plantuml.com/plantuml/svg/VT2zgiCm30NWtKyXo73lXMIuoPQXv3rA1pSwnAQA3RPI2gNltX1Q-bFIISFXayJfijgaqoZcXyI70tWUMLlo8IEfZy7qOdEcevK9_tGsH04dRSt5F2Sr5KC2mbhUl4hd6JH2NUHiRgkhv0UdsoA1Iuwgu5srkUkM6085gVDv-VITBUVBVPG7gsVM9zXFLdzZpIfhgFhzep29c0w1vzgk)

Time complexity

* insert at front **O(1)**
* insert at end **O(n)**                      // you need to traverse the whole list to read the end
* insert after a node **O(n)**            // in the worst case you will need to traverse till the end as well

Space complexity is **O(1)** independently where insertion happens

### Linked list deletion of element

![linked list deletion](http://www.plantuml.com/plantuml/svg/VT2z2i9030VmFKyHwA12EzXk7QJl8Gvd4tg7wHtSfIA8x-uX5J-aJXd-_FAHBgc9Eeq2AnJdJqov96sHM5XTyD2BIGdFHYRUuXKGFL-qXHky9pKMaMafRJwTTSGuijf02UR6LNI3rNqnH6PV7eFGeTezTOjzPAECQbrwhFdDyl2IWYg_M8tp4J-i_iUQ9PQJQhr1Fub0nvxop-u0)

Time complexity

* insert at front **O(1)**
* insert at end **O(n)**                      // you need to traverse the whole list to read the end
* insert after a node **O(n)**            // in the worst case you will need to traverse till the end as well

Space complexity is **O(1)** independently where insertion happens

## **LinkedList vs Array**

* Use **Linked list** when
  * you have a **large** number of **insert** or **delete** operations&#x20;
  * you have **no idea** what **size** the list can have
* User **Array** when
  * **read** operations need to be very **fast** and you have relatively **few** **updates** to the array
  * you require **random access** to array elements



## Doubly linked list

![doubly linked list](http://www.plantuml.com/plantuml/svg/SoWkIImgAStDuL9NACxCBSX9LKZ9BqtAgLJ8oSpBJaq1KiKbNCavYSN52cM9EQMfXWhLN0eA1KMfPLP0EY-reiIAgvOBMOKHGHN6s5LaPAQaAkIcbcJafnHpGItJjOCQoWMXu0A6w0B6N10AIOj3QbuAq6i0)

#### Memory allocation

![](https://415484505-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxtoAXZwwOc4XGto8vb%2F-M4TQQLFgIlZclkYCjy6%2F-M4Tx4aZuLITyW6yrxT-%2Fmemoty_allocation_array_linkedList.jpeg?alt=media\&token=0448c870-3fde-40b6-ab5e-9647b93daed2)

