Home
Subjects
Explanations
Create
Study sets, textbooks, questions
Log in
Sign up
Upgrade to remove ads
Only $2.99/month
Science
Computer Science
Data Structures
Data Structures Final
STUDY
Flashcards
Learn
Write
Spell
Test
PLAY
Match
Gravity
Terms in this set (43)
Constructor
A method for creating an object in a class.
Ex: public class Student { }
Differentiate between a class and an object.
A class is a blueprint which you can create objects. Objects are the instance of the class , which helps programmers to use variables and methods from inside the class.
Polymorphism
When multiple classes are related due to their inheritance.
Ex: class Animal {
public void animalSound() {
System.out.println("The animal makes a sound"); }
}
class Pig extends Animal {
public void animalSound() {
System.out.println("The pig says: wee wee"); }
}
class Dog extends Animal {
public void animalSound() {
System.out.println("The dog says: bow wow"); }
}
Binary Tree
A data structure that consists of nodes, with one root node at the base of the tree, and two nodes (left child and right child) extending from the root, and from each child node.
Root
The starting node that leads to the rest of the binary tree.
leaf
The last node in a path of a Binary tree. It has no successors.
child
the Node that comes directly after a prior node. A node can have at most, two children
parent
the node that exists prior to a child. each node can have only one parent.
subtree
a branch of an original binary tree that has a new root starting at the place the tree broke off.
path
collection of nodes from root to planed destination.
path length
the number of nodes from point a to point b
height
the total number of nodes leading from the root to the furthest leaf.
level of node
height from root to node + 1. tells distance from start
Full Tree
A tree in which every node other than the leaves has two children.
Complete tree
A tree in which there are no missing nodes when looking at each level of the tree. The lowest level of tree may not be completely full, but may not have any missing nodes. All other levels are full.
infix notation
Left, Visit, Right
Prefix notation
Visit, Left, Right
Postfix notation
Left, Right, Visit
list notation
this dang thing
array notation
this other dang thing
linear search
search that moves one by one in a list O(n)
Binary Search
search that starts halfway, and cuts that half in half until it finds what it needs. O(log2n)
selection sort
finds the node that should come first, then second, then third ect.
Insertion Sort
Each items is take in turn, compare to the items in a sorted list and placed in the correct position.
Bubble Sort
Moving through a list repeatedly, swapping elements that are in the wrong order.
Quick Sort
breaks the array in half and then half again, putting the points in order.
Iterator
an object that provides functionality to iterate over all elements of a collection one at at time.
hasNext()
boolean function that returns true as long as there is another object in the array
next iterator
next node in a list
code for using an iterator
while(iter.hasNext()){
//add the code you want}
recursive algorithms
an algorithm that breaks the problem into smaller subproblems and applies the algorithm itself to solve the smaller subproblems.
ex: if (N == 1)
return 1
else
return N * ( N - 1)
base case
a case where a recursive algorithm completes without applying itself to a smaller subproblem
ex: if (N == 1) return 1
recursive function
A function that calls itself, either directly or indirectly.
ex: Factorial(N) {
if (N == 1) return 1
else
return N * Factorial(N - 1) }
Fibonacci sequence
a numerical sequence where each term is the sum of the previous 2 terms in the sequence, except the first 2 terms, which are 0 and 1.
ex: FibonacciNumber(termIndex) {
if (termIndex == 0)
return 0
else if
(termIndex == 1)
return 1
else
return FibonacciNumber(termIndex - 1) + FibonacciNumber(termIndex - 2) }
binary search
an algorithm that searches a sorted list for a key by first comparing the key to the middle element in the list and recursively searching half of the remaining list so long as the key is not found.
ex: BinarySearch(numbers, low, high, key) {
if (low > high)
return -1 mid = (low + high) / 2
if (numbers[mid] < key) {
return BinarySearch(numbers, mid + 1, high, key) }
else if (numbers[mid] > key) {
return BinarySearch(numbers, low, mid - 1, key) }
return mid }
singly-linked list
a data structure for implementing a list ADT, where each node has data and a pointer to the next node.
ex: numList = new List
(head)
(tail)
ListAppend(numList, node 99)
ListAppend(numList, node 44)
ListPrepend(numList, node 66)
head
A singly-linked list's first node
tail
the last node of a singly-linked list
null
a special value indicating a pointer points to nothing.
Append() operation
inserts the new node after the list's tail node
ex: ListAppend(numsList, node 45) appends node 45 to numsList.
Prepend() operation
inserts the new node before the list's head node.
ex: ListPrepend(list, newNode) {
if (list⇢head == null) {
// list empty
list⇢head = newNode
list⇢tail = newNode }
else { newNode⇢next = list⇢head list⇢head = newNode } }
RemoveAfter() operation
removes the node after the specified list node.
ex: if (curNode is null && list⇢head is not null) { sucNode = list⇢head⇢next list⇢head = sucNode
doubly-linked list
a data structure for implementing a list ADT, where each node has data, a pointer to the next node, and a pointer to the previous node.
ex: ListAppend(list, newNode) {
if (list⇢head == null) {
// List empty list⇢head = newNode
list⇢tail = newNode }
else { list⇢tail⇢next = newNode
newNode⇢prev = list⇢tail
list⇢tail = newNode } }
Recommended textbook explanations
Introduction to the Theory of Computation
3rd Edition
Michael Sipser
389 explanations
Computer Organization and Design MIPS Edition: The Hardware/Software Interface
5th Edition
David A. Patterson, John L. Hennessy
220 explanations
Starting Out with Python
4th Edition
Tony Gaddis
629 explanations
Data Structures and Algorithms in Java
6th Edition
Roberto Tamassia
520 explanations
Other sets by this creator
ARTH 360 Midterm
50 terms
Ethics Exam II
42 terms
HIST 101 Final
39 terms
US History to 1865 Midterm
44 terms