Your Web News in One Place

An Interest In:

Web News this Week

Search Archive

Some of Our Sources

View All Sources

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
October 13, 2021 04:17 pm GMT

Javascript Data Structure - Doubly Linked list

Definition

Doubly linked list is a type of linked list in which each node apart from storing its data has two pointers. The first pointer points to the previous node in the list and the second pointer points to the next node in the list. The head node its previous value points to NULL and similar to the tail node its next value points to null.

image

and saving a second reference to nodes requires more space in memory.

let's recap the main properties of the linked list:

The main properties of the linked list are:

  • length: The number of nodes in the linked list
  • Head: The first node
  • Tail: The last node

See more in my last post Javascript Data structure - Linked list

in this case the nodes will be contain the next properties:

  • next: pointer to the next node
  • value: actual value of the node
  • prev: pointer to the previous node

and the main operations here are:

  • append: Add a node to the end in the linked list

  • prepend: Add a node to the beggining the linked list

  • removeFirst: remove the first node (head)

  • removeLast: remove the last node(tail)

  • search: find a node by his value and returned

  • remove: remove a node by its value from the linked list

Implemetation

class LinkedList {    constructor() {        this.head = null;        this.tail = null;        this.length = 0;    }    //** add at the end of the linked list */    append(value) {        // if empty        if (!this.tail) {            this.tail = { value };            this.head = this.tail;        } else {            let oldTail = this.tail;            this.tail = { value };            oldTail.next = this.tail;            this.tail.prev = oldTail;        }        this.length++;    }    //** add to the beggining  */    prepend(value) {        if (!this.head) {            this.tail = { value };            this.head = this.tail;        } else {            let oldHead = this.head;            this.head = { value };            oldHead.prev = this.head;            this.head.next = oldHead;        }        this.length++;    }    removeFirst() {        if (!this.head) {            throw new Error("The list is empty");        } else {            let tempHead = this.head;            // ** when theres only one node            if (this.head === this.tail) {                this.head = null;                this.tail = null;            } else {                this.head = this.head.next;                this.head.prev = null;            }            this.length--;            return tempHead.value;        }    }    removeLast() {        if (!this.tail) {            return null;        } else {            let tempTail = this.tail;            if (this.tail === this.head) {                this.tail = null;                this.head = null;                this.length--;            } else {                this.tail = this.tail.prev;                this.tail.next = null;                this.length--;                return tempTail.value;            }        }    }    search(value) {        let currentNode = this.head;        while (currentNode) {            if (currentNode.value === value) {                return currentNode;            }            currentNode = currentNode.next;        }        return null;    }    remove(value) {        let tempNode = this.search(value);        if (tempNode === this.tail) {            this.removeLast();            return;        } else if (tempNode === this.head) {            this.removeFirst();            return;        } else {            tempNode.prev.next = tempNode.next;            tempNode.next.prev = tempNode.prev;        }        this.length--;    }}
  • Create a class with a constructor that initializes the head, tail and length of the linked list.

  • Define a method search() that iterate through the list to find a specific node.

  • Define two convenience methods, append() and prepend() that use to insert a new element at the start or end of the nodes respectively and increase the length.

Define a method remove() that uses the search to find the node and replacing its value to delete it.

  • Define two convenients methods removeFirst() and removeLast() to remove the head or the tail.
let list = new LinkedList();list.append(1);list.append(2);list.append(23);list.append(3);list.prepend(55);list.append(2);list.append(22);list.remove(22);console.log(list);

In my last post of linked list I made a mistake writting the linked list, the point of the linked list is to avoid arrays, so in this post I want to make up for my mistake :) this series is for learning and thank u all for the feedbacks.


Original Link: https://dev.to/riviergrullon/javascript-data-structure-doubly-linked-list-7bh

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To