9.1.2. Comparison of Arrays and Lists

Try these first

1. 1.

   Define arrays and lists.

   Hint

   Think about how each type organizes its data.

2. 2.

   What is the time complexity of accessing an array element?

   Hint

   Consider that accessing an element involves direct indexing.

3. 3.

   What is the time complexity of accessing an element in an array?

   • O(1)
   • O(n)
   • O(log n)

   Hint

   Think about how direct indexing works.

4. 4.

   True or False: Insertion into a linked list is more efficient than in an array.

   • True
   • False

   Hint

   Consider the flexibility of memory management.

5. 5.

   Design an algorithm that finds the middle element of a linked list in O(n) time. Discuss potential scenarios in which linked list usage would benefit over an array.

   Hint

   How can you optimize your traversal?

6. 6.

   Propose a way to implement an array that can dynamically resize itself when elements exceed its initial capacity. Discuss the time complexity of the resizing operation.

   Hint

   Think about managing pointers during resizing.