Data Structures

Data structures is a format used to store , organise, modify and access data

An indexed set of related elements Must be finite and indexed An array often start from zero Must only contain elements with the same data type

FIFO ( First item added is the first to be removed ) Used in keyboard buffers and breadth first search algorithm

It has two pointers ( front and rear) IsEmpty , IsFull , Enqueue and Dequeue

By comparing the front and rear pointers

It is more memory efficient

A type of queue where the front and rear pointers can move over the two ends of the queue

Items are assigned a priority High priority items are dequeued first before lower priority items

Items are removed in first in first out

It has a pointer Push Pop Peek IsFull and IsEmpty

A stack overflow is thrown

Stack underflow

Can be used to represent networks such as transport networks, IT networks and the Internet.

Consists of nodes (sometimes called vertices) joined by edges (sometimes called arcs)

A weighted graph is one in which edges are assigned a value

○ Adjacency matrices ○ Adjacency lists

● A tabular representation of a graph ● Each of the nodes in the graph is assigned both a row and a column

● Represent a graph using a list ● For each node, a list of adjacent nodes is created ● Only records existing connections in a graph

Adjacency matrix Stores every possible edge between nodes, even those that don’t exist. Almost half of the matrix is repeated data. Memory inefficient Allows a specific edge to be queried very quickly, as it can be looked up by its row and column. Time efficient. Well suited for dense graphs where there are a large number of edges Adjacency list Only stores the edges that exist in the graph. Memory efficient. Slow to query, as each item in a list must be searched sequentially until the desired edge is found. Time inefficient. Well suited to sparse graphs, where there are few edges.

They are connected , undirected with no cycles

● The root node is the only node with no parent, all other roots stem from them

child nodes with no children

A rooted tree in which each parent node has no more than two child nodes.

A hashing algorithm takes an input and returns a hash.A hash table stores key-value pairs