Data Structure
Data structures are used by computers as the containers within which information is stored
Static Data Structure
A fixed data structure that is reserved memory at the start of the program. The contents of a static array can be changed but the array cannot be resized
Dynamic Data Structure
Memory can be allocated and deallocated as required while the program is running.
Abstract data types
Do not exist as data structures in their own right, and instead make use of other data structures such as arrays to form a new way of storing data. It is a conceptual model that describes how data is organized and which operations can be carried out on the data
Primitive Data Type
only contains one value
Benefits of Static Data Structures?
- The compiler can allocate space during compilation
- Easy to program
- Arrays allow for random access
- Easy to check for overflow
- Contiguous
- Random access allowed
- Uses less memory when storing the same amount of data
- Store data in consecutive memory locations
Points 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
- Non-contiguous
- Sequential Access
- If fragmented can be slow to access
- Do not store data in consecutive memory locations
Array
An array is an indexed set of related elements, finite and only contains elements of the same data type
Example of 1D array
Array Names = {“Bob, “Will”, “Sam”}
Example of 2D array
Array Colours = {“light blue, dark blue, blue”}, {“light pink, dark pink, pink”}, {“light green, dark green, green”}}
(indexing starts at 0)
Colours(0,1) would return ‘dark blue’
Colours(2,0) would return ‘light green’
Static Memory Allocation
- A fixed list can be set up, this is a contiguous space on disk.
- The next memory location is the next address and its position can be implied.
- Removing something is not easy as all succeeding elements have to be moved back one place. Leaving unused memory locations (wasted space)
How does Dynamic Memory Allocation occur
- Dynamic memory allocation uses linked lists making it much easier to remove and add elements.
- Each element points to the address of the succeeding element.
- Removing an element just requires pointing to a different address
What is Recursion?
A recursive subroutine is one that calls itself.
What is a Base case?
The case where recursion does not occur
Criteria for recursion?
- Size of the problem must get repeatedly smaller
- There is a general case
- There is a base case
Factorial
A Factorial (n!) is a function that multiplies a number by every number below it.
What are Queues? How/where are they used?
- First in first out data structure, abstract and based on arrays
- Typically queues are used in buffering where a sequence of instructions are sent to a printer for instance, and the printer prints documents in the order that they arrive - Lists can be used to represent queues.
- Also used in keyboard buffers where each key press is added to the queue, so that letters appears in the order they are type
- The breadth first search algorithm uses a queue to keep track of which nodes in a network have been visited
Queue Operations
- Add; add element to the queue
- Remove; remove element
- IsEmpty
- IsFull
- Queue.Dequeue() removes an element from the front
- Queue.Enqueue() adds an element
Emptiness can be checked by comparing front and rear pointers, if they are the same, a queue is empty
How to remove items in a circular queue?
1. Check the queue is not already empty;
2. Compare the value of the front pointer with the maximum size of the array;
3. If equal then front pointer becomes one; A. index of the first position in the array instead of one
4. Otherwise, add one to the front pointer;
How to add items to a Linear queue?
- Check that the queue is not already full;
- (if it isn’t) then add 1 to the value of the rear pointer;
- then add the new item to the position indicated by the rear pointer;
How to add items to a Priority Queue?
- Starting with the item at the rear of the queue move each item back one place in the array;
- Until you (reach the start of the queue or) find an item with the same or higher priority than the item to add;
- Add the new item in the position after that item;
Linear Queue
As an item is removed from the queue all other items move up one space. For a long queue this can take a lot of processing.
pointers
the pointer representing the start of the queue moves as an item is removed from the queue. However, this leads to a lot of empty cells/wasted memory at the front of the list. You also need to know the queue length and how many elements have been removed.
Circular Queues
As an item is removed memory locations are recycled: Unused memory locations at the front now become memory locations at the back of the queue, making it more memory efficient
-
Fundamentals of programming34
-
Data Structures52
-
Algorithms55
-
A model of computation37
-
Data Representation83
-
Computer Systems37
-
Computer Architecture45
-
Computer Architecture: Principles of Operations23
-
Consequences and Uses of Computing14
-
Communication and Networking105
-
Databases46
-
Big Data13
-
Functional Programming wip0
