Deconstructing Data Structures: Linked List

We have a data structure that is synonymous to the word list — array. An array is a sequence of data that is ordered and is contiguous in memory, meaning that the memory location for each item in the array is next to the memory location of the next item. What is a linked list, and how does it differ from an array? What are the tradeoffs? This article will answer these questions.

When I first learned about linked lists, I didn’t really get a good explanation on how they were constructed. I had to do my own research and come up with a way to explain linked lists in a much more understandable fashion. When I was able to explain it to myself, construct it, and apply it to certain problems, I was confident enough to use it. The reason why it is called a linked list is because every object in the linked list is linked by a pointer from another object. That object is known as the node. The node contains a value and a pointer that points to the memory location of the next node in the linked list. Here is an illustration on what that looks like.

The first node in the linked list containing the value 3 is known as the head node. The head node does not have a pointer that references it, just as how nodes with values 4, 1, and 2 have them. The last node in the linked list with the value 2 is known as the tail node, and this node does not have a pointer that is referencing another node’s memory location. When you traverse a linked list, you have to make sure that each node that you are going through has a pointer. When a…