Graphs, Hash Tables & Stacks

Directed & Undirected Graphs

Graphs are data structures used to represent data items which have connections between them, such as locations on a map or products on an e-commerce website.

Graphs

Graphs consist of ‘nodes’ or ‘vertices’ which are joined by ‘arcs’ or ‘edges’ and can either be directed or undirected.
A directed graph is one where the connections between the nodes only go in one direction (the arcs are represented as arrows).
In an undirected graph, the connections are two-way.

Graph traversal

There are two methods of traversing a graph:
- Depth-first.
- Breadth-first.

Depth-first traversal

Depth-first traversal involves travelling down one route as far as possible, before reversing and travelling as far down the next route as possible.
In the graph shown, depth-first traversal would involve visiting the nodes in the following order:
- A, B, E, C, D, G, F

Breadth-first

Breadth-first traversal involves visiting all the adjoining nodes for each node in turn.
In the graph shown, breadth-first traversal would involve visiting the nodes in the following order:
- A, B, C, E, D, F, G

Hash Tables

A hash table is a data structure used for very large collections of data or where quick access to the data is required, such as customer records or password verification.

Hashing algorithm

Hashing algorithms allows for the efficient location and retrieval of data.
The hashing algorithm generates indexes based on the key fields of sets of data.
A common example of a hashing algorithm is one which takes the key and divides it by the number of storage spaces available.
The remainder is then used as the address at which to store the key.

Example

If the keys 738, 271 and 560 need storing in a hash table with 6 storage spaces, the process would be as follows:
Calculate the remainder when 738 is divided by 6.
- 738 MOD 6 = 0
That means first key should be stored in location 0.

Example cont.

For the second key, 271 MOD 6 = 1.
- We store this in location 1.
For the third key, 560 MOD 6 = 2.
- We store this in location 2.

Collisions

A perfect hashing algorithm will always generate a unique index.
Should this not be the case, a ‘collision’ is said to occur .
When a collision occurs, a rehashing algorithm is used to determine the next available slot in which to store the data.
Alternatively, we can create a separate data structure such as a linked list from each storage location and store the collisions there.

Example

Key 362 would need adding to the hash table above in location 2 as:
- 362 MOD 6 = 2
However, it’s already filled by 560.
In this case, the next available slot is location 3, so key 362 is stored there.

Stacks

A stack is a data structure where data items are always added and removed from the top. It is often referred to as a ‘last in, first out’ data structure.

Stacks

A stack is a data structure where data items are always added and removed from the top. It is often referred to as a ‘last in, first out’ data structure.
Stacks can be implemented using other data structures, such as arrays or linked lists. In either case, an extra variable is required to identify the top of the stack.

Stack operations

Several operations can be carried out on stacks:
- push() - adds an item to the top of a stack.
- pop() - removes and displays the item at the top of a stack
- peek() - displays the item at the top of a stack without removing it
- isEmpty() - checks to see if the stack is empty
- isFull() - checks to see if the stack is full

Uses

The most common use of stacks is to reverse the order of a set of data items, as they are ‘popped’ in the opposite order that they were ‘pushed’ to a stack.
They are also used by processors to handle interrupts.
Stacks can be ‘static’ (fixed in size) or ‘dynamic’ (able to grow in size as necessary)

Errors

Stack overflow errors can occur in static stacks when attempting to push an item onto a stack that is full.
Similarly, when trying to pop from an empty stack a stack underflow error occurs.

1Components of a Computer

1.1Structure & Function of the Processor

1.1.1Structure of the CPU

1.1.2Fetch, Decode, Execute Cycle

1.1.3Factors Affecting CPU Performance

1.1.4CPU Architecture

1.2Types of Processors

1.2.1CISC & RISC

1.2.2Multicore & Parallel Cores

1.3Input, Output & Storage

1.3.1Computer Systems

1.3.2Magnetic Storage

1.3.3Optical Storage

1.3.4Types of Optical Storage

1.3.5Types of Memory

1.3.6Flash Memory

1.3.7Virtual Memory

2Software & Software Development

3Exchanging Data

4Data Types, Data Structures & Algorithms

4.1Data Types

4.1.1Data Types

4.1.2Arrays & Strings

4.1.3Representing Numbers

4.1.4Binary Arithmetic

4.1.5Hexadecimal

4.1.6Converting Binary Numbers

4.1.7Floating Points in Binary

4.1.8Floating Point Arithmetic

4.1.9Bitwise Manipulation

4.1.10Character Sets

4.2Data Structures

4.2.1Arrays, Linked Lists & Queues

4.2.2Graphs, Hash Tables & Stacks

4.2.3Trees

4.3Boolean Algebra

4.3.1Computational Logic

4.3.2Boolean Logic

4.3.3Karnaugh Maps

4.3.4Boolean Identities

4.3.5Flip Flops & Adder Circuits

5Legal, Moral, Cultural & Ethical Issues

5.1Computing Related Legislation

5.1.1Data Protection Act (1998)

5.1.2Computer Misuse Act (1990)

5.1.3Copyright Designs and Patents Act (1988)

5.1.4Regulation of Investigatory Powers Act (2000)

5.2Moral & Ethical Issues

5.2.1Online Activity Tracking

5.2.2Censorship

5.2.3Cultural Issues

5.2.4Environmental Issues

5.2.5Layout, Colour Paradigms & Character Sets

6Elements of Computational Thinking

6.1Thinking Abstractly

6.1.1Abstraction

6.2Thinking Procedurally

6.2.1Decomposition

6.3Thinking Logically

6.3.1Pseudocode & Flow Diagrams

7Problem Solving & Programming

7.1Programming Techniques

7.1.1Programming Fundamentals

7.1.2Modularity

7.2Programming Construction

7.2.1Integrated Development Environments

7.2.2Testing

8Algorithms

8.1Algorithms

8.1.1Interpreting, Correcting & Completing Algorithm

8.1.2Sort Algorithms

8.1.3Insertion & Merge Sort

8.1.4Search Algorithms

Jump to other topics