As one of the most common data structures, the linked list has to be one of the simplest in concept; yet still very powerful. In this post we will be looking at what linked lists are; what types of linked lists there are; when to use a linked list; and whether or why a linked list might be better than an array. We'll even build a simple linked list. Let's go!
A linked list is a data structure; a way of organizing data that can be used in a particular way. In its most basic form a linked list is a single node that holds a value, as well as an (optional) reference to another single node. Through this reference (or pointer) these nodes are linked to each other creating a list. The first node of a list is often called the head, and it represents the entry point of a linked list. The tail can either refer to the last node, or the rest of the list after the head.
Linked lists are often compared to array's, which in itself is of course a list of some sorts. But the way an array works has some limitations / drawbacks. For example; it uses adjoining memory locations to store its values. This makes it super efficient in returning values, as it can look it up very fast. But when it comes to adding, inserting or removing items it isn't as fast. For deletion, it will mark the memory slot as vacant, so it wil skip these slots when iterating; but the memory isn't freed up. When inserting a value, it needs to allocate more memory, and move every value that comes after the insertion. When inserting a value in the front of an array, this means it has to move every value.