Geek Culture
Published in

Geek Culture

Learning Linked Lists

One does not learn data structures without implementing a linked list and a binary tree from scratch

I will admit that when I first started learning data structures and algorithms, I was terrified. After studying them for a little while, I’m really enjoying them. My impression is that most people who love programming would enjoy studying DS if they haven’t already. For me, the negativity was tied to a fear of having to know every data structure and sorting algorithm for job interviews. Once I actually started learning, it was easy to forget about the pressure of job interviews and just enjoy coding.

Since I know it can seem overwhelming at first, I am writing this article to give an overview of what Linked Lists are, the time complexity(big O) of the most common operations with a Linked List, and when you may want to use one. Because Linked Lists are not data structures provided for us by JavaScript, we have to create them as classes. Here are links to my Repl.it pages I made for Singly Linked Lists and Doubly Linked Lists. Each of those pages has a JavaScript class with some of the most common methods needed in a data structure, such as push, pop, shift, and unshift.

Much like an array, a Linked List is an ordered list of data. However, they work quite differently. In an array, we index each item with a number. Linked lists consist of nodes, each of which has a value and is connected by a ‘pointer.’ Nodes in Singly Linked Lists(SLL) have a value and then a ‘pointer’ that connects it to the next node in the list. In a Doubly Linked List(DLL), each node has a pointer to both the node after it and the node before it. The beginning and end of a linked list are called the Head and Tail, respectively. An important thing to note is that the Tail will not be connected to a node, and instead have ‘null’ as the value of its forward-facing pointer. In a DLL, the Head also has one ‘null’ pointer, since there is no node before it.

Singly Linked List

example of a Singly Linked List
check out this and more great visualizations from visualgo.net
Constructors for both a SLL and it’s nodes
Constructors for both a SLL and it’s nodes.

Doubly Linked List

example of a DoublyLinked List
check out this and more great visualizations from visualgo.net
Constructors for both a DLL and it’s nodes
Constructors for both a DLL and it’s nodes

Linked List Big O

spreadsheet showing time complexity of operations with different data structures
check out bigocheatsheet.com for more great information

After looking at these images, you might be wondering why even bother having two kinds of Linked Lists when they are so similar in terms of structure and performance. If they perform the same, why bother doing a extra setup and using up more memory with a DLL? The answer lies in edge cases.

If you ever need to access the data from your list in reverse order(a browser history is a great example), a Doubly Linked List will perform far better. This is because all you have to do is find the tail, look at the previous node, and so on. Compare this to the code below for a Singly Linked List.

code to reverse a singly linked list

Additionally, removing an item from a DLL is ALWAYS constant time. With a SLL, it can actually vary depending on where you are removing from. If we want to add to the end of a SLL, we have to iterate through the entire thing until we find the second to last node. In a DLL, we can just go straight to the tail. If you do not need access to the list in reverse order, SLL may be the way to go, especially if you are concerned about the extra memory being taken up by having an additional pointer on each node.

I have really enjoyed learning about Linked Lists and writing the class methods from scratch. It has taught me more about programming in general than I would have expected, and I’m excited to keep learning more data structures! Thanks for reading!

A new tech publication by Start it up (https://medium.com/swlh).

Recommended from Medium

What are the different SAP S/4HANA Adoption Scenarios?

The case for and against Amazon Cognito

Frontend-Design Knowledge Sharing #2

Flutter TextEditingController class for text fields

What is Apple’s MDM Solution

How to Get Macro Info from a DOCX File in Java

How to perform Named Entity Recognition NER in Python with NLP

Wordpress mysql application in k8s Cluster using Ansible

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
Liam Hanafee-Areces

Liam Hanafee-Areces

More from Medium

LeetCode 88. Merge Sorted Array

Array Stepper Algorithm Problem

[Data Structure & Algorithm]: Binary Search with Javascript

LeetCode 66 — Plus One Java