CoDEVIANT #22 — Linked Lists and Pyramid Schemes (I.P.)(10/12/20)
Hey people, sorry for the delay. I try to make these articles a daily thing (or as close to it as my pea-brain will allow). However, as is wont to occur, I occasionally run into new concepts that take a while for me to wrap my head around. My personal belief is that if you can teach something to someone you’re that much closer to really understanding what the hell you’re talking about.
To that end, I found myself learning more about data-structures these past few days. I spent alot of time on linked-lists. I always knew that the difference between an array and a a linked-list was that arrays required that their bytes be continuous in the memory that was available to a computer and that linked-lists had pointers that referred to other bytes in memory that allowed a computer to store information that could more-or-less act like an array with out the need for the bytes to be physically contiguous. At any rate. I’m going to share what I can about linked lists and then I’m going to break down how to create a doubly-linked list with methods to manage traversing, altering, and verifying data within the linked-list.
So what is a linked list? Unfortunately it’s not the title of some terrible Zelda game that Philips is responsible for in what was probably the worst 3rd party deal Nintendo ever made.
A linked list is a collection of data in memory that is linked together non-continuously (physically speaking) with the help of pointers. These pointers tell our operating system where to look in our memory-canvas (imagine a giant quilt with squares to represent our working memory) in order to reach the next bit of data. Linked lists are made of nodes.
A NODE within a linked-list consists of the following:
- Data
- Pointer to the next node
They are represented like this on paper: 1-> (value and the pointer, an arrow)
Here is a linked list on paper: 1-> 2-> 3-> 4 (The first node is called the head and the last node is called the tail).
In code, they typically look something like this:
let linkedList= {
head: {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: ...etc. etc.
}
}
}
}Let’s assume we’re working with a 64-bit OS. What this means is that our integers (numbers) are going equal 64bits in length. Each byte is 8bits long. Ergo, we need 8bytes to get to 64 bits (because 8x6 = 64). Why am I telling you this? Because with the diagram below, I need you to imagine that each square is actually 8 squares that are each a byte.
So we have our value in one square represented in red. Then in the adjacent square in memory, we have a pointer (named ‘next’)that tells us where our next value is at. Adjacent to THAT value is another pointer…etc. This pattern goes on until we reach the node where the pointer ‘next’ points to…well…nothing. There’s nothing after that so the OS fills in the system’s memory address for null.
So assuming we wanted to insert a new node within this linked list…say we had a value of 7 that we wanted to plug into the middle of our linked list so that 1 -> 2-> 3-> 4 would become 1->2->7->3->4 we have to do a little finagling with the pointers. Since these bits of data, these nodes, are not contiguous, the only way the linked-list has any form at all is if the pointers are…well…on point.
What this will require is that we update the pointer from the node before where we want to insert the node with the value of 7. Then we’ll make the 7-node’s next pointer point to what was the node-before’s ‘next’ property.
Here’s crude diagram:
Let’s put it in terms of code. We create a class called Node the constructor accepts an argument for a value and the class-property value is set to equal the value that was passed in as an argument. The class-property of next is defaultly set to null.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}Next we’re going to make a class called SinglyLinkedList. It’s constructor, which is called upon the class’ instantiation (a fancy word for when someone makes a variable that is an instance of the class like:)
let thing = new SinglyLinkedList()…um as I was saying it’s constructor will set head to equal null and set tail to equal null.
class singlyLinkedList {
constructor() {
this.head = null
this.tail = null
}
...
}Now let’s create some methods inside this singlyLinkedList class of ours to help us manage this thing.
However…this can be a complicated thing. You make one mistake with the pointers and it’s like losing the grip of a loved one that’s hanging off a cliff…eesh that’s an intense visual. It’s more like losing the toy you really want in a crane game that will complete a set and you have no more quarters.
So let’s up the ante and in lieu of answering our question about how we can properly insert a node inside of a singly-linked list (the most common of all linked lists), let’s talk about how to flesh out the class we started creating with a suite of methods that will allow us to manage the nodes in our linked-list.
We’re going to want the following capabilities:
- We want to set the head of the linked list
- We want to set the tail of the linked list
- We want to be able to set a new node before a particular node
- We want to be able to set a new node after a particular node
- We want to insert a node at a particular position in the linked-list
- We want to be able to remove a node with a particular value
- We want to know if a node in our linked list has a particular value
- We want to be able to remove a node in general
I know I know….this sounds like a really tall order.
…but guess what? You got me and I’ve got Google and an incredible amount of persistence, grit, moxy, and mojo.
Now there’s a trick to doing this whole thing: we want to find the least common denominator methods that will power the other methods. That’s right, we’re going to make engines out of the methods that will be instrumental to making the other methods go. I like to visualize the strategy we’re going to take to a pyramid.
We’re going to create 8 (technically 9 methods) to help us manage a linked-list in a robust way. These methods will be written INSIDE the class we created called singlyLinkedList, outside of the constructor. Assume that the Node class we wrote out above is within a global scope so we can reference it.
- containsNodeWithValue(value)
With this method we want traverse the linked list to see if there is a node within it whose value matches the given value passed as our argument to the method.
containsNodeWithValue(value) {
let node = this.head
while(node !== null && node.value !== value) {
node = node.next
}
return node !== null
}We create a method called containsNodeWithValue and pass in a single argument representing the value we are seeking within a node in the linked-list.
containsNodeWithValue(value) {...}So we first create a variable called *GASP* node. We make it equal this.head
let node = this.headThen we create a while-loop and have it active so long as node does not equal null AND node.value does not equal the value that is passed in as an argument. So long as these conditions are met, node becomes node.next.
containsNodeWithValue(value) {
let node = this.head while(node !== null && node.value !== value) {
node = node.next
}
}
Next we return a boolean generated by the statement that node DOES NOT equal null. We do this outside of and after the while-loop.
return node !== nullThe way this works is that given the head of a linked list, we traverse the linked-list by making node equal the subsequent node in the linked list (by assigning node to node.next). Eventually one of two things happens:
- We get to a node whose value equals the value that was passed in as the argument
- The node we get to is null (as in, we went beyond the length of the linked list itself because we couldn’t find a node with the value that was passed into the method)
By returning the boolean from saying “node does not equal null”, if we get true it means that the node at present has the value we seek and therefore node can not be null. However, if we get false, then it means the value we were looking for isn’t held in any of the linked-list nodes.
Here it is again:
containsNodeWithValue(value) {
let node = this.head
while(node !== null && node.value !== value) {
node = node.next
}
return node !== null
}Now we’ve taken care of the first part of our pyramid. We have quite a ways to go before we can walk like an Egyptian.
2. removeNode(node) [and 2.5 removeNodeBindings(node)]
This method is good for removing a node you already know of and want to get rid of. It also comes into play later when we create our method to remove nodes that have a particular value. It also makes use of a helper method: removeNodeBindings(node).
First, lets deal with removeNode(node)
remove(node) {
if(node == this.head) {
this.head = this.head.next
}
//after settling issues of dealing with potential head/tail, then we remove the bindings (pointers) of the
//passed-in node argument
this.removeNodeBindings(node)
}First let’s find out if we are dealing with the head of the linked list. If we are, we want to make the head equal whatever node is at head.next
removeNode(node) {
if(node === this.head) {
this.head = this.head.next
}
}Great, we’ve avoided the equivalent of having Marty McFly failing to get his mom and dad together in Back to the Future for our linked list.
Next we pass the node argument of our method to the helper method we’re about to get into called removeNodeBindings. It takes a node as an argument.
removeNodeBindings(node) {
let arrayOfNodes = []
let nodeToDelete = this.head while(nodeToDelete !== null && nodeToDelete!== node) {
arrayOfNodes.push(nodeToDelete)
nodeToDelete = nodeToDelete.next
} arrayOfNodes[arrayOfNodes.length - 1].next = node.next node.next = null
}
First we create a variable of an empty array called arrayOfNodes.
removeNodeBindings(node) {
let arrayOfNodes = []
}Then we make another variable called nodeToDelete equalling this.head.
removeNodeBindings(node) {
let arrayOfNodes = []
let nodeToDelete = this.head
}Next we create a while-loop and have it active so long as nodeToDelete is not null and does not equal the node we are trying to remove. In the while loop, so long as those conditions are met, we push nodeToDelete into the arrayOfNodes array and we make nodeToDelete equal nodeToDelete.next, the next node in the list.
removeNodeBindings(node) {
//update pointer of node before this one
let arrayOfNodes = []let nodeToDelete = this.head
while(nodeToDelete !== null && nodeToDelete!== node) {
arrayOfNodes.push(nodeToDelete)
nodeToDelete = nodeToDelete.next
}
}
Once we break out of this while-loop, we should end up with an array whose last member is the node in the linked list prior to the node we are trying to delete. We then make the last node in the array’s .next equal the .next of the node we are deleting.
arrayOfNodes[arrayOfNodes.length - 1].next = node.nextNow all that’s left is to make the node we are trying to delete have a .next value of null. By doing things in this order we preserve the linked-list attribute of there being pointers to the next node in the list.
node.next = nullOnce again:
removeNodeBindings(node) {
let arrayOfNodes = []
let nodeToDelete = this.headwhile(nodeToDelete !== null && nodeToDelete!== node) {
arrayOfNodes.push(nodeToDelete)
nodeToDelete = nodeToDelete.next
}arrayOfNodes[arrayOfNodes.length - 1].next = node.nextnode.next = null
}
Now let’s review how remove(node) makes use of this helper method we made:
remove(node) {
if(node == this.head) {
this.head = this.head.next
}
this.removeNodeBindings(node)
}3. removeNodesWithValue(value)
removeNodesWithValue(value) {
let node = this.head
while(node !== null) {
let nodeToRemove = node
node = node.next
if(nodeToRemove.value === value) {
this.remove(nodeToRemove)
}
}
}This is a pretty cool method because this is where our pyramid-scheme ;) approach starts to pay off…
First we create a variable called node which we’ll make equal the head.
removeNodesWithValue(value) {
let node = this.head
}Next we create a while-loop that stays active as long as node does not equal null. Inside the block of the while-loop, we say create a temp-variable to hold onto node information for us called nodeToRemove and we make it equal node (the variable we just created before the while-loop). Then we make node equal node.next.
removeNodesWithValue(value) {
let node = this.head while(node !== null) {
let nodeToRemove = node
node = node.next
}
}
Next, still inside the while-loop, we say that if the value of nodeToRemove equals the value which we want to not exist in any of our nodes we’re going to call the remove(node) method we created earlier passing in nodeToRemove as the method’s argument.
removeNodesWithValue(value) {
let node = this.head while(node !== null) {
let nodeToRemove = node
node = node.next if(nodeToRemove.value === value) {
this.remove(nodeToRemove)
}
}
}
4. insertBefore(node, nodeToInsert)
insertBefore(node, nodeToInsert) {
if(nodeToInsert === this.head && nodeToInsert === this.tail) {
return
}
this.remove(nodeToInsert)
nodeToInsert.next = node
let temp = this.head
let arrayOfNodes = [] while(temp !== null && temp !== node) {
arrayOfNodes.push(temp)
temp = temp.next
} if(arrayOfNodes.length === 0) {
this.head = nodeToInsert
} else {
arrayOfNodes[arrayOfNodes.length - 1].next = nodeToInsert
}
}
First we manage an edge case where if the nodeToInsert equals our head and tail. In that case, we return right away and that’s that. There’s nothing that needs doing.
if(nodeToInsert === this.head && nodeToInsert === this.tail) {
return
}Then assuming we don’t want any duplicates, we run the remove(node) method passing in the nodeToInsert argument into it. If that node doesn’t exist in the linked list, then it doesn’t cost the system any effort to run it.
this.remove(nodeToInsert)Next we create a temp variable equalling the head and an empty array called arrayOfNodes.
let temp = this.head
let arrayOfNodes = []Next we create a while-loop that remains active so long as temp does not equal null AND temp does not equal node (which is the node that we want to insert nodeToInsert before). Inside the block of this while-loop, we push temp into arrayOfNodes and then make temp equal temp.next
while(temp !== null && temp !== node) {
arrayOfNodes.push(temp)
temp = temp.next
}Finally we say that if the length of arrayOfNodes is zero, that means there was never a node found in the while-loop whose value was not null. This would mean that the node we’re trying to insert must become the head. If that condition is not the case, then we say that the next of the last element in arrayOfNodes must equal nodeToInsert.
if(arrayOfNodes.length === 0) {
this.head = nodeToInsert
} else {
arrayOfNodes[arrayOfNodes.length - 1].next = nodeToInsert
}5. insertAfter(node, nodeToInsert)
insertAfter(node, nodeToInsert) { if(nodeToInsert === this.head && nodeToInsert === this.tail) {
return
} this.remove(nodeToInsert)
nodeToInsert.next = node.next if(node.next === null) {
this.tail = nodeToInsert
} node.next = nodeToInsert
}
Like with 4 — insertBefore, we do our edge check to see if nodeToInsert equals the head and the tail, in which case we immediately return.
if(nodeToInsert === this.head && nodeToInsert === this.tail) {
return
}Then we use our class’ remove method on nodeToInsert. If the nodeToInsert isn’t already present in our linked-list, then this will be a no-op, so it won’t cost our cpu anything.
this.remove(nodeToInsert)After this, we say that nodeToInsert.next should equal node.next . This makes sense, since we’re rewiring the list so that what comes after node now comes after nodeToInsert instead, since we’re putting nodeToInsert after node.
nodeToInsert.next = node.nextNow we run a little check to see if node.next equals null. If this is the case, then we declare nodeToInsert to be our linked-list’s tail.
if(node.next === null) {
this.tail = nodeToInsert
}Finally, with our list almost entirely re-wired, we say that node.next equals nodeToInsert.
node.next = nodeToInsert6. setHead(node)
setHead(node) {
if(this.head === null) {
this.head = node
this.tail = node
return
} this.insertBefore(this.head, node)
}
Don’t you love the simplicity? Since we’ve already come up with methods in the class to manage all the logistics for us, we get to program declaratively, which means that we issue commands from a more distant, generalized perspective or paradigm . It’s as though we’re in a game of Command & Conquer and you tell the engineers to convert an enemy facility to something you can command. As the commander barking out orders (or in this case, calling methods), you don’t have to concern yourself with what tools the engineer is going to bring, whether they’re going to cut the power first, if they have to fight anyone while sabotaging the place. All you have to say is “this.insertBefore(this.head, node)”, and you’ll be on your way to winning the war.
We’re going to break it down anyways, because why not?
if(this.head === null) {
this.head = node
this.tail = node
return
}Here we say that if the head of the linked-list is null, then (because then there must be no tail either), set the node to be the head and tail, then return.
Should this.head NOT be null, then use the class’ insertBefore method with the node argument being placed before this.head.
this.insertBefore(this.head, node)7. setTail(node)
setTail(node){
if(this.tail === null) {
this.setHead(node)
return
} this.insertAfter(this.tail, node)
}
Again, we get to lean on our past work to get the job done.
We check to see if the linked-list’s tail is null. If it is then we pass the node argument to the setHead method we detailed above. Then we return.
if(this.tail === null) {
this.setHead(node)
return
}If the tail is not null, then we call the insertAfter method passing in this.tail and node.
if(this.tail === null) {
this.setHead(node)
return
}8. insertAtPosition(position, nodeToInsert)
insertAtPosition(position, nodeToInsert) {
if(position == 1) {
this.setHead(nodeToInsert)
return
} let node = this.head
let currentPosition = 1
while(node != null && currentPosition != position) {
node = node.next
currentPosition++
} if(node != null) {
this.insertBefore(node, nodeToInsert)
} else {
this.setTail(nodeToInsert)
}
}
This is the final step in creating our linked-list class. This method allows us to place a node in any non-zero-indexed position in the linked-list.
First we say that if the position argument equals 1, then all we’re really needing to do is set the head. We call this.setHead passing in nodeToInsert and then we return. We’re all done and we can sit on the couch and eat chips.
if(position == 1) {
this.setHead(nodeToInsert)
return
}If this is not the case, then we create two variables to help us fuel a while-loop: node and currentPosition. We set node to equal the head and currentPosition to equal 1.
let node = this.head
let currentPosition = 1Next we create the while-loop the variables above were created for. Essentially, we say that the while loop remains active so long as:
- node does not equal null
- currentPosition does not equal the position argument that was passed in
Inside of the while-loop’s block, we made node equal node.next and we increment currentPosition by 1.
while(node != null && currentPosition != position) {
node = node.next
currentPosition++
}What this does is set up node and currentPosition to be just ahead of the position we want to place nodeToInsert into. And why would we want to do this?
…It’s because we have some values now that we can use with the insertBefore method!
So long as node does not equal null, we call this.insertBefore passing in node and nodeToInsert! And if that’s not the case (i.e. node DOES equal null) we find ourselves in a position where we are simply setting a tail — and do so with this.setTail passing in nodeToInsert as its argument.
if(node != null) {
this.insertBefore(node, nodeToInsert)
} else {
this.setTail(nodeToInsert)
}And THAT is how we get it done.
Sorry for taking so long to getting back to finishing this article. I’ve been inundated with side-projects, interviews, and courses lately. All good things, but they’ve been distractions. I’ll try to be better about being more consistent.
Peace!