1.4.2 - Data structures Flashcards
What is an array?
A data structure which contains a set of data items of the same data type grouped under a single identifier.
Is static so size cannot change.
Each individual element can be addressed and accessed directly via its index or subscript i.e. random access.
Contents are stored contiguously in computer memory.
Unlike lists, they can be multi-dimensional.
Therefore it isn’t flexible (static)
But is faster to read through
Contiguous
What is a record?
are data stores organised by attributes (fields).
What are lists?
A List is an ordered collection of elements of a single data type. There is no limit on how many elements can be in the list so therefore
is more flexible
but is slower to read through if there are loads of elements
but isn’t contiguous
What is a tuple?
Tuples are lists that cannot be modified once set up i.e. immutable.
Used to store multiple items of different data types in a single variable.
What are linked lists?
Is a dynamic data structure
Uses index values and pointer to sort a list in a specific way.
Can be organised on more than one category.
Needs to be traversed until the desired element is found
To add data to a list, it is added in the next available space and the pointers are updated accordingly
To remove an item from the list, the pointer in the previous item is set to the value in the item to be removed,
effectively bypassing the removed item.
The contents may not be stored contiguously in memory.
What are graphs?
Is a collection of data nodes/vertices and the connections/edges set between them.
The connections (edges) can be:
- directional or bi-directional
- directed or undirected
- weighted or unweighted.
Can be represented by an adjacency matrix.
What are stacks?
Are LIFO (‘last in, first out’) dynamic data structures.
There are two pointers: a top and a bottom. The top is often called the stack pointer.
Data is added and removed from the top of the stack.
Use the command PUSH to add data and POP to remove data.
What are queues?
Are FIFO (‘first in, first out’) dynamic data structures.
There are two pointers: a start and an end. The start is often called the queue pointer.
Data is added from the end and removed from the start of the queue.
Use the command PUSH to add data and POP to remove data.
What are trees?
Are dynamic branching data structures.
They consist of nodes that have sub nodes (children).
The first node at the start of the tree is called the ‘root node’.
The lines that join the nodes are called ‘branches’.
What are hash tables?
Enable access to data that is not stored in a structured manner.
Hash functions generate an address in a table for the data that can be recalculated to locate that data.
What is a binary search tree (BST)?
One specific kind of tree is a BST, where each node only has maximum of 2 children from a left branch and a right
branch.
To add data to the tree, it is placed at the end of the list in the first available space and added to the tree following the
rules:
If a child node is less than a parent node, it goes to the left of the parent.
If a child node is greater than a parent node, it goes to the right of the parent.
What is stack overflow?
When an item is attempted to be pushed onto a stack but the stack is full.
What is a stack underflow?
Returning the value from the top of the stack without removing it.
What is popping?
Adding an item to the top of a stack.
What is pushing?
Removing an item from the top of the stack.
