Data Structures Two Ways: Linked List (Pt 1)

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.