Abstract Data Types
From charlesreid1
Main abstract data types:
- Lists
- Maps/Dictionaries
- Sets
- Stacks
- Queues
- Trees
These are basic types of data structures (although some of the data types above may utilize other data types in their implementation, e.g., a linked list structure used to store a dictionary).
Lists
Array list data type
Dynamically expanding array list type. The best way to implement a dynamically expanding array is to have it double in size when the array of capacity n reaches n+1 items. Increasing by a fixed amount incurs an O(n^2) cost.
We also want to dynamically shrink the array, but at a different multiple than 1/2 (otherwise we have a single size change that can toggle the size of the array, incurring O(n) cost with each operation.)
Array list interface
The array list type should implement the following methods:
- search
- append/insert
- remove/pop
- get
- minimum
- maximum
Array list computational complexity
| Operation | Array list | Array list, sorted |
|---|---|---|
| Search(L,k) | O(n) | O(log n) |
| Insert(D,x) | O(1) | O(n) |
| Delete(L,x) | O(1)* | O(n) |
| Successor(L,x) | O(n) | O(1) |
| Predecessor(L,x) | O(n) | O(1) |
| Minimum(L) | O(n) | O(1) |
| Maximum(L) | O(n) | O(1) |
Linked list data type
Linked data structures: much/most of the data in a linked list data type is dedicated to links/addresses
Main differences in implementation of linked list types are in the links themselves. Doubly linked lists have simpler algorithms and are easier to implement, but come with the extra overhead of additional pointers.
Speed of operations on sorted and unsorted linked lists:
| Operation | Singly Linked List | Doubly Linked List | Singly Linked List, Sorted | Doubly Linked List, Sorted |
|---|---|---|---|---|
| Search(L,k) | O(n) | O(n) | O(n) | O(n) |
| Insert(D,x) | O(1) | O(1) | O(n) | O(n) |
| Delete(L,x) | O(n)* | O(1) | O(n)* | O(1) |
| Successor(L,x) | O(n) | O(n) | O(1) | O(1) |
| Predecessor(L,x) | O(n) | O(n) | O(n)* | O(1) |
| Minimum(L) | O(n) | O(n) | O(1) | O(1) |
| Maximum(L) | O(n) | O(n) | O(1)* | O(1) |
Map/Dictionary
Dictionary data type
Flags
 |
Data Structures Part of Computer Science Notes
This is the staging ground for computer science notes as part of the 2017 CS Study Plan.
Classes of data structures: Abstract Data Types Array-based and Link-based memory management: ArrayLists and Linked Lists Algorithmic Analysis of Data Structures: Algorithmic Analysis of Data Structures Advanced data structures: Advanced Data Structures
|
|
Arrays Part of Computer Science Notes
Series on Data Structures Python: Arrays/Python · Arrays/Python/Sizeof · Arrays/Python/AppendCost · Arrays/Python/CaesarCipher · Arrays/Python/CompactArrays · Arrays/Python/DynamicArray Java: Arrays/Java · Arrays/Java/CaesarCipher · Arrays/Java/FisherYates · Arrays/Java/PythonList · Arrays/Java/Repeatedly_Remove Categories: Category:Python Arrays
|
|
Stacks and Queues Part of Computer Science Notes
Series on Data Structures
Stacks and Queues: Python StacksQueues/Python · StacksQueues/Python/ArrayStack · StacksQueues/Python/ArrayQueue · StacksQueues/Python/ArrayDeque StacksQueues/Python/LinkedStack
Stacks and Queues: Java StacksQueues/Java · StacksQueues/Java/ArrayStack · StacksQueues/Java/ArrayQueue · StacksQueues/Java/ArrayQueueFS · StacksQueues/Java/ArrayDeque StacksQueues/Java/LinkedStack · StacksQueues/Java/LinkedQueue · StacksQueues/Java/LinkedDeque
Applications Postfix_Expressions#Stacks · StacksQueues/Subsets · StacksQueues/Subsets/Java
|
|
Priority Queues and Heaps Part of Computer Science Notes
Series on Data Structures
Java: Priority Queues/Java · Priority Queues/ADT · Priority Queues/Sorted · Priority Queues/Unsorted Performance: Priority Queues/Timing and Performance Applications: Maximum Oriented Priority Queue · Priority Queues/Stack
Priority Queues/Heap · Priority Queues/Java · Priority Queues/Comparators
|
|
Linked List Part of Computer Science Notes
Series on Data Structures Java: Linked Lists/Java · Linked Lists/Java/Single · Linked Lists/Java/Double · Linked Lists/Java/Circular Performance: Linked Lists/Java/Timing · Linked Lists/Java/Reverse Python: Linked Lists/Python · Linked Lists/Python/Single
|
|
Trees Part of Computer Science Notes
Series on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree · Trees/ArrayTree · SimpleTree
Tree Traversal Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP · Tree Traversal/Traversal Method Template Tree operations: Trees/Operations Performance · Trees/Removal
Tree Applications Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree · Binary Trees/ArrayBinTree Binary Trees/Cheat Sheet · Binary Trees/OOP · Binary Trees/Implementation Notes
|
|
Search Trees Part of Computer Science Notes
Series on Data Structures
Binary Search Trees · Balanced Search Trees Trees/OOP · Search Trees/OOP · Tree Traversal/OOP · Binary Trees/Inorder
(Note that heaps are also value-sorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)
|
|
Maps and Dictionaries Part of Computer Science Notes
Series on Data Structures
Maps/Dictionaries Maps · Maps/ADT · Maps in Java · Maps/OOP · Maps/Operations and Performance Map implementations: Maps/AbstractMap · Maps/UnsortedArrayMap · Maps/SortedArrayMap Dictionary implementations: Dictionaries/LinkedDict · Dictionaries/ArrayDict
Hashes Hash Maps/OOP · Hash Maps/Operations and Performance Hash Maps/Dynamic Resizing · Hash Maps/Collision Handling with Chaining Hash functions: Hash Functions · Hash Functions/Cyclic Permutation Hash map implementations: Hash Maps/AbstractHashMap · Hash Maps/ChainedHashMap
Skip Lists · Java/ConcurrentSkipList · Java implementations: SkipList
Sets Sets · Sets/ADT · Sets in Java · Sets/OOP · Multisets
|
