CSC 305

Data Structure and Algorithms

3Credit Compulsory
Lesson I: Introduction
By
Dr. R.M. Isiaka
Department of Computer Science
Kwara State University, Malete
 Objectives
Objectives of the course: To lead the students to be able
to:
i. Appreciate the role of data structure and algorithms
in computer science
ii. Discover and express Algorithms for basic problems
iii. Explain the workings of common Algorithms
iv. Explain both the specifications and implementations
of standard data structures (String, Array, lists, stacks,
queues, linked structures, trees and graph)
v. Build and apply abstract tools in a programming
Language
• C:\Users\KWASU Compt Sc\Documents\KWASU DOCS\Department\CSC 305 - Data Structure and
Algorithm\CSC 305 2015-2016 Session.docx
 The concepts of Problem, Algorithm /
Data Structure and Program
• The overall goal is to transform problem to
program using efficient algorithm and data
structure
• Pictorially, the relationships are:
Program

Algorithm

Problem

Data Structure
 Concept of Problem
• Problem = Task + Constraints
- It is a general question to be answered. Usually
it possesses one or more parameters. It can be specified by
describing the form of parameters taken and the questions
about the parameters
- It is a task to be performed. It usually includes the
constraints on resources that may be consumed by acceptable
solution. It does not however include any constraint on how
the problem is to be solved
 Instance of a problem
• An instance of a problem is an assignment of
values to the parameters
Mathematically :
a problem is a function that maps input domain
to an output range. The values making up an input
are called the parameters for the function while a
specific selection of values is known as instance of
the problem.
E.g y = f(x) ; y = x2 -x -2, where x=3
 Algorithm
• An algorithm is a clearly specified set of
simple instructions to be followed to solve a
problem.
• It is a method of implementing a function
(transforming the input to an output)
• It is an ordered set of unambiguous, executable
steps that defines a terminating process.
Hence, a correct algorithm halts with the correct output
for every input instance.
 Algorithm
• Informally: An algorithm is:
i. a set of rules that precisely defines a sequence
of operations
ii. a sequence of computational steps that
transform the input into output
iii. a tool for solving a well specified computational
problem
iv. any well-defined computational procedure that
takes some value(s) as input and produces some
value(s) as output
 Algorithm Representations

Algorithm is an abstraction but it can be

represented and executed using tools such
as:
i. Graphical / pictorial technique like flowchart
ii. Pseudocodes: simple expressive method
that is clear and concise not concerned with
issues of S/W Engineering, issue of
abstraction, modularity and error handling
iii. Programming language (primitive +
collection of rules)
Algorithm Representations
Graphical
Algorithm Representations
Graphical
Algorithm Representations
Pseudocodes
Algorithm Representations
Pseudocodes
Algorithm Representations
Programming Primitives
Algorithm Representations
Programming Primitives
 Facts about Algorithm
i. For a single problem there could be several
algorithms but An algorithm solves a single
problem
ii. Algorithm exists everywhere and it exists for
everything
iii. An algorithm is the thing which stays the same
whether the program is in Pascal running on a
Cray in New York or is in BASIC running on a
Macintosh in Kathmandu!
iv. To be interesting, an algorithm has to solve both
general and specified problems
 More Facts about Algorithm
v. Algorithms are the ideas behind computer
programs
vi. An Expert is aware of several algorithms to a
problem
vii. An algorithmic problem is specified by
describing the set of instances it must work on
and what desired properties the output must
have
 Properties of Algorithm
- Correctness : must solve the intended problem
with out mistake

- Non-ambiguity : must be very clear, straight

forward and easy to follow

- Termination: it must end completely

 Classification of Algorithm:
i. By means of implementation (Recursion or
iteration, logical deduction, serial or parallel or
distributed, deterministic or non-
deterministic, exact or approximate)
ii. By design Paradigm (brute force, divide and
conquer, dynamic programming, greedy
method, linear programming, reduction)
iii. By Efficiency and correctness
a. Using scenario- Best case, Average case or Worst case
b. Using Big theta-notation- φ(n2) , φ(lgn)
 Applications of Algorithm
i. Used in human Genome project: it is used to
determine the sequence of the 3million chemical base
pairs that make up human Deoxyribonucleic acid
(DNA). Also for storage and analysis of the DNA
ii. On the Internet Access: it is used for Routing
algorithm and Search Engine algorithm e.g the
shortest path algorithm
iii. In electronic commerce and security: it is used
for security algorithm for credit cards, passwords
using cryptography, digital signature and biometrics
iv. For optimization issues: algorithm exist for
Program, Hardware, Power and Storage optimization.
 Algorithm Design Approaches
• The two design approaches to algorithm are
the top-down and the bottom-up approaches.
• The two approaches can be demonstrated
using modular programming technique

?
From the name can you try to differentiate the
two approaches
 Top-Down Design

• The principle of top-down design dictates that

a program should be divided into a main
module and its related modules.

• The modules should also be divided

continuously into sub-modules until
elementary process that is intrinsically
understood and that cannot be further
subdivided.
 Top-down algorithm design
• is a technique for organizing and coding
programs in which a hierarchy of modules is
used
• Each module will have a single entry and a
single exit point
• Control is passed downward through the
structure without unconditional branches to
higher levels of the structure.
 Top – Down
M ain

Function1 Function 2 (Fxns called by Main)

Fxn 1a Fxn 1b Fxn 1c Fxn 2a Fxn 2b Fxn 2c (Fxns called by Submain)

 Bottom-Up Algorithm Design
• Bottom-up algorithm design is the opposite of
top-down design
• It is a programming style in which an
application is constructed starting with
existing primitives of language, gradual
construction of complicated features, until all
of the application has been written.
• It starts a design with specific modules and
then builds into more complex structures that
end at the top.
 Analysis of Algorithm
• Analyzing of algorithm is the process of checking it
for correctness and performance prediction
(efficiency and simplicity).
• The correctness can be verified by
i. tracing the instructions step-by-step
ii. reading the algorithm for logical correctness,
iii. testing it on some data using mathematical techniques

• The efficiency and simplicity can be verified by

i. Space complexity
ii. Time complexity
 Space Complexity
• Analysis of space complexity of an algorithm or program
is the determination of its memory requirement to run
completely.
• Reasons for studying space complexity:
i. to determine the amount of memory to be allocated to
the program especially in a multi user system
ii. to verify in advance availability of sufficient memory to
run a program using a specific amount of data
iii. to be a guide in making choice among several possible
solutions with different space requirements
iv. It facilitate the estimation of the largest problem that a
program can solve
v. It provide a guide for hardware requirement and budget
 Components of space requirements
• The space needed by a program consists of
following components.
i. Instruction space : Space needed to store the
executable version of the program. It is fixed.
ii. Data space : Space needed to store all constants,
variable values and has further three components :
(a) Space needed by constants and simple variables. This
space is fixed.
(b) Space needed by fixed sized structural variables, such as
arrays and structures.
(c) Dynamically allocated space. This space usually varies.
 Components of space requirements
(Cont.)

iii. Environment stack space: This space is needed

to store the information to resume the
suspended (partially completed) functions.
Each time a function is invoked the following data is saved on
the environment stack :
(a) Return address : i.e., from where it has to resume after
completion of the called function.
(b) Values of all lead variables and the values of formal
parameters in the function being invoked.
 Time Complexity
• the time complexity of an algorithm or a
program is the amount of time it needs to run to
completion
• the exact time will depend on the:
i. programming language
ii. implementation data structure
iii. optimizing capabilities of the compiler used
iv. CPU speed and other peripherals’ specifications
v. volume of data used
 Time Complexity (cont)
• the exact executing time is not required (it varies
between systems), what is required is the order
of magnitude for execution time
• Thus the time complexity can be expressed as
function of number of key operations performed
• The rate growth analysis of an algorithm are log2 n,
n log2n, n, n2, n3, n!, 2n and nn
• Algorithm analyzed based on the input data can
either be Best case, Average case or Worst case
 Algorithm discovery (General problem)

The Polya’s approach to problem solving

i. Understanding the Problem
ii. Devising a plan
iii. Carry out the plan
iv. Looking back
Primitives
Pseudo codes Conventions
Convention Example

Assignment statement Name expression

Variable declaration type name Integer count
Array declaration Type Arrayname [size] String venuename[4,5]
Selection Statement IF…THEN…ELSE IF (Condition) THEN (activities)
ELSE (other activities)
Repeated Statement While…Do While (Condition) do (activities)
For … Loop For counter {
} Loop

Subprogram / Subroutine/ Module Procedure Procedure name (Parameter)

Function Function name (Parameter)
Comment // line comment
/* */ block comment
Terminator ;
Block Statement {}
Continuous line _
Boolean operator AND, OR, NOT

Arithmetic Operator +,-,*./

Relational Operator =, <>, <, >, <=, >=

 Algorithms Discovery I
Using any of the three techniques to determine an algorithm for the following
problems
i. ‘Sign up’ in a portal, and an algorithm for ‘login’ into the portal

ii. Determine the number of bikes and tricycle to be produced from 27

Seats and 60 Wheels. A bike requires 1 seat 2 wheels, while a tricycle
requires 3 seats and 3 wheels.

iii. For a traveler with seven chain of gold, each of which is equivalent to its
hotel bill per night. He wishes to have minimum cut on the chain such
that he should be able to pay for his room on daily bases without paying
for room in advance

iv. For measure exactly four litters of Kerosene using eight litters and five
litters containers
v. For finding the defective balls in two weighing only if you have 8 balls,
one of which is defective and weighs less than others. When you have a
balance to measure balls against each other.
 Algorithms Discovery II
vi. Determining the letter grades for
examination raw score
vii. Calculating GPA and CGPA for KWASU
Students
viii. Determining the available balance for a
current account if COT is =N=1 per =N=1,000
ix. Generating Amortization table for a 12 month
loan duration at 3% interest (No moratorium)
x. Borrowing Airtime from a GSM provider considering
subscriber’s history, type of subscription and
current balance
 Algorithms Discovery III
xi. Fixing examination venues for a course
considering number of registered students,
room capacity and avoiding clashing
xii. Currency conversion – Naira to three
international currencies one must be in
Africa
xiii. Time conversion – CAT to four other regions
 Sample Sorting Algorithms
Sorting: act of arranging data in specific
(ascending or descending) order.
Consider:
• Input: A sequence of n numbers a1, a2, . . . ,
an.
• Output: A permutation (reordering) a’1, a’2, .
. . , a’n of the input sequence such that
a’1≤ a’2≤ · · · ≤ a’n for Ascending order Or such
that a’1 ≥ a’2≥ · · · ≥ a’n for Descending order.
 Insertion-Sort Algorithms
Insertion sort is an efficient algorithm for sorting a
small number of elements. It is built on an
incremental approach. It works the way many
people sort a hand of playing cards.

Other Sorting Algorithms include:

- Bubble Sort and
- Merge Sort
Insertion-Sort Algorithms
 Insertion-Sort Algorithms
Correctness of an Algorithm can be verified either
by Instance Problem or via loop invariants
properties: Initialization, Maintenance and
Termination.
• Initialization: It is true prior to the first iteration
of the loop.
• Maintenance: If it is true before an iteration of
the loop, it remains true before the next
iteration.
• Termination: When the loop terminates, the
invariant gives us a useful property that helps
show that the algorithm is correct.
 Insertion-Sort Algorithms
• Illustrate the operation of the INSERTION
SORT Algorithm using:
i. A=(e,b,d,f,a,c)
ii. A=(5,2,4,6,1,3)
iii. A= (31,41,59,26,41,58)
iv. Rewrite the INSERTION SORT Algorithm for
Descending order
v. Verify the correctness of the Algorithm using
loop invariants properties: Initialization,
Maintenance and Termination
Bubble -Sort Algorithms
 Merge -Sort Algorithms
• MERGE-SORT(A, p, r)
• 1 if p < r
• 2 then q ← Floor((p + r)/2)
• 3 MERGE-SORT(A, p, q)
• 4 MERGE-SORT(A, q + 1, r)
• 5 MERGE(A, p, q, r)
Merge -Sort Algorithms
 Data Structure (Definition)
• Structural representation of logical
relationships between elements of data.
• It mainly specifies the structured organization
of data, by providing accessing methods with
correct degree of associatively.
• It affects the design of both the structural and
functional aspects of a program.
• They are the building blocks of a program
 Data Structure (Definition)
• Algorithm + Data Structure = Program
• Data Structure = Organized data + Operations
• Data structure is a pattern of data storage /
management in the memory.
• Representation of Data Structure in the main
memory is called storage structure
• Its representation in the auxiliary memory is
called file structure
 Types of Data Structure
• Data structure can be classified either as
Primitive or Non-primitive.
• Primitive Data structure:
- Basic data structure that are directly operated
upon by machine instructions
- They are the basis for the discussions of the
more sophisticated Non-primitive data
structures
- Examples include: Integers, floating point
numbers, characters, string constants,
pointers etc.
 Types of Data Structure
• Non-Primitive Data structure:
- They are sophisticated data structures
emphasizing on structuring of a group of
homogenous or heterogeneous data items
- Examples include: Array, linked list, files, trees
and graphs.
 Types of Data Structure

Data Structure

Primitive Non-Primitive

Integer float character pointer Arrays Lists Files

Linear List Non-Linear List

Stacks Queues Graphs Trees

 Constituent Terms of Data Structure
- Understanding requires establishment of
relationship between Type, Data items, Data
type and Abstract Data type.
- Type: a collection of values (simple -Integer,
boolean – T/F, logic – AND, OR, NOT, aggregate
/composite – Record)
- Data item: value drawn from a Type ( 234,
true, OR, STUDENT (matricno, sex, dept, dob)
 Constituent Terms of Data Structure
- Data type: a type together with a collection of
operations to manipulate the type (IF var data:
Integer, then, +,-,*,/ are legal operations)
- Abstract Data Type: realization of Data type as a
software component defined in terms of a type
and possible operations using encapsulation.
- Data Structure is the implementation for ADT as
OOP class. Objects when created takes up
storage during execution.
Procedure for Selection of Data Structure
i. Analyse the problem to determine the basic
operations ( insertion, searching and deletion)
ii. Quantify the resource constraints for each
operation
iii. Select the best Data structure that best meet
these requirements
- Appropriate Data Structure determine the
efficiency of a solution
- A solution is efficient if it solves the problem
within the required resource constraints with
minimum cost
 Overall objective of a Data Structure
To allow the data user to build
and access collection of data
as abstract tools rather than
forcing the user to think in
terms of the computer main
memory organization.
 Operations on Data Structures
• Traversal – Processing each element
• Search – Finding the location of an element
with a given value
• Insertion – Adding a new element
• Deletion – Remove an element from a list
• Sorting- Arrange the element in some type of
order
• Merging – Combine elements from separate
structures
 Arrays
• Set of items that can be referred to by a single
identifier and the individual element in the set
can be referenced by subscript(s).
• For array A, the elements of A can be denoted
by
• Subscript notation: a1,a2,a3 . . . An or
• Parenthesis notation: A(1), A(2), A(3) . . . A(n)
• Bracket notation: A[1], A[2], A[3] . . . A[n]
• Array can be one-dimensional (linear or
vector) or multi-dimensional (matrix).
 Linear Arrays (LA)
• LA is a set of ‘n’ finite numbers of homogenous
data elements.
• Array length = UB – LB + 1
• Algorithm for Transverse LA
for k = LB to UB
Do process LA[k]
• Representation of LA in Memory
Loc (LA[k]) = Base (LA) + w(k – LB)
Where LA: Array, Base (LA): start address, k: element,
w: word length
 Multidimensional Arrays (MA)
• MA (2D Array m x n array A is a collection of m.n data
elements such that each element is specified by a pair of
integer (j,k) called subscripts with 1≤ j ≤ m and 1≤ k ≤ n.
• Algorithm for Transverse MA
for p = LB to m
for q = LB to n
Do process MA[p,q]
• The memory representation for MA[ j,k]) in MA[M,N] by row
or by column:
Row-Major order:
Loc (MA[ j,k) = Base (A) + w[N(j – 1) + (k-1))
Column-Major order:
Loc (MA[ j,k]) = Base (A) + w[M(k – 1) + (j-1))
 Activities III Application of Array and
its memory representation
i. Identify and briefly explain two (2) data
structures that can be implemented using
Array
ii. Highlight Five (5) applications of Array Data
Structure
iii. Given Array A[m,n] = A[8,5] with a base
address of 2015 and word length of 32.
Calculate the memory address for A[6,4].
a. Using Row Major technique
b. Using the Column Major Technique
 Application of Array
• SPARSE ARRAY (SA) : sparse array is an array where
nearly all of the elements have the same value
(usually zero) and this value is a constant. One-
dimensional sparse array is called sparse vectors
and two-dimensional sparse arrays are called sparse
matrix.
• SA allocates memory space for only non-zero
elements thereby minimize the memory space
requirement and improve the execution speed of a
program.
• SA = A[0…n][1…3]. n is number of non-zero element
 Sparse Array
• SA = A[0…n][1…3].
- n is the number of non-zero element
- A[0][1] num_row; A[0][2] num_column; A[0][3]
num_non zero elements
Relevant examples
Class practice
Assignment
 Activities III
1. Build the Sparse Array with the memory representation shown below

1 2 3

0 5 7 7

1 1 3 8

2 2 2 1

3 2 6 9

4 3 4 3

5 4 2 31

6 4 6 4

7 5 7 7

2. a. Formulate a Sparse Matrix A(4,6) with the first 6 alphabet sparsely distributed
b. Formulate the Sparse Array representation
 STACK DATA STRUCTURE
Stack is a non-primitive linear and dynamic data
structure. It allowed data insertion and deletion
only from one end (top of the stack).
The stack’s mode of operations is known as Last in
First Out (LIFO). Hence Stack is also known as
LIFO list, Piles, or Push-down list.
Primitive Operations: PUSH and POP
PUSH ≡ Insertion at the top; Top ← Top + 1 or Over
flow for Full Stack .
POP ≡ Removal at the top; Top ← Top - 1 or Under
flow for Empty Stack
 Illustration of Stack Operations

top
Empty
 Stack Implementation
Implementation could either be Static using Array or
Dynamic using Pointers.
Static implementation is not flexible.

Could any one

justify this
statement?
 PUSH & POP Algorithms
STACK-EMPTY(S)
1 if top[S] = 0 Exercise:
2 then return TRUE
3 else return FALSE
Write the STACK-
FULL(S) functions and
PUSH(S, x) rewrite the PUSH
1 top*S+← top*S+ + 1
2 S*top*S++← x (S,x)
POP(S)
1 if STACK-EMPTY(S)
2 then error “underflow”
3 else top*S+← top*S+ − 1
4 return S[top[S] + 1]
 Application of Stack
- It is used for backtracking activities, such as ?
- Recursive loop, evaluating parenthesis, interrupts,
subprogrames, Blogs etc.
- By compiler to implement recursive function non-
recursively
- Evaluating arithmetic expressions.
 Evaluating arithmetic expressions
The three basic types of notation in mathematics are
Infix, Prefix and Postfix. Stack can be used to calculate
the Postfix expressions.
Infix notation: commonly used in general mathematics,
order of operations not determined by the position of
operators, but the preference rules.
BODMAS, Operator precedence, Parenthesis and
Associativity,
Hence, Infix notation not okay for parenthesis free
expression. E.g. Evaluate 3^2+5*3^4-12/4
Also A+B*C ≠ (A+B)*C
 Evaluating arithmetic expressions- II
Prefix notation: Developed by Polish Mathematician Jan
Lukasiewicz, hence it is also known as Polish notation.
In the notation, operator is placed before its operands,
parenthesis not required because operations is determined
by the positions of operators and operands. Valid
expressions: ± AB, *GH, /MN, *+ABC, +*-ABCD.
The notation is adopted by most programming language fxn.
Add(A,B)

Examples:
i. (A+B)*C = [+AB]*C = *+ABC
ii. A+B*C = A+[*BC] = +A*BC
iii. (A+B) / (C-D)
NB. [ ] is used to indicate partial translation.
 Evaluating arithmetic expressions- III
Postfix notation: Reversed Polish notation. It is an analogous
notation in which the operator is placed after the operand.
Valid expressions: AB±, GH*, MN/, AB+C*, AB*CD+-
Rule of converting Infix to Postfix
i. Parenthesize the expression from left to right
ii. During parenthesizing, the operands associated with operator
having higher precedence are first parenthesized
iii. The sub-expression which has been converted into postfix is to
treated as single operand
iv. Once the expression is converted to postfix form, remove the
parenthesis
Examples:
i. (A+B)*C = [AB+]*C = AB+C*
ii. A+B*C = A+[B*C] = A+[BC*] = A[BC*]+ = ABC*+
iii. (A+B) / (C-D) iv. A^B+C*D^E-F/G
STACK Evaluation of Infix Notation II
The two steps required are: i. infix-to- Postfix Conversion
ii. Evaluation of Postfix in Stack
The Algorithm for (ii)
1. Add a right parenthesis “)” as sentinel for P
2. While P <> sentinel “)”
3. Scan P from L to T into STACK
4. IF an operand is encountered THEN PUSH to Stack
5. IF an operator ʘ is encountered, THEN
a. POP A,B from STACK, where A is top and B is previous top
b. Evaluate BʘA
c. PUSH the result of b on STACK
6. Set value equal to the top element on STACK
 STACK Evaluation of Infix Notation III
Example. Simulate in Stack the Evaluation of P:
P= 5,6,2,+,*,12,4,/,-
Solution: P= 5,6,2,+,*,12,4,/,-,)
S/N Scanned Elements STACK
1 5 5
2 6 5,6
3 2 5,6,2
4 + 5,8
5 * 40
6 12 40,12
7 4 40,12,4
8 / 40,3
9 - 37
10 )
 STACK Evaluation Binary Conversion
Function binaryconversion (int n)
Stack s New stack 2
While n>0 do Example. Convert 23 to Base
int bit n modulo 2 S/ Scanned STACK STACK
(PUSH) (POP)
s.PUSH(bit) N. Elements

IF s is full THEN return Err 1 23 1 101111

n floor (n/2) 2 11 1
3 5 1
4 2 1
While NotEmpty(s) do 5 1 0
6 0 1
s.POP()
 STACK Exercises
1. Write the STACK-FULL(S) functions and rewrite the PUSH (S,x)
2. Generate the Prefix and Postfix for:
i. A + [(B+C) + (D+E)*F]/G
ii. (A+B)*C/D+E^F/G
iii. A*(B+D)/E-F*(G+H/K)
3. Consider P: 12,7,3,-,/,2,1,5,+,*,+
a. Translate P into the infix equivalent
b. Evaluate the infix expression
c. Simulate the evaluation of P in STACK
4. Simulate the evaluation of binary conversion of 27 in Stack Data
Structure
 QUEUE Data structure- INTR.
A queue is a pile of items added at one end (rear) and
removed from the other end (front). The mode is
known as FIFO.
Applications of queue: Traffic, Customer services,
Printer spooling and Time sharing activities
Queue operations: ENQUEUE for Insert and DEQUEUE
for Delete. It uses a head and a tail pointers
The elements in the queue are in locations head[Q],
head*Q+ +1, . . . , tail*Q+ − 1
 QUEUE Data structure – INTR. II
Initially, we have head[Q] = tail[Q] = 1. When the
queue is empty, an attempt to dequeue an element
causes the queue to underflow.
When head[Q] = tail[Q] + 1, the queue is full, and an
attempt to enqueue an element causes the queue
to overflow
 ENQUEUE & DEQUEUE ALGORITHMS
ENQUEUE(Q, x)
1 Q*tail*Q++ ← x
2 if tail[Q] = length[Q]
3 then tail*Q+ ← 1
4 else tail*Q+ ← tail[Q] + 1

DEQUEUE(Q)
1 x ← Q*head*Q++
2 if head[Q] = length[Q]
3 then head*Q+ ← 1
4 else head*Q+ ← head*Q+ + 1
5 return x
QUEUE IMPLEMENTATION IN ARRAY
 QUEUE ACTIVITIES
Using Figure 10.1 as a model, illustrate the result of
each operation in the sequence PUSH(S, 4), PUSH(S,
1), PUSH(S, 3), POP(S), PUSH(S, 8), and POP(S) on an
initially empty stack S stored in array S[1 . . 6].

Rewrite ENQUEUE and DEQUEUE to detect underflow

and overflow of a queue.
 LINKED LISTS – INTR. I
A linked list is a data structure in which the
objects are arranged in a linear order.
Unlike an array, though, in which the linear
order is determined by the array indices, the
order in a linked list is determined by a pointer
in each object.
A list may either be singly linked or doubly
linked, sorted or unsorted, and it may be
straight or circular.
 LINKED LISTS – INTR. II
Each element of a doubly linked list L is an object with a
key field and two other pointer fields: next and prev.
The object may also contain other satellite data.
Given an element x in the list, next[x] points to its
successor in the linked list, and prev[x] points to its
predecessor.
If prev[x] = NIL, the element x has no predecessor and is
therefore the first element, or head, of the list.
If next[x] = NIL, the element x has no successor and is
therefore the last element, or tail, of the list.
An attribute head[L] points to the first element of the list.
If head[L] = NIL, the list is empty
 LINKED LISTS – INTR. III
If a list is singly linked the prev.- pointer in each element is
omitted
If a list is sorted, the linear order of the list corresponds to
the linear order of keys stored in elements of the list;
the minimum element is the head of the list, and the
maximum element is the tail.
If the list is unsorted, the elements can appear in any
order.
In a circular list, the prev.- pointer of the head of the list
points to the tail, and the next pointer of the tail of the
list points to the head. The list may thus be viewed as a
ring of elements.
LINKED LISTS – ILLUSTRATIONS

Assuming unsorted and doubly linked list

 LINKED LISTS – Insert / Delete
LIST-INSERT(L, x) LIST-DELETE(L, x)
1 next*x+ ← head*L+ 1 if prev[x] = NIL
2 if head[L] = NIL 2 then next[prev*x++ ← next*x+
3 else head*L+ ← next*x+
3 then prev*head*L++ ← x 4 if next[x] = NIL
4 head*L+← x 5 then prev*next*x++ ← prev[x]
5 prev*x+ ← NIL

It must be given a pointer to x, hence, it might

Given an element x whose key field has be necessary to first call LIST-SEARCH
already been set to retrieve a pointer to the element
 LINKED LISTS – Traversing / Searching
LIST-SEARCH(L, k)
1 x ← head*L+
2 while x = NIL and key[x] = k
3 do x ← next*x+
4 return x

The procedure LIST-SEARCH(L, k) finds the first element with

key k in list L by a simple linear search, returning a pointer
to this element. If no object with key k appears in the list,
then NIL is returned.
 Implicit Implementation of Pointers
and Objects
• For programming languages with out explicit
data type for pointers, a multi-array (Matrix) is a
popular tool for such implementation though a
linear array can also be used.
• In matrix implementation, each object is
represented on the same index (x) of columns
prev[x], key[x] and next[x] columns.
Array Representation of Pointers and
Objects
 Allocating and freeing objects
To insert a key into a dynamic set represented by a
doubly linked list, it is essential to manage the
unused object in the linked-list representation.

The process known as garbage collector

management involves “allocate” and
“deallocate” procedures to produce the free list.
 Allocating and freeing objects II

Suppose that the arrays in the multiple-array

representation have length m and that at some
moment the dynamic set contains n ≤ m elements.
Then n objects represent elements currently in the
dynamic set, and the remaining m−n objects are
free; the free objects can be used to represent
elements inserted into the dynamic set in the
future.
 Algorithms to allocate and De-allocate
objects

ALLOCATE-OBJECT() FREE-OBJECT(x)
1 if free = NIL 1 next*x+ ← free
2 then error “out of space” 2 free ← x
3 else x ← free
4 free ← next*x+
5 return x
Allocating and freeing objects
(Matrix Representation)
 Explanation of Matrix Representation
The free list uses only the next array, which stores
the next pointers within the list. The head of
the free list is held in the global variable free.
When the dynamic set represented by linked
list L is nonempty, the free list may be
intertwined with list L.
 Linked List - Exercises
i. Draw a picture of the sequence 13, 4, 8, 19,
5, 11 stored as a doubly linked list using the
multiple-array representation.
ii. Read up the single-array representation and
draw its representation for the sequence in
(i).