1. Data Structures
(*) Arrays
Array – is a data structure that allows to store one single type of data
during running of a computer program.
2D Array – collection of elements that are stored in rows and columns
(x,y).
3D Array – collection of elements that are stored in rows, columns and
tables (x,y,z).
NOTE: In programming the most popular type of array is 1D and 2D arrays
as with the 3D arrays it is very complex to represent them due to extra
dimension is added.
When searching element in the array:
1D - ArrayName(position in a row) Array(0)
2D – ArrayName(row, column) Array(1,2)
3D – ArrayName(table, row, column) Array(1,2,1)
(*) Hash Tables
Hash table is created from two components which are: table where the
actual data is stored, mapping function (hashing algorithm).
Purpose of mapping function - It calculates the number of characters in
the value that is going to be stored, then the length of the string is divided
by 5 using MOD operator to find the remainder. When the value is
calculated the index (key identifier) is written to the hash table where the
value is stored.
,NOTE: If someone with a name that contains the same number of
characters and a previous name is used, then it generated the same index
value. It will therefore overwrite the previous name with the new one.
E.g. ERIN is to be added ERIN = 4 MOD 5 = 4
(*) Pointers and Lists
List – is an ordered collection of data or items that can be different data
type (but usually they are the same).
Each record in list is called a node.
Null pointer – is a last node in the list.
Start Pointer – links to the first node in a list.
Next Free – gives the address of the next free record space.
,Lists also can be represented as a diagram, where data and a pointer are
used to link each element in the list.
(*) Stacks and Ques
Stack – is a linear data structure that operates in a LIFO manner (Last in
First out). Elements are added on the top of the stack, can only be the
elements that are able to be accessed or removed.
Pushing – is adding a new element to the top of the stack.
Popping – is removing of element on the top of the stack.
Stack Pointer – is a variable that denotes the location of the top of the
stack.
Why stacks are important in computing?
When a program runs and a specific action is carried out, like calling
a procedure, the program remembers where it stopped by saving
that location in a stack. Then, it executes the procedure, and once
it's finished, it goes back to the point in the program saved on the
top of the stack (which is removed from the stack). This process
allows procedures to call other procedures, creating a chain of
actions.
, Used to evaluate an arithmetic expression in a Reversed Polish
Notation. For example, the signs of operators are placed after the
operands. For example, if we want to do following calculation 3 + 4
in Reverse Polish Notation it will be written as 3 4 +. Operands are
pushed onto the stack as they are encountered, and when an
operator is encountered, it operates on the top elements of the
stack. This makes evaluation straightforward and efficient because
operators always have their operands immediately available on the
stack.
Queue – is a linear data structure that operates in a FIFO manner (First in
First out). The first item added is the first item that can be accessed.
Front Pointer – is a variable that denotes the first element in the queue
(item that was the longest).
Back Pointer – is a variable that denotes the last element in the queue
(item that was recently added).
Circular Queue – is a queue where first element is connected to the last
element forming a circular structure.
Why queues are important in computing?
Task Scheduling: They are important for scheduling tasks and
processes in computer system. For example, in operating systems,
queues are used in task scheduling algorithms to prioritise and
schedule tasks for execution based on various criteria such as
priority levels, deadlines, and resource availability.
(*) Tree Traversal Algorithms
A binary tree can be implemented in the format of array or linked list. It is
more useful to implement it using a linked list as it allows the binary tree
to be dynamic and they can grow to any size.
