DEV Community

Code_Regina
Code_Regina

Posted on

Doubly Linked Lists

                   -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.

Alt Text

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

Discussion (7)

Collapse
joelbonetr profile image
JoelBonetR

Nice job on that,
You can add a getLast function as well, simply:

getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
}
Enter fullscreen mode Exit fullscreen mode

Just out of curiosity, in your bio says you are on a bootcamp learning to become a developer, using custom data structures is something more advanced that is not usually covered in bootcamps, are you finishing it and preparing yourself to find a job?

Collapse
code_regina profile image
Code_Regina Author

No, I am just trying to learn a little bit of everything for now.

Collapse
joelbonetr profile image
JoelBonetR

Oh nice, Let me recommend you a book then, it helps people understanding the IT building blocks and adds a global understanding of some complex processes following a bottom-up arrangement of subjects that progresses from the concrete to the abstract, resulting in a sound pedagogical presentation in which each topic leads to the next.

pearson.com/store/p/computer-scien...

And if you want to specialize in JS you can check afterwards the JavaScript The Definitive Guide from O'Reilly 😄

Collapse
3z1ooo profile image
Ezio

Why getLast?
Wouldn't that be: "this.tail". ?

Collapse
joelbonetr profile image
JoelBonetR • Edited on

The only difference is the name you want to use unless you index it on a circular linked list, where you'll expect to get the last added (last index) and head/tail doesn't exist.
The same way I would name getFirst to my method to get the head one, it's more plain language. Of course, it's just my opinion or likening, not something to blind follow (unless again, you use a circular linked list, doubly or not, where there's no such thing like head or tail).

As it's a custom data structure and the methods/functions are custom as well, you can name it potato if you want.

*It is highly not recommended to name a method/function "potato", please use semantically correct names.

Thread Thread
3z1ooo profile image
Ezio

If we had stack we can use getLast.
What you did .i.e: "getLast" , was useless; to redo the same thing but only more complex.
This way we can add getSecond, getThird, get fourth, getFifth ...
Guess what? We dont need that, and that's why it's a double linked list.

*This comment unlike the previous one has nothing todo with potato

Thread Thread
joelbonetr profile image
JoelBonetR • Edited on

getLast / getTail has the same utility than getFirst / getHead, you can implement it or not, just depends on the need of getting some specific position, no matter the index being first, last, in the middle or in any other arbitrary position.
If for any reason you need to check the second element multiple times then sure, go and implement a getSecond. Or simply implement a search method and ask for the second one, which will be the same.

Is a non sense to argue about that since we are not talking about a specific use case. On the other hand, being a double linked list has nothing to do with the utility of those hypothetical methods. Again, they only have no sense when talking about circular lists, which is not the case.

Just to clarify, a circular doubly linked list is the same than a doubly linked list but the head and the tail are considered as prev/next between them (so you'll always have a "next" or a "prev" item as there's no end, thus there are no start point and you need to consider the number of items to avoid infinite looping.
You can learn more about here: humanwhocodes.com/blog/2019/03/com....

Best regards