CSC148 Linked Lists Post #7

During week 8, we took a look at another ADT called Linked Lists. A Linked List is sort of a linear set of nodes where each node can only have one child node. An easy way that I thought of to help understand what Linked Lists are is to think of a Tree with only one child node for each node.

Now for Linked Lists I found that this concept was actually easier to understand compared to Binary Trees, and Binary Trees are already pretty easy to understand. I think it's because there is only one branch direction now, instead of a left and a right.

Another thing that I noticed about Linked Lists is that there is barely any recursion involved. In our labs, I used recursion only once in one function, but that was only to bring the arguments up from negative to positive to satisfy our if statements.

So what exactly is a Linked List?
A Linked List has three things, a front, a back, and a size. The front refers to the first node of the Linked List, the back refers to the last node of the list, and the size is the total number of nodes in the Linked List. These nodes, in our Python implementation are called LLNode, where each node has a value and a "child" node called nxt (since "next" is a built-in function). If you look at the representation of a Linked List, you can see it sort of resembles the representation of a Tree.

For example:

LLNode(1, LLNode(2, LLNode(3, LLNode(4))))

In this example, the front of the Linked List would be LLNode(1), the back would be LLNode(4), and the size would be 4. If you take a close look, you can notice that it is sort of like a Tree where each node has a child node, except for LLNode(4), which would essentially be a leaf. The only difference is that Trees can have multiple children coming from the same parent node, where as in Linked Lists, there can only be one.

Taking that into consideration, we can see that Linked List could be used in Trees to help represent them. A path in a Tree could basically be a Linked List because the path is referring to a linear set of nodes. For example,

I coloured each path of this Tree to show how a Linked List representation would work. Since in each path, there is only at most one child node coming from the previous node, We can use Linked Lists to represent each path. For example the red path would be, LLNode(A, LLNode(B, LLNode(D))), and the blue path would be, LLNode(A, LLNode(B, LLNode(F))).

That's all I've got this week about Linked Lists, thanks for reading.