Abstract data structures

Question 1

What is the time complexity for linked list insertion and deletion?

Answer 1

O(1)

Question 2

What is the time complexity for linked list search and indexing

Answer 2

O(n)

Question 3

What is a contiguous list? State an example of a type of contiguous list

Answer 3

A contiguous list refers to a list of entries that is stored in memory cells that are in sequence with consecutive addresses

Array is an example of contiguous list.

Question 4

What are the limitations of contiguous lists?

Answer 4

Must determine how much space to allocate to each entry and number of entries, to determine how much memory to allocate to list

If the list is a dynamic list which changes frequently, this causes a lot of shuffling and reallocation of the computer’s memory.

The entire list might need to be shifted to a new location in the computer’s memory to ensure that there are sufficient contiguous memory cells to store all the entries

Question 5

What is a linked list?

Answer 5

A linked list is a linear data structure which stores data in nodes which do not need to be located in contiguous memory cells

(Linked list is NOT contiguous)

Question 6

What are the benefits of linked lists?

Answer 6

When entries in the list need to be added, deleted or reordered, only the pointers need to be changed, which makes such operations much more efficient, especially when the data stored in each entry is large

Being a dynamic data structure, linked lists only use as much memory as they require as additional memory is allocated to the linked list only when required