As I try to wrap my brain around all of these different data structures that exist in the world of programming, today I’m looking into linked lists and how they differ from arrays. Each structure is a way to store groups of data and provide different advantages and disadvantages when working with the structure.
An array stores each element, or piece of data, in contiguous memory locations. This allows easy and fast access to any particular array element by using the index of the array. The index describes the position of each element in an array in its memory location. The index starts from 0 and counts up until the end of the array.
The main advantage of using an array is the ease with which you can select elements. However, adding elements requires adding a space in the pre-allocated memory block which makes doing this less efficient than using a linked list. If you know the size of the array and you want to search for elements within it often, go with an array.
A linked list is similar to an array, however each piece of data in the list has both the data item and a value which points to the next element of the list. In this way, linked lists can be spread across memory and don’t require one contiguous block as arrays do. So for each element in the list, it has to include something to point to the next element. While this may use more memory per element than an array, there is a lot more flexibility when changing the size of a linked list. An array needs to allocate a certain amount of memory upon declaration, but with a linked list one can add and delete items with ease without having to block out a certain amount of memory from the start. Linked lists have the advantage of being able to add and delete elements with ease and are incredibly dynamic in their size. However, one of the drawbacks for a linked list is to find any one element, you must start with the first element and traverse through the list until you reach the element you are looking for.
Linked lists and arrays each have their place when it comes to programming, and I hope this article helps demonstrate when to use one vs the other.