DEV Community: Freddie Duffield

Data Structures Two Ways: Linked List (Pt2)

Freddie Duffield — Wed, 12 Aug 2020 20:46:13 +0000

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(' => ');
        }
    }
}

Data Structures Two Ways: Linked List (Pt 1)

Freddie Duffield — Tue, 11 Aug 2020 21:12:57 +0000

I work primarily with JavaScript, but the place I work is using Java on the backend. Always being fascinated with different programming languages and different ways of getting things done - I have decided to learn java! My team's tech lead suggested - why not try and do everything you can do in JavaScript in Java. So I am! Alongside this, as someone without a CS degree, the more I dig into software engineering the more I become curious about the fundamentals. So this series of blog posts sets out to explore data structures in Java and JavaScript.

Following the old adages of software development: "breaking down problems into the smallest possible pieces" and "better shipped than perfect", I will iterate incrementally and add one or two methods to each structure each time I write. JavaScript first, then on to the Java. This may take a while, so hold on to your butts!

Singly Linked List

🤔 WTF?

Picture this: You are meeting a friend on a train to leave the city for weekend but a sequence of unfortunate events means you arrive at Waterloo stations only moments before the train is due to depart from the station. After you barge through crowds and barriers, you manage to hop on the first carriage of the train moments before it pulls out of the station. phew 😅. You check your phone. Your friend has texted you that they are sitting in carriage D. You look around and a sign indicates that you are in carriage A. You precede to traverse the train carriage by carriage until you reach carriage D and find your friend. Hi!

A linked list is bit like a train, it consists of parts - or nodes- each part only know about the next one. It is group of nodes that collectively represent a sequence. These nodes don't necessarily need always sit one after the other, that is occupy the same physical placement in memory, they just know what comes next.

🧐 Use Cases

A linked list is gateway data structure on top of which other data structures can be built. A good example of this is a first in first out queue, the type you could experience everywhere in programming .

A linked list is really efficient if you want to add something at the beginning or the end. You can just make the new node the head and what was the head next of the new node. In comparison to an array, to insert at the beginning you would need to re-index each and every item with in that array.

🥺 Features

Here the methods I propose to implement for the singly linked list:

append add a node to the end of the linked list.
to string convert the linked list into a readable format.
pop remove the last element from the list.
unshift add a node to the beginning of the linked list.
shift remove the first element from the list.
insert insert an element at specific index.
remove remove a value from a specific index.
reverse reverse the list.

📜 JavaScript

Create Node

First of all we need a way to create node. I am going to declare a function createNode, which take the parameters value, and next. It will return an object containing the value and next value.

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

Create Linked List

Now let's make a function that will make use of createNode to instantiate the link list object itself. The createLinkedList function will not take any parameters and will return an object initially with a head, tail and length property.

function createLinkedList() {
    return {
        head: null,
        tail: null,
        length: 0
    }
}

Now our list is ready to receive some methods!

Push or Append

Push in JavaScript Array speak means adding to the end of an array. We could also call this append as it will add a new node the end of our list.

First things first lets create our new node

   const node = createNode(value);

Then let's handle what happens if there is nothing in the list, in other words if there is no head. If there is no head then our new node will the head and the tail and we will need to increase length by 1. Finally we will return the node to exit the code.

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

    return node;
}

Now what will happen if there is already stuff in our list?
We will want to make the current tail reference the new node as it next property and the new node will be come the tail. Then we will in increase the length and thats our push method done.

this.tail.next = node;
this.tail = node;
this.length++

So lets put it all together...

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;
        },
    }
}

To String

Now we have got a way to create a linked list and add new nodes to the end of it would nice to have a method that we can show us what we have got in our list in readable fashion. Enter the to string method.

Basically the idea is to print each item with => in between, so a basic list would look like this...

'1 => 2 => 3'

first we'll create an empty array to store the values of each node and create a variable current that we will use as we move across the list. we will initial set to the head.

const values = [];
let current = this.head;

next we will move from node to node and add each value into the values array. To this we will use a while loop. The next door to the tail of the linked list is null, we will use this to break the while loop

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

finally we will return the values array joined together as a string.

return values.join(' => ');

Now lets put it all together and try out creating a linked list and printing it out

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;
        },
        toString() {
            const values = [];
            let current = this.head;

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

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

const list = createLinkedList();
list.push(1)
list.push(2)
list.push(3)
console.log(list.toString());

//prints '1 => 2 => 3' to the console.