A1 Theory W4

Question 1

Briefly describe Sorted List ADT giving details about

Main property of a Sorted List ADT;

Key operations of the Sorted List ADT;

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

Answer 1

Main property of a Sorted List ADT is that the elements are arranged in a specific order which allows for efficient searching and retrieval operations based on that order.

Main operations:
Add: this operation adds an element to the list while maintaining sorted order
TBC

Sorted or unsorted?
Sorted lists are preferred:
- when you need to find elements that satisfy a certain condition, like finding all elements within a certain range
- when you perform operations that require maintaining the order of elements, like finding the median element
- when you need to efficiently insert and maintain a sorted order simultaneously

Unsorted lists can be better when:
- you need frequently add and remove elements and order is not crucial
- when memory usage is concerned, sorted lists require additional overhead to maintain order

Question 2

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 2

index():
Best-case is O(1) - binary search algorithm finds the desired element at the middle of the array in the first step, giving constant time complexity
Worst-case is O(log n) - binary search algorithm takes logarithmic time to find desired element. Occurs when element is at either end of list or not present.

add():
Best-case is O(1) - adding an element at the end of the array and no shifting is required, giving constant time.
Worst-case is O(n) - adding an element at the beginning of the array and all elements being shifted one position to the right. Giving linear time.

Question 3

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 3

Linear search involves sequentially checking each element of the list until the desired element is found or until the end of the list is reached. This is simple to implement and works on both sorted and unsorted lists but can be slow for larger lists.

Binary search involves a more efficient search algorithm that takes advantage of the sorted nature of the list. It repeatedly divides the search range in half, eliminating half of the remaining elements each time. Binary search is significantly faster for larger sorted lists compared to linear but requires the list to be sorted and works only on sorted lists.

Linear search complexity:
Best-case is O(1) - this is when the desired element is first in the list
Worst-case is O(n) - when the desired element is last in the list or not present requiring the algorithm to traverse the whole list.

Binary search complexity:
Best-case is O(1) - when the desired element is in the centre of the list
Worst-case is O(log n) - when this list is large and the search space is halved with each step

Question 4

State three advantages and disadvantages of Linked Nodes data structures?

Answer 4

Advantages of Linked Node Data Structures:
- Dynamic size: Linked node data structures allow for dynamic sizing like linked lists. Elements can be easily added or removed without needing to allocate or deallocate memory in advance.

• Efficient insertions and deletions: Insertions and deletions can be efficient in linked nodes, especially when dealing with elements in the middle of the structure. No need for time consuming element shifting like in arrays, linked nodes only require a few pointer adjustments.
• Constant time insertions at Beginning: adding an element at the beginning of a linked node structure takes constant time as it involves updating only a few pointers.

Disadvantages of Linked Nodes:
- Memory overhead: linked nodes consume more memory compared to array-based data structures due to the additional memory required for the pointers that connect the elements. Each element has its own data and a reference to the next element.

• Random access inefficiency: Linked nodes do not support constant-time random access to elements like arrays do. Accessing elements in linked structures require traversing through the list.
• Pointer management: the need for maintaining pointers between nodes can complicate the implementation and increase the potential for memory leaks.
• Cache inefficiency: Linked nodes can suffer from cache inefficiency due to their non-contiguous memory allocation. This can lead to more cache misses than array based structures.