Do linked lists require more memory than arrays?

Linked List vs Array

Arrays store elements in contiguous memory locations, resulting in easily calculable addresses for the elements stored and this allows faster access to an element at a specific index. Linked lists are less rigid in their storage structure and elements are usually not stored in contiguous locations, hence they need to be stored with additional tagsgiving a reference to the next element. This difference in the data storage scheme decides which data structure would be more suitable for a given situation.

Table of Contents Show

Linked List vs Array
Arrays Vs Linked Lists
Difference between Array and Linked List
Question: Are Linked Lists More Memory Efficient Than Arrays?
Array vs Linked List Data Structures
Array vs Linked List

Data storage scheme of an array

Data storage scheme of a linked list

Major differences are listed below:

Size: Since data can only be stored in contiguous blocks of memory in an array, its size cannot be altered at runtime due to the risk of overwriting other data. However, in a linked list, each node points to the next one such that data can exist at scattered (non-contiguous) addresses; this allows for a dynamic size that can change at runtime.
Memory allocation: For arrays at compile time and at runtime for linked lists. but, a dynamically allocated array also allocates memory at runtime.
Memory efficiency: For the same number of elements, linked lists use more memory as a reference to the next node is also stored along with the data. However, size flexibility in linked lists may make them use less memory overall; this is useful when there is uncertainty about size or there are large variations in the size of data elements; memory equivalent to the upper limit on the size has to be allocated (even if not all of it is being used) while using arrays, whereas linked lists can increase their sizes step-by-step proportionately to the amount of data.
Execution time: Any element in an array can be directly accessed with its index; however in the case of a linked list, all the previous elements must be traversed to reach any element. Also, better cache locality in arrays (due to contiguous memory allocation) can significantly improve performance. As a result, some operations (such as modifying a certain element) are faster in arrays, while some others (such as inserting/deleting an element in the data) are faster in linked lists.

Following are the points in favor of Linked Lists.
(1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, the upper limit is rarely reached.

(2) Inserting a new element in an array of elements is expensive because room has to be created for the new elements and to create room existing elements have to be shifted.

For example, suppose we maintain a sorted list of IDs in an array id[ ].

id[ ] = [1000, 1010, 1050, 2000, 2040, …..].

And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).

Deletion is also expensive with arrays unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

So Linked list provides the following two advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion

Linked lists have the following drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
3) Arrays have better cache locality that can make a pretty big difference in performance.

4) It takes a lot of time in traversing and changing the pointers.

5) It will be confusing when we work with pointers.

References:
http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Article Tags :

Arrays

Linked List

Practice Tags :

Linked List

Arrays

Read Full Article

Arrays Vs Linked Lists

Arrays and Linked Lists both are linear data structures, but they both have some advantages and disadvantages over each other.

One advantage of the linked list is that elements can be added to it indefinitely, while an array will eventually get filled or have to be resized (a costly operation that isn't always possible).

Elements are also easily removed from a linked list whereas removing elements from an array leaves empty spaces that are a waste of computer memory.

Insertion in Array and Linked List

However, unlike arrays which allow random access to the elements contained within them, a link list only allows sequential access to its elements. Linked lists also use more storage space in a computer's memory as each node in the list contains both a data item and a reference to the next node.

It follows that linked lists should be used for large lists of data where the total number of items in the list is changing. Arrays, on the other hand, are better suited to small lists, where the maximum number of items that could be on the list is known.

Difference between Array and Linked List

Both Linked List and Array are used to store linear data of similar type, but an array consumes contiguous memory locations allocated at compile time, i.e. at the time of declaration of array, while for a linked list, memory is assigned as and when data is added to it, which means at runtime.

Before we proceed further with the differences between Array and Linked List, if you are not familiar with Array or Linked list or both, you can check these topics first:

Array in C
Linked List

This is the basic and the most important difference between a linked list and an array. In the section below, we will discuss this in details along with highlighting other differences.

Question: Are Linked Lists More Memory Efficient Than Arrays?

Feb 19 2022

▲ 15 ▼

Answer The Question

Array vs Linked List Data Structures

Matthew Chan

Mar 6, 2020 · 5 min read

This article aims to distinguish when to use a linked list data structure over an array.

Let’s start by going over the basics of an array and a linked list.

Array vs Linked List

Array and Linked List are the two most used data structures. It's really important to understand and compare the advantages and disadvantages of both array and linked list. In this blog, we will compare these two linear data structures. So let’s get started.

To start of the things, we will take some parameters through which we can compare both the data structures.

Structure

Array and Linked list are used to store linear data of similar type but the major difference between them is related to their structure. Arrays are an index-based data structure where each element is associated with an index. On the other hand, Linked list relies on references of where the next element in the list is stored, the last element of the linked list refers to NULL denoting that its the end of the list.

Arrays

Linked List

Size

Arrays have fixed size and it is required to know the size of the array at the time of declaration whereas Linked List is not restricted to size and can be expanded during the execution. So, Linked lists are dynamic, flexible.

Memory Required

The memory required to store data in the linked list is more than that of an array because of additional memory used to store the address/references of the next node.

Storage Allocation

In an array, memory is assigned during compile time while in a Linked list it is allocated during execution or runtime.

The elements in the array are stored at contiguous positions in the memory whereas the elements in the linked list are stored at random positions.

Accessing Time

Elements in the array can be accessed using it’s index i.e. if you want to get into the fourth element you have to write the array variable name with its index or location within the square bracket. But, in a linked list, you have to start from the head and iterate until you get to the fourth element.

The elements in an array can be directly and sequentially accessed but in a linked list only sequential access is possible. To conclude, accessing an element in an array is fast and is a constant time operation whereas, in a linked list, it takes linear time.

Memory utilization

Memory utilization is inefficient in the array as we need to declare the size of the array during the time of declaration. Conversely, memory utilization is efficient in the linked list.

Insertion/ Deletion

Operations like insertion and deletion in arrays consume a lot of time as shifting of elements are required but these operations are easy, fast and efficient in linked lists.

Conclusion

From the above points, we can conclude that Array and Linked lists are the types of data structures that differ in their structure, accessing and manipulation methods, memory requirement, and utilization and have particular advantages and disadvantages over its implementation.

Linked List: Dynamic Size, Fast insertion, and deletion once the element is reached

Arrays: Fast Random element access and requires less memory per element