Programming foundations

Stage 4 · Lesson 3 of 10

Linked lists

Data structures and Big-O

A stores each item in its own node, together with a pointer to the next node. In a doubly linked list, each node also points to the one before. Inserting or removing a node you already hold is O(1), because nothing has to shift.

But reaching the i-th item means walking from the head (the first node), which is O(n). Nodes scattered around memory are also slow for the . In everyday code you will nearly always choose a instead.

Build a linked list anyway. Writing insert, delete and reverse makes references concrete, and linked nodes are how , queues, trees and are built. Draw boxes and arrows on paper before you write any pointer code.

A question to check yourself, an AI practice session and 1 cheat sheet entry come when you add the roadmap to your account. Add it

Resources for this stage

Start with· follow one of these

Practise

Keep handy

  • VisuAlgo

    Step through linked lists, hash tables and sorts with your own input

  • The Python Tutorial

    Chapter 5 on lists, dicts, sets and deque: the built-ins you will use from now on

Also worth your time

Mark this stage as not done?