Week 12 Dynamic & Static Data Structures

Question 1

Describe some properties of static data structures

Answer 1

Static data structures have storage size determined at compile-time / before program is run / when program code is translated / before the data structure is first used

Static data structures have fixed (maximum) size;

Static data structures can waste storage space / memory if the number of data items stored is small relative to the size of the structure

Static data structures (typically) do not need (memory to store) pointers;

Static data structures (typically) store data in consecutive memory locations;

Question 2

Describe some properties of dynamic data structures

Answer 2

Dynamic data structures can grow / shrink during execution / at run-time // size of dynamic data structures can change;
Dynamic data structures only take up the amount of storage space required for the actual data;
Dynamic data structures require (memory to store) pointers to the next item(s);
Dynamic data structures (typically) do not store data in consecutive memory locations;

Question 3

State the time complexity of directly accessing an item in a dynamic and static data structure

Answer 3

O(1) for static
O(n) for dynamic

Question 4

State two advantages of using static data structures

Answer 4

No additional memory needed for pointers;
Faster to access an item directly (O(1) vs O(n));

Question 5

State two advantages of using dynamic data structures

Answer 5

No wasted memory;
Can grow as more data is added to the data structure // no limit on number of items that can be added (except due to hardware limitations);
Resources only allocated as they are needed (with static data structures they are allocated at creation even if not needed until later);