Data Structures Two Ways: Linked List (Pt2)

If you are new- well hello! check out part one if you like to start at the beginning or just jump straight in

Pop

Right on with the next method - pop. If you are familiar with JavaScript, no doubt you might know the array method pop. It removes and returns the last item in the array. Here is a quick cake based demo.

const cakes = ['sponge', 'chocolate', 'jam roly-poly'];

cakes.pop()
// "jam roly-poly"

console.log(cakes); 
// ['sponge', 'chocolate']

Hope that gives an idea and doesn't make you too hungry! Anyway lets implement a pop method for our Linked List.

In order to pop we can just return the tail, right? wrong! We can't just return the tail because we need to make the node before last the tail and the current tail doesn't have access to what goes before it. That means we need to make our way through the linked list to the one before last and make that our tail. Here's some pseudo code:

• if there is one item - remove the item
• Traverse the list to find the penultimate node
• make the penultimate node the tail
• return the node

lets go...

const node = this.tail; 

We'll start by saving the node that is currently the tail because that is the one we will need to return. Then lets deal with if the there is on one item in the list

if(this.head === this.tail) {
    this.head = null;
    this.tail = null;
    this.length--; 
    return node
}

Great, now lets traverse the list to find the penultimate node. Go!

let current = this.head;
let penultimate; 

We'll start at the head like boarding the train and create a variable to save the value of penultimate node when we find it. Now we will initiate a while loop to check each value one by one. How will we know when we have found the penultimate? when the node next to the current node is the tail.

while(current) {
    if(current.next === this.tail) {
        penultimate = current;
        break;
    }
    current = current.next;
}

Whoop whoop, now we safely have our penultimate value stored away. We can make it a tail, pop off the old node and decrease the length.

penultimate.next = null;
this.tail = penultimate;
this.length--;

return node;

And that's our pop function.

unshift

So here's where we are at:

• push ✅
• toString ✅
• pop ✅

next prepend or JavaScript array speak unshift. This method is the opposite of pop(), it will add a node at the beginning of the linked list.

So unshift in the linked list is easy, we like getting on in the first carriage. The function will take one parameter, of the value we would like to add. We'll take that value and make new node, assign that to the head, increase the length and return the list.

unshift(value) {
    const node = createNode(value, this.head);
    this.head = node;
    this.length++;

    return this;
}

What is if the list is empty said nobody. Well then the new node is the tail as well.

if(!this.tail) {
    this.tail = node;
}

cool cool cool, let wrap this up and put it all together...

function createNode(value, next = null) {
    return {
        value,
        next
    }
}

function createLinkedList() {
    return {
        head: null,
        tail: null,
        length: 0,
        push(value) {
            const node = createNode(value);

            if (!this.head) {
                this.head = node;
                this.tail = node;
                this.length++

                return this;
            }

            this.tail.next = node;
            this.tail = node;
            this.length++;
            return this;
        },
        pop(){

            const node = this.tail;

            if (this.head === this.tail) {
                this.head = null;
                this.tail = null;
                this.length--;
                return node;
            }

            let current = this.head;
            let penultimate;

            while(current) {
                if(current.next === this.tail) {
                    penultimate = current;
                    break;
                }

                current = current.next;
            }

            penultimate.next = null;
            this.tail = penultimate;
            this.length--;

            return node;
        },
        unshift(value) {
            const node = createNode(value, this.head);
            this.head = node;
            this.length++;

            if(!this.tail) {
                this.tail = node;
            }

            return this;
        },
        toString() {
            const values = [];
            let current = this.head;

            while(current) {
                values.push(current.value);
                current = current.next;
            }

            return values.join(' => ');
        }
    }
}