Describe a primitive data type
A data type which is assigned to a variable used to hold a single piece of data
Describe a composite or compound data type
A data type which is assigned to a variable used to hold multiple related pieces of data
Describe an abstract data type
A conceptual model that describes how data is stored and which operations can be carried out on them
Describe what a data structure is
The implementation of an abstract data type in a program
Explain what a static data structure is
A set amount of memory locations / size to store data
Explain what a dynamic data structure is
Can group data, while also being able to grow in size
What is an array data structure?
A data type that holds data that are usually related. It has a fixed size that cannot be changed during running.
What is a tuple data structure?
A data structure that cannot mutate, which contains multiple constants
Describe a list data structure
A dynamic array
Describe a record data structure
A data structure which allows you to make your own data type consisting of different fields
Describe a linked list data structure
A list data structure which stores data in the next free space, and links them together with pointers
What is a node, for a linked list, and what does it contain?
An individual element of the linked list
Contains the data item and the next address location
What are some advantages of a linked list?
- Flexible structure - pointers can be changed to shape the ordering system
- Can easily remove nodes, as very few pointers need to be changed
What are some disadvantages of a linked list?
- Slow to check through as it must be started at the beginning and then worked through
- Hard to update with new nodes, as all previous nodes have to be checked and pointers moved to add the new item
- Hard to find a specific item, as every node has to be gone through to find it
- More storage space is required since the pointers also have to be stored
Describe a linear queue data structure
FIFO. Pointers point to the start of the queue where items are removed, and to the end where items are added
Describe a circular queue data structure
Functions the same as a linear queue, except it reuses the empty spaces at the front of the queue
What is the advantage of a circular queue over a linear queue?
After elements are removed, the circular queue can reuse the space left behind
Describe a priority queue structure
Each element has a priority value alongside the data, and it is all stored in priority order. This is similar to an ordered linked list.
A new element is added according to its priority value, and the highest priority element is removed first
Describe a stack data structure
LIFO. The last item to be added to the stack is the first item to be removed.
What is the purpose of the peek() operation?
Returns the item at the top of a stack without removing it
What is the purpose of the push() operation?
Adds an element to the top of the stack
What is the purpose of the pop() operation?
Removes an element from the top of a stack
Describe a tree data structure
A hierarchical structure of data, stored as nodes, with parent nodes branching into children nodes.
Define a node in a tree data structure
A unit for data, containing: a sub-tree pointer, the node's data, and pointers to other nodes on the same level
Define a parent and child for a tree data structure
Parent: the predecessor node to branching nodes
Child: a node branching from a predeceasing node
Describe a binary search tree data structure
A dynamic data structure, which can change size during program running. It can have only 0, 1 or 2 branches from each node
What is an advantage of binary search trees over standard root search trees?
Binary trees take a shorter time to search for a particular item than a rooted tree
What are the 3 methods of traversing a binary tree?
What are the features of a preorder traversal?
Is a 'top down' method
Can be used to duplicate the data to create an identical binary tree
Describe a preorder traversal
Pointers are to the left of the node
- Root visited first
- Traverses left sub-tree
- Traverses right sub-tree