What are the types of list?
- Linear list - starage order is logical order (can be sorted and unsorted)
- Linked list - stores pointers to next location
what lists can be searched using binary search?
- Sorted linear list
Advantages/disadvantages of linear lists?
- Fast acess time as items are stored consectivly. (direct access)
- Can be sorted and use binary search
- Easy to code
- Static array has fixed size
- Static array wastes memory
- Slow inserting/deletion in a sorted list as items must move.
What must be checked when inserting into a linear list?
that the list isnt full
What is meant by the term dynamic structure?
memory space is allocated when required. The size of the structure is free to change at runtime.
What is the heap?
the memory locations available to application programs for dynamic allocation
how is new memory allocated at runtime?
The heap stores the new data, the stack stores the heap loation as a pointer.
What is the stack?
used for static memory alocation, has a predefined size . (often stores pointers to the heap )
Advantages and disadvanteges of linked lists?
- Memory usage is very efficent
- Inserting and deletion is very efficent as no items are move, just pointers change.
- Acess speed is slower
- Cant do binary search
Stuff needed for a stack?
- Top pointer
- Pop (removes top item)
- Push (adds new item)
- Isempty
- Create
what is a stack known as?
last in first out data type
Uses for a stack?
- Balancing brackets
- Reverse polish notation
- Funtion calls - stores the variable values, current position, register values.
Advantages of reverse polish notation?
- Simpler for macine to evaluate
- Do not need brackets
- no need for order of operations
what is a queue known as
first in first out data type
Stuff needed for a queue?
- Add
- remove
- isfull/isempty
- Rear pointer - points to where you are adding to
- Front pointer - points to where you are removing from
what is a priority queue
A queue where certain things added to the queue have prority over other things and go infort of them
Whats a circular queue?
If an array is used to store the queue and people leave a full queue, this means that theres no space at the end of the array so it gets added to the start of the array.
what is a model?
an abstraction of an entity in the real world/problem. The abstaction is a representation of the problem that leaves out unnessary details.
Whats an entities attributes?
A property of an object.
Simulating a queue
Needs random number generators for stuff like server time, rate of people arriving.
whats a psudo random number generator?
A generator that makes apparently random numbers but the algorithm with the same seed will produce the same number.
(is useful if you want to recreate a simulaton twice)
What is a recursive routine
a routine defined in terms of itself
Pros and cons of recursion
- concise code
- easier to code some problems
- Can get v slow after many repeat calls
- Infinite reapeats can happen
- Uses more memory to store all the local variable etc
Types of sorting algothims and how they work
- Insertion sort - each data item is chose where it goes
- Selection sort - finds smallest first then next smallest
- Bubble sort - compares adjacent data
