A singly linked list is a list of items, where each element has reference to the next element. Elements do not have info on the previous element. So we can only go to the next element while traversing a singly linked list.
NOTE
In this article, we are discussing in detail, the implementation of Singly Linked List in JavaScript and TypeScript.
Check the link below to check the details of Linked List and Singly Linked List-
Implementation
Here is the detailed implementation of Singly Linked List in JavaScript and TypeScript, step-by-step –
Step #1: Node Class
The purpose of the Node class is to store information on a single node. It stores data and references to the next node.
// Node class for storing data
// and reference to the next node
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
JavaScript// Node class for storing data
// and reference to the next node
class Node<T> {
data: T;
next: Node<T> | null;
constructor(data: T) {
this.data = data;
this.next = null;
}
}
TypeScriptNOTE
For TypeScript we are using a generic and passing the type as <T>. This “T” type will be the type of data.
This is used to provide the flexibility of storing any type of data in the list.
You can assign a fixed type to the data, if you are going to use the list implementation for a specific single purpose.
Step #2: Linked List Class
The lined list class is the place where are implementing the actual linked list-
// Singly Linked List class
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
JavaScript// Singly Linked List class
class SinglyLinkedList<T> {
public head: Node<T> | null;
public tail: Node<T> | null;
public length: number;
constructor() {
// Initialize head, tail, and length
this.head = null;
this.tail = null;
this.length = 0;
}
}
TypeScriptNOTE
For TypeScript we are using a generic and passing the type as <T>. We need to pass this type <T> to the “Node” item.
Step #3: Push (Node to the end)
class SinglyLinkedList<T> {
//...
push(data: T): SinglyLinkedList<T> {
// Add data at the end of the list
const node = new Node(data);
if (!this.head) {
// If list is empty, set head and tail to new node
this.head = node;
} else {
// Otherwise, set the next of current tail to new node
this.tail!.next = node;
}
// Set new node as the tail
this.tail = node;
// Increase the length
this.length++;
return this;
}
//...
}
JavaScriptclass SinglyLinkedList<T> {
//...
push(data: T): SinglyLinkedList<T> {
// Add data at the end of the list
const node = new Node(data);
if (!this.head) {
// If list is empty, set head and tail to new node
this.head = node;
} else {
// Otherwise, set the next of current tail to new node
this.tail!.next = node;
}
// Set new node as the tail
this.tail = node;
// Increase the length
this.length++;
return this;
}
//...
}
TypeScriptStep #4: Pop (Last Node)
class SinglyLinkedList {
//...
// Pop the last item
pop() {
// If there is no head
// then the list does not exist
if (!this.head) {
return null;
}
let current = this.head;
let newTail = current;
// Traverse through the list
// and get the second last item as newTail
while (current.next) {
newTail = current;
current = current.next;
}
// Assign the newTail to the tail
this.tail = newTail;
// Delete the next pointer of the tail
this.tail.next = null;
this.length--;
// Reset head and tail if it was the last item
if (this.length == 0) {
this.head = null;
this.tail = null;
}
// Return the popped item
return current;
}
//...
}
JavaScriptclass SinglyLinkedList<T> {
//...
pop(): Node<T> | null {
// Remove and return the last element from the list
if (!this.head) {
// If list is empty, return null
return null;
}
let current = this.head;
let newTail = current;
while (current.next) {
// Traverse the list to find the second last node
newTail = current;
current = current.next;
}
// Update tail and remove the last node
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
// If list becomes empty, reset head and tail
this.head = null;
this.tail = null;
}
return current;
}
//...
}
TypeScriptStep #5: Traverse all Nodes
class SinglyLinkedList<T> {
//...
traverse(): void {
// Traverse the list and log the data of each node
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
//...
}
JavaScriptclass SinglyLinkedList<T> {
//...
traverse(): void {
// Traverse the list and log the data of each node
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
//...
}
TypeScriptStep #6: Shift Head
class SinglyLinkedList {
//...
// Shift head
// and make the second item as head
// also return the first item
shift() {
// If there is no head then return null
if (!this.head) {
return null;
}
const currHead = this.head;
// Set the second item as head
this.head = currHead.next;
// Reduce the length by one
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
// Return the head item
return currHead;
}
//...
}
JavaScriptclass SinglyLinkedList<T> {
//...
shift(): Node<T> | null {
// Remove and return the first element from the list
if (!this.head) {
// If list is empty, return null
return null;
}
const currHead = this.head;
// Move head to the next node
this.head = currHead.next;
this.length--;
if (this.length === 0) {
// If list becomes empty, reset head and tail
this.head = null;
this.tail = null;
}
return currHead;
}
//...
}
TypeScriptStep #7: Unshift Head
class SinglyLinkedList<T> {
//...
unshift(value: T): SinglyLinkedList<T> {
// Add data at the beginning of the list
let newHead = new Node(value);
if (!this.head) {
// If list is empty, set head and tail to new node
this.tail = newHead;
} else {
// Otherwise, set the next of new node to current head
newHead.next = this.head;
}
// Set new node as the head
this.head = newHead;
// Increase the length
this.length++;
return this;
}
//...
}
JavaScriptclass SinglyLinkedList<T> {
//...
unshift(value: T): SinglyLinkedList<T> {
// Add data at the beginning of the list
let newHead = new Node(value);
if (!this.head) {
// If list is empty, set head and tail to new node
this.tail = newHead;
} else {
// Otherwise, set the next of new node to current head
newHead.next = this.head;
}
// Set new node as the head
this.head = newHead;
// Increase the length
this.length++;
return this;
}
//...
}
TypeScriptStep #8: Get Node by Index
We want to pass some index and want to get the node at that index-
class SinglyLinkedList {
//...
// Get node by index(sequence numbers)
// 0 based index (index starts from 0)
get(index) {
// Check if the index is valid
if (index < 0 || index >= this.length) {
return null;
}
let selectedNode = this.head;
for (let i = 1; i <= index; i++) {
selectedNode = selectedNode.next;
}
return selectedNode;
}
//...
}
JavaScriptclass SinglyLinkedList<T> {
//...
get(index: number): Node<T> | null {
// Get node at a specified index
if (index < 0 || index >= this.length) {
// If index is out of range, return null
return null;
}
let selectedNode = this.head;
for (let i = 1; i <= index; i++) {
// Traverse the list to find the node at the given index
selectedNode = selectedNode!.next;
}
return selectedNode;
}
//...
}
TypeScriptStep #9: Search by data
Here we want to search for specific data. Whichever node has the data, we want to get that index.
class SinglyLinkedList {
//...
// Search the list for specific data
search(data) {
let current = this.head;
let index = 0;
while (current) {
if (current.data === data) {
return index;
}
current = current.next;
index++;
}
return null;
}
//...
}
JavaScriptclass SinglyLinkedList<T> {
//...
search(data: T): number | null {
// Search for the index of a specific data in the list
let current = this.head;
let index = 0;
while (current) {
// Traverse the list and check data of each node
if (current.data === data) {
// If data is found, return its index
return index;
}
current = current.next;
index++;
}
// If data is not found, return null
return null;
}
//...
}
TypeScriptStep #10: Set data at Node by Index
Here we want to set the data of an existing, at a specific index.
class SinglyLinkedList<T> {
//...
set(index: number, data: T): boolean {
// Set data of a specific node at a given index
let nodeAtIndex = this.get(index);
if (nodeAtIndex) {
// If node at given index exists, update its data
nodeAtIndex.data = data;
return true;
}
// If node at given index does not exist, return false
return false;
}
//...
}
JavaScriptclass SinglyLinkedList<T> {
//...
set(index: number, data: T): boolean {
// Set data of a specific node at a given index
let nodeAtIndex = this.get(index);
if (nodeAtIndex) {
// If node at given index exists, update its data
nodeAtIndex.data = data;
return true;
}
// If node at given index does not exist, return false
return false;
}
//...
}
TypeScriptStep #11: Insert Data at Specific Index
We want to create a new node with data, and add that to some specific index.
class SinglyLinkedList<T> {
//...
insert(index: number, data: T): boolean {
// Insert new node at a specific index
if (index < 0 || index > this.length) {
// If index is out of range, return false
return false;
}
if (index === this.length) {
// If index is at the end, use push method
this.push(data);
return true;
}
if (index === 0) {
// If index is at the beginning, use unshift method
this.unshift(data);
return true;
}
// Otherwise, insert new node at the specified index
let newNode = new Node(data);
let prevNode = this.get(index - 1);
newNode.next = prevNode!.next;
prevNode!.next = newNode;
// Increase length
this.length++;
return true;
}
//...
}
JavaScriptclass SinglyLinkedList<T> {
//...
insert(index: number, data: T): boolean {
// Insert new node at a specific index
if (index < 0 || index > this.length) {
// If index is out of range, return false
return false;
}
if (index === this.length) {
// If index is at the end, use push method
this.push(data);
return true;
}
if (index === 0) {
// If index is at the beginning, use unshift method
this.unshift(data);
return true;
}
// Otherwise, insert new node at the specified index
let newNode = new Node(data);
let prevNode = this.get(index - 1);
newNode.next = prevNode!.next;
prevNode!.next = newNode;
// Increase length
this.length++;
return true;
}
//...
}
Step #12: Remove Item from Specific Index
class SinglyLinkedList {
//...
// Remove item at index
remove(index) {
// Return false if index is out of range
if (index < 0 || index >= this.length) {
return undefined;
}
if (index === 0) {
return this.shift();
}
if (index === this.length - 1) {
return this.pop();
}
let prevNode = this.get(index - 1);
const removedNode = prevNode.next;
prevNode.next = prevNode.next.next;
this.length--;
return removedNode;
}
//...
}
JavaScriptclass SinglyLinkedList<T> {
//...
remove(index: number): Node<T> | null {
// Remove node at a specific index
if (index < 0 || index >= this.length) {
// If index is out of range, return undefined
return null;
}
if (index === 0) {
// If index is at the beginning, use shift method
return this.shift();
}
if (index === this.length - 1) {
// If index is at the end, use pop method
return this.pop();
}
// Otherwise, remove node at the specified index
let prevNode = this.get(index - 1);
const removedNode = prevNode!.next;
prevNode!.next = prevNode!.next!.next;
// Decrease length
this.length--;
return removedNode;
}
//...
}
TypeScriptStep #13: Reverse a Singly Linked List
class SinglyLinkedList<T> {
//...
reverse(): SinglyLinkedList<T> {
// Reverse the linked list
let currentNode = this.head;
let prevNode = null;
let nextNode = null;
while (currentNode) {
// Traverse the list and reverse each node
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
currentNode = nextNode;
}
// Update head and tail references
this.tail = this.head;
this.head = prevNode;
return this;
}
//...
}
JavaScriptclass SinglyLinkedList<T> {
//...
reverse(): SinglyLinkedList<T> {
// Reverse the linked list
let currentNode = this.head;
let prevNode = null;
let nextNode = null;
while (currentNode) {
// Traverse the list and reverse each node
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
currentNode = nextNode;
}
// Update head and tail references
this.tail = this.head;
this.head = prevNode;
return this;
}
//...
}
TypeScriptFull Implementation Code
Here is the full implementation of Singly Linked List, with all the functionality.
// sll.js
// Singly linked list in JavaScript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
// Push item at the end of the list
push(data) {
const node = new Node(data);
// If the list is empty
// then make this node as head and tail
if (!this.head) {
this.head = node;
} else {
// set the current tail's next value to new node
this.tail.next = node;
}
// Set the tail to this new node
this.tail = node;
// Increase the length by 1
this.length++;
// Return the SinglyLinkedList
return this;
}
// Pop the last item
pop() {
// If there is no head
// then the list does not exist
if (!this.head) {
return null;
}
let current = this.head;
let newTail = current;
// Traverse through the list
// and get the second last item as newTail
while (current.next) {
newTail = current;
current = current.next;
}
// Assign the newTail to the tail
this.tail = newTail;
// Delete the next pointer of the tail
this.tail.next = null;
this.length--;
// Reset head and tail if it was the last item
if (this.length == 0) {
this.head = null;
this.tail = null;
}
// Return the popped item
return current;
}
// Traverse the list
traverse() {
let current = this.head;
while (current) {
console.log(current.data);
// Change current to the next node
current = current.next;
}
}
// Shift head
// and make the second item as head
// also return the first item
shift() {
// If there is no head then return null
if (!this.head) {
return null;
}
const currHead = this.head;
// Set the second item as head
this.head = currHead.next;
// Reduce the length by one
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
// Return the head item
return currHead;
}
// Unshift head
// Create new node and set that as head
unshift(value) {
// Create new Node from value
let newHead = new Node(value);
if (!this.head) {
this.tail = newHead;
} else {
newHead.next = this.head;
}
// Set the new node as head
this.head = newHead;
// Increase length by one
this.length++;
return this;
}
// Get node by index(sequence numbers)
// 0 based index (index starts from 0)
get(index) {
// Check if the index is valid
if (index < 0 || index >= this.length) {
return null;
}
let selectedNode = this.head;
for (let i = 1; i <= index; i++) {
selectedNode = selectedNode.next;
}
return selectedNode;
}
// Set data of a specific node at specific index
// 0 based index(index starts from 0)
set(index, data) {
let nodeAtIndex = this.get(index);
if (nodeAtIndex) {
nodeAtIndex.data = data;
return true;
}
return false;
}
}
export default SinglyLinkedList;
JavaScript// sll.ts
// Singly linked list in TypeScript
class Node<T> {
// Node class for storing data and reference to the next node
data: T;
next: Node<T> | null;
constructor(data: T) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList<T> {
// Singly Linked List class
public head: Node<T> | null;
public tail: Node<T> | null;
public length: number;
constructor() {
// Initialize head, tail, and length
this.head = null;
this.tail = null;
this.length = 0;
}
push(data: T): SinglyLinkedList<T> {
// Add data at the end of the list
const node = new Node(data);
if (!this.head) {
// If list is empty, set head and tail to new node
this.head = node;
} else {
// Otherwise, set the next of current tail to new node
this.tail!.next = node;
}
// Set new node as the tail
this.tail = node;
// Increase the length
this.length++;
return this;
}
pop(): Node<T> | null {
// Remove and return the last element from the list
if (!this.head) {
// If list is empty, return null
return null;
}
let current = this.head;
let newTail = current;
while (current.next) {
// Traverse the list to find the second last node
newTail = current;
current = current.next;
}
// Update tail and remove the last node
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
// If list becomes empty, reset head and tail
this.head = null;
this.tail = null;
}
return current;
}
traverse(): void {
// Traverse the list and log the data of each node
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
shift(): Node<T> | null {
// Remove and return the first element from the list
if (!this.head) {
// If list is empty, return null
return null;
}
const currHead = this.head;
// Move head to the next node
this.head = currHead.next;
this.length--;
if (this.length === 0) {
// If list becomes empty, reset head and tail
this.head = null;
this.tail = null;
}
return currHead;
}
unshift(value: T): SinglyLinkedList<T> {
// Add data at the beginning of the list
let newHead = new Node(value);
if (!this.head) {
// If list is empty, set head and tail to new node
this.tail = newHead;
} else {
// Otherwise, set the next of new node to current head
newHead.next = this.head;
}
// Set new node as the head
this.head = newHead;
// Increase the length
this.length++;
return this;
}
get(index: number): Node<T> | null {
// Get node at a specified index
if (index < 0 || index >= this.length) {
// If index is out of range, return null
return null;
}
let selectedNode = this.head;
for (let i = 1; i <= index; i++) {
// Traverse the list to find the node at the given index
selectedNode = selectedNode!.next;
}
return selectedNode;
}
search(data: T): number | null {
// Search for the index of a specific data in the list
let current = this.head;
let index = 0;
while (current) {
// Traverse the list and check data of each node
if (current.data === data) {
// If data is found, return its index
return index;
}
current = current.next;
index++;
}
// If data is not found, return null
return null;
}
set(index: number, data: T): boolean {
// Set data of a specific node at a given index
let nodeAtIndex = this.get(index);
if (nodeAtIndex) {
// If node at given index exists, update its data
nodeAtIndex.data = data;
return true;
}
// If node at given index does not exist, return false
return false;
}
insert(index: number, data: T): boolean {
// Insert new node at a specific index
if (index < 0 || index > this.length) {
// If index is out of range, return false
return false;
}
if (index === this.length) {
// If index is at the end, use push method
this.push(data);
return true;
}
if (index === 0) {
// If index is at the beginning, use unshift method
this.unshift(data);
return true;
}
// Otherwise, insert new node at the specified index
let newNode = new Node(data);
let prevNode = this.get(index - 1);
newNode.next = prevNode!.next;
prevNode!.next = newNode;
// Increase length
this.length++;
return true;
}
remove(index: number): Node<T> | null {
// Remove node at a specific index
if (index < 0 || index >= this.length) {
// If index is out of range, return undefined
return null;
}
if (index === 0) {
// If index is at the beginning, use shift method
return this.shift();
}
if (index === this.length - 1) {
// If index is at the end, use pop method
return this.pop();
}
// Otherwise, remove node at the specified index
let prevNode = this.get(index - 1);
const removedNode = prevNode!.next;
prevNode!.next = prevNode!.next!.next;
// Decrease length
this.length--;
return removedNode;
}
reverse(): SinglyLinkedList<T> {
// Reverse the linked list
let currentNode = this.head;
let prevNode = null;
let nextNode = null;
while (currentNode) {
// Traverse the list and reverse each node
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
currentNode = nextNode;
}
// Update head and tail references
this.tail = this.head;
this.head = prevNode;
return this;
}
}
export default SinglyLinkedList;
TypeScriptDemo
Here is the demo code for using the implemented functionality of Singly Linked List-
// demo.js
import SinglyLinkedList from "./sll.js";
// Create a new Singly Linked List
let bigboxList = new SinglyLinkedList();
console.log("nn----------- Singly Linked List Push example -----------n");
// Push items
console.log('Push - "Big" | Result: ', bigboxList.push("Big"));
console.log('Push - "Box" | Result: ', bigboxList.push("Box"));
console.log('Push - "Code" | Result: ', bigboxList.push("Code"));
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Pop example -----------n");
console.log("Popped Item: ", bigboxList.pop());
console.log("Popped Item: ", bigboxList.pop());
console.log("List value: ", bigboxList);
console.log("Popped Item: ", bigboxList.pop());
console.log("List value: ", bigboxList);
console.log("Popped Item: ", bigboxList.pop());
console.log("List value: ", bigboxList);
// Push items again
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");
console.log("nn----------- Singly Linked List Shift example -----------n");
console.log("Shift head from list: ", bigboxList.shift());
console.log("List value: ", bigboxList);
console.log("Shift head from list: ", bigboxList.shift());
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Unshift example -----------n");
console.log("Unshift - 'Box' | Result: ", bigboxList.unshift("Box"));
console.log("List value: ", bigboxList);
console.log("Unshift - 'Big' | Result: ", bigboxList.unshift("Big"));
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Get example -----------n");
console.log(`Get - at index: 0 | result:`, bigboxList.get(0));
console.log(`Get - at index: 2 | result:`, bigboxList.get(2));
console.log(`Get - at index: 99 | result:`, bigboxList.get(99));
console.log("nn----------- Singly Linked List Set example -----------n");
console.log(
`Set - "New Val" at index: 0 | result: ${bigboxList.set(0, "New Val")}`
);
console.log(
`Set - "Second" at index: 2 | result: ${bigboxList.set(2, "Second")}`
);
console.log(
`Set - "Out bound" at index: 99 | result: ${bigboxList.set(99, "Out bound")}`
);
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Insert example -----------n");
console.log(
`Insert - "New Val 1" at index: 0 | result: ${bigboxList.insert(
0,
"New Val 1"
)}`
);
console.log(
`Insert - "New Val" at index: 2 | result: ${bigboxList.insert(
2,
"New Val 2"
)}`
);
console.log(
`Insert - "Out bound" at index: 99 | result: ${bigboxList.insert(
99,
"Out bound"
)}`
);
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Remove example -----------n");
// Reinitialize the list
bigboxList = new SinglyLinkedList();
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");
console.log(`Remove - form index: 2 | result:`, bigboxList.remove(2));
console.log(`Remove - from index: 0 | result:`, bigboxList.remove(0));
console.log(`Remove - form index: 99 | result:`, bigboxList.remove(99));
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Reverse example -----------n");
// Reinitialize the list
bigboxList = new SinglyLinkedList();
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");
bigboxList.push("Singly");
bigboxList.push("Linked");
bigboxList.push("List");
console.log("List value: ");
bigboxList.traverse();
bigboxList.reverse();
console.log("List value after reverse: ");
bigboxList.traverse();
console.log("List value: ", bigboxList);
JavaScript// demo.ts
import SinglyLinkedList from "./sll";
// Create a new Singly Linked List
let bigboxList = new SinglyLinkedList<string>();
console.log("nn----------- Singly Linked List Push example -----------n");
// Push items
console.log('Push - "Big" | Result: ', bigboxList.push("Big"));
console.log('Push - "Box" | Result: ', bigboxList.push("Box"));
console.log('Push - "Code" | Result: ', bigboxList.push("Code"));
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Pop example -----------n");
console.log("Popped Item: ", bigboxList.pop());
console.log("Popped Item: ", bigboxList.pop());
console.log("List value: ", bigboxList);
console.log("Popped Item: ", bigboxList.pop());
console.log("List value: ", bigboxList);
console.log("Popped Item: ", bigboxList.pop());
console.log("List value: ", bigboxList);
// Push items again
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");
console.log("nn----------- Singly Linked List Shift example -----------n");
console.log("Shift head from list: ", bigboxList.shift());
console.log("List value: ", bigboxList);
console.log("Shift head from list: ", bigboxList.shift());
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Unshift example -----------n");
console.log("Unshift - 'Box' | Result: ", bigboxList.unshift("Box"));
console.log("List value: ", bigboxList);
console.log("Unshift - 'Big' | Result: ", bigboxList.unshift("Big"));
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Get example -----------n");
console.log(`Get - at index: 0 | result:`, bigboxList.get(0));
console.log(`Get - at index: 2 | result:`, bigboxList.get(2));
console.log(`Get - at index: 99 | result:`, bigboxList.get(99));
console.log("nn----------- Singly Linked List Search example -----------n");
console.log(`Search - item "Big" | result:`, bigboxList.search("Big"));
console.log(`Search - item "Code" | result:`, bigboxList.search("Code"));
console.log(
`Search - item "Non exiting" | result:`,
bigboxList.search("Non exiting")
);
console.log("nn----------- Singly Linked List Set example -----------n");
console.log(
`Set - "New Val" at index: 0 | result: ${bigboxList.set(0, "New Val")}`
);
console.log(
`Set - "Second" at index: 2 | result: ${bigboxList.set(2, "Second")}`
);
console.log(
`Set - "Out bound" at index: 99 | result: ${bigboxList.set(99, "Out bound")}`
);
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Insert example -----------n");
console.log(
`Insert - "New Val 1" at index: 0 | result: ${bigboxList.insert(
0,
"New Val 1"
)}`
);
console.log(
`Insert - "New Val" at index: 2 | result: ${bigboxList.insert(
2,
"New Val 2"
)}`
);
console.log(
`Insert - "Out bound" at index: 99 | result: ${bigboxList.insert(
99,
"Out bound"
)}`
);
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Remove example -----------n");
// Reinitialize the list
bigboxList = new SinglyLinkedList<string>();
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");
console.log(`Remove - form index: 2 | result:`, bigboxList.remove(2));
console.log(`Remove - from index: 0 | result:`, bigboxList.remove(0));
console.log(`Remove - form index: 99 | result:`, bigboxList.remove(99));
console.log("List value: ", bigboxList);
console.log("nn----------- Singly Linked List Reverse example -----------n");
// Reinitialize the list
bigboxList = new SinglyLinkedList<string>();
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");
bigboxList.push("Singly");
bigboxList.push("Linked");
bigboxList.push("List");
console.log("List value: ");
bigboxList.traverse();
bigboxList.reverse();
console.log("List value after reverse: ");
bigboxList.traverse();
console.log("List value: ", bigboxList);
TypeScriptOutput:
Output of the demo code will look like below-
----------- Singly Linked List Push example -----------
Push - "Big" | Result: SinglyLinkedList {
head: Node { data: 'Big', next: null },
tail: Node { data: 'Big', next: null },
length: 1
}
Push - "Box" | Result: SinglyLinkedList {
head: Node { data: 'Big', next: Node { data: 'Box', next: null } },
tail: Node { data: 'Box', next: null },
length: 2
}
Push - "Code" | Result: SinglyLinkedList {
head: Node { data: 'Big', next: Node { data: 'Box', next: [Node] } },
tail: Node { data: 'Code', next: null },
length: 3
}
List value: SinglyLinkedList {
head: Node { data: 'Big', next: Node { data: 'Box', next: [Node] } },
tail: Node { data: 'Code', next: null },
length: 3
}
----------- Singly Linked List Pop example -----------
Popped Item: Node { data: 'Code', next: null }
Popped Item: Node { data: 'Box', next: null }
List value: SinglyLinkedList {
head: Node { data: 'Big', next: null },
tail: Node { data: 'Big', next: null },
length: 1
}
Popped Item: Node { data: 'Big', next: null }
List value: SinglyLinkedList { head: null, tail: null, length: 0 }
Popped Item: null
List value: SinglyLinkedList { head: null, tail: null, length: 0 }
----------- Singly Linked List Shift example -----------
Shift head from list: Node {
data: 'Big',
next: Node { data: 'Box', next: Node { data: 'Code', next: null } }
}
List value: SinglyLinkedList {
head: Node { data: 'Box', next: Node { data: 'Code', next: null } },
tail: Node { data: 'Code', next: null },
length: 2
}
Shift head from list: Node { data: 'Box', next: Node { data: 'Code', next: null } }
List value: SinglyLinkedList {
head: Node { data: 'Code', next: null },
tail: Node { data: 'Code', next: null },
length: 1
}
----------- Singly Linked List Unshift example -----------
Unshift - 'Box' | Result: SinglyLinkedList {
head: Node { data: 'Box', next: Node { data: 'Code', next: null } },
tail: Node { data: 'Code', next: null },
length: 2
}
List value: SinglyLinkedList {
head: Node { data: 'Box', next: Node { data: 'Code', next: null } },
tail: Node { data: 'Code', next: null },
length: 2
}
Unshift - 'Big' | Result: SinglyLinkedList {
head: Node { data: 'Big', next: Node { data: 'Box', next: [Node] } },
tail: Node { data: 'Code', next: null },
length: 3
}
List value: SinglyLinkedList {
head: Node { data: 'Big', next: Node { data: 'Box', next: [Node] } },
tail: Node { data: 'Code', next: null },
length: 3
}
----------- Singly Linked List Get example -----------
Get - at index: 0 | result: Node {
data: 'Big',
next: Node { data: 'Box', next: Node { data: 'Code', next: null } }
}
Get - at index: 2 | result: Node { data: 'Code', next: null }
Get - at index: 99 | result: null
----------- Singly Linked List Set example -----------
Set - "New Val" at index: 0 | result: true
Set - "Second" at index: 2 | result: true
Set - "Out bound" at index: 99 | result: false
List value: SinglyLinkedList {
head: Node { data: 'New Val', next: Node { data: 'Box', next: [Node] } },
tail: Node { data: 'Second', next: null },
length: 3
}
----------- Singly Linked List Insert example -----------
Insert - "New Val 1" at index: 0 | result: true
Insert - "New Val" at index: 2 | result: true
Insert - "Out bound" at index: 99 | result: false
List value: SinglyLinkedList {
head: Node {
data: 'New Val 1',
next: Node { data: 'New Val', next: [Node] }
},
tail: Node { data: 'Second', next: null },
length: 5
}
----------- Singly Linked List Remove example -----------
Remove - form index: 2 | result: Node { data: 'Code', next: null }
Remove - from index: 0 | result: Node { data: 'Big', next: Node { data: 'Box', next: null } }
Remove - form index: 99 | result: undefined
List value: SinglyLinkedList {
head: Node { data: 'Box', next: null },
tail: Node { data: 'Box', next: null },
length: 1
}
----------- Singly Linked List Reverse example -----------
List value:
Big
Box
Code
Singly
Linked
List
List value after reverse:
List
Linked
Singly
Code
Box
Big
List value: SinglyLinkedList {
head: Node { data: 'List', next: Node { data: 'Linked', next: [Node] } },
tail: Node { data: 'Big', next: null },
length: 6
}
PlaintextTesting
Let’s test the functionality using automated testing. Use the following code for testing.
// sll.test.js
import SinglyLinkedList from "./sll";
describe("SinglyLinkedList", () => {
describe("Push item to SinglyLinkedList", () => {
let singlyLinkedList;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList();
});
test("Should have correct head and tail", () => {
// Initially head and tails should be null
expect(singlyLinkedList.head).toBeNull();
expect(singlyLinkedList.tail).toBeNull();
singlyLinkedList.push("Big");
expect(singlyLinkedList.head.data).toBe("Big");
expect(singlyLinkedList.tail.data).toBe("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
expect(singlyLinkedList.head.data).toBe("Big");
expect(singlyLinkedList.tail.data).toBe("Code");
});
test("Should have correct length", () => {
expect(singlyLinkedList.length).toBe(0);
singlyLinkedList.push("Big");
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.push("Box");
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.push("Code");
expect(singlyLinkedList.length).toBe(3);
});
});
describe("Pop item from SinglyLinkedList", () => {
let singlyLinkedList;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
test("Should pop item propertly", () => {
const pop1 = singlyLinkedList.pop();
expect(pop1.data).toBe("Code");
const pop2 = singlyLinkedList.pop();
expect(pop2.data).toBe("Box");
const pop3 = singlyLinkedList.pop();
expect(pop3.data).toBe("Big");
const pop0 = singlyLinkedList.pop();
expect(pop0).toBeNull();
});
test("Should have correct head and tail", () => {
expect(singlyLinkedList.head.data).toBe("Big");
expect(singlyLinkedList.tail.data).toBe("Code");
singlyLinkedList.pop();
expect(singlyLinkedList.head.data).toBe("Big");
expect(singlyLinkedList.tail.data).toBe("Box");
singlyLinkedList.pop();
expect(singlyLinkedList.head.data).toBe("Big");
expect(singlyLinkedList.tail.data).toBe("Big");
singlyLinkedList.pop();
expect(singlyLinkedList.head).toBeNull();
expect(singlyLinkedList.tail).toBeNull();
});
test("Should have correct length", () => {
const pop1 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(2);
const pop2 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(1);
const pop3 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(0);
const pop0 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(0);
});
});
describe("Shift item from SinglyLinkedList", () => {
let singlyLinkedList;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
test("Should shift head propertly", () => {
const shift1 = singlyLinkedList.shift();
expect(shift1.data).toBe("Big");
const shift2 = singlyLinkedList.shift();
expect(shift2.data).toBe("Box");
const shift3 = singlyLinkedList.pop();
expect(shift3.data).toBe("Code");
const shift0 = singlyLinkedList.pop();
expect(shift0).toBeNull();
});
test("Should have correct head and tail", () => {
singlyLinkedList.shift();
expect(singlyLinkedList.head.data).toBe("Box");
expect(singlyLinkedList.tail.data).toBe("Code");
singlyLinkedList.shift();
expect(singlyLinkedList.head.data).toBe("Code");
expect(singlyLinkedList.tail.data).toBe("Code");
singlyLinkedList.shift();
expect(singlyLinkedList.head).toBeNull();
expect(singlyLinkedList.tail).toBeNull();
});
test("Should have correct length", () => {
singlyLinkedList.shift();
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.shift();
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.shift();
expect(singlyLinkedList.length).toBe(0);
// Try to pop one more time
singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(0);
});
});
describe("Unhift item from SinglyLinkedList", () => {
let singlyLinkedList;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList();
});
test("Should unhift head propertly", () => {
const unshift1 = singlyLinkedList.unshift("Code");
expect(unshift1).not.toBeNull();
const unshift2 = singlyLinkedList.unshift("Box");
expect(unshift2).not.toBeNull();
});
test("Should have correct head and tail", () => {
singlyLinkedList.unshift("Code");
expect(singlyLinkedList.head.data).toBe("Code");
expect(singlyLinkedList.tail.data).toBe("Code");
singlyLinkedList.unshift("Box");
expect(singlyLinkedList.head.data).toBe("Box");
expect(singlyLinkedList.tail.data).toBe("Code");
singlyLinkedList.unshift("Big");
expect(singlyLinkedList.head.data).toBe("Big");
expect(singlyLinkedList.tail.data).toBe("Code");
});
test("Should have correct length", () => {
singlyLinkedList.unshift("Code");
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.unshift("Box");
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.unshift("Big");
expect(singlyLinkedList.length).toBe(3);
});
});
describe("Get item from SinglyLinkedList by index", () => {
let singlyLinkedList;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
test("Should return node at specific index", () => {
const node0 = singlyLinkedList.get(0);
expect(node0.data).toBe("Big");
const node2 = singlyLinkedList.get(2);
expect(node2.data).toBe("Code");
});
test("Should return null for invalid index", () => {
const nodenve = singlyLinkedList.get(-1);
expect(nodenve).toBeNull();
const nodelarge = singlyLinkedList.get(999999);
expect(nodelarge).toBeNull();
});
});
describe("Set item to SinglyLinkedList by index", () => {
let singlyLinkedList;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
test("Should set value at node properly", () => {
const set0 = singlyLinkedList.set(0, "New Val");
expect(set0).toBeTruthy();
const get0 = singlyLinkedList.get(0);
expect(get0.data).toBe("New Val");
const set2 = singlyLinkedList.set(2, "Second");
expect(set2).toBeTruthy();
const get2 = singlyLinkedList.get(2);
expect(get2.data).toBe("Second");
const setN = singlyLinkedList.set(99, "Out Bound");
expect(setN).toBeFalsy();
});
test("Should handle empty list without any exception", () => {
singlyLinkedList = new SinglyLinkedList();
const set0 = singlyLinkedList.set(0, "Out Bound");
expect(set0).toBeFalsy();
});
});
describe("Insert item to SinglyLinkedList by index", () => {
let singlyLinkedList;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList();
});
test("Should insert data at index", () => {
const insert0 = singlyLinkedList.insert(0, "Big");
expect(insert0).toBeTruthy();
const get0 = singlyLinkedList.get(0);
expect(get0.data).toBe("Big");
const insert1 = singlyLinkedList.insert(1, "Code");
expect(insert1).toBeTruthy();
const get1 = singlyLinkedList.get(1);
expect(get1.data).toBe("Code");
const insert1_1 = singlyLinkedList.insert(1, "Box");
expect(insert1_1).toBeTruthy();
const get1_1 = singlyLinkedList.get(1);
expect(get1_1.data).toBe("Box");
const get1_2 = singlyLinkedList.get(2);
expect(get1_2.data).toBe("Code");
const setN = singlyLinkedList.insert(99, "Out Bound");
expect(setN).toBeFalsy();
});
test("Should have proper length after insert", () => {
singlyLinkedList.insert(0, "Big");
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.insert(1, "Code");
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.insert(1, "Box");
expect(singlyLinkedList.length).toBe(3);
singlyLinkedList.insert(99, "Out Bound");
expect(singlyLinkedList.length).toBe(3);
});
});
describe("Remove item from SinglyLinkedList by index", () => {
let singlyLinkedList;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
test("Should remove data at index", () => {
const remove2 = singlyLinkedList.remove(2);
expect(remove2.data).toBe("Code");
const get2 = singlyLinkedList.get(2);
expect(get2).toBeNull();
const remove0 = singlyLinkedList.remove(0);
expect(remove0.data).toBe("Big");
const get0 = singlyLinkedList.get(0);
expect(get0.data).toBe("Box");
const removeN = singlyLinkedList.remove(99);
expect(removeN).toBeFalsy();
});
test("Should have proper length after remove", () => {
singlyLinkedList.remove(1);
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.remove(99);
expect(singlyLinkedList.length).toBe(2);
});
});
describe("Reverse SinglyLinkedList", () => {
let singlyLinkedList;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
singlyLinkedList.push("Singly");
singlyLinkedList.push("Linked");
singlyLinkedList.push("List");
});
test("Should set head properly", () => {
singlyLinkedList.reverse();
expect(singlyLinkedList.head.data).toBe("List");
});
test("Should set tail properly", () => {
singlyLinkedList.reverse();
expect(singlyLinkedList.tail.data).toBe("Big");
});
test("Should set all elements properly", () => {
singlyLinkedList.reverse();
const get1 = singlyLinkedList.get(1);
expect(get1.data).toBe("Linked");
const get2 = singlyLinkedList.get(2);
expect(get2.data).toBe("Singly");
const get4 = singlyLinkedList.get(4);
expect(get4.data).toBe("Box");
});
test("Should not change the length", () => {
singlyLinkedList.reverse();
expect(singlyLinkedList.length).toBe(6);
});
});
});
JavaScript// sll.test.ts
import { describe, it, beforeEach, expect } from 'vitest';
import SinglyLinkedList from "./sll";
describe("SinglyLinkedList", () => {
describe("Push item to SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
});
it("Should have correct head and tail", () => {
// Initially head and tails should be null
expect(singlyLinkedList.head).toBeNull();
expect(singlyLinkedList.tail).toBeNull();
singlyLinkedList.push("Big");
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Code");
});
it("Should have correct length", () => {
expect(singlyLinkedList.length).toBe(0);
singlyLinkedList.push("Big");
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.push("Box");
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.push("Code");
expect(singlyLinkedList.length).toBe(3);
});
});
describe("Pop item from SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should pop item properly", () => {
const pop1 = singlyLinkedList.pop();
expect(pop1!.data).toBe("Code");
const pop2 = singlyLinkedList.pop();
expect(pop2!.data).toBe("Box");
const pop3 = singlyLinkedList.pop();
expect(pop3!.data).toBe("Big");
const pop0 = singlyLinkedList.pop();
expect(pop0).toBeNull();
});
it("Should have correct head and tail", () => {
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Code");
singlyLinkedList.pop();
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Box");
singlyLinkedList.pop();
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Big");
singlyLinkedList.pop();
expect(singlyLinkedList.head).toBeNull();
expect(singlyLinkedList.tail).toBeNull();
});
it("Should have correct length", () => {
const pop1 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(2);
const pop2 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(1);
const pop3 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(0);
const pop0 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(0);
});
});
describe("Shift item from SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should shift head properly", () => {
const shift1 = singlyLinkedList.shift();
expect(shift1!.data).toBe("Big");
const shift2 = singlyLinkedList.shift();
expect(shift2!.data).toBe("Box");
const shift3 = singlyLinkedList.pop();
expect(shift3!.data).toBe("Code");
const shift0 = singlyLinkedList.pop();
expect(shift0).toBeNull();
});
it("Should have correct head and tail", () => {
singlyLinkedList.shift();
expect(singlyLinkedList.head!.data).toBe("Box");
expect(singlyLinkedList.tail!.data).toBe("Code");
singlyLinkedList.shift();
expect(singlyLinkedList.head!.data).toBe("Code");
expect(singlyLinkedList.tail!.data).toBe("Code");
singlyLinkedList.shift();
expect(singlyLinkedList.head).toBeNull();
expect(singlyLinkedList.tail).toBeNull();
});
it("Should have correct length", () => {
singlyLinkedList.shift();
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.shift();
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.shift();
expect(singlyLinkedList.length).toBe(0);
// Try to pop one more time
singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(0);
});
});
describe("Unshift item from SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
});
it("Should unshift head properly", () => {
const unshift1 = singlyLinkedList.unshift("Code");
expect(unshift1).not.toBeNull();
const unshift2 = singlyLinkedList.unshift("Box");
expect(unshift2).not.toBeNull();
});
it("Should have correct head and tail", () => {
singlyLinkedList.unshift("Code");
expect(singlyLinkedList.head!.data).toBe("Code");
expect(singlyLinkedList.tail!.data).toBe("Code");
singlyLinkedList.unshift("Box");
expect(singlyLinkedList.head!.data).toBe("Box");
expect(singlyLinkedList.tail!.data).toBe("Code");
singlyLinkedList.unshift("Big");
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Code");
});
it("Should have correct length", () => {
singlyLinkedList.unshift("Code");
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.unshift("Box");
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.unshift("Big");
expect(singlyLinkedList.length).toBe(3);
});
});
describe("Get item from SinglyLinkedList by index", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should return node at specific index", () => {
const node0 = singlyLinkedList.get(0);
expect(node0!.data).toBe("Big");
const node2 = singlyLinkedList.get(2);
expect(node2!.data).toBe("Code");
});
it("Should return null for invalid index", () => {
const nodenve = singlyLinkedList.get(-1);
expect(nodenve).toBeNull();
const nodelarge = singlyLinkedList.get(999999);
expect(nodelarge).toBeNull();
});
});
describe("Search item in SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should return correct index of the item", () => {
const search0 = singlyLinkedList.search("Big");
expect(search0).toBe(0);
const search2 = singlyLinkedList.search("Code");
expect(search2).toBe(2);
});
it("Should return null for non existing item", () => {
const searchResult = singlyLinkedList.search("Non existing item");
expect(searchResult).toBeNull();
});
});
describe("Set item to SinglyLinkedList by index", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should set value at node properly", () => {
const set0 = singlyLinkedList.set(0, "New Val");
expect(set0).toBeTruthy();
const get0 = singlyLinkedList.get(0);
expect(get0!.data).toBe("New Val");
const set2 = singlyLinkedList.set(2, "Second");
expect(set2).toBeTruthy();
const get2 = singlyLinkedList.get(2);
expect(get2!.data).toBe("Second");
const setN = singlyLinkedList.set(99, "Out Bound");
expect(setN).toBeFalsy();
});
it("Should handle empty list without any exception", () => {
singlyLinkedList = new SinglyLinkedList<string>();
const set0 = singlyLinkedList.set(0, "Out Bound");
expect(set0).toBeFalsy();
});
});
describe("Insert item to SinglyLinkedList by index", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
});
it("Should insert data at index", () => {
const insert0 = singlyLinkedList.insert(0, "Big");
expect(insert0).toBeTruthy();
const get0 = singlyLinkedList.get(0);
expect(get0!.data).toBe("Big");
const insert1 = singlyLinkedList.insert(1, "Code");
expect(insert1).toBeTruthy();
const get1 = singlyLinkedList.get(1);
expect(get1!.data).toBe("Code");
const insert1_1 = singlyLinkedList.insert(1, "Box");
expect(insert1_1).toBeTruthy();
const get1_1 = singlyLinkedList.get(1);
expect(get1_1!.data).toBe("Box");
const get1_2 = singlyLinkedList.get(2);
expect(get1_2!.data).toBe("Code");
const setN = singlyLinkedList.insert(99, "Out Bound");
expect(setN).toBeFalsy();
});
it("Should have proper length after insert", () => {
singlyLinkedList.insert(0, "Big");
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.insert(1, "Code");
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.insert(1, "Box");
expect(singlyLinkedList.length).toBe(3);
singlyLinkedList.insert(99, "Out Bound");
expect(singlyLinkedList.length).toBe(3);
});
});
describe("Remove item from SinglyLinkedList by index", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should remove data at index", () => {
const remove2 = singlyLinkedList.remove(2);
expect(remove2!.data).toBe("Code");
const get2 = singlyLinkedList.get(2);
expect(get2).toBeNull();
const remove0 = singlyLinkedList.remove(0);
expect(remove0!.data).toBe("Big");
const get0 = singlyLinkedList.get(0);
expect(get0!.data).toBe("Box");
const removeN = singlyLinkedList.remove(99);
expect(removeN).toBeFalsy();
});
it("Should have proper length after remove", () => {
singlyLinkedList.remove(1);
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.remove(99);
expect(singlyLinkedList.length).toBe(2);
});
});
describe("Reverse SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
singlyLinkedList.push("Singly");
singlyLinkedList.push("Linked");
singlyLinkedList.push("List");
});
it("Should set head properly", () => {
singlyLinkedList.reverse();
expect(singlyLinkedList.head!.data).toBe("List");
});
it("Should set tail properly", () => {
singlyLinkedList.reverse();
expect(singlyLinkedList.tail!.data).toBe("Big");
});
it("Should set all elements properly", () => {
singlyLinkedList.reverse();
const get1 = singlyLinkedList.get(1);
expect(get1!.data).toBe("Linked");
const get2 = singlyLinkedList.get(2);
expect(get2!.data).toBe("Singly");
const get4 = singlyLinkedList.get(4);
expect(get4!.data).toBe("Box");
});
it("Should not change the length", () => {
singlyLinkedList.reverse();
expect(singlyLinkedList.length).toBe(6);
});
});
});
TypeScriptTime Complexity
The time complexity of operation on a Singly Linked List is as below-
Operation | Complexity |
---|---|
Insertion | O(1) |
Removal | O(N) |
Search | O(N) |
Access element | O(N) |
Source Code
Use the following links to get the source code used in this article-
Source Code of | Implementation Code | Demo Code | Test Code |
---|---|---|---|
JavaScript Implementation | GitHub | GitHub | GitHub |
TypeScript Implementation | GitHub | GitHub | GitHub |
Related Data Structures
Command | Details |
---|---|
Doubly Linked List | Doubly Linked List Detail |
Other Code Implementations
Use the following links to check the Singly Link List implementation in other programming languages-