Linked Lists Quick Review 

Linked List = An ordered sequence of Link objects

Each linked list has two parts:

  1. First = A value, can be any type (integer, string, linked list)

  2. Rest = Has to be a linked list

Linked lists (very similar to trees) are naturally recursive structures because the rest of a linked list is also a linked list, so any function that can be called on a linked list can be called on the rest of a linked list (here’s your smaller subproblem!)

Creating vs mutating

When working with linked lists, make sure to pay attention to whether you are asked to create and return a new linked list (nondestructive) or mutate an already existing one (destructive). Creating a new linked list means that you call the Link constructor at some point in your code, while mutating means that you are changing the values/links in the given linked list and are NOT calling the Link constructor at any point. Also, nondestructive linked list functions typically return a new linked list, while destructive linked list functions usually don’t return anything.

Box and pointer diagrams

Similarly to with lists, we can also use box and pointer diagrams to represent linked lists. For each Link object, we represent it using two boxes, one for the first and one for the rest. Let’s see an example:

Link(1, Link(2, Link(3, Link(4))))

Screen Shot 2019-01-13 at 4.44.43 PM.png

The first Link object has a first of 1 and the rest is Link(2, Link(3, Link(4))), and if we look at the first pair of boxes, we can see this is represented by a 1 in the first box and an arrow to another Link object. The second Link object has a first of 2 and a rest of Link(3, Link(4)), and looking at the second pair of boxes matches that. The third Link object has a first of 3 and a rest of Link(4), and we can see the third pair of boxes matches that. The very final pair of boxes has a 4, then a slash — this slash represents Link.empty, since the last Link object has a rest of Link.empty.

We can also have linked lists where the first of the linked list is also a linked list itself. Let’s see an example of what that would look like as a box and pointer diagram:

Link(Link(1), Link(2))

 
Screen Shot 2020-01-09 at 1.56.23 PM.png
 

Notice here that since both the first and the rest of the linked list are linked lists, both boxes of the first link have arrows pointing to other links.