> For the complete documentation index, see [llms.txt](https://amartyushov.gitbook.io/tech/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://amartyushov.gitbook.io/tech/computer-science/general-notes/linkedlist.md).
# LinkedList
## Linked list
Implementation of Linked list
[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;
}
}
/**
* source
* 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 %}
Rotate counter clockwise Linked list
```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; }
}
/**
* source
* 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
```
Reverse LinkedList
```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
```
Print LinkedList values in reverse order (recursive solution)
```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)
*/
```
find Nth last element
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*.
1 -> 2 -> 3 -> 4 -> 5 -> null
^
current
^
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;
}
```
Split LinkedList in half
```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;
}
```
Find duplicates in LinkedList
```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 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;
}
}
```
Check LinkedList contains cycles
```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 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;
}
```
### Linked list insertion of element
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
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
* 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
#### Memory allocation
