Arun Pariyar

Learn Data Structures building a Linked List

Programming is all about input and output in its most basic sense. We provide some input to a program, and it returns a result. For example, consider the "eligible to drive" program below:

function IsEligibleToDrive(yearOfBirth) {
  const today = new Date();
  return today.getFullYear() - yearOfBirth > 16 ? "Yes" : "No";
}

IsEligibleToDrive(2015); //"No"
IsEligibleToDrive(1998); //"Yes"

The program above receives a year of birth, calculates the age, and returns either “Yes” or “No.”

In this example, we're working with a very simple type of data—numbers. But what if we needed a way to work with a series of data that could be stored and used as needed?

Data structures are a fundamental concept in programming. When I first started learning about them, the term "data structures" scared me, but with focused learning, I realized they weren't as intimidating as I initially thought.

Let’s see if I can help make you slightly less scared of data structures (if you feel that way!) by introducing you to a basic one: the Linked List.

A Linked List is designed to store data in a particular way, allowing us to work with it efficiently. Below, we see a series of numbers and pointers, starting with the head and ending at the tail, which points to null.

head                          tail
20 -> 30 -> 50 -> 70 -> 90 -> 10 -> null

In this post, we'll create a linked list and implement the push and pop functionalities to understand the basic concepts. To get started, let’s abstract the data and pointer information into a separate class called Node. Here’s what that looks like:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

With this, we can create a single instance of a node that has a value property and a next pointer, which initially points to null.

Let’s create an instance of the Node class:

const node = new Node(20);
console.log(node); // {value: 20, next: null}

Now that we have the Node class in place, let’s create the Linked List. A linked list consists of a head reference, a tail reference, and, for our implementation, we'll also keep track of the length. Here’s the code:

class LinkedList {
  constructor(value) {
    const newNode = new Node(value);
    this.head = newNode;
    this.tail = newNode;
    this.length = 1;
  }
}

Let’s create an instance of the linked list and log it in the console:

const linkedList = new LinkedList(20);
console.log(linkedList);

// Output:
{
  head: { value: 20, next: null },
  tail: { value: 20, next: null },
  length: 1
}

Now that the linked list can be created and initialized with a value, let’s see how we would implement the push method, which allows new values to be added to the tail of the linked list.

Here’s the push method implementation:

push(value) {
  const newTail = new Node(value);

  if (this.length === 0) {
    this.head = this.tail = newTail;
  } else {
    this.tail.next = newTail;
    this.tail = newTail;
  }

  this.length++;
  return this;

We can now use the push method, as shown below:

const linkedList = new LinkedList(20);
linkedList.push(50).push(30).push(10);

console.log(linkedList);

/* Console output: */
LinkedList {
  head: Node { value: 20, next: Node { value: 50, next: [Node] } },
  tail: Node { value: 10, next: null },
  length: 4
}

We can see above that the head holds the value 20, the tail holds the value 10, and the length is correctly shown as 4.

Next, let’s create the pop method, which will remove values from the tail and set the previous node as the new tail.

Here’s the pop implementation:

pop() {
  if (!this.head) {
    return undefined;
  }

  let removedNode;

  if (this.length === 1) {
    removedNode = this.head;
    this.head = this.tail = null;
  } else {
    let currentNode = this.head;
    let previousNode = null;
    /* find the last node and second last node */
    while (currentNode.next) {
      previousNode = currentNode;
      currentNode = currentNode.next;
    }
    removedNode = currentNode;
    this.tail = previousNode;
    this.tail.next = null;
  }

  this.length--;
  return removedNode;
}

Let’s test this implementation in different scenarios. First, when there's only one value:

const ll = new LinkedList(20);
console.log(ll.pop());
console.log(ll.pop());

/* Console output: */
Node { value: 20, next: null }

Next, when the linked list is empty (we run pop() twice):

const ll = new LinkedList(20);
ll.pop();
console.log(ll.pop());

/* Console output: */
undefined;

Finally, let’s check if it removes the correct node and sets the tail correctly when there are multiple nodes:

const ll = new LinkedList(20).push(50).push(10).push(40);

console.log("Node removed: ", ll.pop());
console.log("Current tail: ", ll.getTail());

/* Console output: */
Node removed:  Node { value: 40, next: null }
Current tail: Node { value: 10, next: null }

We’ve successfully implemented a linked list! Here’s what the full implementation looks like:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor(value) {
    const newNode = new Node(value);
    this.head = newNode;
    this.tail = newNode;
    this.length = 1;
  }

  push(value) {
    const newTail = new Node(value);

    if (this.length === 0) {
      this.head = this.tail = newTail;
    } else {
      this.tail.next = newTail;
      this.tail = newTail;
    }

    this.length++;
    return this;
  }

  pop() {
    if (!this.head) {
      return undefined;
    }

    let removedNode;

    if (this.length === 1) {
      removedNode = this.head;
      this.head = this.tail = null;
    } else {
      let currentNode = this.head;
      let previousNode = null;
      while (currentNode.next) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      removedNode = currentNode;
      this.tail = previousNode;
      this.tail.next = null;
    }

    this.length--;
    return removedNode;
  }

  getHead() {
    return this.head;
  }

  getTail() {
    return this.tail;
  }
}

One key takeaway is that the linked list itself doesn't keep track of all the values. Instead, the relationships we create between nodes link the list together.

I hope this step-by-step implementation helps you better understand linked lists and, through them, how data structures are designed to store, retrieve, and manipulate data efficiently

← Back Home