in

Doubly Linked Lists – DEV Community


                   -Intro to Doubly Linked List 
                   -Doubly Linked List: Push
                   -Doubly Linked List: Pop
                   -Doubly Linked List: Shift
                   -Doubly Linked List: Unshift
                   -Doubly Linked List: Get Intro
                   -Doubly Linked List: Set Intro
                   -Doubly Linked List: Insert Intro
                   -Doubly Linked List: Remove Intro
                   -Doubly Linked List: Reverse Intro
                   -Doubly Linked List: BIG O Complexity
Enter fullscreen mode

Exit fullscreen mode



Intro to Doubly Linked List

Doubly Linked List is a data structure that is similar to a singly linked list but doubly linked list adds an additional pointer to the previous node as well as the next node. Therefore each node will point in either direction.

There is no indexing.
There is an head and tail.



Doubly Linked List: Push


class Node{
    constructor(val){
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}


class DoublyLinkedList {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(this.length === 0){
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
}


Enter fullscreen mode

Exit fullscreen mode



Doubly Linked List: Pop


    pop(){
        if(!this.head) return undefined;
        var poppedNode = this.tail;
        if(this.length === 1){
            this.head = null;
            this.tail = null;
        } else {
            this.tail = poppedNode.prev;
            this.tail.next = null;
            poppedNode.prev = null;
        }
        this.length--;
        return poppedNode;
    }
}

Enter fullscreen mode

Exit fullscreen mode



Doubly Linked List: Shift


    shift(){
        if(this.length === 0) return undefined;
        var oldHead = this.head;
        if(this.length === 1){
            this.head = null;
            this.tail = null;
        }else{
            this.head = oldHead.next;
            this.head.prev = null;
            oldHead.next = null;
        }
        this.length--;
        return oldHead;
    }
}

Enter fullscreen mode

Exit fullscreen mode



Doubly Linked List: Unshift


    unshift(val){
        var newNode = new Node(val);
        if(this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
}

Enter fullscreen mode

Exit fullscreen mode



Doubly Linked List: Get Intro



   get(index){
        if(index < 0 || index >= this.length) return null;
        var count, current;
        if(index <= this.length/2){
            count = 0;
            current = this.head;
            while(count !== index){
                current = current.next;
                count++;
            }
        } else {
            count = this.length - 1;
            current = this.tail;
            while(count !== index){
                current = current.prev;
                count--;
            }
        }
        return current;
    }
}

Enter fullscreen mode

Exit fullscreen mode



Doubly Linked List: Set Intro



    set(index, val){
        var foundNode = this.get(index);
        if(foundNode != null){
            foundNode.val = val;
            return true;
        }
        return false;
    }
}


Enter fullscreen mode

Exit fullscreen mode



Doubly Linked List: Insert Intro


    insert(index, val){
        if(index < 0 || index > this.length) return false;
        if(index === 0) return !!this.unshift(val);
        if(index === this.length) return !!this.push(val);

        var newNode = new Node(val);
        var beforeNode = this.get(index-1);
        var afterNode = beforeNode.next;

        beforeNode.next = newNode, newNode.prev = beforeNode;
        newNode.next = afterNode, afterNode.prev = newNode;
        this.length++;
        return true;
    }
}

Enter fullscreen mode

Exit fullscreen mode



Doubly Linked List: BIG O Complexity

Alt Text



Source: https://dev.to/code_regina/doubly-linked-lists-217c

Leave a Reply

Your email address will not be published. Required fields are marked *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

GIPHY App Key not set. Please check settings

Event-driven integration platform powered by Kubernetes and Knative

A basic calculator using CSS, styled-components and react