This content originally appeared on DEV Community and was authored by Rivier Grullon
Definition
A linked list is a linear data structure that represents a collection of elements that we'll call nodes , where each node points to the next one or previous one, the first node in the linked list is the head and the last is the tail
In the linked list each node must be have the following properties:
- Value: The value of the node
- next: A pointer to the next node in the linked list(null is there no one)
The main properties of the linked list are:
- Size: The number of nodes in the linked list
- Head: The first node
- Tail: The last node
and the main operations of a linked list data structure are:
insertAt: Inserts a node at the specific index.
removeAt: Removes the node at the specific index.
getAt: Retrieves the element at the specific index.
Clear: Empties the linked list
Reverse(in this case): Reverses the order of nodes in the linked list
Implementation
class LinkedList {
constructor() {
this.nodes = [];
}
get size() {
return this.nodes.length;
}
get head() {
return this.size ? this.nodes[0] : null;
}
get tail() {
return this.size ? this.nodes[this.size - 1] : null;
}
insertAt(index, value) {
const previousNode = this.nodes[index - 1] || null;
const nextNode = this.nodes[index] || null;
const node = { value, next: nextNode };
if (previousNode) previousNode.next = node;
// console.log(previousNode);
this.nodes.splice(index, 0, node);
}
insertFirst(value) {
this.insertAt(0, value);
}
insertLast(value) {
this.insertAt(this.size, value);
}
getAt(index) {
return this.nodes[index];
}
removeAt(index) {
const previousNode = this.nodes[index - 1];
const nextNode = this.nodes[index + 1] || null;
if (previousNode) previousNode.next = nextNode;
return this.nodes.splice(index, 1);
}
removeFirst() {
this.removeAt(0)
}
removeLast() {
this.removeAt(this.size - 1)
}
clear() {
this.nodes = [];
}
reverse() {
this.nodes = this.nodes.reduce((acc, {value}) => [{value, next: acc[0]}], [])
}
*[Symbol.iterator]() {
yield* this.nodes;
}
}
Create a class with a constructor that initializes an empty array, nodes, for each instance.
Define a size getter, that returns that uses Array.prototype.length to return the number of elements in the nodes array.
Define a head getter, that returns the first node of the nodes array or null if empty.
Define a tail getter, that returns the last element of the nodes array or null if empty.
Define an insertAt() method, which uses Array.prototype.splice() to add a new object in the nodes array, updating the next key of the previous element.
Define two convenience methods, insertFirst() and insertLast() that use the insertAt() method to insert a new element at the start or end of the nodes array respectively.
Define a getAt() method, which retrieves the element in the given index.
Define a removeAt() method, which uses Array.prototype.splice() to remove an object in the nodes array, updating the next key of the previous element.
Define a clear() method, which empties the nodes array.
Define a reverse() method, which uses Array.prototype.reduce() and the spread operator (...) to reverse the order of the nodes array, updating the next key of each element appropriately.
Define a generator method for Symbol.iterator, which delegates to the nodes array's iterator using the yield* syntax.
const list = new LinkedList();
list.insertFirst(1);
list.insertFirst(2);
list.insertFirst(3);
list.insertLast(4);
list.insertAt(3, 5);
list.size; // 5
list.head.value; // 3
list.head.next.value; // 2
list.tail.value; // 4
[...list.map(e => e.value)]; // [3, 2, 1, 5, 4]
list.removeAt(1); // 2
list.getAt(1).value; // 1
list.head.next.value; // 1
[...list.map(e => e.value)]; // [3, 1, 5, 4]
list.reverse();
[...list.map(e => e.value)]; // [4, 5, 1, 3]
list.clear();
list.size; // 0
This content originally appeared on DEV Community and was authored by Rivier Grullon
Rivier Grullon | Sciencx (2021-10-09T22:09:27+00:00) Javascript Data Structure – Linked list. Retrieved from https://www.scien.cx/2021/10/09/javascript-data-structure-linked-list/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.