# Linked List

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.

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 `tail`

which 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 `newNode`

we 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.

- Declare two arguments, the index that we’ll position the new value and the value we’ll add.
- 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. - We also create the method
`traverseToIndex`

(remember the basics, computer indexes start with the number`0`

and not the number`1`

like human counting). - 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`

. `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.

`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:

- Introduction to Data Structures
- What is a Linked List
- Code an entire Linked List Class with an additional Class to create Nodes and the following methods:
- Append
- Prepend
- Insert
- Return an array
- Traverse to Index
- Remove

# References:

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