Arrays store a set of values by index using O(n) space, where n is the largest...

 

Transcribed Image Text:

Arrays store a set of values by index using O(n) space, where n is the largest index of the array. In some cases, most indices of the array are null, wasting space; such arrays are called sparse arrays. In other words, the number of non- default values stored m, is much smaller than the largest index n. Given the array A that consists of: [1, null, null, null, 2, null, null, null, null, null, null, null, null, null, null, 3] we have n = 16, m = 3. We can instead store the data using a doubly linked list, storing each non-null value as an (index, value) pair. Since we only store the non- null values, this list implementation gives us O(m) storage. a) Draw a doubly linked-list representation of the data in A, showing both the structure and the data. b) Explain one disadvantage of storing A using a doubly linked list instead of an array? c) Explain why a linked list is usually implemented as a doubly linked list, rather than as a singly linked list. d) Sparse arrays can also be implemented efficiently with hash tables. Describe how a hash table might be used to store a sparse array with O(m) storage. Arrays store a set of values by index using O(n) space, where n is the largest index of the array. In some cases, most indices of the array are null, wasting space; such arrays are called sparse arrays. In other words, the number of non- default values stored m, is much smaller than the largest index n. Given the array A that consists of: [1, null, null, null, 2, null, null, null, null, null, null, null, null, null, null, 3] we have n = 16, m = 3. We can instead store the data using a doubly linked list, storing each non-null value as an (index, value) pair. Since we only store the non- null values, this list implementation gives us O(m) storage. a) Draw a doubly linked-list representation of the data in A, showing both the structure and the data. b) Explain one disadvantage of storing A using a doubly linked list instead of an array? c) Explain why a linked list is usually implemented as a doubly linked list, rather than as a singly linked list. d) Sparse arrays can also be implemented efficiently with hash tables. Describe how a hash table might be used to store a sparse array with O(m) storage.

Answer rating: 100% (QA)

a Here is a representation of the data in array A using a doubly linked list 1 2 3 In this represent... View the full answer