Week 8: Linking with Linked Lists

The focus of this week, or should I say last week (I am running a little late), is a data structure called linked lists.  We will go over the basics of linked lists and compare it to Python lists.  So what is a linked list?  A linked list is a sequence of nodes.  Every node in the sequence contains an object and a link to next node in the sequence.  We can represent a linked list with this diagram:

2  ---> 5 ---> 7 ---> 11 ---> 13 ---> 17 ---> 19 ---> None

Notice that 2 is actually a node that contains both the item 2 and a link to the node that contains the item 3.  Every node in this linked list follows this structure with the exception of the node that contains the item 17, which contains a link to None.  This indicates that the node that contains the item 17 is the last node in the linked list. Due to the similarities between linked lists and Python lists, the elements of the linked list in the diagram can be represented equivalently in a Python list:

[2, 5, 7, 11, 13, 17, 19]

However, linked lists have an important advantage over Python lists when it comes to inserting items.  If you insert an item into the front or middle of a Python list, Python shifts every element with an index that is equal to or greater than the index of insertion to the right.  The efficiency of the insertion operation can be greatly reduced if there are many items to shift.  In contrast, if we are to insert an item 3 at index 1 to the following linked list, then the operation is as follows:

Start:  2  ---> 5 ---> 7 ---> 11 ---> 13 ---> 17 ---> 19 ---> None

Step 1:  2 ---> 3

Step 2:  3 ---> 5 ---> 7 ---> 11 ---> 13 ---> 17 ---> 19 ---> None

End:  2 ---> 3 ---> 5 ---> 7 ---> 11 ---> 13 ---> 17 ---> 19 ---> None

No items are shifted if we are performing an insertion operation on a linked list.  Instead, the node that is to the left of the insertion index re-links to the node of the inserted item.  Meanwhile, the node of the inserted item links to the node that previously occupied the insertion index.  As a result of linked lists being a sequence of connected nodes, not only do linked lists have the data storage capabilities of Python lists but also they handle the insertion operation to the front and middle indexes with a much greater efficiency.

            My personal reaction with the linked lists is not too different from that of trees.  As the professor said, the two are somewhat similar in that linked lists are simply linear trees with an arity of one.  Additionally, my comfort level with the syntax of classes increased after relentless exposure to them in these two months.  Therefore, I think I am currently in pretty good shape.