Start learning →

Arrays and linked lists

How to count the cost of an operation, what arrays make cheap and expensive, and how linked lists give up indexing in return for easy insertion.

About 9 hours of study

Learning objectives

Lessons

  1. 1

    What a data structure is

    A way to store data so the operations you need are fast, and how to count the cost of an operation.

  2. 2

    Arrays: insert, delete and 2D arrays

    Insert and delete by shifting, keep a count next to the capacity, and see how a 2D array sits in memory.

  3. 3

    Singly linked lists

    Append with a tail pointer, search, and delete a value while keeping the chain joined.

  4. 4

    Doubly and circular linked lists

    Nodes with prev and next pointers, removing a node in O(1), and a circle of nodes for the Josephus problem.

Module practice

Module quiz

1. An algorithm does about n × n steps on n items. What is its Big-O?
2. Which operation is O(1) on an array?
3. An array holds 8 items and has capacity 10. A new item is inserted at index 2. How many existing items move?
4. A singly linked list has only a head pointer. What does adding a node at the end cost?
5. The node cur follows the node prev in a list. Which order deletes cur correctly?
6. A doubly linked list has 3 nodes, and the middle one is removed. How many pointers inside the two remaining nodes change?
7. An O(n²) algorithm takes 2 seconds for 1,000 items. About how long does it take for 10,000 items?

Stacks and queues ›