Arrays vs Linked Lists
Arrays are the most commonly used data structure to store collection of elements. Most programming languages provide methods to easily declare arrays and access elements in the arrays. Linked list, more precisely singly-linked list, is also a data structure that can be used to store collection of elements. It is made up of a sequence of nodes and each node has a reference to the next node in the sequence.
Shown in figure 1, is a piece of code typically used to declare and assign values to an array. Figure 2 depicts how an array would look like in the memory.
Above code defines an array that can store 5 integers and they are accessed using indices 0 to 4. One important property of an array is that entire array is allocated as a single block of memory and each element gets its own space in the array. Once an array is defined, its size is fixed. So if you are not sure about the size of the array at compile time, you would have to define a large enough array to be in the safe side. But, most of the time we are actually going to use less number of elements than we have allocated. So a considerable amount of memory is actually wasted. On the other hand if the “large enough array” is not actually large enough, the program would crash.
A linked list allocates memory to its elements separately in its own block of memory and the overall structure is obtained by linking these elements as links in a chain. Each element in a linked list has two fields as shown in Figure 3. The data field holds the actual data stored and the next field holds the reference to the next element in the chain. The first element of the linked list is stored as the head of the linked list.
| data | next |
Figure 3: Element of a Linked List
Figure 4 depicts a linked list with three elements. Each element stores its data and all elements except the last one store a reference to the next element. Last element holds a null value in its next field. Any element in the list can be accessed by starting at the head and following the next pointer until you meet the required element.
Even though the arrays and linked lists are similar in the sense that both of them are used to store collection of elements, they incur differences due to the strategies they use to allocate memory to its elements. Arrays allocate memory to all its elements as a single block and the size of the array has to be determined at runtime. This would make the arrays inefficient in situations where you don’t know the size of the array at compile time. Since a linked list allocates memory to its elements separately, it would be much efficient in situations in which you don’t know the size of the list at compile time. Declaration and accessing elements in a linked list would not be straight forward compared to how you directly access elements in an array using its indices.