Week 4

Question 1

Linear Data Structure

Answer 1

A collection of nodes (elements) where each node has a unique predecessor and a unique successor

Question 2

What is static array?

Answer 2

A static array is a static structure

Question 3

Advantages

Answer 3

*Faster access to each entry as long as the index is known - O(1) to visit arr[i]

Question 4

Disadvantages

Answer 4

*Fixed size - cannot be easily extended or reduced to fit the data set
*Can be expensive to maintain

Question 5

Limitations of using an array (Searching)

Answer 5

*Unsorted data - linear search (Efficiency O(n))
*Sorted data - binary search (Efficiency O(log2n))

Question 6

Limitations of using an array (Insertion)

Answer 6

*Unsorted data - (Efficiency O(1))
*Sorted data - (Efficiency O(n))

Question 7

Limitations of using an array (Deletion)

Answer 7

*Unsorted data - (Efficiency O(1))
*Sorted data - (Efficiency O(n))

Question 8

What is Linked List ?

Answer 8

*A collection of objects, called nodes
*A dynamic data structure
(The number of nodes in the list is not fixed)
(The linked list can grow and shrink on demand)

Question 9

Components of every node

Answer 9

*information - to be stored (the data)
*reference - to the next node (often called a link)

Question 10

Advantages

Answer 10

*Easily extended or reduced to fit the data set
*Efficient - O(1) to insert / delete item, once located

Question 11

Disadvantages

Answer 11

*Does not allow direct access to individual items
*Uses more memory compared to an array

Question 12

Components of accessing SLL

Answer 12

*head
(Static variable)
(Contains a reference to the first node)
*head.data
(accesses data sorted in the first node)
*head.link
(reference to the second node)

Question 13

Other types of Linked Lists

Answer 13

*Singly Linked List with a Dummy Node
*Circular Singly Linked List
*Doubly Linked List
*SkipList

Question 14

SkipList Data Structure

Answer 14

*Probabilistic data structure
*Based on a set of parallel linked lists
*Has improved efficiency, compared to a SLL, for must operations

Question 15

Orders in SkipList

Answer 15

*Extension of an ordered SLL with additional forward links, added in a randomized way
*Effect - During a search we can skip parts of the list
*Efficiency - On average all operations are performed in logarithmic randomized time O(log2n)

Question 16

SkipList Deletion(Part 1)

Answer 16

*Determine level by using a probabilistic technique: A random number generator to determine level of insertion
*Find where to insert: You will need to build an array to hold references for each level
*Insert by adjusting references at each level

Question 17

SkipList Deletion(Part 2)

Answer 17

*Need to build an update array during the search for the item to be deleted
*Nodes specified by the update array will have their forward references adjust around the node to be deleted