The Alchemist.
Back to Problem Solving with DSA

~/blog/tutorials/problem-solving-with-dsa

Linked List

Linked List

A linked list is a chain of nodes where each node holds data and a reference to the next one. That's the whole model. The trade is that you give up O(1) random access — to find the 50th element, you walk from the head — and you get O(1) insertion and deletion once you're at the right position.

This section builds the linked list from scratch. Four posts that cover construction, traversal, mutation, and search.

What's in this section

  1. Introduction to linked lists — Node class, linking, traversal, the LinkedList wrapper
  2. Taking input and length — building a list from data, measuring its size
  3. Insertion and deletion — head, tail, and position variants
  4. Searching — finding a value by traversal

Start with the first post if you've never built a linked list before. Skip ahead if you have.

Tutorial
Jun 2, 202611 min read
0

Linked Lists vs Arrays

The Problem A music player queue. Songs get added to the front when the user taps "play next", and removed from the front when they finish. In Python, the obvio…

Tutorial
Jun 2, 202611 min read
0

Linked List Input and Length

The Problem You have a sequence of values — integers from stdin, items from a list, rows from a file. You need to turn them into a linked list. And once you hav…

Tutorial
Jun 2, 202615 min read
0

Linked List Insertion and Deletion

The Problem Insert a node at a given position. Delete a node at a given position. These are the operations that make linked lists useful — O(1) at the point of…

Tutorial
Jun 2, 20268 min read
0

Linked List Search

The Problem Find whether a value exists in a linked list. If it does, return the 0-indexed position. If it does not, return -1. This is the same problem as sear…