Linked list is like a chain where each node connects to the next one.
Every nodes has a pointer that shows where the next node is.
This keeps going until we reach the end.
The last node also has a pointer. It points to null, which means it doesn’t connect to anything else,
but it still holds variable there.
Arrays hold space in memory in a straight line,
and LinkedList has a separate location for each, pointer to find the node behind it.
LinkedList vs ArrayList
| Operation | Linked List | Array List |
|---|---|---|
| Append | O(1) | O(1) |
| Remove Last | O(n) | O(1) |
| Prepend | O(1) | O(n) |
| Remove First | O(1) | O(n) |
| Insert | O(n) | O(n) |
| Remove | O(n) | O(n) |
| Lookup by Index | O(n) | O(1) |
| Lookup by Value | O(n) | O(n) |
LinkedList Example
public class LinkedList {
public Node head;
public Node tail;
public int length;
public LinkedList (int value) {
Node newNode = new Node(value);
head = newNode;
tail = newNode;
length = 1;
}
public void append(int value) {
}
public void prepend(int value) {
}
public void insert(int index, int value) {
}
}
public class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}