Why use an array if linked lists can grow indefinitely?

Arrays take up less memory because they don't need to store pointers. They also allow instant access to any element, which is essential for algorithms like binary search. Sometimes, raw read speed is more important than the ability to resize.

Can a linked list go backwards?

A standard 'singly linked list' only goes forward. However, you can create a 'doubly linked list' where each node stores two pointers: one pointing to the next node, and one pointing to the previous node. This lets you traverse in both directions, but it uses even more memory.

What is a dynamic array?

A dynamic array (like an ArrayList in Java or a list in Python) is a standard array in the background that automatically resizes itself. When it gets full, it builds a new array double the size and copies the elements over. It gives you the fast access of an array with the flexible sizing of a linked list, though the resizing step still temporarily slows down the computer.

What is the difference between an array and a linked list?

The main difference between an array and a linked list is how they store data in your computer's memory. An array stores elements in a single, continuous block of memory, which makes finding a specific item very fast but makes resizing difficult. A linked list stores elements in scattered memory locations, connecting them with pointers, which makes resizing and inserting items easy but slows down searching.

Think of an array like a row of connected lockers: if you know the locker number, you can go straight to it. A linked list is more like a treasure hunt: you only know where the first clue is, and each clue tells you exactly where to find the next one. Both hold your data, but they require very different strategies to use effectively.

What is an array?

An array is a data structure that holds a fixed number of items of the same type in sequential memory addresses. When you create an array, the computer reserves a single, solid block of memory for it. Because the items are stored right next to each other, the computer can instantly calculate exactly where any item is using its index (its position in the array). This is called random access, and it happens in $O(1)$ time.

However, this rigid structure has a downside. If your array is full and you want to add another item, you cannot just stick it on the end—the memory space next to your array might already be used by another program. You have to create a brand new, larger array and copy all your data over, which takes time.

What is a linked list?

A linked list is made up of individual building blocks called nodes. Each node contains two things: the data you want to store, and a pointer (a memory address) that links to the next node in the sequence. The computer can store these nodes wherever it finds free space in memory; they do not need to be next to each other.

Because the memory isn't continuous, you cannot instantly jump to the 10th item. To find it, you must start at the very first node (the head) and follow the pointers one by one until you reach your destination. This sequential access takes $O(n)$ time. The huge advantage is that adding a new item is easy: you just find some free memory, create a node, and update a single pointer to include it in the chain.

Comparing memory and performance

Arrays win when it comes to reading data. If your program needs to look up values frequently by their index, arrays are incredibly fast. They also use less memory per item because they do not have to store pointers.

Linked lists win when your data size changes constantly. If you are frequently inserting or deleting items in the middle of your data, linked lists do this efficiently. You just change a couple of pointers, rather than shifting thousands of elements down one spot like you would have to do in an array.

Where students commonly slip up

When working with arrays, students often forget that indexes start at zero. This leads to the classic 'Index Out Of Bounds' error when trying to access the $n$ -th element using index $n$ instead of $n-1$ .

With linked lists, the most common trap is the 'Null Pointer Exception'. This happens when you try to follow a pointer that leads nowhere, or if you accidentally overwrite a pointer before saving the rest of the list, permanently losing the chain of data.

Worked through

Imagine you have a list of 4 numbers: [10, 20, 30, 40]. You want to insert the number 25 between 20 and 30. How much work does the computer have to do if this is an array versus a linked list?

If it is an array: You must first ensure the array has space for a 5th element. Then, you have to shift the number 40 one spot to the right. Next, you shift the number 30 one spot to the right. Finally, the spot where 30 used to be is open, and you can write 25 into that space. You had to move every element that came after the insertion point.

If it is a linked list: You start at the head (10) and follow the pointer to (20). You create a new node containing 25 somewhere in memory. You tell the new node (25) to point to (30). Then, you change the pointer of (20) so it points to (25) instead of (30). You didn't have to touch or move the number 40 at all.

Questions students ask

Ask about this topic

Explain at

Where this comes from: Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein · OpenStax Data Structures and Algorithms · Khan Academy: Computer Science - Data Structures