Data Structures Flashcards
Tuple properties
Has elements of mixed types
It is immutable
Use round brackets () to indicate a tuple
Define dynamic
The number of elements can change
Define static
Number of elements cannot change
Define record
Composed of a fixed number of fields of different data types
Can be implemented as an object
Arrays (size, contents, data types)
Size: static
Contents: mutable
Data types: single
Tuple (size, contents, data types)
Size: static
Contents: immutable
Data types: mixed
Record (size, contents, data types)
Size: static
Contents: mutable
Data types: mixed
List (size, contents, data types)
Size: dynamic
Contents: mutable
Data types: mixed
Stacks properties
LIFO- last in first out
Single pointer (points to top of stack)
Pushing stack steps
- Check if stack is full
- If full -> report error, stop
- Increment the stack pointer
- Insert new data item into cell pointed to by the stack pointer
- Stop
Popping stack steps
- Check if stack is empty
- If empty -> report error, stop
- Copy data item from cell pointed to by the stack pointer
- Decrement the stack pointer
- Return the data
- Stop
Peeking stack steps
- Check if stack is empty
- If empty -> report error, stop
- Copy data item from cell pointed to by the stack pointer
- Return the data
- Stop
Enqueue steps
- Check if queue is full
- If full -> report error, stop
- Else increment rear pointer
- Insert new item at rear pointer
- Stop
Dequeue steps
- Check if queue is empty
- If empty -> report error, stop
- Else item = queue[head]
- Increment head pointer
- Return item
- Stop
Queue properties
FIFO- first in first out
Two pointers- head and tail pointer
Abstract data type
Peeking queue steps
- Check if queue is empty
- If empty -> report empty, stop
- Else
- Copy data item from cell pointed to by the head pointer
- Return the data item
- Stop
What does isEmpty() do?
Test for empty list
What does append(item) do?
Adds a new item to the end of a list
What does remove(item) do?
Remove first occurrence of an item from the list
What does count(item) do?
Return the number of occurrences in the list
What does len() do
Returns the number of items in the list
What does index(item) do
Return the position of the item
What does insert(pos,item) do
Add a new item at position pos
What does pop() do
Remove and return the last item in the list
What does pos(pos) do
Remove and return the item at position pos
Define linked list
Dynamic abstract data structure which can be implemented as an array and pointers
Composed of nodes
A node is composed of two parts: (linked list)
The data (may be complex data structure)
A pointer to the next node
Linked list pointers
A start pointer identifies the first node in the list
A next free pointer shows the index of the next free space in the array
What is a graph
An abstract data structure used to represent complex relationships
Made up of nodes and edges
Define undirected graph
No arrows on the edges that indicate direction
Define graph
A set of vertices or nodes connected by edges or arcs
Define edges
May be weighted, indicating a cost of traversal
Define undirected graph
All edges are bidirectional
Define directed graph (bigraph)
All edges are one way
Define adjacency matrix
Each row and column represents a connection
Adjacency matrix connection
The item at [row, column] indicates a connection
In unweighted
Adjacency matrix pros
Convenient to work with, and adding edges is simple
Adjacency matrix cons
A sparse graph with not many edges will leave most of the cells empty, wasting a lot of memory space
Adjacency list pros
Only uses storage for the connections that exist, so it is more space- efficient
A good way of representing a large, sparsely graph
Graph applications include
Computer networks, with nodes representing computers and weighted edges representing bandwidth between them
Page rank algorithm
States in a finite state machine
Social networks
Web pages and links
Chemistry, with nodes as atoms, edges as connections
Project management, with nodes as tasks, edges representing sequence and weights, time or cost
Maps, with nodes representing cities or landmarks, edges representing routes
How can a weighted graph be represented
As a dictionary of dictionaries
Each key in the dictionary being the node, and the value, a dictionary of adjacent edges and edge weights
Define binary tree
A tree in which each node has a maximum of two children
