Data Structures Review Sheet


Structure Command Description Big Oh Necessary Variables Code
Stack push(o) Insert o on top of stack Array: O(1)
List: O(1) 		int size
Node top
Array: Stack[++top} = obj;
List: Node v = new Node();
v.setElement(elem);
v.setNext(top);
top = v;
size++;
Stack pop() Remove object from top of stack Array: O(1)
List: O(1) 		int size
Node top
Array: Object elem = S[top];
S[top--] = null;
Return elem;
List: Object temp = top.getElement();
temp = top.getNext();
size--;
return temp;
Stack top() Look at object at top of stack, but don't remove Array: O(1)
List: O(1) 		int size
Node top
Array: Object elem = S[top];
List: return top.getElement();
Stack size() Returns number of objects Array: O(1)
List: O(1) 		int size
Node top
Array: return top+1;
List: return size;
Stack isEmpty() Checks to see if size is zero Array: O(1)
List: O(1) 		int size
Node top
Array: return top == -1;
List: return size == 0;
Queue enqueue(o) Insert o at rear of queue Array: O(1)
List: O(1) 		int size
List: node head, tail 		 
Queue dequeue() Remove object from front of queue Array: O(1)
List: O(1) 		int size
List: node head, tail 		 
Queue size() Returns number of elements Array: O(1)
List: O(1) 		int size
List: node head, tail 		 
Queue isEmpty() Checks to see if size is zero Array: O(1)
List: O(1) 		int size
List: node head, tail 		 
Queue front() Look at front object, but do not remove it Array: O(1)
List: O(1) 		int size
List: node head, tail 		 
Deque insertFirst(e) Insert element e at first position O(1) int size
Node top, bottom 		 
Deque insertLast(e) Insert element e at last position O(1) int size
Node top, bottom 		 
Deque removeFirst() Remove first element O(1) int size
Node top, bottom 		 
Deque first() Examine first element O(1) int size
Node top, bottom 		 
Deque last() Examine last element O(1) int size
Node top, bottom 		 
Deque size() Returns number of objects O(1) int size
Node top, bottom 		 
Deque isEmpty() Checks to see if size is zero O(1) int size
Node top, bottom 		 
Vector elemAtRank(r) Return element at rank r Array: O(1)
Dynamic Array: O(1) 		int size
List: node head, tail 		 
Vector replaceAtRank(r,e) Replace element at rank r with element e Array: O(1)
Dynamic Array: O(1) 		int size
List: node head, tail 		 
Vector insertAtRank(r,e) Insert new element e at rank r Array: O(n) (at end O(1))
Dyanmic Array: O(n) (at end O(1) - after every n calls, it takes O(n), however, the average is O(1)) 		int size
List: node head, tail 		 
Vector removeAtRank(r) Remove element at rank r Array: O(n) (at end O(1))
Dyanmic Array: O(n) (at end O(1)) 		int size
List: node head, tail 		 
List before(p) Return preceeding position Linked List: O(1) int numElements
Node header
Node tail 		 
List after(p) Return following position Linked List: O(1) int numElements
Node header
Node tail 		 
List replaceElements(p,e) Set element e at position p Linked List: O(1) int numElements
Node header
Node tail 		 
List swapElements(p,q) Exchange the elements at positions p and q Linked List: O(1) int numElements
Node header
Node tail 		 
List insertBefore(p,e) Place element e at a new position directly before position p Linked List: O(1) int numElements
Node header
Node tail 		 
List insertAfter(p,e) Place element e at a new position directly after position p Linked List: O(1) int numElements
Node header
Node tail 		 
List remove(p) Remove position p and its element Linked List: O(1) int numElements
Node header
Node tail 		 
List insertFirst(e) Create new position at beginning of list containing element e Linked List: O(1) int numElements
Node header
Node tail 		 
List insertLast(e) Create new position at end of list containing element e Linked List: O(1) int numElements
Node header
Node tail 		 
Trees root() Returns the root O(1) Tree t
Position/Node v 		 
Trees parent(v) Returns the parent of v O(1) Tree t
Position/Node v 		 
Trees children(v) Returns the iterator of children of v O(# of children of v) Tree t
Position/Node v 		 
Trees size() Returns the number of nodes O(n) Tree t
Position/Node v 		 
Trees elements() Returns the iterator of all elements O(n) Tree t
Position/Node v 		 
Trees positions() Returns the iterator of all position nodes O(n) Tree t
Position/Node v 		 
Trees swapElements(v,w) Swaps the elements at positions v and w O(1) Tree t
Position/Node v 		 
Trees replaceElement(v,e) Replaces the element at position v with e O(1) Tree t
Position/Node v 		 
Trees isInternal() Tests if a node is internal O(1) Tree t
Position/Node v 		 
Trees isExternal() Tests if a node is external O(1) Tree t
Position/Node v 		 
Trees isRoot() Tests if a node is root O(1) Tree t
Position/Node v 		 
Trees depth(t,v) Determine the number of ancestors to a node O(n) Tree t
Position/Node v 		 
Trees height(t) Determines the height of a tree t Naive: O(n^2)
Good: O(n) 		Tree t
Position/Node v 		 
Binary Tree leftChild(v) Returns the left child of v O(1) BinaryTree t
Position/Node v 		 
Binary Tree rightChild(v) Returns the right child of v O(1) BinaryTree t
Position/Node v 		 
Binary Tree sibling(v) Returns the sibling of v O(1) BinaryTree t
Position/Node v 		 
Priority Queue insertItem(k,e) Insert element e with key k Unsorted Sequence: O(1)
Sorted Sequence: O(n) 		Node head, tail
int size
key k 		 
Priority Queue extractMin() Return element with min key and remove it from queue Unsorted Sequence: O(n)
Sorted Sequence: O(1) 		Node head, tail
int size
key k 		 
Priority Queue minElement() Return, but do not remove, min element Unsorted Sequence: O(n)
Sorted Sequence: O(1) 		Node head, tail
int size
key k 		 
Priority Queue minKey() Returns the minimum key Unsorted Sequence: O(n)
Sorted Sequence: O(1) 		Node head, tail
int size
key k 		 
Priority Queue size() Returns the number of elements Unsorted Sequence: O(n)
Sorted Sequence: O(n) 		Node head, tail
int size
key k 		 
Priority Queue isEmpty() Checks to see if size is zero Unsorted Sequence: O(1)
Sorted Sequence: O(1) 		Node head, tail
int size
key k