What is the Difference Between Array and Linked List

The main difference between Array and Linked List is that Array allocates memory at compile time, which is the time of declaring the array, while Linked List allocates memory at runtime, which is the time of adding elements to the linked list.

An array is a data structure that contains a group of elements of the same data type. An array is pre-defined. In other words, it has a fixed length. On the other hand, a Linked List is a linear data structure that considers each element as a separate object. It has a dynamic length. Therefore, it is possible to increase or decrease it at runtime.

Key Areas Covered

1. What is an Array
     – Definition, Functionality
2. What is a Linked List
     – Definition, Functionality
3. What is the Difference Between Array and Linked List
     – Comparison of Key Differences

Key Terms

Array, Linked List

What is an Array

An array is a data structure that has a fixed size. It can store elements of the same type. When there are multiple elements of the same type, it is not possible to store each of them as separate variables. An array provides an alternative to this issue. It stores all the elements as a single element. For example, double salary [10]; declares an array called salary that can store 10 double values. This array size is 10. Therefore, the programmer cannot store more than 10 elements in this array.

The index of the 1^st element in the array is 0. If there are 10 elements in the array, the index of the last element is 9. All the elements in the array are in contiguous memory locations. The lowest address corresponds to the first element while the highest address corresponds to the last element. Moreover, it is possible to perform operations such as insert, delete, modify elements, and traversing through the array and merging arrays.

What is a Linked List

Linked List is a linear data structure which contains a group of nodes in a sequence. Each node consists of its own data and the address of another node. It can store the address of the next node, or both the next node and the previous node. The elements are linked together and form a structure similar to a chain. The main advantage of a Linked List is that it is dynamic. Unlike in an array, it is not necessary to allocate all required memory initially. Instead, a linked list allows allocating memory when required.

On the other hand, a Linked List requires more memory as it stores the addresses of other nodes. In a linked list, it is not possible to access an element randomly at once. The programmer should go through each node sequentially to access a particular element.  Furthermore, it is difficult to perform reverse traversing in the linked list.

Difference Between Array and Linked List

Definition

An array is a data structure consisting of a collection of elements each identified by the array index whereas a Linked List is a linear collection of data elements whose order is not given by their location in memory. Thus, this is the main difference between Array and Linked List.

Accessing the Elements

An array supports random access. Therefore, the programmer can directly access an element in the array using the index. Linked List supports sequential access. Therefore, the programmer has to sequentially go through each element or node until reaching the required element. Hence, this is one important difference between Array and Linked List.

Memory Locations

Memory locations is another difference between Array and Linked List. The elements in an array are stored in contiguous memory locations. On the other hand, the elements in the linked list can be stored anywhere in the memory. It is not necessary to store elements in contiguous memory locations.

Size

Moreover, the programmer has to specify the size of the array at the time of declaring the array. However, there is no need for specifying the size of a linked list. It can increase at runtime when adding more nodes.

Memory Allocation

Furthermore, in an array, memory allocation happens at compile time. It is a static memory allocation. However, in a linked list, memory allocation happens at runtime. It is a dynamic memory allocation. Hence, this is another difference between Array and Linked List.

Dependency among Elements

Also, the elements in an array are independent of each other whereas an element or node in a linked list points to the next node or both next node and previous node. 

Conclusion

Both Array and Linked List help to store data linearly. The main difference between Array and Linked List is that Array allocates memory at compile time, which is the time of declaring the array while Linked List allocates memory at runtime, which is the time of adding elements to the linked list.

Reference:

1. “Introduction to Linked Lists.” Types of Network Topology in Computer Networks | Studytonight, Available here.
2. Types of Network Topology in Computer Networks | Studytonight, Available here.

Image Courtesy:

1. “Array2” By No machine-readable author provided. Jarkko Piiroinen assumed (based on copyright claims). – No machine-readable source provided. Own work assumed (based on copyright claims) (Public Domain) via Commons Wikimedia
2. “CPT-LinkedLists-addingnode” By Singly_linked_list_insert_after.png: Derrick Coetzeederivative work: Pluke (talk) – Singly_linked_list_insert_after.png (Public Domain) via Commons Wikimedia