Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data structures
linked lists
arrays

What are the differences between arrays and linked lists?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

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:​

Arrays

Linked Lists

svg viewer
svg viewer

1. Memory allocation

Array

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

Linked list

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​.

Linked list

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.

Linked list

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.

Linked list

Space is required to store pointers next to nodes.

5. Accessing elements

Array

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

Linked list

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

6. Search options

Array

Linear search and Binary search (if sorted).

Linked list

Linear search only.

RELATED TAGS

data structures
linked lists
arrays
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

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.

Keep Exploring