Linked Lists

When I started learning about data structures, especially linked lists, I was completely lost. I had no earthly idea that one could traverse or loop through anything else, besides an array or an object; but after a few manic episodes, a little research, and a substantial amount of coffee, I believe I have finally wrapped my head around how a linked list is structured and how it behaves.

To begin, linked lists are fairly similar to arrays considering they both store data. On the other hand, linked lists store data non-contiguously, unlike arrays who store their data contiguously. This means that linked lists can store data anywhere in memory, while arrays have to store their data in order. However, in both arrays and linked lists order matters.

Unlike arrays, linked lists are a dynamic data structure, meaning their size can either shrink or grow depending on the situation. Arrays do not account for more memory to be added. One would need to make a new copy of the array to add more data.

Here's an example how memory being stored contiguously works:

Linked lists are compiled of elements, usually referred to as nodes, that contain two values, the data and a reference to the next node. These nodes can be considered as selfish, since it only cares about the data it consists of and where it points to to continue the chain of connected nodes. The first node, or head, isn't actually considered a node, but instead a direction to start the chain of connected nodes. The conclusion to this chain is called the tail, which is a node but its value is set to null.

Here's an example of the basic setup of the structure of a linked list and a Node without the functions to add/remove a head or a tail:

There are a couple of different types of linked lists. Depending on the situation, one of the types might be more efficient to use than the other. The most primitive form of a linked list is known as a singly linked list. This list is partially hindered as it can only travel in one direction. Its older brother with considerably more life experience is known as a doubly linked list. The only difference between the two is that the doubly linked list can start at the tail and reverse through list, allowing for easier access to nodes closer to the end of the list. What took me a while to understand was that the actual structure of linked lists aren't too complicated, but rather knowing when to use them in real life situations.

Moreover, in terms of the Big O notation, which account for run time and memory allocation, to traverse over a linked list one has to account for every node position, increasing time complexity. To have the best time complexity, one wants to perform the least amount of operations. Linked lists use both linear and constant time complexities. Linear is used when traversing and constant is used when inserting or removing a node at the beginning of the list. The best case scenario for using a linked list is when one doesn't have to traverse, insert or remove a node a considerable amount of times.

Now how would someone use this in real life. In the early form of linked lists, they were actually used to create the first AIs, or artificial intelligence. In addition, most people are using linked lists every day. They are used in media players, when one changes a song; image viewers, when one precedes to the next or previous picture; and rendering game object.

In conclusion, linked lists can be very useful, depending on how one uses them. They are dynamic in size, allowing for size manipulation. Nodes contain two values, the data and a reference to the next node. And finally, they use both linear and constant time complexities.