What is a data structure?
A data structure is simply a way of representing the data held in a computer’s memory. There are hundreds of different data structures available to programmers but at A Level you only need to understand a few of the most common ones:
- one-dimensional arrays
- two-dimensional arrays
- three-dimensional arrays
- records
- tuples
- lists
- linked lists
- stacks
- queues
- binary trees
- directed graphs
- undirected graphs
- hash tables
Static vs Dynamic
Data structures usually fall into one of two categories: static and dynamic.
In static data structures the size of the data structure is set at the beginning of the program and cannot be changed. This is very limiting (and inefficient) because it means that you have to know in advance how large your data structure needs to be. However, static data structures are easy to program and you always know how much space they will take up.
Dynamic data structures, on the other hand, do not have a limited size and can expand or shrink as needed, however, they tend to be more complex to implement.
It is also very common for more complex data structures to be made up of simpler ones. For example, it is normal practice to implement binary trees using a linked list or create a stack by using an array (we will look more into this during this topic area).
| DYNAMIC | STATIC |
| Memory is allocated to the data structure dynamically i.e. as the program executes. | Memory is allocated at compile time. Fixed size. |
| Disadvantage: Because the memory allocation is dynamic, it is possible for the structure to ‘overflow’ should it exceed its allowed limit. It can also ‘underflow’ should it become empty. | Advantage: The memory allocation is fixed and so there will be no problem with adding and removing data items. |
| Advantage: Makes the most efficient use of memory as the data structure only uses as much memory as it needs | Disadvantage: Can be very inefficient as the memory for the data structure has been set aside regardless of whether it is needed or not whilst the program is executing. |
| Disadvantage: Harder to program as the software needs to keep track of its size and data item locations at all times | Advantage: Easier to program as there is no need to check on data structure size at any point. |
Arrays:
allow you to store multiple entries of the same datatype under a common name
Tuple:
– Ordered set of values
-It may contain mixed data types
-it is immutable (the elements of a tuple cannot change)
Records:
like a database/spreadsheet
STACKS
LIFO – Last In First Out
Push items onto/into the stack
Pop items off/out of the stack
QUEUES
FIFO – First in First Out
items are poped out the front of the queue and pushed into the end
Linked lists
no pre defined number of elements. Items are indexed and easy to add, remove and change.
each item holds data and a pointer.
Binary Trees
The RULE: The LEFT node always contain values that come before the root node and the RIGHT node always contain values that come after the root node.
Graphs
