DEV Community

Cover image for Javascript Data Structure - Linked list
Rivier Grullon
Rivier Grullon

Posted on • Updated on

Javascript Data Structure - Linked list

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

image

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;
    }
}
Enter fullscreen mode Exit fullscreen mode
  • 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

Enter fullscreen mode Exit fullscreen mode

Discussion (8)

Collapse
jcubic profile image
Jakub T. Jankiewicz

Real linked list should not use Arrays to keep the nodes. You have duplication that you need to keep in sync array of nodes and linked node. So IMHO this implementation doesn't make sense. You should only have two variable in LinkedList head and tail that are references to first and last item.

Collapse
marcosteinke profile image
Marco Steinke

This is completely true. The whole point of a linked list is that you have nodes which always consist of an element which can be of any data type and a pointer to the next node (if there is)

The linked list itself only consists of a pointer to the head node (if not empty) and some methods to insert and remove nodes. There may also be a instance variable which counts the length of the linked list.

Using this Implementation you directly realize the idea of dynamic data structures against the idea of arrays.

But still thank you for the nice read :)
Greetings :)

Collapse
riviergrullon profile image
Rivier Grullon Author

Like I said in the comment below I started to learning data structures, this is a simple way to introduce the people of kinda understand of how linked works, but I really appreciate the feedbacks xd

Collapse
jcubic profile image
Jakub T. Jankiewicz • Edited on

The problem is that this is not how to teach data structures like linked lists, it's unneceraly confusing. Wikipedia have good article with some implementation of linked lists. Your code is not even close. Another example is Rosseta Code

Collapse
kkrypt0nn profile image
Krypton

The post is interesting and everything, but I think the point of making a linked list is not to use arrays. You should change that :)

Collapse
invm profile image
Michael

Looking good!

Just one little issue that I've noticed, is that if you remove the last node, you should consider the case that it has a previous node that points to it, and like in the case of removeAt(index), you should change the previous' node next value to null.

How about showing us more structures?

Collapse
riviergrullon profile image
Rivier Grullon Author

Thank you!, Sure I was thinking to make a series of data structure ´cuz I recently started to learning and writing post and receiving feedbacks helps me to get better :)

Collapse
talorlanczyk profile image
TalOrlanczyk

Hi love this article but i would do a small change to the code
Instead of
Something ? X: null
You can do
something && x