Understanding Data Structures in Computer Science
Explore the implementation of abstract data types and sets/dictionaries, emphasizing fundamental data structures like arrays and linked lists. Learn about array and linked list performance, circular arrays, queues, and stacks, and their practical applications in algorithms. Gain insights into the importance of specifying and implementing data structures effectively in computer science.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture 2. Abstract Data Types, Implementations of Sets/Dictionaries CpSc 212: Algorithms and Data Structures Brian C. Dean School of Computing Clemson University Fall, 2012
Fundamental Data Structures A[0] A[N 1] Arrays NULL head Linked Lists Linked list questions are particularly popular in job interviews; e.g., - Insert or delete a node in a linked list - Reverse a linked list 2
Array and Linked List Performance A[0] A[N 1] Retrieve or modify any element in O(1) time. Insert or delete in middle of list: O(N) time. Insert or delete from ends: O(1) time Be careful not to run over end of allocated memory Possibly consider using a circular array NULL head Seek to any position in list: O(N) time. Then insert or delete element: O(1) time. Insert or delete from ends: O(1) time. 3
Circular Arrays, Queues back front A[0] A[N 1] back front First-In, First-Out (FIFO). Could be implemented using linked lists instead void insert(int x) int remove(void) { { A[front] = x; int result = A[back]; front = (front+1) % N; back = (back+1) % N; } return result; } 4
Circular Arrays, Queues back front A[0] A[N 1] back front First-In, First-Out (FIFO). Could be implemented using linked lists instead Example: cat file | grep algorithm | wc l counts the number of lines in file containing algorithm . Queues are used to send data from one program to the next along the pipeline. 5
Stacks top A[0] Last-In, First-Out (LIFO). Could also be implemented with a linked list... void push(int x) int pop(void) { { A[top++] = x; return A[--top]; } }
Stacks top A[0] Example: A stack is used to store the state of unfinished function calls. For example void what_does_this_do(int n) { if (n==0) return; printf ( %d\n , n); what_does_this_do(n-1); printf ( %d\n , n); }
An Important Distinction Specification of a data structure in terms of the operations it needs to support. A concrete approach for implementation of the data structure that fulfills these requirements. (sometimes called an abstract data type) 8
Example: Queues Choices for concrete implementation: Abstract data type: queue Must support these operations: - Insert(k)a new key k into the structure. - Remove the least- recently-inserted key from the structure. (so FIFO behavior) back front 1 9 8 Circular array 4 2 last first 9 1 4 2 8 (Doubly) linked list 9
Enforcing Abstraction in Code Concrete implementation: queue.cpp Abstract data type: queue queue.h: class Queue { private: int *A; int front, back, N; public: Queue(); ~Queue(); void insert(int key); int remove(void); }; 10
Enforcing Abstraction in Code Concrete implementation: queue.cpp Abstract data type: queue queue.h: class Queue { private: int *A; int front, back, N; Queue q; q.insert(6); x = q.remove(); int Queue::remove(void) { int result = A[back]; back = (back+1) % N; return result; } public: Queue(); ~Queue(); void insert(int key); int remove(void); }; 11
Example: Sets / Dictionaries Choices for concrete implementation: Abstract data type: set / dictionary 1 2 3 5 8 Must support these operations: - Insert(k)a new key k into the structure. - Remove(k)a key k in the structure. - Find(k) whether a key is in the structure. - Enumerate all keys in structure (in any order). Sorted array 5 8 Unsorted array 1 3 2 5 3 1 2 8 Sorted (doubly) linked list 3 1 5 8 2 Unsorted (doubly) linked list 12
Running Time Tradeoffs Choices for concrete implementation: Insert Remove Find 1 2 3 5 8 O(n) O(n) O(log n) Sorted array O(1), post-find 5 8 Unsorted array 1 3 2 O(1) O(n) O(1), post-find O(1), post-find 5 3 1 2 8 O(n) Sorted (doubly) linked list O(1), post-find 3 1 5 8 2 O(1) O(n) Unsorted (doubly) linked list 13
Advanced Set Data Structures O(log n) expected height Skip Lists = dummy gap element 1 2 4 5 7 8 9 Sorted Arrays with Gaps Later on: hash tables, balanced binary search trees, B-trees. 14
Skip Lists: Summary Each level contains roughly half the elements of the level below it. Total space: roughly N + N/2 + N/4 + = 2N = O(N). Expected height: O(log N) O(log N) expected time for insert, remove, and find. Insert uses randomization in a clever way: Insert into level 0 first, and then flip a fair coin repeatedly. Keep inserting into higher levels as long as we flip heads. Find analyzed most easily in reverse: Roughly half our steps go up, the others go left. But we can step up only as many times as the max height of the skip list, which is O(log n) in expectation. 15
Arrays with Gaps Store N array elements within a block of size, say, 1.5N, with regularly-spaced gap elements. As long as gaps are regularly-spaced, we can still perform find with binary search in O(log N) time! Remove just creates a new gap element. Insert speeds up, since fewer elements need to be moved (just move them over until we reach a gap). Tricky part: occasionally need to re-distribute the gaps to keep them regularly spaced. Requires amortized analysis to analyze performance. Implemented properly, insert and remove take O(log2 N) amortized time. (slightly complicated though ) 16
