Is a linked list a random access data structure?

There are many different types of data structures that can be implemented into a computer program such as arrays and linked lists. Each type of data structure has its strengths and weaknesses. For these reasons, it is important to understand the advantages and disadvantages of the different kinds of data structures when it come to designing, optimizing, and scaling programs.

Let’s begin by defining an array. In simple words, an array is essentially a data structure, similar to a list of values of the same data type. Another property of arrays is that array elements are stored in continuous memory locations. Furthermore, arrays have a fixed size which is defined upon initialization. Based on these properties, can you see the advantages and disadvantages of arrays?

Advantages of Arrays

As previously mentioned, arrays store elements in continuous memory locations. This means that any element can be accessed by adding an offset to the base value of the array or the location of the first element. The following figures show what I mean in more detail.

Although the memory addresses in Figure 2 seem to be four apart, they are actually consecutive. This means that any element in the array can be located as long as the index of the element is known by adding an offset to the address of the first element. Since there is no time difference between searching for the second or last element in the array, arrays have constant search times or Big O of one (O(1)), which is very fast. Fundamentally, the best possible run time complexity is O(1).

Disadvantages of Arrays

One of the disadvantages of arrays is that memory could be wasted. To explain this point I will describe a scenario. As a programmer, you do not always know how much memory to allocate. For example, you are building an application that will ask users for inputs which will then be stored in an array. Since you do not know how many inputs the user will make, you initialize an array with one million indexes as you presume that one million inputs will be sufficient for any user. What if the user only inputs hundred thousand elements into the array? Then, 90% of the allocated space is wasted.

Slow Insertion/Deletion Time:

Arrays have slow insertion and deletion times. Let’s begin by focusing on insertion. To insert an element to the front or middle of the array, the first step is to ensure that there is space in the array for the new element, otherwise the array needs to be resized. The next step is to open space for the new element by shifting every element after the desired index. Likewise, for deletion, shifting is required after removing an element. This implies that insertion time for arrays is Big O of n (O(n)) as n elements must be shifted. However, inserting and deleting form the end of an array is O(1).

A linked list is another approach to collecting similar data. However, unlike an array, elements in a linked list are not in consecutive memory locations. A linked list is composed of nodes which are connected with each other using pointers. Figure 3 below illustrates a linked list.

As shown in Figure 3, a singly linked list is composed of a head and a set of nodes. Note that there are many types of linked lists such as a singly and doubly linked lists, but for now we will focus on singly linked lists. To explain how a singly linked list works, I must first define a pointer. A pointer is a variable which holds the address of another variable or structure. In Figure 3, head is a pointer which contains the address of the first node on the linked list. The head variable allows the computer to locate the first node in memory and access its data. It is easy to iterate through the linked list once the starting location (first node) is located since each node contains a pointer to the next node.

Advantages of Linked List

From a memory allocation point of view, linked lists are more efficient than arrays. Unlike arrays, the size for a linked list is not pre-defined, allowing the linked list to increase or decrease in size as the program runs. This is possible because to insert or delete from a linked list, the pointers need to be updated accordingly.

Generally, inserting a node into a linked list requires the pointers to be updated after the new node is initialized. Figures 4-6 depict how to insert nodes to the beginning, middle, or end of a linked list.

Even easier than inserting, is deleting from a linked list. The only step is to update the pointers. Figures 7-9 demonstrate the process of deleting nodes at the beginning, middle, or end of a linked list.

As shown in the figures above, inserting and deleting from a link list is quite simple. Furthermore, linked list structures prevent wasted memory as nodes are inserted into the list as they are initialized.

Fast Insertion/Deletion Time:

As shown in the Figure 4, inserting a new node to the beginning or end of a linked list takes constant time (O(1)) as the only steps are to initialize a new node and then update the pointers. Likewise, if there were a tail pointer (similar to the head pointer) insertion to the end of the linked list would also be O(1). However, insertion to the middle of the linked list takes linear time (O(n)) as iteration over n elements is required to get to the correct location before inserting the node. Similarly, deletion of the nodes at the beginning and end of the linked list take constant time while deleting a node in the middle of the linked list takes linear time.

Disadvantages of Linked List

Linked list have slower search times than arrays as random access is not allowed. Unlike arrays where the elements can be search by index, linked list require iteration. This means that if you want to get the data on the tenth node, the head pointer can be used to get to the first node, the pointer on the first node can be used to get to the second node, and so forth until the tenth node is reached. This means that the more nodes that must be iterated while searching for a node, the longer the search time. This implies that the search time for linked list is linear time or Big O of n (O(n)).

Conclusion

In conclusion there are many different data structures. Each data structure has strengths and weaknesses which affect performance depending on the task. Today, we explored two data structures: arrays and linked lists. Arrays allow random access and require less memory per element (do not need space for pointers) while lacking efficiency for insertion/deletion operations and memory allocation. On the contrary, linked lists are dynamic and have faster insertion/deletion time complexities. However, linked list have a slower search time and pointers require additional memory per element in the list. Figure 10 below summarizes the strength and weakness of arrays and linked lists.

If you are interested in learning how to implement a linked list, check out my linked list guide here.