After you become familiar with programming basics, one of the first milestones in terms of your skills will be knowing how computers store and keep data. Arrays and Linked Lists are two of the basic data structures used in programming.
Although both of them can be considered linear sets of elements, there is a difference in the way information is kept in arrays and linked lists. Incorrect usage of data structure can lead to inefficient software operation and waste of computing resources. Here is what you should know about these data structures and their differences.
1. Data Storage
Let’s consider how your computer’s RAM looks like. Consider RAM as a huge set of numbered mailboxes storing one piece of information in each of them.
Arrays: Contiguous Blocks of Data
Arrays are a linear data structure that stores information in contiguous blocks of memory. In other words, creation of an array of five items requires five contiguous blocks of memory.
This allows for quick access to data. When accessing certain array element, computer immediately knows where to look for it. For example, request for element with index 0 implies asking for data located in the first memory block. If you need data from index 3, its address can be found using formula Start Address + 3.
Linked Lists: Scattered Chain of Data
Unlike arrays, linked lists do not require storing elements in contiguous memory addresses. Elements can be stored in any places in the computer’s RAM.
The problem with such type of data structure is the scattering of data all over the memory. To solve this problem, nodes of a linked list are divided into two parts:
Data. Contains actual information that needs to be stored.
Pointer (Reference). Points to the next node in the list.
Every linked list has a pointer called Head. It points to the first node, that points to the second node and so on until the end of list is reached, which is represented by null.
2. Performance: Accessing vs. Modifying
Due to different representations, there are certain differences in performance which are explained using Big-O notation.
Accessing and Searching Data
When it comes to accessing data, arrays perform great. Due to their contiguous nature, arrays allow for constant time ($O(1)$) random access. Therefore, accessing first item (index 0) or item having index 742,411 in a million-element array will take exactly the same amount of time.
Accessing data in linked lists is a terrible performance. Since nodes are scattered around memory, you need to go from the Head pointer to the first node, then jump to the next node, get its reference, then jump to the next node and so on until you reach the required index. Result is linear time ($O(n)$) access.
Inserting and Deleting Data
Modification of arrays is complicated. Let’s consider an array as a set of people seating in a theatre. Adding a new person to the beginning of the row (index 0) means moving everybody to the right to create space. In other words, inserting a new person at index 0 implies shifting all the existing 10,000 items ($O(n)$).
Modification of linked lists is easy. If you want to insert a new node between two nodes, A and B, you just need to allocate a new memory block, assign a reference to Node B and change the reference of Node A so that it pointed to the new node. No shifting, no moving data, just like cutting a chain in half and adding a new link to it ($O(1)$ constant time).
3. Dynamic Size and Memory Overhead
Lastly, let’s talk about yet another difference between these two data structures: handling changes in size.
Fixed vs. Dynamic Nature
Classic arrays are fixed in size. While creating an array, you need to define its size once (array of size 10). In case you realize you need an extra item, you cannot increase size of your array. You’ll have to allocate a new memory block of a bigger size (array of size 11), copy all the existing 10 items to it, add the eleventh item and free memory of the old array.
Dynamic nature of linked lists allows you to add or remove nodes whenever you need it. Starting with a single item, your list can dynamically grow while adding new items.
Memory Overhead
Arrays are extremely memory-efficient since they contain only data. For example, an array of integers contains only these integers without any additional information.
Since their nature, linked lists require more memory than arrays of the same size since each node contains both data and reference to the next item.
Frequently Asked Questions (FAQ)
1. What is the difference between a singly linked list and a doubly linked list?
Singly linked list is a list in which each node has a reference to the next node and you can iterate through nodes in one direction. Doubly linked list is a list in which each node has two references: one to the next node and another to the previous one. You can iterate in both directions, although this increases memory overhead.
2. Why is it said that insertions in linked lists take $O(1)$ time while locating a place for insertion takes $O(n)$ time?
It is a tricky question which often appears during programming interviews. Indeed, insertion takes constant time ($O(1)$) since it always implies doing a certain number of operations. However, locating a place for insertion costs you $O(n)$. Nevertheless, if you already have a reference to the node where you want to insert something, you don’t need to spend time locating it.
3. Do modern programming languages use static arrays?
Static arrays are used in low-level programming languages like C, C++ or Java. On the contrary, high-level programming languages like Python, JavaScript or Ruby use dynamic arrays behind the scenes. They allocate new, bigger memory block when current one becomes full, copy all elements to it and release memory of the old block.
