LinkedLists Part I: Caught In Traffic

Intro to LinkedLists

Hello!

It has been a while; asides from trying to stop Elon Musk from buying Twitter(big boy moves), I’ve also been busy doing a million and one other things. But that not withstanding, we are here now. And that’s all that matters! I think.

Moving on, I’d like to talk about LinkedLists. I’m making this up as I go, however, I hope this newsletter will only cover the introductory aspects of LinkedLists. If it doesn’t, then that implies that I got a little too excited about writing to you.

Introduction

What is a LinkedList? A linkedlist is special kind of list, special in the sense that each item in the linkedlist has a pointer to the next item in that list - if such an item exists.

The above image shows a classic example of a LinkedList. A LinkedList always has a HEAD pointer which points to the start/head of the LinkedList. DO NOT LOSE THE HEAD. Half of the bugs you’ll encounter when working with LinkedLists will come from losing or overriding your head pointer. As shown above, without the head pointer, there will be no way to reference the start of the LinkedList, neither will there will a way to visit any other item in the LinkedList.

No way a five year old would understand any of that.

So let’s think about LinkedLists in terms of their characteristics; this will allow us to draw parallels from our every day life.

Caught in Traffic

For the rest of this section, we assume that you can only look forward while in traffic. We will talk about Doubly LinkedLists later (looking backwards) but for now, we will focus on ONLY looking forward.

When you are caught in traffic, you will be in one of three positions:

• You can be in front of the traffic, that is the first person to go

• You can be in the middle, or

• You can be the last person, thus there’s no one behind you.

Depending on your position, you can only see the plate number of the car in front of you or no car plate at all. If you are the first person, you won’t see a plate number…you will see the traffic lights (lucky you!). Next time you are in traffic, try to see the plate number of the second car in front of you :)

Operations on LinkedLists

Now for the fun part, because in this scenario we can only look forwards, the activities we can perform are controlled.

For instance, how would you count the number of cars in traffic? You start from the last person and ask, what’s the plate number of the car in front of them? By asking every driver what the plate number of the car in front of them is, you can get the total count of all the cars in traffic.

What if the traffic cuts through an intersection and new cars can join the traffic? When a new car joins, the traffic is updated in a couple of ways.

• In front: the driver that was in front suddenly has a car ahead of him and now has a plate number to look at (sorry).

• In between: when a driver enters the traffic midway, the traffic is updated in such a way that the driver behind the new one now sees the new driver’s plate, while the new driver sees the previous driver’s plate.

• At the end: the new driver joining the tail end of the traffic now sees the plate number of the previous driver.

Shown above is the example of driver 12 trying to join the traffic (LinkedList) at the three possible positions.

What do you think happens when a driver leaves the traffic? How would the list above update itself?

Operation Costs

Insertion: Insertion into a Singly LinkedList as shown above is linear - O(n). To add an item to the end of the list, you have to traverse from the head of the list till you get to the end of the list. Same for midway insertions.

Deletion: Deletion of an item in a Singly LinkedList is also linear - O(n). To delete an item from the list, you have to traverse from the head of the list till you find the item.

Retrieval: Retrieval of an item from a Singly LinkedList is linear - O(n).

Why use LinkedLists?

As we can see from the operational cost of Singly LinkedLists, they’re not necessarily better than arrays when it comes to operational cost, so why use them?

Unlike arrays, LinkedLists do not have a defined size, and as a result, they do not need to be resized. LinkedLists enable the movement of pointers rather than values which can sometimes be more efficient than moving the actual values. When adding an item to the middle of a LinkedLists, only the pointers of the two(max) affected items change, the rest of the list remains unchanged. This also true for deletions; thus it is easier to manage insertions and deletions on LinkedLists than Arrays.

Doubly LinkedLists

A doubly linkedlist is a linkedlist in which each item holds a pointer to both the next and the previous item on the list.

Doubly LinkedLists are different from Singly LinkedLists in that each item has two pointers - a next and a previous, to store the pointers to the next and previous items. This feature of doubly linkedlists enables us to build apps such as a music player - we can go forward and backward when on a song in a play list - nice! When you navigate through an application or web site, you can also navigate forward and backward based on the pages you’ve previously visited - doubly linkedlists. Having two pointers make iterating the linkedlist easier, however, a bigger advantage is the ability to easily reverse the linkedlist as every item points to the previous one.

Back to our traffic example, now you can look both ways - forward and backward. You agree that it is easier to reverse the traffic now that you can see both the car in front of you and the car behind you, right?

Conclusion

This seems like a lot already, in Part II, we will discuss Circular LinkedLists, and Doubly Circular LinkedLists. See you!