Learning Linked Lists
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.
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
Doubly Linked List
Linked List Big O
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.
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!