1.1 Data Structures

Data Structure

A group/collection of related data items/elements

Benefits of data structure

i. It is a convenient or best way of organising data relating to a
real problem.
ii. It may be efficient to deal with various elements as one item.

Types of data structures

i. Array.
ii. Record.
iii. Stack
iv. Queue
v. Linked List
vi. Binary Tree
vii. Hash Table

Array

A data structure that stores elements of the same type

How is an array element accessed?

Array element are accessed via indexes or subscripts

Arrays have a fixed or predetermined number of elements. True/Flase

True

Record

A record is a data structure that consists of a fixed number of variables, called fields. Every field has an identifier (field name) and a data type. Each field in a record can have a different data type. Records are often used to represent complex data types by grouping related information together.

Stack

A stack is a container of objects that are inserted and removed according to the last-in, first-out (LIFO) or first-in, last-out (FILO) principle.
It is a limited-access data structure where elements can be
added and removed from the stack only at the top.
A stack can be used as recursive data structure
A stack is either empty or it consists of a top and the rest, which is a stack

What does push do in a stack?

Add an element to the top of a stack

What does pop do in a stack?

Removes an element from the top of the stack

When does an overflow occur in a stack?

When an attempt is made to add to a full stack

When does undeflow occur in a stack?

When an attempt is made to pop an empty stack.

What could stack be used for?

They can be used for:
i. store subprogram return addresses.
ii. store recursion values.
iii. Store short-term arithmetical results.
iv. Enable the undo function.

Pushing onto a stack algorithm

If stackPointer < stackMaixmum, then:
stackPointer = stackPointer + 1
stackArray(stackPointer) = dataItem
Else:
Output "Stack is full, your data has been saved."

Popping from a stack algorithm

If stackPointer > 0, then:
dataItem = stackArray (stackPointer)
stackPointer = stackPointer - 1
Else:
Output "Stack is empty, no data can be
retrieved"

Queue

A queue is a container of objects that are inserted and removed according to the first-in-first-out (FIFO) principle.
Data items are added at the end of queue and removed from the front

What could a queue be used for?

They could be used for:
i. A printer queue.
ii. A keyboard buffer.
iii. Task Scheduling
iv. Traffic Management

How to implement a queue?

The data for a queue would be stored in an array. Two pointers would keep track of the front and back of the queue as data is added and removed. (front pointer and Back pointer)

Adding to a queue algorithm

if backPointer < queueSize then
backPointer = backPointer + 1
queueArray[backPointer] = dataItem
else
output "Queue is full. Your data has not been saved."
end if

Removing from a queue algorithm

if frontPointer <> backPointer then
queueArray[frontPointer] = Null
frontPointer = frontPointer + 1
else
output "Queue is empty. No data can be retrieved."
end if

Linked List

A linked list is a set of data elements, where each element contains the data itself and a pointer to the next element.
It's a dynamic data structure, as it can grow and shrink in size after declaration.
Each element in a linked list is known as a node; the first element is the head note.
The last node in a linked list has a pointer to null.
A node cannot be directly accessed and each node needs to be traversed until the correct node is accessed (sequential access)

Benefits of linked lists

i. New items can be inserted into a linked list without rearranging all the other elements.
ii. If they are programmed dynamically, they use memory more efficiently

Drawbacks of Linked List

i. A Linked list is more complex to program or manipulate
than an array
ii. Extra Programming is required to access the data in the
opposite direction.
iii. Can only be accessed in a linear manner. (sequential access)

iv. Use more data due to nodes

Binary Tree

Is a data structure made up of nodes and branches, with each node containing data and having one or two branches.

What is the node at the top called?

Root Node

How is a binary tree created?

The data is added in the order it occurs. The first data item (no matter what it is) becomes the root node. Additional nodes are added on the left if they are less than (or equal to) the root and to the right if they are greater than the root.

Binary Tree Traversal

The process of visiting each node in a binary tree in a specific order

Preorder Traversal

Visiting the root node, then the left subtree, and finally the right subtree.
It can be used to copy files.

Dot on left

Inorder Traversal

Visiting the left subtree, then the root node, and finally the right subtree.
It can be used to search.

Dot on bottom

Postorder Traversal

Visiting the left subtree, then the right subtree, and finally the root node
It can be used to delete.

Dot on right

Hash Table

A hash table is a data structure that can map keys to values.
A hash table uses a hash function to compute index to store and retrieve data in a table
Collisions how they are handled
They are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.

Hash Function

A function that generates a (unique) index number for a given input data using modulo (MOD).

Modulo (MOD)

A mathematical function that returns the remainder of a division operation

How is hash function generated?

Take the length of the value to be entered and divide by the size of the table, or use the MOD function to generate the index number. The index number is the reminder.