What is a Singly Linked list?
A Singly linked list is a collection of nodes and each node has a value and a pointer to another node or null. The value can be any valid data type. You can see this illustrated in the diagram below.
The entry node in linked list is called Head and the last node is called Tail.
In Javascript a linked list can be implemented like this
class Node {
constructor(val) {
this.val = val;
this.next=null
}
}
class SinglyLinkedList{
constructor() {
this.head = null;
this.tail = null;
this.length=0
}
//This method used to push a value to end of the linked list
push(val){
let newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail=newNode;
}
else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
//this method is used to remove an element from end of linked list.
pop() {
if(!this.head)return undefined
let current = this.head;
let previous = current;
while (current.next) {
previous = current;
current = current.next
}
this.tail = previous
previous.next = null;
this.length = this.length - 1;
if (this.length == 0) {
this.tail = null
this.head=null
}
return this
}
//this method is used to add a value to beginning of a list.
unshift(val) {
let newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail=newNode
}
else {
let currentHead = this.head;
newNode.next = currentHead;
this.head=newNode
}
this.length++
return this
}
//this method is used to remove a value from beginning of a list
shift() {
if (!this.head) return undefined;
if (this.length === 1) {
this.head = null;
this.tail = null
}
else {
this.head = this.head.next;
}
this.length--;
return this;
}
//this method is used to get a value from a particular position in list.
get(position) {
if (position < 0 ||position>=this.length) {
return undefined
}
let index = 0;
let currentHead = this.head;
while (position!=index) {
currentHead = currentHead.next;
index++;
}
return currentHead
}
//this method is used to replace a value from a particular position in list.
set(value, position) {
let getValue = this.get(position)
if (!getValue) return false;
getValue.val=value
return this
}
//this method is user to insert an element in the list at a particular position.
insert(position, val) {
if (position < 0 || position > this.length) {
return undefined;
}
if (position === 0) {
return this.unshift(val)
}
else if (position === this.length) {
return this.push(val)
}
let newNode = new Node(val)
let previous = this.get(position - 1)
if (!previous) return false;
let nextEl = previous.next;
newNode.next = nextEl;
previous.next=newNode
this.length++;
return this;
}
//this method is used to remove a value from a particular position
remove(position) {
if (position < 0 || position > this.length) {
return undefined
}
if (position === 0) {
return this.shift(val)
}
else if (position === this.length-1) {
return this.pop(val)
}
let getEl = this.get(position-1)
getEl.next = getEl.next.next;
this.length--;
return this
}
//this method is used to get the size of the list
size(){
return this.length
}
}
Advantages of singley linked list
- Insertions and Deletions can be done easily
- It does not need movement of elements for insertion and deletion unlike arrays.
Disadvantages of singley linked list
- Search operations are slow in linked lists. Unlike arrays, random access of data elements is not allowed. Nodes are accessed sequentially starting from the first node.
BIG O Notation
- Access O(n)
- Search O(n)
- Insertion O(1)
- Deletion O(1)
Top comments (0)