Data Structures Flashcards
Stack
Holds Data in a FILO, First-In-Last-Out, pattern. Each data item is stacked one on top of the other and only the top is accessible.
Examples:
- Plates
- Call Stack (many languages)
Stack Interface (6)
Pop() - Remove & Return top of stack
Push() - Add to top of stack
Peek() - Return top of stack
Contains() - Returns true if item in stack
Length() - Returns how many items in stack
Clear() - Remove all items from the stack
Queue
Holds Data in a LILO, Last-In-Last-Out pattern. Each data item is added to the back of a queue and is accessible when everything before has been dequeued.
Examples:
- Shop ticket queue systems
Queue Interface (5)
Enqueue() - Add item to back of queue
Dequeue() - Return & remove item from front of queue.
Contains() - is item in queue
Length() - Length of Queue
Clear() - Remove all items from the queue.
(Linked & Double Linked) List
A List of Items where each node (data item with relational metadata) is linked to the next (& to the previous in double linked lists.
The list itself must point to the head (first item in the list) & the tail (last item in the list)
Examples:
Javascript Arrays
Linked List Interface
AddFirst() RemoveFirst() AddLast() RemoveLast() AddAtIndex() RemoveAtIndex() Remove() AddAfter() Find() Clear() Length()
Graph
A linked collection of items whereby each Vertex (node) can contain an Edge (link) to any other vertex. Edges can have values (think as length or weight of link).
Graph Interface
isAdjacent() - Is there an edge between two vertices
neighbours() - Returns a list of
addVertex() - Adds a vertex if it is not there
removeVertex() - removes the vertex , if it is there;
addEdge(): adds the edge between 2 vertices if there
removeEdge() - Removes edge between 2 vertices if there.
getVertexValue(): returns the value associated with the vertex
setVertexValue(G, x, v): sets the value associated with the vertex.
Length() - How Many Items In Graph
Contains() - Is Vertex/Value in Graph (BFS/DFS)
getEdgeValue(): returns the value associated with an Edge
setEdgeValue(G, x, y, v): sets the value associated with the edge
Tree
A Tree is a hierarchical collection of data, where each node points via an edge (link) to child nodes. iF
- “Root” is a node with no parents.
- “Sibling” children of the same parent
- “Ancestor” parent, grandparent for a given node
- “Depth of a node” length of the path from the root to that node
“Height of a Node” height from a particular node to the deepest node (leaf node)
Tree Interface
AddChild() RemoveChild() ClearChildren() IsAncestor() IsSibling() getDepth() getHeight();
Array
An Array is a set of contiguous data items in memory, which means they cannot be added to after initialisation.
Record / Struct
A record is a simple data structure that contains indexed fields that contains rows of data for each index. Sometimes these are referred to as Plain Objects
Set
A set is a collection that contains unique (no duplicates), unordered data values.
Set Interface
MAIN
union() - returns a set containing all items (removing duplicates) of all input sets.
intersection() - returns a set containing all items that are common to any input sets.
difference() - returns a set containing all items that are found in only one input set.
subset() - a predicate that tests whether the input set is a subset (all items contained within) of the set.
Contains(): checks whether the value in set.
isEmpty(): checks whether the set is empty.
size(): Returns size of set
B-Tree
A B-Tree is a tree that self resizes to make sure that one side of the tree
