Data Structures Overview Terms & Concepts Flashcards
array
primitive data structure
collection of items
stored sequentially
array insertion
new value placed in arbitrary position
all following elements move over one position to make room
array index
access any item
abstract data type (ADT)
a scheme for organizing data that is independent of how it is stored in the computer
defined by a name and list of operations that can be performed on it
List ADT operation: Size
get the number of items in the list
List ADT operation: Get
get the value at a specific location
List ADT operation: Find
find the location of a matching element
List ADT operation: insert
put a new value into the list at a specific location
List ADT operation: remove
take a value out of the list at a specific location
List ADT operation: Set
replace one item with another
big-O notation
tool for measuring operation execution speed
dependent on data type and implementation
“order of”
Efficiency of List ADT Size operation implemented with an array
O(1)
Efficiency of List ADT Get operation implemented with an array
O(1)
Efficiency of List ADT Find operation implemented with an array
O(n)
Efficiency of List ADT Set operation implemented with an array
O(n)
Efficiency of List ADT insert operation implemented with an array
O(n)
Efficiency of List ADT Add at end operation implemented with an array
O(1)
Efficiency of List ADT Remove operation implemented with an array
O(n)
Efficiency of List ADT Sort operation implemented with an array
O(n log n)
Efficiency of Ordered List ADT Size operation implemented with an array
usually O(1)
Efficiency of Ordered List ADT Get operation implemented with an array
O(1)
Efficiency of Ordered List ADT Find operation implemented with an array
O(log n)
Efficiency of Ordered List ADT Insert operation implemented with an array
O(n)
Efficiency of Ordered List ADT Remove operation implemented with an array
O(n)
Set ADT
like a list that doesn’t allow duplicates, but the position of items in the collection is undefined and irrelevant.
Set ADT operations
Add, In, Intersection, Union
Set ADT operation: Add
add an item to the set
Set ADT operation: In
is an item in the set?
Set ADT operation: Intersection
Return the intersection of two sets
Set ADT operation: Union
Return the union of two sets
grow your program
instead of trying to write the whole thing at once, divide the problem into convenient steps.
test in isolation
get your ADT working separately from the main program by creating new main program from scratch
Trace statement
track errors
testing operations
commented out
toString method
always written for ADTs
outputs results
when printing out a reference, toString called automatically, without explicit call
boundary testing
using a testing method for values at the start and end of a collection
intersection operation
the set of all elements the two have in common.
orthogonal methods
two similar methods, working the same way.
union operation
all the elements found in either of two sets.
refactoring
improving code quality without affecting results
data structure
an arrangement of data in a computer’s memory.
algorithm
manipulates data in data structures
iteration in a data structure
visiting each item in turn to perform some action on it
recursion
a method that calls itself
fields
an object’s variables
instantiating an object
creating an object
instance
object of a class
constructor
has the same name as the class called whenever a new object is created
access modifiers
keywords public and private
determine which methods can access a method or field
private
a field or method that can only be accessed by methods of the same class
public
a field or method that can be accessed by methods in other classes
inheritance
the creation of one class, called the extended or derived class, from another class called the base class. the extended class has all the features of the base class, plus some additional features
polymorphism
treats objects of different classes the same way. different class must be derived from same base class
garbage collection
blocks of memory with no valid references are returned to the free memory store
insertion, searching, deletion operations
fundamental to most data structures
array hole
one or more empty cells that have filled cells above them at higher index numbers
initialization list
single statement creates a new array with size determined by the number of values in the list.
container class
a class used to store data objects
class interface
the functions and arguments of class methods
abstraction
the process of designing a program by first starting with class functionality rather than implementation details
ordered array
data items arranged by ascending key values, smallest to largest.
binary search
for ordered arrays
each guess divides the range of possible values in half until the range is only one number long
the correct number is identified in only seven guesses, this is the maximum.
logarithm
the inverse of raising something to a power.
the logarithm to the base B of a number A is roughly the number of times you can divide A by B before the result is less than 1.
bubble sort
slow and simple
compare two items, if item closer to beginning of array is larger than item closer to end, then swap them. move to next pair and swap if necessary, continue to end of array and start over and continue until all ascending.
invariants
conditions in algorithms that remain unchanged as the algorithm proceeds.
selection sort
pass through all the items and pick the lowest number, swap the least with the first (position 0). start again at position 1, swap least with position 1. process continues until all sorted.
insertion sort
partially sorted group. remove first item of unsorted items, shift the sorted items to make room for the item at each position and compare each position until item reaches it’s sorted position, then insert. process repeats until all unsorted items are inserted in sorted positions.
operation of compareTo( ) method
s2.compareTo(s1)
s1 < s2 - return value is < 0
s1 equals s2 - return value is 0
s1 > s2 - return value > 0
stable algorithms
sort only what needs to be sorted and leave everything else in original order.
in place sorting
very little extra memory is required
