Linked Lists
Where the behavior of arrays is largely defined by using contiguous blocks of memory, link lists are defined by the opposite: their ability to use non-contiguous memory. How do linked lists represent a cohesive collection of items then? In its simplest implementation, each node of a linked lists is a combination of the value and a reference to the next item in the list. Therefore, instead of relying on absolute position from a starting point, as array do, linked lists require each node to know the location of its sibling.
Implementation
function LinkedList() {
this.head = null;
this.tail = null;
this.add = function(value) {
var node = new Node(value);
if (this.head == null) { this.head = node; }
if (this.tail != null) { this.tail.next = node; }
this.tail = node;
};
}
function Node(value) {
this.value = value;
this.next = null;
}
var list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
Example
Click step to add the values to our linked list
Manipulation
Manipulating the linked lists comes down to updating the affected head, tail and next references.
Remove Implementation
this.removeAt = function(index) {
var prev = null;
var node = this.head;
var i = 0;
while (node != null && i++ < index) {
prev = node;
node = node.next;
}
if (prev == null) { this.head = node.next;}
else { prev.next = node.next; }
};
list.removeAt(1);
Remove Example
Click step to remove the value from our linked list
Characteristics
In a world where memory isn't measured in gigabytes, linked lists have many advantages. Namely, they allow a structure to grow with minimal impact on available memory. Linked list can grow even within fragmented memory, and do so while providing constantly good insert performance. However, one does not have random access to individual nodes, resulting in constantly poor read performance. The overhead of a simple linked lists is essentially one reference per value.
It is also common for each node to have a reference to the previous node. This is known as a doubly-linked list. This doubles the memory overhead as well as making manipulation more complicated (two references must be maintained rather than just one). However, it does make insertion and deletions within the list simpler.
In The Real World
Link lists' memory friendliness isn't the great benefit it once was. Dynamic arrays, with spare space to grow, are generally a better fit for today's programs. However, linked lists are still a solid implementation for collections which provide sequential access, like queues and stacks.