This is the most common used linked list. It is a single chain of nodes.
The Node
In singly linked list, each node contains two parts; data and a link to next node.
Linked List
Singly Linked List contains a header pointer which contains address of the first node (the head node). Forward sequential movement, only, is possible here.
Note that the last node has it's link part set to null
Implementation
- First we'll create a node class which we will instantiate when we want to create a node.
class Node {
constructor(data, next = null) {
this.data = data;
//link to next node
this.next = next;
}
}
The link to next node is set to null for a single node.
- We then create a Linked List class
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//methods added here...
}
For an empty list, head is null and the size is 0.
- We then need to add methods in our linked list class to perform various operations such as add, remove and find.
Add node to start of list
insertFirst(data) {
this.head = new Node(data, this.head);
this.size++;
}
If the list was empty, the new node is set as the head and the link is set to null.
If the list was not empty, the new node is set as the new head and it's link set to the previous head.
The size of list is increased by one.
Add node to end of list
insertLast(data) {
let node = new Node(data);
let current;
//if list is empty, make new node the head
if (this.size === 0) {
this.head = node;
} else {
//select head as current node
current = this.head;
//go to end of list
while (current.next) {
current = current.next;
}
//add new node as next value of the last node
current.next = node;
}
this.size++;
}
The while loop terminates if current.next is null and the new node is added as it's value. The size of list is increased by one.
Remove first node of list
removeFirst() {
if (this.size !== 0) {
this.head = this.head.next;
this.size--;
if (this.size === 0) {
this.head = null;
}
}
}
If the list is not empty, the head is removed and replaced by the next node.
The size is decreased
Remove Last node of list
removeLast() {
let current, previous;
//if list is not empty
if (this.size !== 0) {
//if list contains one node
if (this.size === 1) {
this.head = null;
} else {
current = this.head;
//go to end of list
while (current.next) {
previous = current;
current = current.next;
}
//remove last node
previous.next = null;
}
this.size--;
}
}
Current and previous variables hold the current node and previous node respectively.
Find index of node in list
findIndexOf(data) {
let idx = 0;
//set current to first node
let current = this.head;
//iterate over list
while (current) {
if (current.data === data) {
console.log(idx)
//return index of item
return idx;
}
//increase index by one
idx++;
//move to next node and recheck
current = current.next;
}
console.log(-1);
//not found
return -1;
}
Starting from the head, we check if data in current node equals the data in question and return it's index. After each check the index counter increases by one. If the data is not in the list -1 is returned.
Print Linked List Data
printListData() {
//set current to first node
let current = this.head;
//iterate over list
while (current) {
console.log(current.data);
current = current.next;
}
}
Clear List
clearList() {
this.head = null;
this.size = 0;
}
Example test code;
//create empty list
const list = new LinkedList();
list.insertLast(400);
list.insertLast(500);
list.insertFirst(600);
list.findIndexOf(500)
console.log(list);
list.printListData();
Thank you for reading ❤️ .
Top comments (0)