Arrays and Lists – The Building Blocks of Data

When you first start programming, one of the most fundamental challenges is organizing data in a way that makes it easy to access and manipulate. Arrays and linked lists are two of the most common ways to store data in a structured way.

In this post, we’ll explore what arrays and linked lists are, how they work, their real-world uses, and when to choose one over the other. For a refresher, or intro, to data strcutres, you can review our previous post on this topic from the fundamentals course.

What is an Array?

An array is a collection of elements stored contiguously (an unbroken sequence) in memory. Think of it like a row of lockers in a school hallway, where each locker has a number (an index) and can store exactly one item.

Key Features of Arrays

Fixed Size – Once created, the size of an array doesn’t change.
Fast Access – You can quickly get any element by its index.
Efficient for Lookup – Searching by index is O(1) time complexity.

Example of an Array in Python

# Creating an array of numbers
numbers = [10, 20, 30, 40, 50]

# Accessing an element
print(numbers[2])  # Output: 30

Real-World Example: Contact Lists

A contact list on your phone is like an array. Each contact has a position, and you can quickly find someone by scrolling to their name (index).

What is a Linked List?

A linked list is a collection of elements, but instead of being stored next to each other in memory, each element (called a node) contains:

Data – The actual value.
A pointer (or link) – A reference to the next node in the list.

Imagine a treasure hunt, where each clue points to the next location instead of everything being in one place.

Key Features of Linked Lists

Dynamic Size – Can grow or shrink as needed.
Slower Access – Must start at the first node and follow links (O(n) time complexity).
Efficient Insertions/Deletions – Adding or removing elements doesn’t require shifting data.

Example of a Linked List in Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Creating nodes
head = Node(10)
second = Node(20)
third = Node(30)

# Linking nodes
head.next = second
second.next = third

# Traversing the linked list
current = head
while current:
    print(current.data)
    current = current.next

Your social media feed is like a linked list. New posts get added at the top, and you scroll down through previous ones, following links between posts.

When to Use Arrays vs. Linked Lists

Feature	Array	Linked List
Size	Fixed	Dynamic (grows/shrinks)
Access Speed	Fast (O(1) by index)	Slow (O(n) sequential)
Insertion/Deletion	Slow (requires shifting)	Fast (just change links)
Memory Usage	Efficient (contiguous)	More overhead (pointers)

Choosing the Right One

Use an array when fast access by index is needed (e.g., game leaderboards). Use a linked list when frequent insertions and deletions are required (e.g., music playlists).

How Arrays and Lists Relate to Algorithms

Data structures and algorithms work hand in hand. Here’s how arrays and linked lists connect to key algorithm topics:

Sorting Algorithms: Arrays are commonly used in QuickSort and MergeSort.
Searching Algorithms: Binary search requires an array to be sorted, while linear search can work on both arrays and linked lists.
Recursion & Backtracking: Linked lists naturally lend themselves to recursive processing.

Next up, we’ll explore Stacks and Queues, which build upon these concepts!

💡 Try This Challenge

Write a program that adds five numbers to an array and then reverses the order using a loop. Can you do the same with a linked list?

Let us know your thoughts and solutions in the comments! 🚀