Programming - Data structures Flashcards
what are static data structures
organisation or collection of data in memory that is fixed in size
eg arrays
features of static data structures
- fixed memory allocation
- predictable memory usage
- elements are stored in contiguous memory locations
what is an array
a list with a fixed size
what is a dynamic data structure
a collection of data in memory that has the ability to grow or shrink in size
eg lists
features of dynamic data structures
- variable memory allocation
- can adjust size based on the needs of the program
- unused memory is allocated or reallocated as needed
advantages of dynamic structures
- makes efficient use of memory because the data structure only uses as much memory as it needs
- Can grow as more data is added to the data structure
- no limit on number of items
that can be added - Resources only allocated as they are needed
disadvantages of dynamic structures
- runs the risk of overflow. can also have under flow if empty
- Additional memory needed for pointers;
- can lead to memory leak
- Can take longer to access an item directly
advantages of static structures
- memory allocation is fixed so there will be no issues with adding and removing items from the data structure
- easier to program as there isn’t a requirement to check on the size of the data structure at any point before accessing it
- predictable memory usage, easy to estimate and manage memory requirements
- Faster access time - elements are stored in contiguous memory, allowing for quick access
features of a stack
LIFO - last in first out structure,
features of a queue structure
FIFO - first in first out
- you can add items onto the back of the queue and remove items from the front
What does a queue need to be able to do?
- add items to the back - enqueue()
- remove items from the front - dequeue()
- test if the queue is empty or full isEmpty() or isFull()
what does a stack need to be able to do
- add items to the stack, from the back
- remove items from the stack from the back
- look at the top item
- test if stack is empty or full
Describe the steps involved in adding a record to a hash table.
-Hash algorithm applied;
to key ;
- result is location in table where the record should be stored (key % number of slots)
- if location is not empty;
then use next free location by incrementing by one
Describe the process that should be followed to add an item to a circular queue
implemented as a static data structure using an array.
1. Check the queue is not already full;
2. Compare the value of the (rear) pointer with the maximum size of the array;
3. If equal then (rear) pointer becomes zero;
4. Otherwise, add one to the (rear) pointer;
5. Insert new item in position indicated by (rear) pointer;
what are abstract data types
a logical description of how the data is viewed and the operations that can be performed on it
where are queues used
- output waiting to be printed/print spooling
- characters typed at a keyboard are held in a queue in a keyboard buffer
- simulation programs
what is a stack?
how does a stack operate?
what are some of the common uses of a stack?
- a stack is a linear data structure which follows the Last in first out principle
- elements are added (pushed) and removed (pop) from the top
- used in text editing, call management
uses of static data structures
- arrays, static stacks and queues
- used when max size of the data structure is known in advance
- when memory usage needs to be predictable and consistent
eg implementing simple buffers