What is a linked list?

A linked list is a linear data structure made of nodes and each node contains a value and a pointer to the next node in the chain, essentially linking them together.

Take a look at the picture below showing how a linked list is stored in memory.

From this example, you can see how the word “DOGS” is broken up into memory. You can see that the value “D” is stored in 214 with a pointer in 215 that “points” to the 219, which is the next location of the next value. This continues on until it points to 226 containing the last value of “S”. If you look at the pointer for the last character you will notice a null stating that it is the end of the linked list. The beginning value is known as the head and the last value is known as the tail.

Now imagine if we wanted to write the value “2” in from of dogs to show that we have “2DOGS”. All we would have to do here is create the node in space 229 and 230. Space 229 would display “2” and space 230 would display the pointer 214, pointing to the “D”.

The best think about linked lists is the fact that you don’t have to store them in a specific order and can be stored anywhere in memory, as long as the pointer is pointing to the next node. This means that it is extremely easy and fast to prepend or append to the current value. This saves time adding nodes and memory allocation.

The downside to linked list is the fact that it has o(i)-time lookups. It takes a little more time to look for pointers and moving to the next node. For example, imagine have the value “AB” store in memory as two nodes. The “A” is stored early in memory at space 10 and the B is stored in space 63,336. That is quite a way to traverse through memory. This example is only using two nodes to simplify it. If we were to store a word document with 5000 words, it would be much more difficult and time-consuming. This means that a linked list is not cache-friendly and has to constantly store the pointers in memory while looking for the next node and taking up that memory space.