home

linear search

arrays

linked lists

hash tables

binary search

bubble sort

insertion sort

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

 
 
 
step

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

1
2
3
step

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.

blog comments powered by Disqus