COMP 410 Final Exam Study Guide Questions and Answers 2024

A data structure is - a particular way of organizing data in a computer so that it can be used efficiently An Abstract Data Type is - A set of objects together with a set of operations (They are a mathematical abstraction) Common Trade-offs - Time vs Space Making one operation faster may make another operation slower Providing more operations (making the data structure more general) may make some operations less efficient Operations are revealed through? - Interfaces and methods Set of objects stored as? - private variables What are the benefits of using an ADT? - Code is easier to understand Implementations of ADTs can be changed ADTs can be reused in future programs Disadvantages of Arrays - Size is capped by a maximum or or requires resizing which is slow (Take time proportional to the length of the array) Inserting an item at the beginning or in the middle of the list is slow Linked List: get - Time: O(N) Linked List: Insertion - Time: O(1) Linked List: add - Time: O(1) Linked List: remove - Time: O(N) for first item What if you only want to remove the last item of a Linked List - Must update the "next" link of the next-to-last Node. Finding the next-to-last node requires following N links Array List vs Linked List (space) - Linked List is always proportional to the number of items in the list while Array List may be arbitrarily greater than number of elements (if removed used) Array List vs Linked List (time) - add (at end of list): AL O(N) (to copy the array); LL O(1) (when we maintain reference to the last node) add at a position: AL O(N) (to copy array); LL O(N) (to reach the position) get: AL O(1); LL O(N) to reach the position What if you want to iterate a link backwards (e.g listIous())? - Each call to previous() requires finding the previous Node Requires time proportional to N Doubly Linked List Double Linked List: Insertion How? - Create a Node Set 4 Link references Double Linked List: Insertion