Data Structure Simplified — Part 1: Introduction to Linked Lists
Linked lists are among the simplest and most commonly used data structures. In this article, we will briefly discuss what linked lists are, the types of linked lists and why we use them. This is my very first blog post as a developer, please feel free to leave comments and feedback kindly 😊
What are Linked Lists?
If you search for the definition of linked list on Wikipedia, the result is quite a mouthful:
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.
Fine… but what does that even mean? Let’s simplify it.
A linked list is nothing more than a sequence of data elements, where each element is linked to an element that is linked to another element and etc. A linked list looks something like this:
As shown in the example above, Data 1 contains the “link” to Data 2, which is basically the address of Data 2. Therefore, Data 1 knows where to find Data 2. Similarly, Data 2 knows where to find Data 3, and so on and so forth… Here are some basic but important concepts:
- Each data element can contain any type of data such as string, number, object and etc.
- Data 1 is called the “head” of the linked list in this case, Data 4 is called the “tail”
- Data 2 is the “next” element of Data 1, and Data 1 is the “previous” element of Data 2
- The “length” of the linked list is equal to the number of elements in the list. In our case, the length is 4
- The index of a linked list starts with 0, just like the array.
- We can not get Data 3 directly from Data 1, since only Data 2 knows where Data 3 lives. We need to get Data 2 from Data 1 first and get Data 3 from Data 2.
- If you know the head (Data 1), you have access to all other elements (Data 2 to 4) in that linked list.
Type of Linked Lists
The example link listed above is actually a type called “Singly Linked List”. The rule is that the link is one-way only, meaning Data 1 knows about Data 2 but Data 2 has no knowledge regarding Data 1’s existence. There’s another type of linked list called “Doubly Linked List”, it looks like this:
Looks very similar to the previous example, isn’t it? That’s right, the only difference is that in the doubly linked list, the next element also knows where to find the previous element. Therefore, if you know any single element (Data 3 for example), you can get access to all other elements in that linked list.
There are also types called “Circular Linked Lists” and “Circular Doubly Linked Lists”. Go ahead and google what they look like.
Why Linked Lists (Linked List vs Array)?
Now you might be thinking, hold on a minute, isn’t that similar to an array? Why can’t we just use an array to do the same job? And why do we even need a linked list?”
To answer those questions, we first need to know how arrays and linked lists are allocated in our computer memory. Let’s say we have an array with a length of 4 in our memory, the computer will find a chunk of continuous memory with enough length to save the array in there, as shown below:
All elements of an array must be saved in a sequence of continuous memory addresses and in the same order as in the array. Even if there are a lot of empty addresses in the second and third rows, they are not long enough to save the array.
Meanwhile, this is an example of how a linked list is allocated in the memory:
Linked list elements can be stored in any location and in any order inside of the memory. Since each data element contains the address of the next element, a link listed does not need a whole chunk of memory to save them all together in one piece.
Now, what if we want to add a new element to the example array? The length of the array becomes 5, and its current memory address now doesn’t have enough space for the new array. It has to find a new chunk of memory that has enough space to save the new array. On the other hand, a linked list doesn’t require any address relocation, the memory only needs to allocate the new element to any empty address. Much less work!
Here is another scenario, we want to delete some random element from the middle of the array. What will happen inside of the memory? Let’s take a look:
Let’s say we deleted element 3, now element 4 needs to be shifted to the left, and element 5 also needs to shift over. If there are 100 elements after 3, then the operation will need to repeat 100 times. The time complexity is O(n).
Whereas the linked list only requires changing the previous element to point to the element after the deleted one:
The time complexity is therefore O(1). Imagine if you have an array/list of 1M elements, that could be a huge advantage compared to the array. Choosing the right data structure is important in terms of operating on large data set.
Summary
A linked list is a type of data structure that includes a series of connected elements. Each element stores the data and the address of the next element. Unlike an array list, they are stored in memory separate locations. A linked list has a significant advantage over an array when trying to add or delete elements from the middle of the array/list.
