Data Structures: Singly Linked Lists

As part of my journey as a Junior Developer, I decided that I would learn and write up a series of articles regarding Data Structures and Algorithms as they are one of the most fundamental Computer Science concepts to learn, especially if you do not come from a traditional Computer Science or Electrical Engineering background.

So this starting point is about Singly Linked Lists. What are they?

A Singly-Linked List is a Data Structure. It is a way to store a collection of elements. These elements can be a series of characters or integers. Each element is stored in the form of a node.

If you read the above definition carefully and thought of arrays, frankly, you would not be alone. Arrays are also a way to store a collection of elements, but there are many differences between arrays and singly-linked lists.

But before I explain the differences, I am going to describe to you, the “anatomy” of a Singly-Linked List.

Above is a visual representation of a simple Singly-Linked List (SLL). As you can see, it is made up of nodes, which I mentioned earlier. A node is a collection of two sub-elements. These two elements consist of the data part that stores the element, which in this case are integers, and a pointer that stores the link to the next node. A Singly-Linked List consists of a Head, Tail (not shown in this picture) and has has a specific length.

Now that I have explained the anatomy of a Singly Linked List. It’s time to explain how different they are to Arrays even though they can be both used to store a collection of elements.

Firstly, Arrays are indexed in order. An index maps the array value to a stored object, in simple terms, indexing allows us to find where a particular element is stored within an Array. Due to this, we can access it using an index. However, there are certain methods within Arrays which make it counterproductive to use, especially when using large data-sets. If we use the Big-O Notation during methods like insertion or deletion within an array, we find that the order of these methods comes to O(n²). This basically means, that as the data-set of Arrays increase, the time that is taken for insertion or deletion to occur is doubled. This is because once an element has been added or deleted from an Array, the whole data-set has to be reindexed, and that can be very intensive on the machine.

A Singly-Linked List, on the other hand, does not have any indexes, and like mentioned previously, it is made up of nodes that are connected, and unlike Arrays, random access of elements is not allowed.

Now that I have explained the basics of Singly-Linked Lists, it is time to see how this concept would look like in code. For this tutorial, I am using JavaScript. To show Singly-Linked Lists in code format, we use the principles of Object-Oriented Programming, but JavaScript isn’t an OOP Language however I believe the new ES6 release has some syntactic sugar that does some “magic” behind the scenes, so it behaves similar to traditional OOP languages like Ruby and Python.

As you can see from the above example, I created a new Singly-Linked List and pushed two values inside it, them being “PUSH” and “GOODBYE” . Since there are only 2 values, the head of this list is “PUSH” and the tail is “GOODBYE”, you know this because if you see the pointer section of “GOODBYE”, the next portion is pointing towards null. Which basically means, we are at the end of the list.

Like arrays, there are many methods within Singly Linked Lists. Most notably, in no particular order

_length: retrieving the number of nodes in a list

head: assigning a node as the head of the list.

add/push: adding a node to the list

remove/pop: removes a node from the end of the list

shift: removes a node from the beginning of a linked list.

unshift: adding a new node to the beginning of a linked list.

get: retrieving a node by its position in the linked list.

As this article was an introduction towards Singly Linked Lists, I will not be going in-depth with the methods mentioned above, however, I will explain that in the next issue of this series. I hope that you as a reader, have now a basic understanding of what Singly Linked Lists are and why we would use them.