LinkedList
Linked list
Implementation of Linked list
Java impl of Linked List (Github)
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);
}
}Rotate counter clockwise Linked list
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 Reverse LinkedList
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)
/*
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
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:
Iterate over list and count its length (n)
Needed element position will be n - N
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
Advance current pointer to the N steps forward (e.g. n = 2)
Then synchronously move both pointers until current reaches the last element
Once reached, follower pointer will be on the Nth to the last position
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
/*
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
/* 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;
}
}Check LinkedList contains cycles
/*
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;
}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
Last updated
