Intro
Last time, we talked about the theory behind a Singly Linked List.
Today, we start implementing it.
Recap from last time
- real life example: a treasure hunt, where you have a starting point and have to seek places and solve riddles in a particular order; the current place knows about the next place, but the current place doesn't know about the previous place
- consists of nodes
- each node has a value and a pointer to the next node (or null at the end of the list)
- has a head (=start), a tail (=end) and a length
- "singly" because only one connection to another node (the next one)
Setup
So we need two basic entities:
- a single place with a riddle (=> a
node
) - the complete treasure hunt (=> the
Singly Linked List
)
Node
- create a file named
singly-linked-list.js
- add this code
// name of the class
class Node {
// the constructor runs when using the class with `new` (see later)
constructor(value){
// set this nodes value property to the instantiation value
this.value = value;
// set this nodes next property to `null`
this.next = null;
}
}
This is a JavaScript class. Under the hood it uses a function, but it doesn't matter, it's all about the concept. We use this object oriented approach, because it is simple to understand.
We have a class and this class acts as a blueprint for a node.
We can instantiate a new instance of this class and save it into a variable:
const newNode = new Node("Empire State Building");
The string "Empire State Building" becomes the value
in the constructor, so this.value
becomes "Empire State Building"
. this.next
becomes null
.
We can see this by logging it:
console.log(newNode); // Node { value: 'Empire State Building', next: null }
We can now create as many nodes as we need by using new Node()
Singly Linked List
- add this code to
singly-linked-list.js
// name of the class
class SinglyLinkedList {
// the constructor runs when using the class with `new`
constructor() {
// set this lists length property to `0`
this.length = 0;
// set this lists head property to `null`
this.head = null;
// set this lists tail property to `null`
this.tail = null;
}
}
Similar to our Node
. Every instance of the Singly Linked List gets a length
, a head
and a tail
.
We can instantiate a new instance of this class and save it into a variable:
const newSinglyLinkedList = new SinglyLinkedList();
Because all of our three properties are set to default values in the constructor, we don't need arguments.
We can see this by logging it:
console.log(newSinglyLinkedList); // SinglyLinkedList { length: 0, head: null, tail: null }
We can now create our Singly Linked List by using new SinglyLinkedList()
.
Next Part
We will implement how to add a node at the end of the Singly Linked List. If you want to be notified, subscribe :)
Questions
- Did you ever use a Singly Linked List in a project? Why?
- Did you ever use classes in JavaScript?
Top comments (3)
Great questions, Amir.
Use cases with benefits are:
O(1)
vs. Array: best caseO(1)
(at the end) - worst caseO(N)
(at the start)But in the end, you're very unlikely to see a Singly Linked List.
Thanks buddy
You're welcome.