CompSci Lecture 3/4/2026 Wed

Efficiency and Runtime Complexity of Linked and Array Bags

• Efficiency Considerations

  • Avoid unnecessary shifts within data structures (especially in linked lists).

  • Although minimizing redundancy in operations is encouraged, runtime complexities still remain significant.

Cloning

• Clone Method Runtime Complexity

  • For Int Linked Bag:

  • Runtime: $O(n)$

  • Explanation: Requires copying every element in the linked structure.

  • For ArrayBag:

  • Runtime: $O(n)$

  • Explanation: Same rationale as above; every single element must be copied.

  • For List:

  • Runtime: $O(n)$

  • Consistent with the previous explanations regarding cloning elements.

Size Method

• Function Description for Linked Bag:

  • Operation: Counts the number of nodes in the linked list.

  • Implementation: Retrieves the value of manyNodes (which tracks node count).

  • Runtime Complexity:

  • $O(1)$

  • Explanation: Direct return of a stored variable (avoids iterating through nodes).

Grab Method

• Description: Generates a random integer between the first and second nodes to access a random element in the bag.

• Worst-case Runtime for Linked Bag:

  • Runtime: $O(n)$

  • Explanation: Accessing the random number from the last item requires linear traversal through nodes.

• For Array Bag:

  • Runtime: $O(1)$

  • Explanation: Direct array access via arithmetic calculation ensures constant retrieval time.

Adding Elements

• Add Many

  • For Int Linked Bag:

  • Worst-case Runtime: $O(n)$

  • Explanation: Linear complexity based on the number of elements being added.

  • For Array Bag:

  • Worst-case Runtime: $O(n + m)$ where $m$ is the number of elements being added.

  • Explanation: May require resizing the existing array when full, leading to linear complexity.

Count Occurrences Method

• Functionality: Counts specific target occurrences within the bag.

• Worst-case Complexity:

  • Linked Bag: $O(n)$

  • Array Bag: $O(n)$

  • Explanation: Both data structures necessitate examining all elements due to unordered nature.

Data Structure Choice Consideration

• Performance Factors:

  • Evaluating overall operations (add/remove vs. accessing elements) determines the choice of underlying data structure.

Preferred Structures by Frequent Operations

• For Frequent Adds and Removes:

  • Recommended Structure: Linked Bag

  • Reasons:

    • Constant time complexity for add and remove operations.

• For Frequent Accessing Elements:

  • Recommended Structure: Array Bag

  • Reasons:

    • Faster random access due to direct indexing allowing for constant time complexity.

Key Advantages

• Linked Bags:

  • No need to resize compared to array bags.

  • Size adapts dynamically with each operation.

• Array Bags:

  • Constant time for accessing random elements.

Implementation Overview

• Next Lab Focus: Double-Linked Sequence

  • Familiarity with double linked implementation allows for greater ease in coding the structure.

Structure Fields in Double-Linked Sequence

• Mandatory Fields:

  • head: Points to the first element.

  • tail: Points to the last element.

  • cursor: Points to the current access element.

  • precursor: Points to the node before the current node.

  • manyNodes: Counts total number of elements in the sequence.

Invariants to Maintain

• During Operations:

  • The respective roles of head, tail, cursor, precursor, and manyNodes illustrate crucial pointers and counts.

  • Consistency must be maintained for each method where the invariants hold true before and after method operations (i.e., updates happen within but are restored at the end).

Implementation Examples

Handling Add Before Method

• Cases to Address:

1. Empty List:

   • All references (head, tail, cursor, precursor) are null pre-operation. After the addition, all point to the new element.

2. Non-empty List with No Current:

   • Points the new node to the head when adding before first element.

3. Current Element is Head:

   • The new element is added before head, and the head pointer needs to be updated.

Handling Remove Method

• Scenarios:

1. Removing the Last Node:

   • Update pointer fields accordingly; cursor and precursor adjusted to reflect removal.

2. Removing Current Element from Middle:

   • Current element gets cleared while cursor points to the next. Precursors might need updating as required.

Conclusion