What is a Singly Linked List?
A singly linked list is a linear data structure similar to an array. However, unlike arrays, elements are not stored in a particular memory location or index. Rather each element is a separate object that contains a pointer or a link to the next object in that list.
Each element (commonly called nodes) contains two items: the data stored and a link to the next node. The data can be any valid data type.
The entry point to a linked list is called the head. The head is a reference to the first node in the linked list. The last node on the list points to null. If a list is empty, the head is a null reference
The structure would look like this in javascript below:
Advantages
- Nodes can easily be removed or added from a singly linked list without reorganising the entire data structure as these nodes don't have an index attached to it, unlike in an array.
Disadvantage
- Search is slow in a singly liked list because you have to traverse from the head to the tail.
- It uses more memory than arrays because of the storage of the pointers to the next node.
Implementation in Javascript
Creating a Node:
class Node {
constructor(val) {
this.val = val
this.next = null
}
}
Creating the function SinglyLinkedList with the shell:
class SinglyLinkedList {
constructor() {
this.length = 0
this.tail = null
this.head = null
}
}
Functions to be implemented:
- push
- pop
- shift
- unshift
- get
- set
- insert
- remove
- reverse
//Piece of data
// reference to the next node - next
class Node {
constructor(val) {
this.val = val
this.next = null
}
}
class SinglyLinkedList {
constructor() {
this.length = 0
this.tail = null
this.head = null
}
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
}
// traverse(){
// let current = this.head
// while(current){
// console.log(current.val)
// current = current.next
// }
// }
pop() {
if (!this.head) {
return undefined
}
let current = this.head
let newTail = current
while (current.next) {
newTail = current
current = current.next
}
this.tail = newTail
this.tail.next = null
this.length--
if (this.length === 0) {
this.head = null
this.tail = null
}
return current
}
shift() {
if (!this.head) return undefined
let currentHead = this.head
this.head = currentHead.next
this.length--
if (this.length === 0) {
this.tail = null
}
return currentHead
}
unshift(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
newNode.next = this.head
this.head = newNode
}
this.length++
return this
}
get(index) {
if (index < 0 || index >= this.length) {
return null
}
let counter = 0;
let current = this.head;
while (counter !== index) {
counter++;
current = current.next
}
return current
}
set(index, value) {
let foundNode = this.get(index);
if (foundNode) {
foundNode.val = value;
return true
}
return false
}
insert(index, value) {
if (index < 0 || index > this.length) return false
if (index === this.length) return !!this.push(value);
if (index === 0) return !!this.unshift(val);
let newNode = new Node(value)
let prev = this.get(index - 1)
let temp = prev.next
prev.next = newNode
newNode.next = temp
this.length++
return true
}
remove(index) {
if (index < 0 || index >= this.length) return undefined
if (index === this.length - 1) return this.pop
if (index === 0) return this.shift
let prev = this.get(index - 1)
let removed = prev.next
prev.next = removed.next
this.length--
return removed
}
reverse() {
//swapping head and tail
let node = this.head
this.head = this.tail
this.tail = node
//new variables used for swapping
let prev = null;
let next = null;
for (var i = 0; i < this.length; i++) {
next = node.next;
//one way linkage between
node.next = prev;
//moving the counter
prev = node
node = next
}
return this
}
print() {
//used to print out as to see things better
var arr = [];
var current = this.head
while (current) {
arr.push(current.val)
current = current.next
}
console.log(arr);
}
}
let list = new SinglyLinkedList()
list.push("20")
list.push("30")
list.push("40")
list.push("50")