Linked Lists

Linked Lists are pretty important to understand! You can think of them like carabiners that latch onto each other, or a skyscraper that has no elevators and you have to go through EACH floor to reach the desired floor you’re looking for.

First of all, that’s a lot of stairs. Secondly, this emphasizes the case that linked lists are an important data structure to understand. They’re more efficient memory wise than arrays since with arrays you have to declare a set size. Whereas with linked lists, you can store it in memory and when you’re ready to add on another node, the pointer from the previous node points to the new address of the new node.

Confusing? Let me give you another example.

From Grokking’s Algorithms, linked lists can be thought of like… going to the movies with your friends. You and your friends show up, the movie theater has some seats left, but they’re far and few between. Clearly, your friends can’t sit with you, so you guys split up. Each of you represents a node. Say you’re sitting in the back, but you can identify the next closest friend, and that friend can identify the next closest friend to them, so on and so forth. This is a linked list!

By saving data in memory by providing addresses (pointers) to the next node, you are more efficient than an array.

Continuing our movie example, say you show up to the movie theater early and save 15 seats, but only 7 of your friends show up. This means that 8 of your friends are questionable, and also that this is inefficient. Rather than saving 15 seats for potential spots in the array, use a linked list to allocate where you and your present friends will be sitting.

Here is how you set up a linked list:

class Node {
constructor(val) {
this.val = val
this.next = null
}
}
class SinglyLinkedList {
constructor() {
this.head = null
this.tail = null
this.length = 0
}
push(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail = this.head
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++
return this
}
//add function here//
}

You must set up the Node first (the current value and the next value). Next, set up another class for the singly linked list in this case and the logic states: if there is no head (you’re initializing the list for the first time), then take the first value given and make it the head AND the tail. If there is a head, then make the new value the tail.

This is how you set it up! Hope this helps.

Happy hacking.

-crystal