Data Structures: Singly Linked Lists
In this blog post we will begin to create a singly linked list. By the end, you should have a basic understanding of what a linked list is, how it is similar and different from an array, and how to begin to add elements to the end of a linked list. In later blogs I will further explore methods for linked lists, like other insertions, removals, and traversal methods. But this will be a general overview and a foundational starting point for linked lists.
A Linked List is like an Array
A linked list is a data structure that stores data, similar to an array in that it is a structure representing a list. In an array, each item is indexed, for example, starting at 0 and going to the length of the array-1. So if the array has 9 objects in it, the first index in the array starts from 0 and the last index ends at 8. A linked list however, consists of elements. There is no index. Meaning the order isn’t determined by an indexed value like the array.
What makes a Linked List
A linked list is made up of elements. Each element is a node. A node has a value and a pointer to another node or null. The values within each node, represents the data (strings, numbers, arrays ect.) in our list, and the pointers within each node determines the order of the linked list; it references the next node or if it’s at the very end, there is no end so it references null. The properties of a linked list are: a head(start), a tail(end) and length (how long the list is). The head element is the first element. It has a value and a pointer to the node of the next item. When using a linked list, we can’t access the fifth item in the list without going through the first four items in the linked list, unlike with an array where we can use array[4] to access the fifth item.
Singly Linked List
A singly linked list is a list of nodes that point to other nodes and only moves in a single direction, from a starting point to an end and not the other way around. A doubly linked list also has a connection pointing back to the previous node. And unlike arrays, there is no random access allowed, meaning that in order to traverse the list to a specific node, we must go through all the previous nodes.
Nodes
A node is a piece of data that contains a value, and a reference to the next node. Let’s create a node. To start we need to create a node class. I go over the JavaScript class syntax in my previous blog post: Understanding Data Structures: Class Syntax in JavaScript, linked here as a refresher.
class Node{
constructor(value){
this.value = value;
this.next = null;
}
}let first = new Node("pikachu")
first.next = new Node("caterpie")
first.next.next = new Node("mankey") // pikachu => caterpie => mankey
If we run first in our terminal after creating the above code, we will see a linked list.
However instead of declaring a node in this way, and using .next over and over again, we will create a LinkedList class that contains a head with the value of null, a tail with the value of null and a length of 0 to start, like so:
class SinglyLinkedList{
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
}Within our Linked List, there are several methods that we can create for inserting, deleting and traversing the linked list. However for this post we will focus just on one of the fundamentals; the push method, which adds a new node to the end of our linked list. Our push method accepts a value and creates a new node from the value passed into the function. If there is no head, we set the head and tail to be the new node. If there is a head, we set the next property of tail to be the new node, and then we set the tail to be the new node. At the end of the function we increment the length of the linked list class by one.
push(value) { //declare the new node with the passed in value
let node = new Node(value) //condition if there is no head
if(!this.head){
this.head = node
this.tail = this.head //set passed in value to be tail.next and set tail to latest value
} else {
this.tail.next = node
this.tail = node
} //increment the length of the list
this.length++
return this
}
To recap in this blog post we have begun to create a linked list. So far we have added the push functionality, below is the full snippet of code for this blog post:
class Node{
constructor(value){
this.value = value;
this.next = null;
}
}class SinglyLinkedList{
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
push(value) {
let node = new Node(value)
if(!this.head){
this.head = node
this.tail = this.head
} else {
this.tail.next = node
this.tail = node
}
this.length++
return this
}
}//Sample
let shoppingList = new SinglyLinkedList()
shoppingList.push("Oat Milk")
shoppingList.push("Tofu")
shoppingList.push("Beans")shoppingList
//Oat Milk => Tofu => Beans
