Data Structures Decoded: Singly Linked Lists I

Photo by Pankaj Patel on Unsplash

Data structures: the other cornerstone of a competent software engineer. This is why I’m compiling all my research and work on the topic in a series of articles titled Data Structures Decoded.

In today’s article, we’ll be exploring the basics of a Singly Linked List.

What is it?

A linked list is a ordered data structure that stores any kind of data you’d like. It contains a head, a tail, and a length property. Linked lists consists of nodes and each node has a value and a pointer to another node or null.

A useful exercise to increase our understanding of a singly linked list is comparing it with an array:

• Arrays are indexed in order, insertion/deletion can be expensive, and can be quickly accessed at a specific index.
• On the other hand, lists do not have indexes, are connected via nodes with a next pointer, and random access is not allowed.

Why is it important?

According to Wikipedia:

The principal benefit of a linked list over a conventional array is that the list elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk, while restructuring an array at run-time is a much more expensive operation. Linked lists allow insertion and removal of nodes at any point in the list, and allow doing so with a constant number of operations by keeping the link previous to the link being added or removed in memory during list traversal.

The downside, though, makes it important to know when to choose the correct tool for the job:

On the other hand, since simple linked lists by themselves do not allow random access to the data or any form of efficient indexing, many basic operations — such as obtaining the last node of the list, finding a node that contains a given datum, or locating the place where a new node should be inserted — may require iterating through most or all of the list elements.

How do we create Singly Linked Lists?

We could define a class of Node like so…

class Node { 
    constructor(val){
        this.val = val; 
        this.next = null; 
    }
}

…and then just add more nodes like this….

let first = new Node("Hi")
first.next = new Node("there")
first.next.next = new Node("how")
first.next.next.next = new Node("are")
first.next.next.next.next = new Node("you")

…but this is inefficient.

Luckily, with a SinglyLinkedList class instead, we can define instance methods for pushing new values to the end of the list, for instance:

class SinglyLinkedList{ 
    // singlylinkedlists are not initialized with any data                constructor() { 
        this.length = 0; 
        this.head = null; 
        this.tail = null; 
    }
    push(val){ 
        // the function should accept a value
        // create a new node with val passed 
        let newNode = new Node(val); 
        // edge case: if no head (empty list), set head + tail to be newly create node
        if (!this.head) { 
            this.head = newNode; 
            this.tail = this.head; 
        // edge case: if no head (empty list), set head + tail to be newly create node
        } else { 
            this.tail.next = newNode; 
            this.tail = newNode; 
        }
        this.length++; 
        return this; 
        // increment by 1
    }
}

By creating code for a .push() an instance of SinglyLinkedList, you can do more familiar things like this:

let list = new SinglyLinkedList();
list.push("Hello")
list.push("Goodbye")

Isn’t that better?

What do you think? If you liked what you read, consider connecting or dropping me a line at nick.echev AT gmail.com!