March 2013
Intermediate to advanced
748 pages
21h 42m
English
book
Data Structures and Algorithms in Python
by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
Content preview from Data Structures and Algorithms in Python
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
Chapter 7
Linked Lists
Contents
7.1.1 Implementing a Stack with a Singly Linked List
7.1.2 Implementing a Queue with a Singly Linked List
7.2.2 Implementing a Queue with a Circularly Linked List
7.3.1 Basic Implementation of a Doubly Linked List
7.3.2 Implementing a Deque with a Doubly Linked List
7.4.1 The Positional List Abstract Data Type
7.4.2 Doubly Linked List Implementation
7.6 Case Study: Maintaining Access Frequencies
7.6.2 Using a List with the Move-to-Front Heuristic
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 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.