What Are Linked Lists?

A singly linked list is a data structure which represents a series of nodes where each node points to the next node in the list. A doubly linked list, in contrast, has nodes which point to the element preceding and following it.

Unlike an array, a linked list doesn’t provide constant-time access to specific indices within the list. So if you need the third element in the list, you have to iterate past the first and second nodes to reach it.

One benefit of a linked list is the ability to add and remove items from the beginning and end of the list in constant time.

These are popular data structures to be questioned about during a technical interviews, so let’s jump right in.

A singly-linked list may be LIFO (last-in-first-out) or FIFO (first-in-first-out). If the list is using the LIFO method, the nodes will be added to and deleted from the same end. If it’s using FIFO, nodes will be added to one end and deleted from the opposite end.

Additionally, the linked list may be sorted. This means that as each node is added to the list, it’s placed into its appropriate spot relative to the other nodes.

Node

A linked list is just a series of nodes, so let’s start with our Node object.

A node has two pieces of information:

• A pointer, or reference, to the next item in the list (for a singly linked list)
• The value of the node

For our node, we’ll just create a function which takes a value, and returns an object with the two values above: a pointer to the next node and the value of the node. Note that we’re able to just declare value instead of value: value. This is because the variables have the same name. You can learn more about the object property shorthand here.

function Node(value) {
  return {
    value,
    next: null
  }
}

NodeList

Now, let’s delve into the NodeList class. This is just that: a list of nodes.

Our node list will contain five methods:

• push(value): Pushes a value on to the end of the linked list
• pop(): Pops off the last value from the list
• get(index): Returns an item from a given index
• delete(index): Deletes an item from a given index
• isEmpty(): Returns a boolean indicating whether the list is empty
• printList(): A method, not native to linked lists, which will print out our list; it’s primarily for debugging purposes

Constructor

I’m going to be using JavaScript class syntax, although you could also use a closure to create a linked list. So let’s set up the constructor.

We’ll need three pieces of information in our constructor:

• head: A reference to the node at the beginning of the list
• tail: A reference to the node at the end of the list
• length: How many nodes are in the list

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

IsEmpty

The isEmpty() method is a helper function which returns true if the list is empty.

isEmpty() {
  return this.length === 0;
}

printList

This utility method will print the nodes in the list. This is solely meant for debugging purposes.

printList () {
  const nodes = [];
  let current = this.head;
  while (current) {
    nodes.push(current.value);
    current = current.next;
  }
  return nodes.join(' -> ');
}

Push

Our push method needs to check whether the list is empty or not before adding a new node. How do we know if the list is empty? Two ways:

• Our isEmpty() method returns true (the length of the list is zero)
• The head pointer is null

For this example, we’ll check whether head is null, although either solution works fine.

If there are no items in the list, we can simply set both the head and tail pointers to the new node and update the length of the list.

if (this.head === null) {
  this.head = node;
  this.tail = node;
  this.length++;
  return node;
}

If the list isn’t empty, we have to do the following:

• Set tail.next to point to the new node
• Set tail to point to the new node
• Increment the list length

Here is our completed push method:

push(value) {
  const node = Node(value);
  // The list is empty
  if (this.head === null) {
    this.head = node;
    this.tail = node;
    this.length++;
    return node;
  }
  this.tail.next = node;
  this.tail = node;
  this.length++;
}

Pop

Our pop method needs check the following two things before removing the last item in the list:

• Check whether the list is empty
• Check whether there is only one item in the list

We can use our isEmpty method to check whether a list contains nodes.

if (this.isEmpty()) {
  return null;
}

How do we know if there’s only one node in the list? If head and tail are pointing to the same node. But what do we need to do in this instance? Removing the only node means we’re essentially resetting the list.

if (this.head === this.tail) {
  this.head = null;
  this.tail = null;
  this.length--;
  return nodeToRemove;
}

If there is more than one element in the list, we can do the following:

while there are nodes in the list
  if the next node in the list is the tail
    update tail to point to the current node
    set the current node to point to null
    decrement the length of the list
    return the previous tail element

It will look something like this:

let currentNode = this.head;
let secondToLastNode;

// Start at the front and iterate until
// we find the second to last node
while (currentNode) {
  if (currentNode.next === this.tail) {
    // Move the pointer for the second to last node
    secondToLastNode = currentNode;
    break;
  }
  currentNode = currentNode.next;
}
// Pop off that node
secondToLastNode.next = null;
// Move the tail to the second to last node
this.tail = secondToLastNode;
this.length--;

// Initialized to this.tail
return nodeToRemove;

If you’re having trouble visualizing this, let’s walk through it.

Lines 6–10: If the next node in the list is the last item, this current item is the new “tail” so we need to save it’s reference.

if (currentNode.next === this.tail) {
  secondToLastNode = currentNode;
}

list

Line 15: Update secondToLastNode to point to null. This is the act of “popping” off the last element from the list.

secondToLastNode.next = null;

Line 16: Update tail to point to secondToLastNode.

this.tail = secondToLastNode;

Line 17: Decrement the length of the list because we just removed a node.

Line 18: Return the node we just popped off.

Here’s our full pop method:

pop() {
  if (this.isEmpty()) {
    return null;
  }
  const nodeToRemove = this.tail;
  // There's only one node!
  if (this.head === this.tail) {
    this.head = null;
    this.tail = null;
    this.length--;
    return nodeToRemove;
  }

  let currentNode = this.head;
  let secondToLastNode;

  // Start at the front and iterate until
  // we find the second to last node
  while (currentNode) {
    if (currentNode.next === this.tail) {
      // Move the pointer for the second to last node
      secondToLastNode = currentNode;
      break;
    }
    currentNode = currentNode.next;
  }
  // Pop off that node
  secondToLastNode.next = null;
  // Move the tail to the second to last node
  this.tail = secondToLastNode;
  this.length--;

  // Initialized to this.tail
  return nodeToRemove;
}

Get

Our get method must check for three situations:

• The index requested is outside the bounds of the list
• The list is empty
• We’re requesting the first element

If the requested index doesn’t exist within the list, return null.

// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

If the list is empty, return null. You can combine these if statements, but to keep it clear, I separated them.

if (this.isEmpty()) {
  return null;
}

If we’re requesting the first element, return the head.

// We're at the head!
if (index === 0 )  {
  return this.head;
}

Otherwise, we just iterate through the list one by one until we find the index we’re looking for.

let current = this.head;
let iterator =  0;

while (iterator < index) {
  iterator++;
  current = current.next;
}

return current;

Here is the full get(index) method:

get(index) {
// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

if (this.isEmpty()) {
  return null;
}

// We're at the head!
if (index === 0 )  {
  return this.head;
}

let current = this.head;
let iterator =  0;

while (iterator < index) {
  iterator++;
  current = current.next;
}

return current;
}

Delete

Our delete method will also have to account for three special use cases:

• The index we want to delete is outside the bounds of the list
• The list is empty
• We want to delete the head

If the index we want to delete doesn’t exist within the list, return null.

// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

If the list is empty, return null. You could combine this logic with the logic to determine whether the index is outside the bounds of the list, but for clarity’s sake I have kept them separate.

if (this.isEmpty()) {
  return null;
}

If we want to delete the head, set head to the next value in the list, decrement the length, and return the value we just deleted.

if (index === 0) {
  const nodeToDelete = this.head;
  this.head = this.head.next;
  this.length--;
  return nodeToDelete;
}

If none of these booleans are true, the logic for deleting a node is as follows:

while the iterator isn't the index we're looking for
  increase the iterator
  move the previous and current pointers up by one
save the current value as the node to be deleted
update the previous node's pointer to point to the next node
if the next value is null
  set tail to the new last node
decrement list length
return the deleted node

If you need help visualizing this, please refer to the diagram found in the Pop section.

The difference between the delete method and the pop method is that the pop method will always delete the last item in the list. In contrast, the delete method can delete an index between 0 and the length of the list.

Here is the completed delete method:

delete(index) {
   // Index is outside the bounds of the list
  if (index < 0 || index > this.length - 1) {
    return null;
  }

  if (this.isEmpty()) {
    return null;
  }

  if (index === 0) {
    const nodeToDelete = this.head;
    this.head = this.head.next;
    this.length--;
    return nodeToDelete;
  }

  let current = this.head;
  let previous;
  let iterator = 0;

  while (iterator < index) {
    iterator++;
    previous = current;
    current = current.next;
  }
  const nodeToDelete = current;
  // Re-direct pointer to skip the element we're deleting
  previous.next = current.next;

  // We're at the end
  if(previous.next === null) {
    this.tail = previous;
  }

  this.length--;

  return nodeToDelete;
}

If you’d like to play around with the code, feel free to fork my CodePen.