30/6/2026

Delete by Value (Crucial - return to Free list)

IF head == -1 THEN OUTPUT "Empty"
ELSE IF data[head] == target THEN
temp <- head
head <- nextPtr[head]
nextPtr[temp] <- free
free <- temp
ELSE
prev <- head
current <- nextPtr[head]
found <- False
WHILE current != -1 AND found == False
IF data[current] == target THEN
nextPtr[prev] <- nextPtr[current]
nextPtr[current] <- free
free <- current
found <- True
ELSE
prev <- current
current <- nextPtr[current]
ENDIF
ENDWHILE
IF found == False THEN OUTPUT "Not Found"
ENDIF

1
 30/6/2026

Describe Linked List:

Is a--
• Dynamic Data Structure: Size changes at runtime.
• Has a Pointer: A variable that stores the address/index of another
node.
• A Node: The building block holding data and a pointer.
• A Head Pointer: The starting point of the list.
• A Null Pointer (None or -1): Terminates the list.
• Traversal: Moving through the list sequentially.

2
30/6/2026

3
30/6/2026

4
30/6/2026

5
30/6/2026

6
30/6/2026

7
30/6/2026

8
30/6/2026

9
30/6/2026

10
30/6/2026

11
30/6/2026

12
30/6/2026

13
30/6/2026

14
30/6/2026

15
30/6/2026

16
30/6/2026

17
30/6/2026

18
30/6/2026

19
30/6/2026

20
30/6/2026

21
30/6/2026

22
 30/6/2026

Graphs:
• is an Abstract Data Type (ADT)
• An Abstract Data Type (ADT) is a collection of data, defined by the
operations you can perform on it.
• A graph GG is a set of vertices and edges: G=(V,E)G=(V,E).
• A graph abstracts the idea of entities and the relationships between them.
• They only need to know that they can add vertices, add edges, find a path,
or traverse the structure.

Feature Description Key Terminologies

VV (Set of vertices). E.g., Cities,
Vertices (Nodes) units or entities in the graph.
People, Web Pages.
EE (Set of edges). E.g., Roads,
Edges (Arcs) The connections that link two vertices.
Friendships, Hyperlinks.
Directed: Edges have a direction (one-way street, Twitter
follow). Arrows on lines indicate
Directed vs. Undirected
Undirected: Edges have no direction (two-way street, Facebook direction.
friendship).
Weighted vs. Weighted: Edges have a numerical value (cost, distance, time).
Numbers labeled on the edges.
Unweighted Unweighted: All edges are equal.
Undirected: Degree.
Degree The number of edges incident to a vertex. Directed: In-degree (incoming)
and Out-degree (outgoing).
Path: A sequence of vertices where each adjacent pair is
Acyclic: A graph with no cycles
Paths & Cycles connected by an edge.
(e.g., a Tree or DAG).
Cycle: A path that starts and ends at the same vertex.
Connected: A path exists
between every pair
Connectivity Whether a path exists between two vertices. (Undirected).
Strongly Connected: A path
exists both ways (Directed).
Subgraphs & Subgraph: A subset of vertices and edges. Isolated vertices are
Components Component: A maximal connected subgraph. components of size 1.

23
 30/6/2026

Operations (The ADT Interface)

. The standard operations of the Graph ADT include:
1. Creation: Initializing an empty graph (directed or undirected).
2. Add Vertex: Inserting a new node into the graph.
3. Add Edge: Connecting two vertices (optionally with a weight).
4. Delete Vertex/Edge: Removing an entity or a relationship.
5. Searching from an element
6. Finding the shortest path (e.g., Dijkstra's algorithm).

Why use a graph as the most appropriate ADT over simpler structures like Arrays, Linked Lists,
Stacks, or Trees.

• Use a Graph when the data involves many-to-many relationships

• If it is strictly one-to-many (hierarchical), use a Tree.
• If relationships are arbitrary and networked, use a Graph.

USES OF GRAPHS
1: GPS Navigation -Finding the fastest route between two cities.
• Mapping: Cities = Vertices. Roads = Edges. Distances/Traffic = Weights.
• A graph is essential here because the road network is not hierarchical. A city can be connected to many
others, and routes can loop.
• A graph's weighted edges allow us to apply shortest-path algorithms (like Dijkstra’s) to find the optimal
route, which a linear list or tree cannot handle natively.

2: Social Media Networks (e.g., Facebook / LinkedIn)

• Suggesting new friends or calculating a user's network influence.
• Mapping: Users = Vertices. Friendships/Connections = Undirected Edges.
• A graph models the "network effect" perfectly. Unlike a tree (where a user has only one parent), a graph
allows a user to be connected to thousands of others in any direction.

3. Computer Networks / The Internet

• Routing data packets from a server to a client.
• Routers/Servers = Vertices. Cables/Wireless links = Edges.
• The internet is highly redundant and dynamic. If one link fails, packets must find an alternative path.
• Graphs naturally model this redundancy, allowing dynamic routing algorithms to find alternate paths in
real-time.

24
 30/6/2026

. Exam Tips & Summary

 Do not confuse Graphs with Trees: A Tree is a specific type of Graph (specifically, a connected, undirected,
acyclic graph). A Graph is a superset—it allows cycles, multiple connections, and directions.
 Justification Keywords: When justifying, always use the words: "Entities (Nodes)", "Relationships (Edges)",
"Many-to-many connectivity", and "Shortest path / Traversal algorithms".
 Weighted vs. Unweighted: Always specify if the situation requires weights. For costs/distances, always
justify using a weighted graph. For simple connections (like family trees or basic friendships), use
unweighted.
 Directed vs. Unweighted: If the relationship is one-way (e.g., "follows", "owes money to", "prerequisite
for"), you must explicitly state that a Directed Graph is required.

Implementation of ADTs
 can be built directly on top of
o built-in types (e.g., arrays, integers, records).
 another ADT (e.g., using a linked list to implement a stack, or using a binary tree to implement a dictionary).
A. Stack
o Use a static array (fixed size) with an integer top pointer.
o Use a Linked List (which is itself an ADT).
 How: The head of the linked list acts as the top of the stack. push is implemented as insertAtHead; pop is
removeFromHead.

 This gives dynamic sizing without overflow, and no need to shift elements.
B. Queue
 Use a circular array (built-in array with two pointers: front and rear).
o Increment pointers modulo the array size. This reuses empty slots efficiently. Size is still fixed, but avoids shifting
elements on deque
o Use a Linked List (ADT).
 Maintain a head pointer (front) and a tail pointer (back). enqueue appends a new node at the tail; dequeue removes
the head node.
Why it works: Linked lists allow O(1) insertions at the tail and O(1) deletions at the head, perfectly matching the queue's FIFO
requirements

25
 30/6/2026

C. Linked List
o Use dynamic arrays or a record/struct plus pointers/references (built-in memory
management).
o Use two Stacks to simulate a linked list’s sequential behaviour (though impractical, it
demonstrates the principle).
D. Dictionary (also called Map / Associative Array)
 A collection of key-value pairs where each key is unique, and values are retrieved by supplying
the key.
 Core operations: insert (put), delete (remove), search (get), and isEmpty.
o Use a direct-address table (an array) if the keys are integer indexes in a small, dense range.
o The key itself is the array index, so lookup is O(1). This is rarely practical for general use
(wastes memory if keys are sparse).
 The array (built-in) provides the base slots; each slot points to a Linked List (ADT) that
stores all key-value pairs that hash to the same index (chaining).
 search hashes the key, goes to that array index, then traverses the linked list to find the
matching key.
 The dictionary is implemented as a Binary Search Tree (BST) where nodes store both a
key and a value.

E. Binary Tree
 Description: A hierarchical structure where each node has at most two children (left and right).
o Use a static array (heap indexing).
o Use Linked Lists to create dynamic nodes.
3. Summary Table of Implementations

Built-in Type
Target ADT Other ADT Implementation
Implementation
Stack Static array with top index Linked List (use head as top)
Queue Circular array with front/rear Linked List (use head for front, tail for back)
Struct/Record + memory pointers (Rare) Two stacks; but primarily built from
Linked List (references) primitives
Direct-address array (integer 1. Hash table (array + linked lists for chaining)
Dictionary keys) 2. Binary Search Tree (BST)
Static array (heap indexing: 2i+1, Linked node structure (using references, similar to
Binary Tree 2i+2) linked list nodes)

26
 30/6/2026

Why choose a certain implementation:

o Array-based: fixed size, fast O(1) access, but insertion/deletion may shift elements (except
stack/queue with pointers).
o List-based: dynamic size, O(1) insert/delete at ends, but uses more memory (pointers) and cache
misses.
 Dictionary is the most flexible: It can be implemented from arrays, linked lists, or binary trees,

27
30/6/2026

28
30/6/2026

29
30/6/2026

30
30/6/2026

31
 30/6/2026

factorial(4)
= 4 * factorial(3)
= 3 * factorial(2)
= 2 * factorial(1)
= 1 * factorial(0)
= 1 (Base Case)
= 1 * 1 = 1
= 2 * 1 = 2
= 3 * 2 = 6
= 4 * 6 = 24

32
30/6/2026

33
30/6/2026

34
30/6/2026

35
30/6/2026

36