Data Structures Two Ways: Linked List (Pt 1)
Tags: java, javascript, computerscience, learning
Published: 2020-08-11 21:12:57

---
title: Data Structures Two Ways: Linked List (Pt 1)
published: true
description: Exploring Data Structures in Java and JavaScript 
tags: java, javascript, computerscience, learning
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/fszrltarno3vx7s09h09.jpg
---

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. 

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

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

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

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

So lets put it all together...

```JS
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...
```JS
'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.

```JS
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

```JS
while(current) {
    values.push(current.value);
    current = current.next;
}
``` 
finally we will return the `values` array joined together as a string. 

```JS
return values.join(' => ');
```
Now lets put it all together and try out creating a linked list and printing it out

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