Mix and Match Data Structures for Efficient Algorithms
Discover how to combine basic data structures like arrays, linked lists, and trees to create specialized data structures for various applications. Explore the concept of mix-and-match data structures with multiple organizations to implement efficient algorithms like adjacency lists and matrices for graphs. Learn about different operations, complexities, and optimizations using hashing techniques for fast searching on unsorted linked lists.
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
CS1020 Data Structures and Algorithms I Lecture Note #17 Mix-and-Match Data Structures with Multiple Organisation
Basic Data Structures Arrays Linked Lists Trees (to be covered in CS2010) We can combine them to implement different data structures for different applications. [CS1020 Lecture 17: Mix-and-Match] 2
Mix-and-Match Array of Linked Lists E.g.: Adjacent list for representing graph E.g.: Hash table with separate chaining 1 2 3 [CS1020 Lecture 17: Mix-and-Match] 3
Adjacency List for Directed Graph v2 1 2 v3 v1 4 2 3 2 4 4 v5 v4 3 4 5 G [CS1020 Lecture 17: Mix-and-Match] 4
Adjacency Matrix for Directed Graph Matrix[i][j] = 1 if (vi, vj) E 0 if (vi, vj) E v2 v3 v1 1 v1v2v3v4v5 1 v10 1 2 v20 0 3 v30 1 4 v40 0 5 v50 0 2 3 4 5 v5 v4 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 G [CS1020 Lecture 17: Mix-and-Match] 5
CS1102 AY2003 [CS1020 Lecture 17: Mix-and-Match] 6
CS1102 AY2003: Use Adjacency Matrix Operation Big-O 1 2 T 3 4 1 O(1) insert(i, j) 2 T T O(1) delete(i, j) 3 T O(1) exists(i, j) 4 T O(n) neighbours(i) [CS1020 Lecture 17: Mix-and-Match] 7
CS1102 AY2003: Use Adjacency List Operation Big-O 1 O(1) insert(i, j) 2 3 O(n) delete(i, j) 4 O(n) exists(i, j) O(ni) neighbours(i) [CS1020 Lecture 17: Mix-and-Match] 8
Problem Searching on an unsorted linked list is O(n) How to improve it to O(1)? Use hashing. (i, j) as key and the hash value returned by hash function to be index to a hash table where (i, j) is stored together with the reference to the node in the linked list. [CS1020 Lecture 17: Mix-and-Match] 9
Use Adjacency List Operation Big-O 1 insert(i, j) O(1) 2 3 delete(i, j) O(n) 4 exists(i, j) O(1) Is delete (i, j) O(1)? neighbours(i) O(ni) [CS1020 Lecture 17: Mix-and-Match] 10
CS1102 AY2003 Build an adjacency list of the graph, where the lists are doubly linked. Build a hash table with (i, j) as key, and a reference to the node representing (i, j) in the adjacency list as value. [CS1020 Lecture 17: Mix-and-Match] 11
