Data Structures and Algorithms in Python

Chapter 7

Linked Lists

Contents

7.1 Singly Linked Lists

7.1.1 Implementing a Stack with a Singly Linked List

7.1.2 Implementing a Queue with a Singly Linked List

7.2 Circularly Linked Lists

7.2.1 Round-Robin Schedulers

7.2.2 Implementing a Queue with a Circularly Linked List

7.3 Doubly Linked Lists

7.3.1 Basic Implementation of a Doubly Linked List

7.3.2 Implementing a Deque with a Doubly Linked List

7.4 The Positional List ADT

7.4.1 The Positional List Abstract Data Type

7.4.2 Doubly Linked List Implementation

7.5 Sorting a Positional List

7.6 Case Study: Maintaining Access Frequencies

7.6.1 Using a Sorted List

7.6.2 Using a List with the Move-to-Front Heuristic

7.7 Link-Based vs. Array-Based Sequences

7.8 Exercises

In Chapter 5 we carefully examined Python's array-based list class, and in Chapter 6 we demonstrated use of that class in implementing the classic stack, queue, and dequeue ADTs. Python's list class is highly optimized, and often a great choice for storage. With that said, there are some notable disadvantages:

1. The length of a dynamic array might be longer than the actual number of elements that it stores.
2. Amortized bounds for operations may be unacceptable in real-time systems.
3. Insertions and deletions at interior positions of an array are expensive.

In this chapter, we introduce a data structure known as a linked list, which provides an alternative to an array-based ...