The Startup
Published in

The Startup

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.

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.

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 nodeclass LinkedListNode {
constructor(data) {
this.data = data
this.next = null
}
}
// this gives us the framework to create our listclass 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 boxlet 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 5let secondNode = new LinkedListNode(5)
firstNode.next = secondNode
// last we will instantiate our linked listlet newList = new LinkedList(firstNode)// the result of this structure will look like thisnewList = 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.

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Gabriel Hicks

Gabriel Hicks

Software Engineer from Iowa, living in NYC. Interested in new technologies and exploring opportunities to grow. https://gabrielhicks.dev