Singly, Doubly and Circularly Linked Lists(SLL, DLL, SCLL, DCLL) — Data Structures

Data Structures are a topic that can be very confusing at first but once you get the hang of it, you will start to see places everywhere that you can apply it. In this blog, we will talk about the 4 basic types of linked lists, without any code, as it is possible to do this in many coding languages, once you understand the concept.

What are Linked Lists?

Linked Lists are a type of data storage, in other words, it simply stores and organizes your data. This data can be almost anything, from integers to strings, and even objects.

Generally, the structure consists of Nodes that contain data and an address (or addresses) to other Nodes. This allows you to traverse (or navigate) between the nodes, in order to achieve some goal, or just add a browsing system. You can think of this Node system as a train that has different carts that are all connected.

What are they used for?

They can have a lot of different uses, but one that helped me understand was a ‘sequential’ system. Let's use Youtubes autoplay feature as an example. The data could be the video information, providing the link that will play the video. Then when it is done it will look at the address part of the node to find the next node containing a video. And the process continues, jumping from one video to the next.

Another example could be Tinder! If you think of each profile as a Node, it contains the information or data for the profile, which includes name, pictures, description, etc. That Nodes also has the address for the next profile so when you swipe left or right, it goes to the next address, and once again repeats, jumping from one profile to the other.

Singly Linked Lists

Both of the above examples work as a Singly Linked List. This means that each Node consists of data and ONE address, which just states the next address. We can think of these nodes as having addresses 1,2,3,4 which makes the order clear but it could be 3,7,13,3000 and as long as position 3 has the address for position 7, those two are in order, where the address 3 is the first Node and 7 is the second Node. The address numbers don’t actually have to be in any order, they are just a reference.

In the above example, we have 4 Nodes each with 2 boxes, which represent the data (first box) and the address(second box). The first Node also called the Head, is our starting point. The data in this case are just integers.

The second box shows the address of the next Node. Our first Node has an address of 4800 and points to the address 4900. Note that 5000 (3rd Node) points to 3000 (4th Node), meaning that you are free to reorganize, no matter what the numbers are, as long as they are unique.

The last Node, in the case of SLL, has an address of null which indicates that this is the end. Depending on the language this could be some variation of null, but basically, it just means that there is nothing it points to.

Take your time to understand this, as the other 3 Linked Lists build off of this one!

Singly Circularly Linked Lists

If you understand SLL, understanding SCLL should be easy. The only difference between the two is the last Node’s address. If you look at the below example, the last Node’s address pointer is the first Node’s position, 1001.

The reason for using Circularly Linked Lists is to allow you to loop back around to the start.

A good example of this is Netflix’s library system. On Netflix, you can scroll through your saved shows but once you get to the end it goes back to the beginning so you can infinitely scroll through that list.

Doubly Linked Lists

A DLL is the same as a SLL, except it stores 2 addresses instead of 1.

One is the address for the next Node, just like a SLL, but the other address is for the previous Node. This allows us to traverse both ways through the list, which is something not possible with SLL.

You can also see that the first Node’s previous address is null, and the last Node’s next address is null since those are the start and ending points of the list.

An example that would possibly use a DLL, would be an online Quiz. You can navigate between the questions using a ‘next’ and ‘previous’ button to go to the next or previous question but you cannot jump from the first question to the last, or vice versa.

Doubly Circularly Linked Lists

The final of the three, which incorporates all the features into one, is the DCLL. This stores the same things as a normal DLL but instead of having the null value in the start and end, those will point to each other to make it circular, just like the SCLL. That’s a lot to take in, let’s take it piece by piece.

Breaking it down, each Node has 3 parts. One stores the data, one stores the previous address, and one stores the next address. This makes a DLL, but to make it circular you point to the last Node in the first Node’s previous address and point the first Node in the last Node’s next address. Take a good look at the image below and visualize how you would traverse the list, in both directions and looping around.

We can use the same online Quiz example as before, but with a DCLL you can jump from the first question to the last, and the last question to the first using the same ‘next’ and ‘previous’ buttons you would use to navigate the rest of the questions.

To associate the Nodes with its three parts to the example, think of the data in the current Node as the information needed to render and populate the current question. The Node’s next address would hold a pointer to the next question, and lastly, the Node’s previous address would hold a pointer to the previous question.

Conclusion

There are many different structures to use, and they all have their purpose depending on the app you are aiming to make. Despite the features mentioned, there are also time signatures and space differences to also consider when deciding which one to use. Happy Coding!