Anatomy of a Singly Linked List in JS

A closer look at the linear data structure

https://www.educative.io

Singly Linked List

A linked lists is a linear data structure that consists of units of data (nodes) that are chained together and implemented through storing information as well as holding reference to other nodes. In the above image, the number 5 is the head of our linked list. The right half of the node, illustrated by the arrow, holds a reference to the purple node containing the number 7. At the end of our linked list, the green number 15 holds a null reference, indicating that it is the end of the list. This demonstrates the fundamental structure of a singly linked list.

https://www.educative.io

Doubly Linked Lists

It is important to note that linked lists do not have to strictly move in one direction. Although singly linked lists may be implemented more frequently in other data structures, it is possible that each node can carry a reference to the node in front of it, as well as the node behind it. Doubly linked lists inferring by name alone, do take up more memory and are not as useful as singly linked lists when sorting large amounts of data.

https://www.interviewbit.com/tutorial/arrays-vs-linked-lists/

Arrays VS Linked Lists

Linked lists and arrays from an outside perspective can seem very similar. Both store information in a linear direction, but there are many differences and reasons why a person would want to use one over the other. Arrays are indexed, and any addition of deletion of an item in an array, requires a re-indexing of every other element. Linked lists however, can easily insert and delete information, simply by changing references in nodes.

When accessing a particular item in a collection, or needing to sort a collection, arrays are the best choice. The time complexity of accessing an index of an array is O(1). While accessing a particular node in a linked list, you must start at the head, or tail and move through each item, making the time complexity for accessing O(n). In the previous example, when inserting or deleting an item from toward the end of a collection, the time complexity is reversed and linked lists are more efficient than arrays.

A Singly Linked List

// here we are constructing the structure of the node for our linked list. each node contains data, as well as a place to store a reference to another node

class LinkedListNode {

    constructor(data) {

        this.data = data

        this.next = null


    }

}

// this gives us the framework to create our list

class LinkedList {

    constructor(head) {

        this.head = head


    } 

}

// here we will create the first node of our new list with a value of 2, using the class we created in the first code box

let firstNode = new LinkedListNode(2)

// next we will create a second node, and assign it to the value of the referenced "next" node with a value of 5

let secondNode = new LinkedListNode(5)

firstNode.next = secondNode

// last we will instantiate our linked list

let newList = new LinkedList(firstNode)

// the result of this structure will look like this

newList = LinkedList {

            head: LinkedListNode {

              data: 2,

              next: LinkedListNode { data: 5, next: null }

             }

           }

Conclusion

The fundamental anatomy and structure of a singly linked list is important. As I learn more about data structures and specifically linked lists, I hope to write more in depth about their use cases and time complexity when it comes to implementation. As a person who is very fond of arrays, I found the wealth of knowledge on the internet written comparing the two compelling. I enjoyed seeking to understand the basic idea of a singly linked list, and hope to continue taking you all along with me in my journey.

Sources/References:

What is a linked list?
What is a linked list?www.educative.io
Intro to Linked Lists via JavaScript - Part 1: Overview | DigitalOcean
*While this tutorial has content that we believe is of great benefit to our community, we have not yet tested or edited…*www.digitalocean.com
Intro to Linked Lists via JavaScript - Part 2: Implementation | DigitalOcean
*While this tutorial has content that we believe is of great benefit to our community, we have not yet tested or edited…*www.digitalocean.com
How to Implement a Linked List in JavaScript
*If you are learning data structures, a linked list is one data structure you should know. If you do not really…*www.freecodecamp.org

I am always happy to connect, you can find me on Twitter, LinkedIn, or my portfolio!