As a group, discuss the run-times (i.e., big-$O$) of the following operations to arrays and linked lists (both singly- and doubly- linked lists).

1. Adding an element to the beginning of the list

   1. Answers: O(n) for array, O(1) for linked (singly and doubly)

2. Adding an element to the end of the list (what are things to consider for arrays?)

   1. Answers: O(1) for array if it is not full. O(n) if it is full. O(n) linked for singly and doubly with no end pointer, O(1) for both if there is an end pointer

3. Adding an element to the middle of the list

   1. Answers: O(n) for array, O(n) for linked (singly and doubly)

4. Deleting an element from the end of the list

   1. Answers: O(1) for array, O(n) if no end pointer for linked (both)

5. Deleting an element from the middle of the list

   1. Answers: O(n) for all

6. Deleting an element from the beginning of the list

   1. Answers: O(n) for array, O(1) for linked (singly and doubly)

7. Finding an element in the list

   1. Answers: O(1) for array, O(n) for linked (singly and doubly)

8. Accessing the 5th element of the list (assuming there are at least 5 elements)

   1. Answers: O(1) for array, O(n) for linked (singly and doubly)

What are some of the disadvantages of arrays?

In Java, its static which occupies space if you need a new copy to expand the size

What are some ideas you have for improving upon these disadvantages?

What are some of the disadvantages of linked lists?

What are some ideas you have for improving upon these disadvantages?