Transcript Data Structures Presentation

Data Structures
Static and Dynamic
Learning Objectives
Explain the difference between static and
dynamic implementation of data
structures, highlighting the advantages
and disadvantages of each.
Static Data Structures
Structures that do not change in size
while the program is running.

e.g. Arrays
As once you declare their size, they cannot
be changed.

Actually there are some languages that do
allow the size of arrays to be changed in which
case they become dynamic data structures.
Advantages Of Static Data
Structures
Compiler can allocate space during
compilation.
Easy to program.
Easy to check for overflow.
An array allows random access.
Disadvantages Of Static Data
Structures
Programmer has to estimate the maximum
amount of space that is going to be
needed.
Can waste a lot of space.
Dynamic Data Structures
Structures that can change size while a
program is running.

e.g.
Linked Lists

See Linked Lists Presentation in the AS section.
Binary Trees

See earlier Binary Trees Presentation.
Advantages Of Dynamic Data
Structures
Only uses the space needed at any time.
Makes efficient use of memory.
Storage no longer required can be
returned to the system for other uses.
Disadvantages Of Dynamic Data
Structures
Difficult to program.
Can be slow to implement searches.
A linked list only allows serial access.
Plenary
Give an example of a dynamic and static
data structure?
What is the difference between a dynamic
data structure and a static data structure?
Plenary
Dynamic data structure:


Linked list
Can alter size dependent upon the number of
items stored.
Static data structure:


Array
Remains a fixed size throughout its use.
Plenary
What are the advantages and
disadvantages of static and dynamic data
structures?
Advantages Of Static Data
Structures
Compiler can allocate space during
compilation.
Easy to program.
Easy to check for overflow.
An array allows random access.
Disadvantages Of Static Data
Structures
Programmer has to estimate the maximum
amount of space that is going to be
needed.
Can waste a lot of space.
Advantages Of Dynamic Data
Structures
Only uses the space needed at any time.
Makes efficient use of memory.
Storage no longer required can be
returned to the system for other uses.
Disadvantages Of Dynamic Data
Structures
Difficult to program.
Can be slow to implement searches.
A linked list only allows serial access.