Dissecting Linked Lists
In order to understand this data structure, I believe we need to break it apart. Since that is how I, personally learn the best. Just taking things apart and building them from the ground up! I decided to break it up into three different sections to better understand it, the Node, Linked List, and a section where we will put it together!
Node
What is a node?
We can compare a node to an atom, they are the building block for some data structures. A node is a basic unit of a data structure, they contain information that also may link to other nodes, links between nodes are often implemented by pointers. They are usually present in linked lists and trees, it is possible to traverse from one node to another using these pointers.
We can take a look at how it can be built in Javascript:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}Once a node’s link is null it usually means we have come to the end of the path we were traversing.
Another thing to note, nodes can be “orphaned,” which means there are no existing links to them.
In the image above, Node_B is now an orphaned node, the link between Node_A has been changed from Node_B to Node_C. It now exists, but nothing is linked to it, Orphaned nodes can be reassigned or completely removed.
Linked List
What is a linked list?
A linked list is a linear data structure where the elements are not stored in a contiguous location, meaning elements are not next to each other or touching. Rather, the elements are linked by using pointers. We can also view linked lists similar to nodes where they are used as the foundations for other data structures. They are also an alternative to arrays if we are trying to store information in a linear way. There are similarities, but there are also vast differences between the two. (I won’t discuss that now as that isn’t the purpose of this write-up!)
Linked lists have their data stored in nodes and each node is linked to the next, this is what is called a Singly Linked List, but they can also link to the previous node, which is called a Doubly Linked List. For now, we will focus on Singly Linked List.
Each node in a linked list consists of the following:
- Data
- Pointer to the next node
- (Doubly Linked List): Pointer to the previous node
The anatomy of a linked list consists of the following:
- A head node serves as the first node in the list, if the linked list is empty, the value of the head node is
null. This is where we usually start the list and traverse. - Nodes in between
- A tail node, which is the last node in the list. How we usually tell it is the tail node is due to the fact the pointer is always pointing or linking to a
nullvalue, this indicates the end of the list.
Putting it together
Let us put it together!
Start with the Node:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
setNextNode(node) {
if (node instanceof Node || node === null) {
this.next = node;
} else {
throw new Error('Next node must be a member of the Node class.');
}
}
getNextNode() {
return this.next;
}
}In this code snippet, we set up our node with two different methods, these two methods are set up in a way to allow us to traverse through nodes later on!
Let us now construct our linked list! We will start by creating the constructor and adding to head method. As a refresher, a node consists of the information/data and a link to the next node.
We will utilize the Node class that we created and the methods inside of it as well!
class LinkedList {
constructor(){
this.head = null
}
addToHead(data){
const newHead = new Node(data)
const currentHead = this.head
this.head = newHeadif(currentHead){
this.head.setNextNode(currentHead)
}
}
}
Next up, since we created adding to the head of the linked list, let us create a method that will add to the tail.
We need to create a temporary tail variable that we will set equal to the list’s head. If there is no head, then that would mean the list is empty and we need to use our addToHeadmethod instead. If there is a head, then we will iterate through the list until we find the last node, once it is found, we will add a pointer from that node to our new tail!
class LinkedList {
constructor(){
this.head = null
}addToHead(data){
const newHead = new Node(data)
const currentHead = this.head
this.head = newHeadif(currentHead){
this.head.setNextNode(currentHead)
}
}addToTail(data) {
let tail = this.head;
if (!tail) {
this.head = new Node(data);
} else {
while (tail.getNextNode() !== null) {
tail = tail.getNextNode();
}
tail.setNextNode(new Node(data));
}
}}
Now we have methods set up to add to the head and tail of the linked list, we need a method that will allow us to remove it from the head. We need to check if the list has a head first, if it does not, then there is nothing to return. Though if there is, we need to remove it by setting the head equal to the original head’s next node, then return the original head.
class LinkedList {
constructor(){
this.head = null
}addToHead(data){
const newHead = new Node(data)
const currentHead = this.head
this.head = newHeadif(currentHead){
this.head.setNextNode(currentHead)
}
}addToTail(data) {
let tail = this.head;
if (!tail) {
this.head = new Node(data);
} else {
while (tail.getNextNode() !== null) {
tail = tail.getNextNode();
}
tail.setNextNode(new Node(data));
}
} removeHead() {
const removedHead = this.head;
if (!removedHead) {
return;
}
this.head = removedHead.getNextNode();
return removedHead.data;
}}
Here comes the magic!
We will add a method that will allow us to log our list.
We need to create a variable equal to a string that will hold the data from every node in the list. To start, we will traverse from the list’s head and iterate the list and we will add to our string variable.
class LinkedList {
constructor(){
this.head = null
}addToHead(data){
const newHead = new Node(data)
const currentHead = this.head
this.head = newHeadif(currentHead){
this.head.setNextNode(currentHead)
}
}addToTail(data) {
let tail = this.head;
if (!tail) {
this.head = new Node(data);
} else {
while (tail.getNextNode() !== null) {
tail = tail.getNextNode();
}
tail.setNextNode(new Node(data));
}
} removeHead() {
const removedHead = this.head;
if (!removedHead) {
return;
}
this.head = removedHead.getNextNode();
return removedHead.data;
}showList() {
let currentNode = this.head;
let output = '[HEAD NODE] ';
while (currentNode !== null) {
output += currentNode.data + ' ';
currentNode = currentNode.getNextNode();
}
output += '[TAIL NODE]';
console.log(output);
}}
Now that we have all of that written… let us try to make our own linked list!
In my example, we will make the days of the week as it is only fitting for a pre-school teacher.
const weekdays = new LinkedList()Now let us use the methods we created.
We also need to use our showList method to view how our list looks like. Can you guess what it would look like?
const weekdays = new LinkedList()weekdays.addToTail("Saturday")
weekdays.addToTail("Sunday")
weekdays.addToHead("Friday")
weekdays.addToHead("Thursday")
weekdays.addToHead("Wednesday")
weekdays.addToHead("Tuesday")
weekdays.addToHead("Monday")
weekdays.addToHead("Hello!")weekdays.showList()
Uh oh! “Hello!” does not belong in the linked list, it is not part of our days of the week!
Good thing we created a method that would help us remove just that node.
const weekdays = new LinkedList()weekdays.addToTail("Saturday")
weekdays.addToTail("Sunday")
weekdays.addToHead("Friday")
weekdays.addToHead("Thursday")
weekdays.addToHead("Wednesday")
weekdays.addToHead("Tuesday")
weekdays.addToHead("Monday")
weekdays.addToHead("Hello!")weekdays.showList()weekdays.removeHead()
weekdays.showList()
Now I wonder, did that fix our problem?
Yup, that fixed it!
Now if you are curious like I am, let us check out what our weekdayswill show us if we were to console.logit
console.log('what does weekdays look like?', weekdays)
Thank you for taking the time in joining me in learning about Linked Lists!
Please reach out if I missed anything or misunderstood something!
