Week 8: Linked Lists

In week 8 of CSC148, we learned about Linked Lists (LLs).

Summary of Linked Lists:

- Linked lists are data structures
- Linked lists are similar to trees in that they utilize nodes.
- These nodes are represented as a sequence.
- Linked lists are similar to arrays (lists), as they both store data.
- However, there is a unique difference between lists and LLs.

- In a vector, if we wish to insert data into our array, we have to move all of the subsequent entries by one or more indices. Although this is not too much of a problem when we have a list of length 1 or 2, this becomes a huge undertaking when we have a list of length 2,000,000. The amount of work grows in direct proportion to the number of items in the list.
- Insertion and deletion operations in an array grows linearly with the number of entries.

- We can use another data structure to perform an insertion or deletion operation that is independent of the number of items in the array : the LL
- In a LL structure, each of our nodes is linked to the node following it.
- We access elements in a vector through indices. Each element is contiguous to one another
- In a LL, the way we get to another node is through links that use pointers to point to the memory address with the next node in the LL. We also have a terminating value for our last node in the list to indicate that it is the end of the list.

- To insert a new element in the list, all we must do is grab one of the pointers in the list (let's call this point A) and point it to this new value (C). Initially, node (A) was pointing to node (B). So, we can point this new node (C) to point (B). In a LL, we can have a million values, but all we have to do to insert one node is redirect those three values. This is in comparison to having an array with a million values. Nifty!
- However, vectors(arrays/lists) excels in different ways. Although LL are superior for insert/deletion. It does excel at being able to access any particular element in a constant amount of time through the power of indices.
- In the case of LLs, you must follow the pointers throughout the LL to "find" the node that we're interested in. In LLs, we only have a mechanism to go forward, and we must start at the front of the LL and traverse the entire LL to "find" our node.
- WLists can go backwards, but we have not covered this topic.