Forgotten slog: Week 8: Linked Lists

So turns out I had this slog post saved into my drafts rather than having posted it, so a quick update to "fill-in" my missing week 8 slog post. (oops). Anyways, moving on:

This week's covered topic was of linked lists, an introduction to another data type, which to me, is a bit of a doozy. In essence, I think of linked lists as a recurring single-item list implementation with a little sprinkle of recurring trees. The way linked lists work is a single element "node" with a reference to another front "node" and "back node". This way, each node contains the element that you want to store, as well as the next and previous elements for manipulation. This notion serves as the list aspect, with the linked part commenting on the back/front references.

Let's examine this crudely drawn diagram. For demonstration, an arbitrary list could be:

[1, 2, 3, 4, 5]

A linked list would be:

[ 1 | x <-]------[->2 | x <-]------[->3 | x <-]------[->4 | x <-]------[->5 | x <-]------[->None]

The 'x' represent the pointer in which other nodes refer to them. We can see that the first element, 1, points forward as its "back" node is 2, while 2's front node is 1. This creates a linked aspect between the elements. Now for the implementation, this will explain why I see it as a single branched tree.

Each linked list has a front, which is of an arbitrary form LinkedList(<val>, front). Val points towards what you're storing, and front refers to another node, which would normally be another linked list. So, a LinkedList(<val>, LinkedList(<val2>, LinkedList(<val3>, None))) would be a nested linked list to create a 3 element linked list. Now, to perform and implement specific methods, such as append, delete, remove element, extend, reverse and all that jazz, you need to iterate over each node as per your function.

To do this, there are 2 methods: iteration and recursion. Using iteration, such as a one-way while or for loop, you check each element of the linked list one by one for your condition, perform the task, and then break the loop. It's almost identical to iterating over a regular list using "for i in range", except slightly more complicated. The other approach, which wasn't really discussed all that much in lecture was using recursion. This simplified the method bodies by reusing code from the method itself, called until the method was completed. Although recursion seems neater and is more concise, iteration for me works better as it comes more naturally to me. It's easier for me to grasp the concept of checking each item once over rather than attempting for simplify my code for a few lines' difference in method length.

So what's the benefit of using a linked list? Well for one, there are many many more operations that you can customize using a linked list. For example, as each element or node is unique in the sense of its data, in addition to its storage as a node, allows for more specific operations that would otherwise require more and more and more nested lists, which in contrast to its seemingly deceptive nature, would make the process more complicated should the standard lists be used.