The task of implementing LinkedList can also be encountered during interviews with newcomers. The solution depends on the type of list you require: unidirectional (singly linked) or bidirectional. The following implementation uses a unidirectional (singly linked) LinkedList.
General points of the algorithm:
- Store head and tail in the class fields.
- Create the following methods:
– void add(T value)
– void remove(int i)
– T get(int i) - Method add(…) is used for add a new node to the list: set the new node as a next node of the tail and reassign the tail.
- Method remove(int i) is used to remove i node in order. Iterate through the list, incrementing the counter to position on the correct node. Reassign the tail of the previous node to the next one after the removed node.
- Method get(int i) is used accordingly own name to get i node in order the list. To do this, iterate through the list, incrementing the counter to position on the desired node, similar to the remove method.
- Time complexity:
– add(…): O(1)
– remove(int i): O(n) in worst case
– get(int i): O(n) in worst case - Space complexity:
– add(…): O(1)
– remove(int i): O(1)
– get(int i): O(1)
public class ImplementLinkedList {
static class LinkedList<T> {
private Node<T> head;
private Node<T> tail;
private static class Node<T> {
private final T value;
private Node<T> next;
public Node(T value, Node<T> next) {
this.value = value;
this.next = next;
}
}
public void add(T value) {
var node = new Node<T>(value, null);
if (head == null) {
this.head = node;
this.tail = node;
}
if (tail != node) {
this.tail.next = node;
this.tail = node;
}
}
public void remove(int i) {
var j = 0;
Node<T> prevNode = null;
var currentNode = this.head;
while (currentNode != null && j != i) {
prevNode = currentNode;
currentNode = currentNode.next;
j++;
}
if (i == j) {
if (prevNode == null) {
this.head = currentNode.next;
} else {
prevNode.next = currentNode.next;
}
if (currentNode.next == null) {
this.tail = prevNode;
}
} else {
throw new IllegalArgumentException("The node with %d index doesn't exist.".formatted(i));
}
}
public T get(int i) {
var j = 0;
var currentNode = this.head;
while (currentNode != null && j != i) {
currentNode = currentNode.next;
j++;
}
if (i == j) {
return currentNode.value;
} else {
throw new IllegalArgumentException("The node with %d index doesn't exist.".formatted(i));
}
}
}
public static void main(String[] args) {
var list = new LinkedList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
System.out.println(list.get(0));
System.out.println(list.get(1));
System.out.println(list.get(2));
System.out.println(list.get(3));
System.out.println(list.get(4));
System.out.println();
list.remove(0);
list.remove(2);
System.out.println(list.get(0));
System.out.println(list.get(1));
System.out.println(list.get(2));
}
}