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!
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.)
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.
Shorter technique:
my_list = List();)But yes, what you showed is the way you'd create your own linked list in Python! Now I'd be curious why you'd do this.
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!
Ah, okay, I was merely under the impression that
Listhad 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.)I also was unaware how
listis implemented in Python. So we both learned something :)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.
I'm trying to imagine what this looks like implemented:
Not far off. ;)