Table of contents
- Introduction
- Key Features of a Linked List:
- Follow the next steps sequentially to implement a linked list:
- STEP 1: Create a Node Class
- STEP 2: Create a Linked List Class
- STEP 3: A Prepend Method For Adding To A LinkedList
- STEP 4: Append Method For Adding To The End of A LinkedList
- STEP 5: Remove Method For Removing A Node From A LinkedList
- STEP 6: Search Method In A LinkedList
- STEP 8: Inserting in a Linked List
- STEP 8: Reversing a Linked List
- STEP 9: Linked List with a Tail
- STEP 10: Doubly Linked List
- CONCLUSION:
Introduction
A linked list is a foundational data structure that can be used to implement other data structures like a queue and a stack. All three data structures are linear, meaning their elements are arranged sequentially, with a next and/or previous element attached to them.
Key Features of a Linked List:
Node Structure: A linked list is a series of connected nodes, where each node contains a:
Value: the data or information stored in the node; and a
Pointer: a reference to the next node in the sequence
Memory Layout: A linked list stores elements in incontiguous memory spaces, using pointers to maintain the sequence.
While an array stores its elements in a contiguous (non-breaking) memory layout, a linked list instead stores its elements in an incontiguous memory space, that is, elements are scattered in memory, while maintaining a reference to each element with additional memory spaces.
In a contiguous memory space, such as an array, elements are stored sequentially, making it possible to access them directly by index. But with an incontiguous data structure, elements are not located next to one another, they can be placed anywhere in the memory where there is space.
Building a linked list prioritizes speed for insertion and deletion at the cost of additional memory for pointers. In contrast, an array optimizes memory usage but incurs higher costs for these operations.
The mode of memory allocation impacts the time complexity for different operations. A linked list is more efficient for insertion/deletion, which is costly in an array. However, for search operations, an array is more efficient if the index is known. Linked lists are dynamic, flexible structures that excel where frequent insertions and deletions are needed. Arrays are more memory-efficient but better suited for scenarios requiring fast random access.
Now that we understand the concept and advantages of linked lists, let's move on to implementing one step by step. We'll start by creating a node, which is the building block of a linked list. Then, we’ll implement the linked list that will contain the nodes, along with methods to update it – adding, removing or searching for a node in it.
Follow the next steps sequentially to implement a linked list:
STEP 1: Create a Node Class
Creating a class from which we can instantiate each node
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
You can create an instance of the Node class like this:
const node_instance = new Node(54)
If you print out the node_instance with console.log(node_instance), you will get:
Node {value: 54, next: null}
STEP 2: Create a Linked List Class
Since we have the building block for our linked list, which is the node class, the next step is to create the linked list that will contain all of the nodes.
//Node Class
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
//Linked List Class
class LinkedList{
constructor(){
this.head = null
this.size = 0
}
getSize(){
return this.size
}
isEmpty(){
return this.size === 0 // returns true or false if the list is empty, which is when the size of the list is 0
}
}
In a linked list, the first node is called the head, and it is an important element for different operations. The size property, together with its methods, getSize and isEmpty, is to manually calculate how many nodes are in the list when we add or delete a node. So in every new instance of the list, the head and size properties are initialized, although empty.
Create a new instance of the node list class like this:
const linkedListInstance = new LinkedList
You can print it out with console.log(linkedList) to see what it currently looks like:
LinkedList {head: null, size: 0}
We can check for the size of the node and whether or not it is empty by running the following command:
console.log(linkedListInstance.isEmpty())
console.log(linkedListInstance.getSize())
Now we can start implementing basic operations on our list. We will implement a prepend, append, delete, search, insert, methods on the LinkedList class.
STEP 3: A Prepend Method For Adding To A LinkedList
Understanding the concept and nature of a linked list as a data structure is pivotal to thinking through the necessary operations that can be performed on a linked list.
Prepending has a time complexity of O(1).
//PREPENDING A NODE TO A LINKED LIST**
//To prepend a node, we would need to:
prepend(value){
// 1. get a node instance of the value to be added
const node = new Node(value)
// 2. add it to the list. Remember we need to maintain a pointer to the head, which is the first node. In prepending, we are adding the node to the beginning of the list, so we would need to keep updating the head whenever we prepend a node. We also need to consider whether or not the list is empty. If it is empty, we only need to update the head node, and increase the size. If not, we need to update the next property of the new node such that it points to the previous node, which is the current head, then update the head to point to the newly added node.
if(this.isEmpty()){
this.head = node
}else{
//update the current's node next, such that it points to the head in an existing linked list
node.next = this.head
//then update the pointer to the head to point to the new node, such that the latest node becomes the head node
this.head = node
//the order of this operation is very important given that the head is the only entry point or reference we have to the list so if we update the head without having a reference to its content, we would lose the entire list.
}
// 3. increase the size count of the linked list in any case of an empty or otherwise list
this.size++
}
At this point, our code looks like this, without the comments:
//Node Class
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
//Linked List Class
class LinkedList{
constructor(){
this.head = null
this.size = 0
}
getSize(){
return this.size
}
isEmpty(){
return this.size === 0
}
//PREPENDING A NODE TO A LINKED LIST
prepend(value){
const node = new Node(value)
if(this.isEmpty()){
this.head= node
}else{
node.next = this.head
this.head = node
}
this.size++
}
}
To visualize our linked list values cleanly, we will implement a print() function so we can see the values of each node.
Print Method:
//Node Class
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
//Linked List Class
class LinkedList{
constructor(){
this.head = null
this.size = 0
}
getSize(){
return this.size
}
isEmpty(){
return this.size === 0
}
//PREPENDING A NODE TO A LINKED LIST
prepend(value){
const node = new Node(value)
if(this.isEmpty()){
this.head= node
}else{
node.next = this.head
this.head = node
}
this.size++
}
**//PRINTING A NODE TO A LINKED LIST**
//To view the values of the list, we would have to iterate over each node to print out its value.
print() {
//An early return to guard against an empty list
if (this.isEmpty()) {
alert('Nothing to print, the list is empty')
return ('Nothing to print, the list is empty')
}
//Where the list is not empty
let current = this.head // getting a reference to the head node from which we can reach other nodes exisitng in the .next property.
// We're checking to see that the current's item next is not null, where it is null, it means that current item is the last item on the list.
while (current !== null) {
//if the current item is not null, we print it's value, and update the current item to the next node for the iteration to continue, or stop where the list is empty
console.log(current.value)
current = current.next
}
}
}
Now we can check to see that our prepend and print methods are working as expected:
//Node Class
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
//Linked List Class
class LinkedList{
constructor(){
this.head = null
this.size = 0
}
getSize(){
return this.size
}
isEmpty(){
return this.size === 0
}
**//PREPENDING A NODE TO A LINKED LIST**
prepend(value){
const node = new Node(value)
if(this.isEmpty()){
this.head= node
}else{
node.next = this.head
this.head = node
}
this.size++
}
**//PREPENDING A NODE TO A LINKED LIST**
print() {
if (this.isEmpty()) {
alert('Nothing to print, the list is empty')
return ('Nothing to print, the list is empty')
}
let current = this.head
while (current !== null) {
console.log(current.value)
current = current.next
}
}
}
//Tests:
const linkedListInstance = new LinkedList
console.log(linkedListInstance.print()) // Returns 'Nothing to print, the list is empty'
linkedListInstance.prepend(40)
linkedListInstance.prepend(50)
linkedListInstance.prepend(30)
console.log(linkedListInstance.print())
// Returns
// 30
// 50
// 40
STEP 4: Append Method For Adding To The End of A LinkedList
With prepending, we add to the beginning of the list, but in appending, we add to the end of the list. As you can imagine, we need to traverse the entire list until we get to the end, which is when the node is pointing to null, and then we add the node.
Appending has a time complexity of O(n) in a singly linked list, but O(1) in a doubly linked list.
Like we did with the head pointer, we would have updated a tail pointer if we maintained a pointer to the tail node, which is the last node. More on the tail node below.
// APPENDING A NODE TO A LINKED LIST**
//To append a node, we would need to:
append(value) {
// 1. create a node instance with the given value
const node = new Node(value)
// 2. get a reference to the list's head
let current = this.head
// 3. Add the node to the list. But to do this, we need to consider the edge case of an empty list or otherwise:
if (this.isEmpty()) {
// 3a. where the list is empty, update the head with the node
this.head = node
} else {
// 3.b otherwise, loop through until you get to the last item
while (current.next !== null) {
//keep updating the current with it's next, where the next is not null
current = current.next
}
// where the next node becomes null, update the last node's next from null to the new node
current.next = node // this will run when the code exits the while block, meaning it has now hit a null value, then we update the current item's next from null to the new node.
}
this.size++ //increase the size of the list where a new node was added to an empty or otherwise list
}
Now we can check to see if our append method is working as expected:
//Node Class
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
//Linked List Class
class LinkedList{
constructor(){
this.head = null
this.size = 0
}
getSize(){
return this.size
}
isEmpty(){
return this.size === 0
}
//PREPENDING A NODE TO A LINKED LIST
prepend(value){
const node = new Node(value)
if(this.isEmpty()){
this.head= node
}else{
node.next = this.head
this.head = node
}
this.size++
}
// APPENDING A NODE TO A LINKED LIST
append(value) {
const node = new Node(value)
let current = this.head
if (this.isEmpty()) {
this.head = node
} else {
while (current.next !== null) {
current = current.next
}
current.next = node
}
this.size++
}
// PRINTING THE VALUES OF THE LINKED LIST
print() {
if (this.isEmpty()) {
alert('Nothing to print, the list is empty')
return ('Nothing to print, the list is empty')
}
let current = this.head
while (current !== null) {
console.log(current.value)
current = current.next
}
}
}
//Tests:
const linkedListInstance = new LinkedList
console.log(linkedListInstance.print()) // Returns 'Nothing to print, the list is empty'
linkedListInstance.append(40)
linkedListInstance.append(50)
linkedListInstance.append(30)
console.log(linkedListInstance.print())
// Returns
// 40
// 50
// 30
STEP 5: Remove Method For Removing A Node From A LinkedList
We can remove a node from a linked list either by it’s value, that is checking each node in the list until the first node containing a value that matches the list, or by its index, that is imitating the indexing system of an array to index each node.
Removing has a time complexity of O(n).
Here is a brief illustration of what removing a node looks like in a linked list:
We will implement both methods of removing a node from a linked list:
- Removing by index
// Delete Method For Removing A Node From A LinkedList By Value
//To delete a node, we would need to:
removeByValue(value) {
// 1. check against the list is empty
if (this.isEmpty()) {
return 'Cannot remove from an empty list'
}
let removedNode;
// 2. Specifically check if the value to be removed matches the value in the head node so we can handle the head pointer
if (value === this.head.value) {
removedNode = this.head
this.head = this.head.next
// the order of the operation really matters. Can you think through the possible error where the steps are swapped?
} else {
let current = this.head; // use this to begin interation
let previous = null; // this will be the node before the particular node we want to remove
while (value !== current.value) {
// while value does not yet match any node, we keep advancing through the list
previous = current
current = current.next
if (current === null) { // this 'if' statement is necessary where we have gone over the list wihout finding the value, and the current is now pointing at null
return 'Value not found in the list'
}
}
// this lines below will run when the while loop is exited, that is when the value === current.value
removedNode = current // use this to save a reference to the node to be removed
previous.next = removedNode.next // use this to update the pointer of the node before the node to be removed from pointing to the node to be removed to point to the next node after the node to be removed.
}
this.size-- // to keep our linked list's size in sync
return removedNode
}
Removing by value
// Delete Method For Removing A Node From A LinkedList By Value**
//To delete a node, we would need to:
removeByValue(value) {
// 1. check against the list is empty
if (this.isEmpty()) {
return 'Cannot remove from an empty list'
}
let removedNode;
// 2. Specifically check if the value to be removed matches the value in the head node so we can handle the head pointer
if (value === this.head.value) {
removedNode = this.head
this.head = this.head.next
// the order of the operation really matters. Can you think through the possible error where the steps are swapped?
} else {
let current = this.head; // use this to begin interation
let previous = null; // this will be the node before the particular node we want to remove
while (value !== current.value) {
// while value does not yet match any node, we keep advancing through the list
previous = current
current = current.next
if (current === null) { // this 'if' statement is necessary where we have gone over the list wihout finding the value, and the current is now pointing at null
return 'Value not found in the list'
}
}
// this lines below will run when the while loop is exited, that is when the value === current.value
removedNode = current // use this to save a reference to the node to be removed
previous.next = removedNode.next // use this to update the pointer of the node before the node to be removed from pointing to the node to be removed to point to the next node after the node to be removed.
}
this.size-- // to keep our linked list's size in sync
return removedNode
}
Now we can check to see if our delete methods are working as expected:
//Node Class
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
//Linked List Class
class LinkedList{
constructor(){
this.head = null
this.size = 0
}
getSize(){
return this.size
}
isEmpty(){
return this.size === 0
}
//PREPENDING A NODE TO A LINKED LIST
prepend(value){
const node = new Node(value)
if(this.isEmpty()){
this.head= node
}else{
node.next = this.head
this.head = node
}
this.size++
}
// APPENDING A NODE TO A LINKED LIST
append(value) {
const node = new Node(value)
let current = this.head
if (this.isEmpty()) {
this.head = node
} else {
while (current.next !== null) {
current = current.next
}
current.next = node
}
this.size++
}
**// Delete Method For Removing A Node From A LinkedList by Index**
removeByIndex(index) {
if (index < 0 || index >= this.size) {
return 'Invalid index provided'
}
let removedNode;
if (index === 0) {
removedNode = this.head
this.head = this.head.next
} else {
let counter = 0;
let current = this.head;
let previous = null;
while (counter < index) {
previous = current
current = current.next
counter++
}
removedNode = current
previous.next = removedNode.next
}
this.size--
return removedNode
}
**// Delete Method For Removing A Node From A LinkedList By Valu**
removeByValue(value) {
if (this.isEmpty()) {
return 'Cannot remove from an empty list'
}
let removedNode;
if (value === this.head.value) {
removedNode = this.head
this.head = this.head.next
} else {
let current = this.head;
let previous = null;
while (value !== current.value) {
previous = current
current = current.next
if (current === null) {
return 'Value not found in the list'
}
}
removedNode = current
previous.next = removedNode.next
}
this.size--
return removedNode
}
// PRINTING THE VALUES OF THE LINKED LIST
print() {
if (this.isEmpty()) {
alert('Nothing to print, the list is empty')
return ('Nothing to print, the list is empty')
}
let current = this.head
while (current !== null) {
console.log(current.value)
current = current.next
}
}
}
//Tests:
const linkedListInstance = new LinkedList
console.log(linkedListInstance.print()) // Returns 'Nothing to print, the list is empty'
linkedListInstance.prepend(40)
linkedListInstance.prepend(90)
linkedListInstance.prepend(30)
linkedListInstance.prepend(50)
console.log(linkedListInstance.print())
// Returns
// 50
// 30
// 90
// 40
console.log(linkedListInstance.removeByValue(30))
console.log(linkedListInstance.removeByValue(2)) // Returns: Value not found in the list
console.log(linkedListInstance.removeByIndex(0))
console.log(linkedListInstance.print())
// Returns
// 90
// 40
STEP 6: Search Method In A LinkedList
We can search for a node within a linked list by its value, by iterating over each node until the first node that matches the provided value.
Searching has a time complexity of O(n).
// SEARCHING FOR A NODE IN A LINKED LIST**
//To search for a node, we need to:
searchByValue(value) {
// 1. Check against an empty list
if (this.isEmpty()) {
return 'Can not search athrough an empty list'
}
let current = this.head;
let index = 0;
// 2. Iterate through the list while the value does not match the value of the current node
while (current.value !== value) {
current = current.next
index++
// 3. Check against a null value, which indicates the end of the list, implying the value was not found
if (current.next === null) {
return 'Cannot find value in the list'
}
}
return index;
}
Now we can check to see if our search method is working as expected:
//Node Class
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
//Linked List Class
class LinkedList{
constructor(){
this.head = null
this.size = 0
}
getSize(){
return this.size
}
isEmpty(){
return this.size === 0
}
//PREPENDING A NODE TO A LINKED LIST
prepend(value){
const node = new Node(value)
if(this.isEmpty()){
this.head= node
}else{
node.next = this.head
this.head = node
}
this.size++
}
// APPENDING A NODE TO A LINKED LIST
append(value) {
const node = new Node(value)
let current = this.head
if (this.isEmpty()) {
this.head = node
} else {
while (current.next !== null) {
current = current.next
}
current.next = node
}
this.size++
}
// Delete Method For Removing A Node From A LinkedList by Index
removeByIndex(index) {
if (index < 0 || index >= this.size) {
return 'Invalid index provided'
}
let removedNode;
if (index === 0) {
removedNode = this.head
this.head = this.head.next
} else {
let counter = 0;
let current = this.head;
let previous = null;
while (counter < index) {
previous = current
current = current.next
counter++
}
removedNode = current
previous.next = removedNode.next
}
this.size--
return removedNode
}
// Delete Method For Removing A Node From A LinkedList By Value
removeByValue(value) {
if (this.isEmpty()) {
return 'Cannot remove from an empty list'
}
let removedNode;
if (value === this.head.value) {
removedNode = this.head
this.head = this.head.next
} else {
let current = this.head;
let previous = null;
while (value !== current.value) {
previous = current
current = current.next
if (current === null) {
return 'Value not found in the list'
}
}
removedNode = current
previous.next = removedNode.next
}
this.size--
return removedNode
}
// Search Method
searchByValue(value) {
if (this.isEmpty()) {
return 'Can not search athrough an empty list'
}
let current = this.head
let index = 0
while (current.value !== value) {
current = current.next
index++
if (current.next === null) {
return 'Cannot find value in the list'
}
}
return index
}
// PRINTING THE VALUES OF THE LINKED LIST
print() {
if (this.isEmpty()) {
alert('Nothing to print, the list is empty')
return ('Nothing to print, the list is empty')
}
let current = this.head
while (current !== null) {
console.log(current.value)
current = current.next
}
}
}
//Tests:
const linkedListInstance = new LinkedList
console.log(linkedListInstance.print()) // Returns 'Nothing to print, the list is empty'
linkedListInstance.prepend(40)
linkedListInstance.prepend(90)
linkedListInstance.prepend(30)
linkedListInstance.prepend(50)
console.log(linkedListInstance.print())
// Returns
// 50
// 30
// 90
// 40
console.log(linkedListInstance.searchByValue(0))
// Returns:
// Cannot find value in the list
console.log(linkedListInstance.searchByValue(90))
// Returns:
// 2
STEP 8: Inserting in a Linked List
Inserting a node into a linked list follows similar patterns of iterating over the list until we reach the index to insert the new node.
Inserting has a time complexity of O(n).
Here is a brief illustration of what inserting looks like in a linked list:
// INSERTING A NODE IN A LINKED LIST
//To insert a node, we need to:
insert(value, index) {
// 1. Check against invalid index and values
if (index < 0 || index > this.size || index === undefined || value == undefined) {
return 'Invalid index/value provided'
}
// 2. Iterate over the list and insert at the right index
if (index === 0) {
this.prepend(value) // where the index is 0, we're basically prepending
} else {
const node = new Node(value) // making a node from the value supplied
let current = this.head
let counter = 0 // to keep track of the index iterated over in the linked list
while (counter !== index) { // advancing through the list where we have not gotten to the required index
current = current.next
counter++
}
node.next = current.next // Updating the new node's next
current.next = node // Updating node before the new node, such that it's next points to the new node
this.size++
}
return 'Node inserted successfully !'
}
Now we can check to see if our insert method is working as expected:
//Node Class
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
//Linked List Class
class LinkedList{
constructor(){
this.head = null
this.size = 0
}
getSize(){
return this.size
}
isEmpty(){
return this.size === 0
}
//PREPENDING A NODE TO A LINKED LIST
prepend(value){
const node = new Node(value)
if(this.isEmpty()){
this.head= node
}else{
node.next = this.head
this.head = node
}
this.size++
}
// APPENDING A NODE TO A LINKED LIST
append(value) {
const node = new Node(value)
let current = this.head
if (this.isEmpty()) {
this.head = node
} else {
while (current.next !== null) {
current = current.next
}
current.next = node
}
this.size++
}
// Delete Method For Removing A Node From A LinkedList by Index
removeByIndex(index) {
if (index < 0 || index >= this.size) {
return 'Invalid index provided'
}
let removedNode;
if (index === 0) {
removedNode = this.head
this.head = this.head.next
} else {
let counter = 0;
let current = this.head;
let previous = null;
while (counter < index) {
previous = current
current = current.next
counter++
}
removedNode = current
previous.next = removedNode.next
}
this.size--
return removedNode
}
// Delete Method For Removing A Node From A LinkedList By Value
removeByValue(value) {
if (this.isEmpty()) {
return 'Cannot remove from an empty list'
}
let removedNode;
if (value === this.head.value) {
removedNode = this.head
this.head = this.head.next
} else {
let current = this.head;
let previous = null;
while (value !== current.value) {
previous = current
current = current.next
if (current === null) {
return 'Value not found in the list'
}
}
removedNode = current
previous.next = removedNode.next
}
this.size--
return removedNode
}
// Search Method
searchByValue(value) {
if (this.isEmpty()) {
return 'Can not search athrough an empty list'
}
let current = this.head
let index = 0
while (current.value !== value) {
current = current.next
index++
if (current.next === null) {
return 'Cannot find value in the list'
}
}
return index
}
insert(value, index) {
if (index < 0 || index > this.size || index === undefined || value == undefined) {
return 'Invalid index/value provided'
}
if (index === 0) {
this.prepend(value)
} else {
const node = new Node(value)
let current = this.head
let counter = 0 list
while (counter !== index) {
current = current.next
counter++
}
node.next = current.next
current.next = node
this.size++
}
return 'Node inserted successfully !'
}
// PRINTING THE VALUES OF THE LINKED LIST
print() {
if (this.isEmpty()) {
alert('Nothing to print, the list is empty')
return ('Nothing to print, the list is empty')
}
let current = this.head
while (current !== null) {
console.log(current.value)
current = current.next
}
}
}
//Tests:
const linkedListInstance = new LinkedList
console.log(linkedListInstance.print()) // Returns 'Nothing to print, the list is empty'
linkedListInstance.prepend(30)
linkedListInstance.prepend(50)
console.log(linkedListInstance.print())
// Returns
// 50
// 30
console.log(linkedListInstance.insert(20, 1))
// Returns
// Node inserted successfully !
console.log(linkedListInstance.print())
// Returns
// 50
// 20
// 30
console.log(linkedListInstance.insert())
// Returns
// Invalid index/value provided
STEP 8: Reversing a Linked List
To reverse a linked list, we want to flip it such that each node’s next points to its previous node. It involves 5 steps:
Update the next variable with the current node’s next
Set the current node’s next to it’s previous
Update the previous to the current node
Update the current node to the next variable
Update the head to point to the last node reversed, which is now the first node
Reversing has a time complexity of O(n).
// REVERSING A LINKED LIST
reverse() {
let current = this.head
let prev = null
while (current) {
let next = current.next
current.next = prev
prev = current
current = next
}
this.head = prev
}
Now we can check to see if our reverse method is working as expected:
//Node Class
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
//Linked List Class
class LinkedList{
constructor(){
this.head = null
this.size = 0
}
getSize(){
return this.size
}
isEmpty(){
return this.size === 0
}
//PREPENDING A NODE TO A LINKED LIST
prepend(value){
const node = new Node(value)
if(this.isEmpty()){
this.head= node
}else{
node.next = this.head
this.head = node
}
this.size++
}
// APPENDING A NODE TO A LINKED LIST
append(value) {
const node = new Node(value)
let current = this.head
if (this.isEmpty()) {
this.head = node
} else {
while (current.next !== null) {
current = current.next
}
current.next = node
}
this.size++
}
// Delete Method For Removing A Node From A LinkedList by Index
removeByIndex(index) {
if (index < 0 || index >= this.size) {
return 'Invalid index provided'
}
let removedNode;
if (index === 0) {
removedNode = this.head
this.head = this.head.next
} else {
let counter = 0;
let current = this.head;
let previous = null;
while (counter < index) {
previous = current
current = current.next
counter++
}
removedNode = current
previous.next = removedNode.next
}
this.size--
return removedNode
}
// Delete Method For Removing A Node From A LinkedList By Value
removeByValue(value) {
if (this.isEmpty()) {
return 'Cannot remove from an empty list'
}
let removedNode;
if (value === this.head.value) {
removedNode = this.head
this.head = this.head.next
} else {
let current = this.head;
let previous = null;
while (value !== current.value) {
previous = current
current = current.next
if (current === null) {
return 'Value not found in the list'
}
}
removedNode = current
previous.next = removedNode.next
}
this.size--
return removedNode
}
// Search Method
searchByValue(value) {
if (this.isEmpty()) {
return 'Can not search athrough an empty list'
}
let current = this.head
let index = 0
while (current.value !== value) {
current = current.next
index++
if (current.next === null) {
return 'Cannot find value in the list'
}
}
return index
}
// Inserting into a Linked List
insert(value, index) {
if (index < 0 || index > this.size || index === undefined || value == undefined) {
return 'Invalid index/value provided'
}
if (index === 0) {
this.prepend(value)
} else {
const node = new Node(value)
let current = this.head
let counter = 0 list
while (counter !== index) {
current = current.next
counter++
}
node.next = current.next
current.next = node
this.size++
}
return 'Node inserted successfully !'
}
// REVERSING A LINKED LIST
reverse() {
let current = this.head
let prev = null
while (current) {
let next = current.next
current.next = prev
prev = current
current = next
}
this.head = prev
}
// PRINTING THE VALUES OF THE LINKED LIST
print() {
if (this.isEmpty()) {
alert('Nothing to print, the list is empty')
return ('Nothing to print, the list is empty')
}
let current = this.head
while (current !== null) {
console.log(current.value)
current = current.next
}
}
}
//Tests:
const linkedListInstance = new LinkedList
console.log(linkedListInstance.print()) // Returns 'Nothing to print, the list is empty'
linkedListInstance.prepend(30)
linkedListInstance.prepend(50)
console.log(linkedListInstance.print())
// Returns
// 50
// 30
console.log(linkedListInstance.insert(20, 1))
// Returns
// Node inserted successfully !
console.log(linkedListInstance.print())
// Returns
// 50
// 20
// 30
console.log(linkedListInstance.reverse())
// Returns
// 30
// 20
// 50
STEP 9: Linked List with a Tail
In the same way we maintained a pointer to the head of the list, we can keep a pointer to the last node, which may reduce the time complexity of particular operations. For example, while for other operations like searching, having a pointer to the tail node might not make a difference, in appending a node to a list, having a pointer to the tail node will save us the operation of traversing the entire list to get to the last node, thereby making it a constant time operation — O(1).
Here’s an implementation of a linked list with a pointer to the tail node including operations where having a pointer to the tail will count:
//Node Class
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
//Linked List Class
class LinkedList{
constructor(){
this.head = null
this.tail = null
this.size = 0
}
getSize(){
return this.size
}
isEmpty(){
return this.size === 0
}
//PREPENDING A NODE TO A LINKED LIST
prepend(value){
const node = new Node(value)
if(this.isEmpty()){
this.head = node
this.tail =node
}else{
node.next = this.head
this.head = node
}
this.size++
}
// APPENDING A NODE TO A LINKED LIST
append(value) {
const node = new Node(value)
let current = this.head
if (this.isEmpty()) {
this.head = node
this.tail = node
} else {
this.tail.next = node
this.tail = node
}
this.size++
}
removeFromBeginning(){
if(this.isEmpty()){
return 'An Empty List'
}
const nodeToRemove = this.head
this.head = this.head.next
this.size--
return nodeToRemove
}
removeFromEnd(){
if(this.isEmpty()){
return 'An Empty List'
}
let nodeToRemove = this.tail
if(this.size === 1){
this.head = null
this.tail = null
}else{
let prev = this.head
while(prev.next !== this.tail){
prev = prev.next
}
prev.next = null
this.tail = prev
}
this.size--
return nodeToRemove
}
// PRINTING THE VALUES OF THE LINKED LIST
print() {
if (this.isEmpty()) {
alert('Nothing to print, the list is empty')
return ('Nothing to print, the list is empty')
}
let current = this.head
while (current !== null) {
console.log(current.value)
current = current.next
}
}
}
STEP 10: Doubly Linked List
Where nodes in a singly linked list only maintain a pointer to the next node in the list, in a doubly linked list, a node maintains a pointer to its next and previous nodes in the list.
Below is an implementation of the linked list with a pointer to the previous node:
//Node Class
class Node {
constructor(value) {
this.value = value
this.next = null
this.previous = null
}
}
//Linked List Class
class LinkedList{
constructor(){
this.head = null
this.size = 0
}
getSize(){
return this.size
}
isEmpty(){
return this.size === 0
}
//PREPENDING A NODE TO A LINKED LIST
prepend(value){
const node = new Node(value)
if(this.isEmpty()){
this.head = node
this.tail = node
}else{
node.next = this.head
this.head = node
}
this.size++
}
// APPENDING A NODE TO A LINKED LIST
append(value) {
const node = new Node(value)
let current = this.head
if (this.isEmpty()) {
this.head = node
this.tail = node
} else {
this.tail.next = node
node.previous = this.tail
this.tail = node
}
this.size++
}
removeFromBeginning(){
if(this.isEmpty()){
return 'An Empty List'
}
const nodeToRemove = this.head
this.head = this.head.next
this.size--
return nodeToRemove
}
removeFromEnd(){
if(this.isEmpty()){
return 'An Empty List'
}
let nodeToRemove = this.tail
if(this.size === 1){
this.head = null
this.tail = null
}else{
let prev = this.tail.previous
prev.next = null
this.tail = prev
}
this.size--
return nodeToRemove
}
// REVERSING A LINKED LIST
reverse() {
let current = this.head
let temp = null
while (current) {
temp = current.next
current.next = current.previous
current.previous = temp
current = temp
}
temp = this.head
this.head = this.tail
this.tail = temp
}
// PRINTING THE VALUES OF THE LINKED LIST
print() {
if (this.isEmpty()) {
alert('Nothing to print, the list is empty')
return ('Nothing to print, the list is empty')
}
let current = this.head
while (current !== null) {
console.log(current.value)
current = current.next
}
}
}
CONCLUSION:
Since each concept is a buildup, it pays more dividends to understand them before moving on to the next, especially to understand the concept of a linked list. If it helps, feel free to explore more resources to understand a linked list, before coming back to this how to Implement it article
Free tip, I found it instrumental to consult multiple resources, which consolidate what I am learning from different perspectives, in different words or forms, like an audiovisual in addition to a written piece.