Linked List

Linked……Link property of Nintendo

In computer science, a data structure is one of those complex topics that can be tedious to talk about in class, Bootcamp, or even more stressful, at technical interviews. After all, it is critical to know how our code will work with our data altogether. I guess that’s why they call us Software Engineers.

Saying that we manage, organize, and store data it’s a description of what data structure is. But the more precise meaning is that a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. Now that we know the Encyclopedic meaning of data structure, let’s talk about one of these structures, the linked list.

A linked list is a linear data structure that represents a collection of elements, where each element points to the next one. The first element in the linked list is the head, and the last element is the tail. Imagine playing the first Legend of Zelda game, and each dungeon is a different element. There’s no side quest, not many secrets to uncover, just approximately 8 hours of a linear approach to the game. That’s how the linked list functions, a pointer moving to the next element. The first element is the head, and the last element is the tail.

A Linked List Graphic

Just imagine giving this map a linear approach. Again, no side quest.

Now that we know what’s a linked list, let’s dig deep with some coding and the different methods we can implement in a linked list class.

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

First things first, we need to create the node class. Some coders would prefer to declare Node in each method. Creating the node class and then, in each new method inside the LinkedList class creating the variable const newNode = new Node(value); turns out to be a cleaner code. Both ways to do it are good, and it’s up to the coder.

class LinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null, 
    };
    this.tail = this.head; 
    this.length = 1;
  }
}

Since we coded the Node class, let’s go ahead and start working on the LinkedList class. In this class, we declare the head with a value and next. We’ll follow by tailwhich will be the head. We’ll complete the LinkedList class declaring the length will start as 1.

append(value) {
    const newNode = new Node(value);
    this.tail.next = newNode; 
    this.tail = newNode; 
    this.length++;
    return this;
}

Before creating the Linked List with some elements, we need to append an additional value. The structure we are creating needs its head and its tail. First,newNode will be a new Node carrying value as the argument. this.tail.next and this.tail will both be newNode. After declaring both as newNodewe increment the length return this.

Note: Please refer to this documentation regarding this the operator if needed.

Now, let’s create the Linked List, and the values will be Link and his princess, Zelda.

First, let’s create the myLinkedList variable, with a string containing the value Link.

let myLinkedList = new LinkedList(“Link”);

Now, let’s call it with the method append by adding Zelda.

myLinkedList.append("Zelda");
//output:
LinkedList {
  head: { value: 'Link', next: { value: 'Zelda', next: null } },
  tail: { value: 'Zelda', next: null },
  length: 2

After adding the append method, let’s learn how to do the prepend method and add it to our class.

prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
    this.length++;
    return this 
}

As you may have noticed,prepend the method is very similar to append. The difference will be that newNode.next will be this.head and this.head is newNode.

myLinkedList.prepend("Ganon");
//output:
LinkedList {
  head: { value: 'Ganon', next: { value: 'Link', next: [Object] } },
  tail: { value: 'Zelda', next: null },
  length: 3
}

Every video game needs a villain, so let’s prepend Ganon to the list.

printList() {
    const array = [];
    let currentNode = this.head;
    while(currentNode !== null){
        array.push(currentNode.value)
        currentNode = currentNode.next
    }
    return array;
}

The insert method is the most complicated of all. So let’s rest for a bit by creating something simpler. The printList method will create an array to display all the values we have so far in the linked list.

myLinkedList.printList()
output:
[ 'Ganon', 'Link', 'Zelda' ]

Okay, now that we took a deep breath, time to do the insert method.

insert(index, value) {
    if (index >= this.length) {
      return this.append(value);
    }
    if (index === 0) {
      this.prepend(value);
      return this.printList();
    }
    const newNode = new Node(value);
    const leader = this.traverseToIndex(index - 1)
    const holdingPointer = leader.next;
    leader.next = newNode;
    newNode.next = holdingPointer;
    this.length++;
    return this.printList();
}
traverseToIndex(index) {
    let counter = 0;
    let currentNode = this.head;
    while (counter !== index) {
      currentNode = currentNode.next;
      counter++
    }
    return currentNode;
}

As said, this one gets complicated. I’m going to enumerate the steps since there is a lot to unfold in this method.

1. Declare two arguments, the index that we’ll position the new value and the value we’ll add.
2. Conditional statements for both append the new value if the newly added index number is higher or equal than the index length and prepend if the newly added index number equals 0. Without the statements, the code will break in both situations.
3. We also create the method traverseToIndex (remember the basics, computer indexes start with the number 0 and not the number 1 like human counting).
4. We add a new node the same way as the previous methods and also create a leader which will be the index subtracted by 1 and holdingPointer which will be next to the leader.
5. leader.next will be the newNode, newNode.next will be holdingPointer, the index length is incremented, and we’ll return using the method printList.

There’s a lot to sink in, but don’t worry, repetition will be key for getting it. Let’s go ahead and finally call it by adding someone else.

myLinkedList.insert(2, "Luigi");
//output:
[ 'Ganon', 'Link', 'Luigi', 'Zelda' ]

So look who’s here. Seems like Luigi got tired of being under his brother’s shadow or scared at haunted mansions. His green clothes make it easy to hide behind Link or any green bushes from Hylure. Since this is not Super Smash Bros, let’s get him out of the list and send him back to the Mushroom Kingdom where he belongs.

I’m sorry Luigi, go back to your mansion.

remove(index) {
    const leader = this.traverseToIndex(index-1);
    const unwantedNode = leader.next;
    leader.next = unwantedNode.next; 
    this.length--; 
    return this.printList();
}

The remove method will consist of leader subtracting the index by 1, the unwantedNode being leader.next, and the leader.next is the unwantedNode. There’s a lot of similarities with the other methods that you’ll notice when you code your own linked lists and the other similar lines of codes are decrementing the index length rather than incrementing and returning the result by using the printList method to see the simpler array.

myLinkedList.remove(2);
output//
[ 'Ganon', 'Link', 'Zelda' ]

We ran the remove method with index 2 and Luigi is gone from index 2.

Note: We can always console.log(myLinkedList) in order to know how the entire list looks like.

Here’s the full code for your reference:

So there we have it, it’s a lot but it’s worth the effort. Remember to practice, read it, look for more references and bring out the best version of yourself if you’re asked to create a Linked List.

Soon, I’ll explain how to create a Doubly Link List.

Happy Coding!

Summary:

1. Introduction to Data Structures
2. What is a Linked List
3. Code an entire Linked List Class with an additional Class to create Nodes and the following methods:
4. Append
5. Prepend
6. Insert
7. Return an array
8. Traverse to Index
9. Remove

References:

1. Data Structures, 1987. Horowitz, E., and Sahni, S. Fundamentals of Data Structures in Pascal, 2nd Ed. Rockville, MD: Computer Science Press.
2. 30 Seconds of Code, Linked List
3. MDN Web Docs, this