Loading [MathJax]/extensions/TeX/newcommand.js

$\newcommand{\E}{\mathrm{E}} \DeclareMathOperator{\ddiv}{div}$

• 1 In­tro­duc­tion
• 1.1 The Need for Ef­fi­ciency
• 1.2 In­ter­faces
• 1.3 Math­e­mat­i­cal Back­ground
• 1.4 The Model of Com­pu­ta­tion
• 1.5 Cor­rect­ness, Time Com­plex­ity, and Space Com­plex­ity
• 1.6 Code Sam­ples
• 1.7 List of Data Struc­tures
• 1.8 Dis­cus­sion and Ex­er­cises
• 2 Ar­ray-Based Lists
• 2.1 ArrayStack: Fast Stack Op­er­a­tions Using an Array
• 2.2 FastArrayStack: An Op­ti­mized Ar­rayStack
• 2.3 ArrayQueue: An Ar­ray-Based Queue
• 2.4 ArrayDeque: Fast Deque Op­er­a­tions Using an Array
• 2.5 DualArrayDeque: Build­ing a Deque from Two Stacks
• 2.6 RootishArrayStack: A Space-Ef­fi­cient Array Stack
• 2.7 Dis­cus­sion and Ex­er­cises
• 3 Linked Lists
• 3.1 SLList: A Singly-Linked List
• 3.2 DLList: A Dou­bly-Linked List
• 3.3 SEList: A Space-Ef­fi­cient Linked List
• 3.4 Dis­cus­sion and Ex­er­cises
• 4 Skiplists
• 4.1 The Basic Struc­ture
• 4.2 SkiplistSSet: An Ef­fi­cient SSet
• 4.3 SkiplistList: An Ef­fi­cient Ran­dom-Ac­cess List
• 4.4 Analy­sis of Skiplists
• 4.5 Dis­cus­sion and Ex­er­cises
• 5 Hash Ta­bles
• 5.1 ChainedHashTable: Hash­ing with Chain­ing
• 5.2 LinearHashTable: Lin­ear Prob­ing
• 5.3 Hash Codes
• 5.4 Dis­cus­sion and Ex­er­cises
• 6 Bi­nary Trees
• 6.1 BinaryTree: A Basic Bi­nary Tree
• 6.2 BinarySearchTree: An Un­bal­anced Bi­nary Search Tree
• 6.3 Dis­cus­sion and Ex­er­cises
• 7 Ran­dom Bi­nary Search Trees
• 7.1 Ran­dom Bi­nary Search Trees
• 7.2 Treap: A Ran­dom­ized Bi­nary Search Tree
• 7.3 Dis­cus­sion and Ex­er­cises
• 8 Scape­goat Trees
• 8.1 ScapegoatTree: A Bi­nary Search Tree with Par­tial Re­build­ing
• 8.2 Dis­cus­sion and Ex­er­cises
• 9 Red-Black Trees
• 9.1 2-4 Trees
• 9.2 RedBlackTree: A Sim­u­lated 2-4 Tree
• 9.3 Sum­mary
• 9.4 Dis­cus­sion and Ex­er­cises
• 10 Heaps
• 10.1 BinaryHeap: An Im­plicit Bi­nary Tree
• 10.2 MeldableHeap: A Ran­dom­ized Meld­able Heap
• 10.3 Dis­cus­sion and Ex­er­cises
• 11 Sort­ing Al­go­rithms
• 11.1 Com­par­i­son-Based Sort­ing
• 11.2 Count­ing Sort and Radix Sort
• 11.3 Dis­cus­sion and Ex­er­cises
• 12 Graphs
• 12.1 AdjacencyMatrix: Rep­re­sent­ing a Graph by a Ma­trix
• 12.2 AdjacencyLists: A Graph as a Col­lec­tion of Lists
• 12.3 Graph Tra­ver­sal
• 12.4 Dis­cus­sion and Ex­er­cises
• 13 Data Struc­tures for In­te­gers
• 13.1 BinaryTrie: A dig­i­tal search tree
• 13.2 XFastTrie: Search­ing in Dou­bly-Log­a­rith­mic Time
• 13.3 YFastTrie: A Dou­bly-Log­a­rith­mic Time SSet
• 13.4 Dis­cus­sion and Ex­er­cises
• 14 Ex­ter­nal Mem­ory Search­ing
• 14.1 The Block Store
• 14.2 B-Trees
• 14.3 Dis­cus­sion and Ex­er­cises