Linked Lists

A linked list is another form of recursive object.
Basically, it is comprised of nodes which consist of two parts.
Each node has an "item" which can be any form of object, and a "reference" which points to another node object.
The rules are that each node may only be referenced, or pointed at by one other node.
In this way, you can make a chain of nodes that reference each other. Using the logic, the last node in the linked list will have a reference value of None.
Another way of thinking of this is as a "Tree" structure, but with a branching, or arity, factor of one.

A linked list. Image from c4learn.com

The advantages of linked lists are:
You are not required to know the number of elements ahead of time unlike in an array. (Less relevant in python)
Linked lists are also flexible in the value or types of objects they can contain.
(Again, less relevant in python)
The addition and removal of items from the middle of a linked list requires significantly less operations and time, particularly if the total number of items is very large.
This is due to the fact that items may be freely added and removed from a linked list by changing their reference pointers, but in an array all of the objects must be copied or shifted to insert or remove an element.


The disadvantages are:
Linked lists are more work to set up than a simple array.
Linked lists must be traversed linearly. That is you can not jump to the 5th node immediately.
This means that performing certain operations, such as sorting, is much more difficult or time consuming.