Fundamentals of Data Structures

Static Data Structure
The amount of data stored and the memory allocated is of a fixed amount
1 of 36
Dynamic Data Structure
The amount of data stored and the memory allocated will vary during runtime
2 of 36
Stack
First-in Last-out data structure
3 of 36
What are the uses of a stack?
1. Reversing List contents. 2. Handling interrupts. 3. Nesting and recursion
4 of 36
Stack Overflow
Occurs when more items are pushed onto a astack than can be stored
5 of 36
Stack Underflow
Occurs when more items are popped from a stack thana re currently stored
6 of 36
What are the operations of a stack?
1. Push(), 2. Pop(), 3. Peek()
7 of 36
Queue
First-in First-out data structure
8 of 36
Linear Queue
Fixed or dynamically sized queue
9 of 36
Circular Queue
Front and rear pointers can wrap around from the end to the start - more efficient
10 of 36
Priority Queue
Some data may leave the queue out of sequence due to having a higher priority
11 of 36
What are the operations of a Queue?
Enqueue(), Dequeue(), isEmpty(), isFull()
12 of 36
Graph
Data structure that models relationships between pairs of objects
13 of 36
Vertex/Node
Object in a graph
14 of 36
Edge/Arc
Relationship between two nodes
15 of 36
Weighted Graph
Data values label the edges
16 of 36
Undirected Graph
Relationships work two ways
17 of 36
Directed Graph
Relationships work one way
18 of 36
What are the uses of a Graph
1. Human newtorks e.g. Family/Work groups. 2. Transport Networks e.g. Calculating fastest route. 3. The internet + Web e.g. mapping the internet
19 of 36
More memory efficient as they only store data where adjecencies exist whereas matricies store every possible combination. Lists are used for graphs with few adjecencies
20 of 36
Allow adjecencies to be identified mroe quickly as every combination is recorded, whereas lists need to be parsed to identify whether particular adjecencies exist. Matricies used for graphs with many adjecencies
21 of 36
Tree
Undirected graph with no loops
22 of 36
Binary Tree
Tree with a maximum of two child nodes
23 of 36
How are binary trees created?
1. Input data in order given. 2. Always start from root. 3. < goes left. 4. > goes right
24 of 36
What are the uses of binary trees?
1. Binary search trees. 2. Compilers: veryfying syntax. 3. Storing data with an inherant heirarchal structure
25 of 36
Hash Table
Data structure thats stores key/value pairs based on an index generated from a hashing algorithm
26 of 36
What are the uses of hash tables?
1. Operating Systems - Storing and locating executable files of programs and utilities. 2. Encryption: encrypting data. 3. Checksums: calculating a value from a set of data
27 of 36
WHat must a good hashing algorithm do?
1. Generate usnique values that create as few collisions as possible. 2. Create a unifrom spread of data to avoid clustering. 3. Balance speed and complexity
28 of 36
Ratio of available indicies to total indicies. A high load factor means it will be increasingly difficult to produce a unique index
29 of 36
Collision
When a hashing algotithm produces the same index for two or more keys
30 of 36
How can collisions be dealt with?
1. Chaining - Create a list in that slot and append elements t the list. 2. Rehashing - apply the same or an alternative algorithm is applied until a unique key is generated. 3. Probing - Placing in the next empty slot
31 of 36
Dictionary
Similar to hash tables in that it maps keys to data. Known as an associative array in that it deals with two sets of asociated data. Values are accessed using the associated key
32 of 36
What is a use of a dictionary?
Information Retreival
33 of 36
Vector
Measurement with both magnitude and direction
34 of 36
How can vectors be represented?
List, Dictionary, Array, Function (F:->R), Arrows, Notation 'n vector over R'
35 of 36
How is Dot Product done?
(a,b).(c,d) = (a * c + b * d) = (a AND c XOR b AND d): Can be used to find the angle of a vector
36 of 36

Other cards in this set

Card 2

Front

The amount of data stored and the memory allocated will vary during runtime

Back

Dynamic Data Structure

Card 3

Front

First-in Last-out data structure

Card 4

Front

1. Reversing List contents. 2. Handling interrupts. 3. Nesting and recursion

Card 5

Front

Occurs when more items are pushed onto a astack than can be stored