1.4.2) Data Structures Flashcards
what is an array?
An ordered, finite set of elements of a single type
What is a record?
A row in a file, made up of fields (eg. 001, Anthony, anthony@gmail.com)
what is a list?
A data structure consisting of a number of orders items where the items can occur more than once, can contain more than one datatype
what is a tuple?
an audit set of values of any type, is immutable so cannot be changed, use regular brackets not square
What is a linked list?
A dynamic data structure used to hold an aud sequence
how does linked list work?
Each piece of data has an index, the data and a pointer. The pointer indicates the next item in the list. The start pointer shows the algorithm where the beginning of the list is.
How do you append to a linked list?
change the other data values pointers
What is a disadvantage of storing pointers?
they waste memory, items cannot be directly accessed
What is a graph?
A set of vertices/nodes connected by edges/arcs.
What are the three different types of graph?
Directed graph, undirected graph, weighted graph
what is the directed graph?
Graph where the edges can only be traversed in One Direction
What is an undirected graph?
when the edges can be traversed in both directions
what is a weighted graph?
When a cost is attached to each edge
what is an adjacency matrix?
A matrix storing graphs using a table (each node is given a row and column)
what is an adjacency list?
A way of storing graphs where each node stores a list where it states its connections to other nodes (eg A:{B:4, C:6})
Advantages of an adjacency matrix
convenient to work with due to quicker access times, easy to add nodes
Advantage of adjacency list
more space efficient for large sparse networks
What structure does a stack have?
Last in first out
What are some real life examples of stacks?
Going back a page in the web browser, undo buttons
what is a static vs dynamic stack?
Static stack – has a fixed size (preferable as more efficient)
Dynamic – has a flexible size
what functions are available when manipulating a stack?
Push, peak, pop
What does the push function do? What must be checked before use?
add a value to the top of the stack, stack must be checked to see if it’s full
what does the peek function do?
Return the top value from the stack
what does the pop value do?
Removes and returns the top value of the stack
what structure do queues follow?
first in first out
where are queues often used?
Printers, keyboards
what is a linear queue?
a queue where items are added to the next available space starting from the front, items are removed from the front of the queue, pointers are used to indicate the front and back of queue
what is a circular queue?
The same as a linear except once the pointer reaches the maximum size of the queue it loops back to the beginning provided it’s empty
disadvantage of a circular queue
Harder to implement
What are the functions for queues?
enQueue, deQueue
what are trees?
A form of graph with a root node which connects to all other nodes using branches
What is a node (trees)?
An item in the tree
What is an edge (tree)?
Connect to nodes together, also known as a branch or arc
what is a root(tree)?
A single node, which does not have any incoming nodes
what is a child (tree)?
A node with incoming edges
what is a parent(tree)?
a node with incoming edges
What is a sub tree?
A subsection of a tree consisting of a parent and all the children of a parent
What is a leaf?
A node with no children
What is a binary tree?
A tree where each node has a maximum of two children
What are binary trees used for?
To represent information for binary searches, making it easy to search through
What are the three methods of traversing a binary tree?
Pre-order, in order, post order
What is pre order traversal?
pre drinks, walking with head stuck to the left
what is in order traversal?
like a photocopier from left to right
what is post order traversal?
i’ve gotta post this! looking at something in the distance (to the left) alllll the time
What is a hash table?
