DEV Community

loading...

Discussion on: What are Linked Lists and How Do I Make One in Python?

Collapse
erikhei profile image
Whiteboarding with Erik Author

This is a great question. There are some advantages to using a linked list over a Python list. Traditionally the question is "why would I use a linked list over an array", and the main point is that arrays in Java and other OOP languages are fixed size, so adding an element requires you to make a new array of size N + 1 and populate it with all the previous values, using O(N) space and time. By comparison, adding to the front of a linked list takes constant time. Python's list is not a true array but instead implements a dynamic array, which has its own advantages and disadvantages. The wikipedia page for dynamic arrays has a table that compares the performance for linked lists vs. arrays vs. dynamic arrays: en.wikipedia.org/wiki/Dynamic_arra...

If you're not worried about performance, then yes, it's easier to use a Python list. The reason for learning how to implement a linked list is along the lines of learning math when you can use a calculator–it's more about learning the concept. It's hotly debated in the developer community whether technical interviews that ask data structures and algorithms problem are really necessary. I don't know the answer to this. This article series is meant to prepare students who only know Python for these kinds of interview questions.

One advantage is that this simple linked list class provides a base to make our own specialized list class with custom methods, which I'll do in a future article when we use our linked list class to make a simple blockchain. So stay tuned for the DIY Bitcoin article!

Collapse
codemouse92 profile image
Jason C. McDonald • Edited

Ah, okay, I was merely under the impression that List had been implemented as a linked list. (I already know the difference between fixed-length array, dynamic-length array, and linked list, but your explanation will be helpful to anyone who isn't.)

Thread Thread
erikhei profile image
Whiteboarding with Erik Author

I also was unaware how list is implemented in Python. So we both learned something :)

Thread Thread
codemouse92 profile image
Jason C. McDonald • Edited

On nerd-level discussion of data structures (language agnostic now), another good option for a dynamic contiguous collection is a circular buffer, which is designed such that the head and tail "float". It's a bit hard to explain — basically, you don't require head to be at element 0, but implement logic for "wrapping around" from the last element to the first, as long as you haven't yet reached tail.

It makes for a time complexity of O(n/2) on insertion/deletion without reallocation, instead of the O(n) of a typical contiguous collection. Even better, head and tail operations are always Θ(1). While this is still a bit higher than the consistent O(1) of a linked list, you don't have the cache misses. It's also better-suited for random access.

No idea how you'd effectively implement this in Python, however. I always use pointer arithmetic to pull it off.

Thread Thread
erikhei profile image
Whiteboarding with Erik Author

I'm trying to imagine what this looks like implemented:

Thread Thread
codemouse92 profile image
Jason C. McDonald

Not far off. ;)