Linked Lists

A linked list is a dynamically-resizable alternative to an array, made of nodes that contain pointers to other nodes. The main advantage of a linked list is its dynamism: that is to say it can be used to store data even if the programmer does not know how much data must be stored. This dynamism, however, comes at the cost of (a) memory, as extra space is required to store all the pointers, as well as (b) time, as binary search is no longer a possibility without random access. Linked lists are an alternative to arrays when implementing stacks and queues, earlier sections in this chapter. In this section, we will discuss singly linked lists in detail, as well as briefly touch on doubly linked lists, go over the trade-offs associated with using this data structure, as well as revisit stacks and queues to see how they can be implemented with a linked list.

• Lecture

  • Watch on Youtube
  • Watch on the CS50 Video Player
  • Download Lecture
  • Lecture Notes

• Shorts

  • Singly-Linked Lists
  • Doubly-Linked Lists
  • Singly-Linked Lists (Jackson)

• Supplementary Resources

  • Pankaj Rai on Know your data structure - Linked List
  • David Pynes on Linked lists: introducing data structures
  • Michael Olorunnisola on How Linked Lists Work

• Thought Questions

  • What are some trade-offs between using an array, a singly linked list, or a doubly linked list?
  • How would one implement a stack and a queue using linked lists?
  • When would one want to implement a stack and a queue using a linked list?

• Problem

  • Decisions