Related Tags

data structures
arrays

# What are the differences between arrays and linked lists?

Arrays and Linked Lists are two of the most popular linear data structures. Let’s look at some of their major differences:​

## 1. Memory allocation

#### Array

The entire array is stored in a contiguous block of memory.

Different elements are stored at different memory locations.

## 2. Size

#### Array

The size of an array is specified at the time of declaration and cannot be changed afterward​.

Data items can be added or removed from the linked list whenever desired.

## 3. Space utilization

#### Array

Due to contiguous allocation, an array can only be stored where there is a ​large block of free space is available.

Different elements are stored at different locations; hence, linked lists can be made within small chunks of free space.

## 4. Space consumption

#### Array

Space consumption is overall ​less.

Space is required to store pointers next to nodes.

## 5. Accessing elements

#### Array

Any element can be directly indexed in $O(1)$ worst-case time.

The list needs to be traversed from the first element up to the required element, taking $O(n)$ worst-case time.

## 6. Search options

#### Array

Linear search and Binary search (if sorted).

Linear search only.

RELATED TAGS

data structures