As part of my efforts to learn the basics of computer science (or at least enough for a coding interview), I am trying to build my own linked list implementation in Python. I have been relying heavily on the awesome tutorial by Pedro Pregueiro of Real Python [1], as well as on the overview provided by Gayle Laakman McDowell in her book, Cracking the Coding Interview [2]. In this post, I’m going to give an overview of what linked lists are and why they’re useful, and include some of the code I wrote.

Linked lists are a data structure that represent a sequence of nodes that are not necessarily stored in a contiguous block of memory [1-3]. Each node contains some data and a pointer to the location in memory of the next node in the sequence, as shown in Figure 1 [1]. The first node is called the head and the final node’s pointer is null (or None if you’re being Pythonic) [1]. Linked lists can be either singly or doubly linked, as demonstrated in Figure 1 [2]. In a singly linked list, each node only points to the next node; in a doubly linked list, each node has pointers to both the previous node and the next node [2].

Figure 1

I followed the Real Python tutorial to implement a basic LinkedList class (wrapped around a Node class) in Python 3, and added some additional methods inspired by the challenges given at the end of the tutorial [1]. You can access my code here, and please keep in mind that the code is drawing heavily from the Real Python tutorial [1].

## Why are Linked Lists Useful?

It wasn’t obvious to me at first why a linked list would be a useful data structure. At first blush, they don’t seem very powerful - for instance, if you want to access the k-th element from within a linked list, you have to iterate through k elements before you find it (i.e. O(n) time) [2]. That’s weak sauce compared to an array or a regular list, where you can access any element in constant time (i.e. O(1) time) [2].

There’s no clear advantage to using a linked list from a memory usage perspective either. Linked lists require some additional space to store the pointers in addition to the data [3]. If the data being stored in the linked list is relatively small in comparison to the memory addresses, then linked lists may actually require significantly more memory than a regular list [3].

When is it helpful to be able to quickly add or remove items from the beginning of a sequence? When you want to build a queue [1]! Queues follow a first-in, first-out (FIFO) ordering, which means that they form the same way you form a queue to buy movie tickets, as shown in Figure 2 [2]. The first person in line is the first person to buy their tickets, and additional customers line up behind them [2]. So when you need to pull items from a queue, you always pull from the head of a queue, which is easy to do in constant time with a linked list, but requires O(n) time for a regular list [1-2].

Figure 2 - Source [1]

Okay, I hope you followed me in this post - I’m feeling a little out of my depth as a mechanical engineer. But I will be trying again soon with another post, probably on dynamically sized arrays and lists, or maybe hash tables? We’ll find out!

## References:

[1] Pregueiro, P. “Linked Lists in Python: An Introduction.” Real Python. 01 Apr 2020. https://realpython.com/linked-lists-python/ Visited 05 Jan 2021.

[2] Laakmann McDowell, G. Cracking the Coding Interview, 6th edition. 2016. CareerCup, LLC.