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 ...
COMP 410 Final Exam 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
COMP 410 Final Exam Questions and Answers 2024
,COMP 410 Final Exam Questions and Answers 2024
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)
COMP 410 Final Exam Questions and Answers 2024
, COMP 410 Final Exam Questions and Answers 2024
get: AL O(1); LL O(N) to reach the position
What if you want to iterate a link backwards (e.g listIterator.previous())? - 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
Computation time - O(N)
Doubly Linked List: remove - O(1) (for first item)
O(N) for the last time
A Stack is - a list in which items can be added and removed only at the end of the
list (called the top)
LIFO
COMP 410 Final Exam Questions and Answers 2024
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller CleanA. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $13.49. You're not tied to anything after your purchase.
