Understanding a Singly Linked List

To better understand something, sometimes you have to attempt to teach it to others. So....in saying that I want to give a crash course of a linked list data structure.

What is a linked list? A linked list is chained or linked nodes filled with data that reference each other. Unlike arrays where they each index takes up a part in memory, linked list use pointers to reference that data which makes them faster performance wise compared to arrays in some cases. A great way to visualize this is just think of a train that has cars linked with the clamps between the cars. These clamps are the pointers in the case of singly linked list.

So how do we start building these linked list? From here I will use Object Orientated Programming, or simply OOP since linked list are composed of a 2 classes. Those classes are a Node class, and a Linked List class.

class Node{
  constructor(element){
    this.element = element
    this.next = next

  }
}

class LinkedList {
    constructor(head){
      this.head = head || null
      this.tail = null
      this.length = 0

    }
}

What's going on in the previous code is the node class is creating your nodes, and your linked list class you are establishing the head because will will need to append the nodes to that head eventually.

There are some properties of a linked list you will need to remember before we get deeper.

• First property is nodes are connected by pointers
• The last node will always point to null
• The head is always maintained and is pointing the the first node of the list. If you you were to get rid of this head, the train is basically not going anywhere
• Lastly Linked List and spread out memory where needed unlike an array.
• The size of the list can get bigger or smaller

We will focus on two operations for linked list with is inserting and deleting.

The first operation which we will call append is basically adding a node behind another node. The pointer from the previous node will point to the new node as the tail.

// Within the linked list class

 append(val){
      let node = new Node(val)

      if (!this.head || !this.tail){
       this.head = node
       this.tail = node
       this.length = 1
      }else{
        this.tail.next = node
        this.tail = node
        this.length++
      }
    }

const train = new LinkedList()

train.append(1)
console.log(train)

//output
{"head":{"el":1,"next":null},"tail:{"el":1,"next":null},"length":1}

In this snippet we defined our append function which is simply appending a new node at the end of the list. The edge case here is in the event the no head is established, the first node will become the head and the size of the list will be 1. On the other hand if the head is established, then the head will point to the new node and that node will become the tail.

Delete on the other hand is a little more but not as involved as the case of doubly linked list which I will blog about pretty soon.

remove(index){
      //keep track of previous pointer
      let deletedNode;
      //deletes from the beginning
      if (index === 0){
        deletedNode = this.head
        let nextNode = deletedNode.next;
        this.head = nextNode
      }else if (index !== this.length -1){
        let current = this.head
        let count = 0

        while(count !== index -1){
          count++
          current = current.next
        }

        let prevNode = current
        deletedNode = prevNode.next
        let nextNode = deletedNode.next

        prevNode.next = nextNode
      }

      this.length--
      return deletedNode

    }

I am going to sum this part up a bit. You have the abilty to delete from whichever index and when you go through the code for the delete depending if its in the middle, beginning or the end, you need to remember to reestablish connection to other nodes and the key here is you will need to keep track of the previous pointers in the middle, and the tail. As mentioned before, let say I have four nodes and I delete node 3, you will need to establish the connection between node 2 and 4. Or if you are deleting current head you will need to designate the next node as the new head.

Well I hope this crash course was enough to get people started, I will at some point touch on this in greater detail.