linear search


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.


 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();


Click step to add the values to our linked list



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; }

Remove Example

Click step to remove the value from our linked list



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