Linked-Lists: another collection ADT to add to the list

From programming in Python, we have become quite acquainted with many different data structures for representing collections of objects. In fact, we have been using so many different ways for representing collections that it's a little overwhelming. There are lists, tuples, dicts, sets, to name some of the built-in types in Python. There are also endless ways of combining these structures: nested lists, list-valued dicts, etc. We have also written our own ADT classes for representing collections: stacks, queues, linked-lists, trees, etc., and not only have written one class for each of these ADTs, we have implemented each of them in a number of different ways! Of course there is a principal reason for this: certain data structures (or certain implementations of a data structure) are more suited to some applications than others are, perhaps because they simplify the code or reduce algorithmic complexity. But there are so many different ways of representing collections and so many different ways of implementing the same data structure that when it comes time to decide on which one to use, there are so many options that it becomes difficult to figure out which one would work best.

Lately we've been working with linked-lists and one of our main motivations for doing so is that linked-lists can be more efficient than the built-in list data type provided by Python. A linked-list consists of a sequence of nodes each of which contains a value and a reference to the next node in the linked-list. We first wrote a class for the nodes and then we wrote a class for linked-lists which for the most part consisted of an attribute reference to the first node of the list as well as some other attributes and methods. One of the ways in which linked-lists are more efficient than the built-in lists is that the algorithm for adding a new item to the front of a linked-list has O(1) complexity whereas the algorithm for adding a new item to the front of a built-in list has O(n) complexity. The reason for this was immediately clear to me: in order to add a new item to the front of a linked-list, the algorithm only needs to create a new node for the item and link it to the front node of the list (which can be done in a constant amount of time), whereas for built-in lists the algorithm needs to "shift" all of the other items down the list after the new item is added, and the time required for this is proportional to the length n of the list. The algorithm for inserting or deleting an item at any point of a linked-list is also more efficient than that for a built-in list for the same reason: built-in lists need the elements after the insertion to be "shifted". I had nothing more than a vague understanding of what this "shifting" was, since I had no clue how the built-in lists were implemented so out of curiosity I did a bit of research. The built-in lists store all of the items together in computer memory and thus when a new item is inserted the other items need to be moved. It turns out that the built-in list data type in Python is actually a dynamic array data type and a linked-list is a list data type. What distinguishes the two is that lists data types use sequential access, while array data types use direct access. Direct access allows for indexing algorithms to access an item by its index in constant time (O(1) complexity), whereas sequential access forces indexing algorithms to traverse through the list in sequence and thus access an item by its index in time that increases proportionally to the index size (O(n) complexity). So although linked-lists beat the built-in lists in Python when it comes to inserting or deleting elements, they lose against built-in lists when it comes to indexing.