13.1. Why linked lists?

Let’s say we want to store a list of numbers that can decrease or increase. We decide to store the list in an array as follows:

int array[4] = {1, 4, 7};

To add a new number to the array between two numbers, we can move all numbers on the left by one place and place our new number as follows:

To delete a number from the array, we can move all numbers on the right by one place to the left to overwrite the number to be deleted as follows:

To insert more numbers that the array size can handle, we have to create a new array, move all numbers to the new array, and then add the new numbers to the array as follows:

However, these operations are all inefficient. The operations require us to move all elements or some to the right or left by one place or to a new array. Arrays are not flexible when it comes to changing the array, because the array elements are stored contiguously – next to each other – in the memory. For example, in the case of adding an element in the array, it would have been easier if we can just add the element in the middle without moving the elements to the right.

In the figure below, we broke down the elements of the array into pieces to form a list of numbers. Each piece is stored any where in the memory (not contiguously as in arrays). We can add a new element in the middle of two elements by just adding the new element in the middle of the two pieces. This is much easier than moving all elements to the right by one place.

In order to maintain the order of the elements, we need to have links between them to determine the first, last (and everything in between) elements . For example, links between all pieces of our array can look as shown in the figure below.

We can now add a new element in the middle of two elements by changing the links to include the new element as shown in the figure below. This is much easier than moving all elements to the right by one place.

Fig. 13.1 Deleting an element from the list can be easily done by changing the links as shown in the figure below. This is much easier than moving all elements to the left by one place.

Extending the list can also be easy by adding a new list to the end of the current list as shown in the figure below. This is much easier than moving all elements to a new array.

This list of numbers that we linked is called a linked list. It is more flexible to add new elements, delete elements, and extend the list than arrays. We will discuss how to implement a linked list in C in the next section.

Quiz

0 Questions

Start Quiz

X