Impressions of Week 8

In week 8, we learned about a new data type called linked lists.  Python has a built in data type called list, where data can be stored in a specific order.  There are many methods for the class list which allow one to add, remove, sort, and analyze data within the list.  Data at any position in the list can be mutated or manipulated with the correct usage of list methods.

In contrast, linked lists can also store different types of data, but their use is very different.  For linked lists, two classes are used, the node class, and the linked list class.  The node class refers to a single point of data within the list, and the linked list organizes a collection of nodes into the linked list by assigning one node as the front, and another as the back.  The way the data is connected is that each node has a property "next" (or .nxt) which points to a new node.  Each node is referred to by another node, and refers to a new node unless it is the beginning or end of the linked list.  Because of the structure of linked lists, a lot more work must be done to use the data in a linked list as compares to a list.  To add data in the middle of a linked list, one must change the .nxt of the node before, and use the .nxt of the node to be added to add to the list properly.  Additionally, to access data in the middle of a linked list, one must walk through each node in the list until the desired node is available.  Recursion must be used for some methods with linked lists.

So far, I don't see the use of linked lists.  It seems like everything they can be used for, the built-in list class can also do, and often times can do more efficiently.  I can't think of a specific type of problem or data where a linked list would be the ideal class to use.  Since recursion must be used for some methods, and others have to access many unneeded nodes before finding the desired node, the runtime for linked list methods would be significantly longer than for lists if one is using a large set of data.  I'm curious to see if we revisit linked lists before the end of the course, and to find out if there is a type of problem which this data type is optimal for.