Understanding the problem
To better understand a linked list, let us first look at some common problems programmers face when designing software systems. When writing a program, we often need a collection of data items that can be accessed sequentially. E.g., a collection of names of all the students in a class. It is common for people to think this is not such a complex problem. What's so hard with it? We can use an array to store this data where the size of the array is equal to the number of students.
Using an array to store names of students
This is an easy way to store data, but what if a new student joins the class? In this case, we will have to increase the size of the array by one, which is not possible. Well, we can solve this problem by creating a new array of a larger size, copying all the data from the previous array, and then adding the new student to it. However, this will be quite inefficient in terms of space and time complexity.
Add a new data item in an array by copying the data in a new array
Now, let's consider another scenario. What if a student leaves the class? We can use the same process again. This time, we create a new array of smaller size and copy all the data items except the one we want to delete.
Deleting a data item in an array by copying data to a new array of smaller size
The examples we looked at above inserted or deleted data from the ends of a sequential collection. What if we had to insert or delete data items from somewhere in the middle?
Limitations of arrays
Even though we can solve the problem using an array, it is inefficient if we have to insert and delete data items frequently. The solution above performs poorly.
- Space complexity O(N): Initializing a new array to add or remove a single data element would waste a lot of memory when we need just one extra block.
- Time complexity O(N): Our algorithm is relatively slow since we try to traverse the entire array and copy the elements to the new array whenever we want to add or remove an item.
An array has other fundamental problems that make it a bad choice for problems like these. For example, we cannot insert or delete data items in place in an array.
Cannot insert/delete data items in arrays
The fundamental challenges of using an array are:
- Fixed size: Arrays have a fixed size defined at their creation and cannot be changed later.
- Insertion and Deletion: Data items in an array reside in contiguous memory blocks. Since an array has a fixed size, we cannot insert or delete data items; we can only overwrite them.
What if we had a magical data structure that could solve the above problem most efficiently?