LinkedList

Linked list

Implementation of Linked list

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

PreviousString NextTree

Last updated 11 months ago

Was this helpful?

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

PreviousString NextTree

Last updated 11 months ago

Was this helpful?