The problem is that many of the people trying to learn data structures but not implementing them.
People start worrying about data structures. This occurs because everyone has heard that a good knowledge of data structures is important for technical interviews and so people get obsessed with trying to learn these topics. They don't realize they'd be better served by implementing them rather than just read about it.
So I have started this series to focus on each data structure and how to implement them in Javascript.
In this article, we will be implementing a **Singly LinkedList **data structure in Javascript.
What is Singly Linked List
A linked list is a linear data structure, in which we can add or remove elements at ease, and it can even grow as needed. Just like arrays, but elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.
Implementing Singly Linked List
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
As in the code above, we have two properties elements which holds the data of the current node and next holds the pointer (address) of the next node which initialized to null.
class SinglyLinkedList {
constructor() {
this.head = null;
}
}
Above code shows a SinglyLinkedList class with constructor, the Linked list has a property called head which will hold the first node of the linked list**.
Adding element into list
add(element) {
//create new node
let node = new Node(element);
let current = null;
//If head is empty then insert at first item
if (this.head == null) {
this.head = node;
} else {
current = this.head;
//iterate to end of list
while (current.next) {
current = current.next;
}
//Finally add new node
current.next = node;
}
this.size++;
}
In order to add an element, in the end, we should consider the following :
If the list is empty then add an element and it will be head
If the list is not empty then iterate to end of the list then add an element to end of the list.
Removing element from the list
removeElement(element) {
if (this.head === null) {
throw Error ('List is empty');
}
let current = this.head;
let prev = null;
//Iterate over the list
while (current != null) {
if (current.element === element) {
//If prev node is null then first node is required element
if (prev === null) {
this.head = current.next;
} else {
//if prev node found then unset current node
prev.next = current.next;
}
return current.element;
}
prev = current;
//iterate to next node
current = current.next;
}
return 'Element not found';
}
-
this.head === nullIf List is empty then throw an error ` - while (current != null)` Iterate list till find the element
-
prev === nullIfprev nodeis null then first node is required element so make second node as head - If prev node is found then
prev.next = current.nextdetach current node from list
That's it we have covered basics of Singly LinkedList.
Unit Test
var assert = require('assert');
const LinkedList = require('./single.linkedlist');
describe('Single Linked List', () =>{
const linkedList = new LinkedList();
it('Should add an element', () =>{
linkedList.add(10);
let result = linkedList.get('list');
assert.equal(JSON.stringify(result), '{"element":10,"next":null}')
})
it('Should add two element', () =>{
linkedList.add(20);
linkedList.add(30);
let result = linkedList.get('list');
assert.equal(JSON.stringify(result), '{"element":10,"next":{"element":20,"next":{"element":30,"next":null}}}')
})
it('Should remove an element', () =>{
linkedList.removeElement(20);
let result = linkedList.get('list');
assert.equal(JSON.stringify(result), '{"element":10,"next":{"element":30,"next":null}}')
})
})
Check Github Repo for full source code.
Stay Tuned for the next story.
This article published on Hashnode
Top comments (0)