book

Data Structures and Algorithms in Python

by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser

March 2013

Intermediate to advanced

748 pages

21h 42m

English

Wiley

Read now

Unlock full access

Book FeaturesOnline ResourcesContents and OrganizationPrerequisitesRelation to Computer Science CurriculumAbout the AuthorsAdditional Books by These AuthorsAcknowledgments
1.1 Python Overview1.2 Objects in Python1.3 Expressions, Operators, and Precedence1.4 Control Flow1.5 Functions1.5.1 Information Passing1.6 Simple Input and Output1.7 Exception Handling1.8 Iterators and Generators1.9 Additional Python Conveniences1.10 Scopes and Namespaces1.11 Modules and the Import Statement1.12 Exercises
2.1 Goals, Principles, and Patterns2.2 Software Development2.3 Class Definitions2.4 Inheritance2.5 Namespaces and Object-Orientation2.6 Shallow and Deep Copying2.7 Exercises
3.1 Experimental Studies3.2 The Seven Functions Used in This Book3.3 Asymptotic Analysis3.4 Simple Justification Techniques3.5 Exercises
4.1 Illustrative Examples4.2 Analyzing Recursive Algorithms4.3 Recursion Run Amok4.4 Further Examples of Recursion4.5 Designing Recursive Algorithms4.6 Eliminating Tail Recursion4.7 Exercises

5.1 Python's Sequence Types5.2 Low-Level Arrays5.3 Dynamic Arrays and Amortization5.4 Efficiency of Python's Sequence Types5.5 Using Array-Based Sequences5.6 Multidimensional Data Sets5.7 Exercises
6.1 Stacks6.2 Queues6.3 Double-Ended Queues6.4 Exercises
7.1 Singly Linked Lists7.2 Circularly Linked Lists7.3 Doubly Linked Lists7.4 The Positional List ADT7.5 Sorting a Positional List7.6 Case Study: Maintaining Access Frequencies7.7 Link-Based vs. Array-Based Sequences7.8 Exercises
8.1 General Trees8.2 Binary Trees8.3 Implementing Trees8.4 Tree Traversal Algorithms8.5 Case Study: An Expression Tree8.6 Exercises
9.1 The Priority Queue Abstract Data Type9.2 Implementing a Priority Queue9.3 Heaps9.4 Sorting with a Priority Queue9.5 Adaptable Priority Queues9.6 Exercises
10.1 Maps and Dictionaries10.2 Hash Tables10.3 Sorted Maps10.4 Skip Lists10.5 Sets, Multisets, and Multimaps10.6 Exercises
11.1 Binary Search Trees11.2 Balanced Search Trees11.3 AVL Trees11.4 Splay Trees11.5 (2,4) Trees11.6 Red-Black Trees11.7 Exercises
12.1 Why Study Sorting Algorithms?12.2 Merge-Sort12.3 Quick-Sort12.4 Studying Sorting through an Algorithmic Lens12.5 Comparing Sorting Algorithms12.6 Python's Built-In Sorting Functions12.7 Selection12.8 Exercises
13.1 Abundance of Digitized Text13.2 Pattern-Matching Algorithms13.3 Dynamic Programming13.4 Text Compression and the Greedy Method13.5 Tries13.6 Exercises
14.1 Graphs14.2 Data Structures for Graphs14.3 Graph Traversals14.4 Transitive Closure14.5 Directed Acyclic Graphs14.6 Shortest Paths14.7 Minimum Spanning Trees14.8 Exercises
15.1 Memory Management15.2 Memory Hierarchies and Caching15.3 External Searching and B-Trees15.4 External-Memory Sorting15.5 Exercises

Content preview from Data Structures and Algorithms in Python

Chapter 7 Linked Lists

images

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:

The length of a dynamic array might be longer than the actual number of elements that it stores.
Amortized bounds for operations may be unacceptable in real-time systems.
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 ...