Linked List: The Identity Crisis

One of the simplest data structures that you learn as a software engineer is the linked list. A linked list consists of a collection of nodes that are strung together in a sequence. Usually each node has a value and a pointer to another node. This is not a data structure that software engineers normally build from scratch at work. It is a data structure that software engineers are normally required to build during interviews.

A linked list is more hypothetical than a Javascript object, so it can be hard to wrap your head around. In a Javascript array, each element has an index. In an object, each element has a key. In a linked list, there is no index or key, the elements connect to each other. However, linked lists do usually have a head and a tail position that can be accessed directly.

Head -> item1 -> item2 -> item3 -> tail

To create a linked list in Javascript, you need a class that has a head and a tail. Then you can create methods, usually removeHead(), addToTail(), and contains() or search(). Other functions may be necessary depending on what the problem is. Doubly-linked lists (pointers in both directions) require more complexity. I'll only be describing a singly-linked list here.

You'll notice that I haven't discussed nodes yet. The 'nodes' that I mentioned above are places in memory and they only exist while another node is pointing to them. Once that relationship is severed, the 'garbage collector' in memory will clear it away. Nodes are not stored in variables and cannot be accessed directly (unless they are a head or a tail).

Here's what a linked list looks like in the pseudoclassical instantiation pattern.

var LinkedList = function(){  
  this.head = null;
  this.tail = null;
};

LinkedList.prototype.addToTail = function(value){  
  var newTail = this.makeNode(value);
  if (this.tail !== null) {
    this.tail.next = newTail;
    this.tail = newTail;
  } else if (this.tail === null) {
      this.head = this.tail = newTail;
  }
};

LinkedList.prototype.removeHead = function(){  
  var headVal = this.head.value;
  if (this.head.value === this.tail.value) {
      this.head = this.tail = null;
  } else {
      this.head = this.head.next;
  }
  return headVal;
};

LinkedList.prototype.contains = function(value){  
  var node = this.head;
  while (node) {
    if (node.value === value) {
      return true;
    } else {
      node = node.next;
    }
  }
  return false;
};

LinkedList.prototype.makeNode = function(value){  
  var node = {};
  node.value = value;
  node.next = null;
  return node;
};

As you can see, you can iterate through a linked list, you just can't use a for loop to do it. The node could have been a subclass, but it wasn't necessary for demonstration purposes.

This is the majority of what you need to prepare for an interview question on linked lists. Good luck!