Related Tags

data structures
arrays

# What are the differences between arrays and linked lists?

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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