Sorted List ADT (array based), List ADT (linked nodes based)

Question 1

Main property of a Sorted List ADT

Answer 1

A sorted list ADT is a collection of values that are ordered according to a comparison function, and can be accessed by index. The main property of a sorted list ADT is that it maintains the order of the elements after each insertion or deletion, and supports efficient searching of elements using binary search.

Question 2

Key operations of the Sorted List ADT

Answer 2

The key operations of a sorted list ADT are add, index, delete_at_index, len, and getitem. Add adds a value to the sorted list at the correct position, index returns the position of a value in the sorted list, delete_at_index removes and returns the value from the sorted list at a given position, len returns the number of elements in the sorted list, and getitem returns the value from the sorted list at a given position without removing it.

Question 3

When (in practice) can sorted lists be preferred to normal (unsorted) lists? When is it better to use unsorted lists?

Answer 3

Sorted lists can be preferred to normal (unsorted) lists when the following conditions are met:

The elements in the list have a well-defined ordering, such as numbers, strings, or objects with a comparison method
The list is frequently searched for specific elements, and the search time is critical for the performance of the program
The list is not modified too often, and the insertion and deletion time is not critical for the performance of the program

Unsorted lists can be better than sorted lists when the following conditions are met:

The elements in the list do not have a well-defined ordering, or the ordering is not relevant for the purpose of the program
The list is rarely searched for specific elements, or the search time is not critical for the performance of the program
The list is modified frequently, and the insertion and deletion time is critical for the performance of the program

Question 4

What is the best-case and worst-case complexity of the below operations for a Sorted List ADT, if implemented with an array? Assume that item search is done with either linear search (or binary search). Explain the reason for the best and worst case. No explanation no marks.

index()

add()

Answer 4

The best-case and worst-case complexity of the below operations for a sorted list ADT, if implemented with an array, are:

index(): O(logn)
in both cases, where n
is the number of elements in the sorted list, because it involves using binary search to find the position of the value in the sorted array, which takes logn
steps in the worst case
add(): O(1)
in the best case, when the value is smaller than the first element or larger than the last element in the sorted list, and O(n)
in the worst case, when the value is somewhere in the middle of the sorted list, because it involves finding the correct position of the value using binary search, which takes logn
steps, and shifting the elements in the array, which takes n
steps in the worst case

Question 5

For a sorted list of elements, what is the difference between linear search and binary search applied to the list? Give the best-case and worst-case complexity of both.

Answer 5

For a sorted list of elements, the difference between linear search and binary search applied to the list are:

Linear search is a simple algorithm that scans the list from left to right, and checks each element until it finds the target value or reaches the end of the list. Binary search is a more efficient algorithm that divides the list into two halves, and compares the target value with the middle element of the list. If the target value is equal to the middle element, the search is done. If the target value is smaller than the middle element, the search continues in the left half of the list. If the target value is larger than the middle element, the search continues in the right half of the list. This process is repeated until the target value is found or the list is exhausted.

The best-case complexity of linear search is O(1)
, when the target value is the first element of the list. The best-case complexity of binary search is also O(1)
, when the target value is the middle element of the list. The worst-case complexity of linear search is O(n)
, where n
is the number of elements in the list, when the target value is the last element of the list or not in the list. The worst-case complexity of binary search is O(logn)
, where n
is the number of elements in the list, when the target value is not in the list.

Question 6

State three advantages and disadvantages of Linked Nodes data structures?

Answer 6

The advantages of linked nodes data structures are:

They have a dynamic size, which means they can grow or shrink as needed, and do not waste memory for unused slots
They allow fast insertion and deletion of elements at any position, as they only require changing the pointers of the nodes, and do not involve shifting the elements
They can store heterogeneous data, as each node can have a different data type, and can be easily extended to implement other ADTs, such as stacks, queues, or trees

The disadvantages of linked nodes data structures are:

They have a high memory overhead, as they require extra space for storing the pointers of the nodes, and may cause memory fragmentation
They do not allow random access to the elements, as they require traversing the nodes from the beginning to reach a specific position, and do not support indexing or slicing operations
They are more complex and difficult to implement, as they require creating and managing the nodes and the pointers, and handling the edge cases, such as empty or single-node lists

Question 7

What is the best-case and worst-case complexity of the below operations for a List ADT, if implemented with an linked nodes? Explain the reason for the best and worst case. No explanation no marks.

insert()

index()

delete_at_index()

__get_node_at_index()

Answer 7

The best-case and worst-case complexity of the below operations for a list ADT, if implemented with linked nodes, are:

insert(): O(1)
in the best case, when the position is at the beginning or the end of the list, and O(n)
in the worst case, when the position is somewhere in the middle of the list, because it involves creating a new node, and changing the pointers of the nodes, which takes one step in the best case, and n
steps in the worst case
index(): O(1)
in the best case, when the value is at the beginning of the list, and O(n)
in the worst case, when the value is at the end of the list or not in the list, because it involves traversing the nodes from the beginning to find the value, which takes one step in the best case, and n
steps in the worst case
delete_at_index(): O(1)
in the best case, when the position is at the beginning or the end of the list, and O(n)
in the worst case, when the position is somewhere in the middle of the list, because it involves deleting the node, and changing the pointers of the nodes, which takes one step in the best case, and n
steps in the worst case
__get_node_at_index(): O(1)
in the best case, when the position is at the beginning of the list, and O(n)
in the worst case, when the position is at the end of the list, because it involves traversing the nodes from the beginning to reach the position, which takes one step in the best case, and n
steps in the worst case