YEAR 1 CO1 WEEK 11 DATA STRUCTURES Flashcards
What type of Data structures are there?
Static
Dynamic
What are static data structures?
Size of data structure is fixed when the structure is created and its size cannot change during processing.
What are dynamic data structures?
Size of data structure can change during processing.
Define a mutable data structure.
Can change contents of data structure during processing.
Define an immutable data structure.
Cannot change contents, add or remove data items to data structure during processing.
State the pros and cons to a static data structure
Inefficient as space might not be needed.
Limiting as you need to know in advance how large structure needs to be.
Amount of memory required can be calculated in advance and will be contiguous (and fast to read).
Fast to access data as memory location is known.
Easy to program.
State the pros and cons of a dynamic data structure.
Makes efficient use of space as memory allocated when needed.
Elements can be added or removed as required.
Tend to be more complicated to implement and use.
Memory requirement is unknown initially.
Slower to access as each memory address is allocated at runtime and so will be fragmented.
Needs to provide a function to calculate the size.
State properties and functions of lists.
When data items are related to one another they can be organised as a list.
Lists are usually dynamic and not stored continuously in memory.
State properties and function of tuples.
Similar to list that it stores a sequence of data items however cannot change add or remove data items at runtime so is immutable.
Can contain elements of different data types.
State properties and function of arrays.
Similar to lists but are static, number of elements are predefined when array is declared.
Collection of variables of same data types which grouped by single identifier.
Each variable in array called an element and accessed using an index which relates to its position in the array.
State properties and function of records.
A set of data types all related to single thing.
Unlike array can contain data items of more than one type.
Usually static.
What are Queues?
FIFO
Very front and back of the queue marked by pointers called ‘head’ and ‘tail’.
push=enqueue
Pop=dequeue
What are stacks ?
Closely related to queues but only one access point called the ‘top’.
Stacks are First In Last Out or LIFO
What is Assembly language?
Low level language
Can be read by humans and CPU
- Easy conversion between assembly and machine
What is the problems with assembly?
Coder needs to k ow a lot about hardware details
Only works for specific CPU
symbolic addressing
