PROGRAMMING TECHNIQUES

Chapter 02

Linear Dynamic Structures

Khoa Công Nghệ Thông Tin

Trường Đại Học Khoa Học Tự Nhiên GV: Thái Hùng Văn
ĐHQG-HCM
OUTLINES
2

1. Data Structure 5. Linked List

▪ Important Data Structures ▪ Concept
▪ Data structure classification ▪ Linked List Structure
2. Linear Data Structure ▪ Variations
▪ Types ▪ Implementaton
▪ Operations ▪ Representation /Declaration
▪ Traversal
3. Dynamic Array (DA) ▪ Prepend /Append /Insert new node
▪ DA Size ▪ Delete a node
▪ DA Declaration ▪ Quiz
▪ DA Operations ▪ Examples
4. Dynamic 2D Array (DA2d) ▪ Sumary
▪ DA2d Declaration 6. Stack
▪ DA2d with different lengths
▪ DA2d Operations
7. Queue
▪ Quiz
1
3
 4

• In the programming world, data is the center and

everything revolves around data.
• Program need to perform all data operations including
organizing, storing, searching, sorting and accessing data
effectively.
• Data structures are the ways of organizing and storing
data in a computer so that we can perform programming
operations efficiently on it.

medium.com/@mklynn100/data-structures-and-algorithms-94cdb0e18d17
 5

Commonly used data structures:

• Array (Static and Dynamic, 1D & 2D)
• String (ASCII & UniCode)
• Stack & Queue
• Linked List (Singly, Doubly, Circular Linked List)
• Tree (Binary Tree, Binary Search Tree)
• Priority Queue
• Hash Table
• Graph

medium.com/@mklynn100/data-structures-and-algorithms-94cdb0e18d17
6
 7

• In the programming world, data is the center and

everything revolves around data.
• We need to do all data operations including storing,
searching, sorting, organizing, and accessing data
efficiently and only then our program can succeed.
• Data structure is an organized collection of data that
helps a program to access data efficiently and rapidly
so that the entire program can function in an efficient
manner.
 8

• In real projects, we often have to process many objects of

the same type (for example, students of a school).
• Data structures representing multiple same type elements
can be categorized into two parts: Linear and Non-Linear.
• Linear data structures (LDSs) have all their elements
arranged in a linear sequence. Each element in a LDS has
exactly 1 predecessor (previous element) and 1 successor (next)

Linear Data Structure Non-Linear Data Structure

Every item is related to its previous & next item Every item is attached with many other items
Data is arranged in linear sequence. Data is not arranged in sequence.
Data items can be traversed in a single run. Data cannot be traversed in a single run.
Eg. Array, Stacks, linked list, queue. Eg. tree, graph.
Implementation is easy. Implementation is difficult.
 9

• LDS consists of Arrays and Linked Lists.

• In terms of memory allocation, LDSs are divided into Static
and Dynamic DSs.
• Linear Static DS is a Static Array (most popular)
• Linear Dynamic DS is Dynamic Array and Linked List.
 10

• Create: an element of Linked List or N elements of Array

• Delete: an element of Linked List or All of Array
• Traversal /Print
• Search
• Get /Update: with attributes of an element
• Add
• Sort
• Merge
• Split
• Reallocate: only for Dynamic Array
 3.
11

DYNAMIC ARRAY

www.nextptr.com/
 12

• Other name: growable array, resizable array, dynamic

table, mutable array, or array list.
• Dynamic Array (DA) is a random access, variable-size list
DS that allows elements to be added or removed. DAs
overcome a limit of static arrays (must have a fixed capacity
that needs to be specified at allocation, store in Stack).
• Operations on DAs can be performed in the same way as
static arrays, except for operations involving allocation.

medium.com/@mklynn100/data-structures-and-algorithms-94cdb0e18d17
 13

• DA can be constructed by allocating an array of fixed-size,

typically larger than the number of elements immediately
required. The elements of the DA are stored contiguously at the
start of array (and the remaining positions towards the end of
array are reserved, or unused).
• Elements can be added at the end of a DA by using the
reserved space, until this space is completely consumed. When
all space is consumed, the fixed-sized array needs to be
increased in size.
• The number of elements used by the DA contents is its logical
size or size, while the size of the underlying array is called the
DA’s capacity or physical size, which is the maximum possible
size without relocating data.

medium.com/@mklynn100/data-structures-and-algorithms-94cdb0e18d17
 14

• Uses a Pointer of Element Type point to the first element,

and an integer variable for the number of elements
• Syntax:
Type * ptr; // similar with Type ptr[MAX] in Static Array
int num;
• We can also define the type of array structure that consists
of the two or three above components:
struct Array { struct Array {
Type * items; Type * items;
int n; // number of elements int capacity; // size of array
}; int n; // number of elements
}; // better
 15

• Uses new operator (C++) or malloc /calloc function (C)

to allocate memory for a new DA.
• Syntax:
ptr = new Type [ N ]; // N is number of elements, ptr is array
//or: ptr = (Type*) malloc (N *sizeof(Type));
//or: ptr = (Type*) calloc (N, sizeof(Type)); initialize 0 for all
• Example - create DA with <num> elements:
// return pointer to DA (or NULL if fail) // return FALSE if can not allocate memory
int * CreateArr (int num) bool CreateArr (Array &A, int num) {
{ A.n = num;
int *p = new int [num]; A.capacity = A.n + RESERVE; // RESERVE>=0
return p; A.items = new int [A.capacity];
} return (A.items != NULL);
//or bool Create(int* &a, int num) {...? } }
 16

• General syntax:
array_name [indexExp]
// or: *(array_name + indexExp)
where indexExp, called an index, is any expression whose value is
a non-negative integer.
• Index value specifies the position of component in array, it
always starts at zero (0).
• Examples:
int k=3, *a =new int [ 2*k+1 ];
*a = 2021; // a[0]=2021
*(a+1) = *(a+2) = 4; // a[1]=a[2]=4
cout<< a[0] << a[1] << a[2]; // output: 202144
 17

DA can be initialized during declaration in some forms:

▪ int* a = new int[7]{ }; // array of 7 items & all of them are zero.

▪ int* a = new int[5]{2,0,21}; //or int* a {new int[5]{2,0,21}};

// array of 5 items, initializes a0=2, a1=0, a2=21 and a3=a4=0

Example:
// Static Array // Dynamic Array
int a[3] = {21, 4}; int *a = new int [3] {21, 4};
cout<<a[0]<<a[1]<<a[2]; //out: 2140 // or: int * a { new int [3] {21, 4} };
int b[5] = { }; cout<<a[0]<<a[1]<<a[2]; //out: 2140
cout<<b[0]<<b[1]<<b[2]; // out: 000 int *b = new int [5] { }; // int*b {new int [5] { }};
cout<<b[0]<<b[1]<<b[2]; // out: 000
 18

• Still use functions / operator like creating dynamic objects

• Syntax:
delete[] Ptr; // Ptr is pointer point to dynamic arrray
//or free (Ptr);
• Example:
int n=2020, * fibonaci = new int[n];
if (fibonaci==NULL) exit(1); // allocate fail
fibonaci[0] = fibonaci[1] = 1;
for (int i=2; i<n; i++)
fibonaci[i] = fibonaci[i-1]+fibonaci[i-2];
...
delete[] fibonaci;
 19

• DAs are passed by a pointer:

▪ bool CreateArray (int * &arr , int &Size)
▪ void InputArray (int * arr , int Size)
▪ void OutputArray (int * arr , int Size)
• The return value of the function can be a DA (can not be a SA)
▪ int * CreateArray (int & Size)
• DA can be a structure
▪ struct Array {
Type * items;
int capacity; // size of array
int n; // number of elements
};
▪ bool CreateArray (Array &Arr)
▪ void InputArray (Array Arr)
▪ void OutputArray (Array Arr)
 20

• Similar to Static Array (use an index variable and a loop to

browse all the elements)
• Example:
void printArray (const int * arr, int num)
{
for (int i=0; i<num; ++i)
cout << arr [ i ] << " "; // print the ith element
}
// or
void printArray (Array Arr)
{
for (int i=0; i<Arr.n; ++i)
cout << Arr.items[ i ] << " "; // print the ith element
}
 21

Known number of elements Number of elements is unknown

void inputArr(Array &A, int n) { void inputArr (Array &A) {
A.n = n; // number of elements A.n = 0 ;
for (int i=0; i<A.n; ++i) { do {
cout<<"element["<<i<<"]="; cout<<"element["<<A.n<<"]=";
cin>> A.items[ i ] ; cin>> A.items[n] ;
} A.n++ ;
} if (A.n==A.capacity ) return;
void inputArr(int* arr, int size){ cout<<"input another?(y/n)";
for (int i=0; i<size; ++i) { char ans = getchar();
cout<<"element["<<i<<"]="; }while (ans=='Y' || ans=='y');
cin>> arr[ i ] ; }
}
}
call: inputArr ( arr, size ); call: inputArr ( Arr );
 22

Hãy điền vào các chỗ trống (phần ...)

#include <iostream> void main() {
using namespace std; int N;
cout<< “Nhap so phan tu: “;
struct Array { cin>>N;
int * items; Array F;
int capacity; //Sizeof array if (CreateArray( F, N ) == false) return;
int n; //Number of elements Fibonaci ( F ); // dat cac phtu Fibonaci vao X
}; cout<< “Day ” <<N<< “ phan tu Fibonaci: “;
PrintArray( F );
...... Free( F );
}
 23

in Unsorted Array - in Sorted Array -

Using Sequential Search Using Binary Search
// return index of the first item that // This function is faster than the left
equals to the key ;if not exists, return-1 int binSearch (Array A, int key) {
int seqSearch(Array A, int key) int left=0, right=A.n-1;
{ do {
for (int i=0; i<A.n; i++) int mid = (left+right)/2;
if (A. items[mid] == key)
if (A.items[ i ] == key) return mid;
return i; // return index if (A. items[mid]<key)
return -1; right=mid-1;
} else left=mid+1;
// in general, we can replace } while (left<=right);
‘A.items[i]==key’ by Check( return -1;
A.items[i]) }
If element exists, the average The maximum number of repetitions
number of repetitions is N/2 is only log2(N)
 24
Normal form Advanced form
// function return the index of the // Searching start from from index (default value is 0)
smallest value in the unsorted array int minIndex (Array A, int from=0) {
int minIndex (const Array A) int minIdx = from;
for (int i=from+1; i<A.n; ++i)
{ if ( A.items[i] < A.items[minIdx] )
int minIdx = 0; minIdx = i;
int min = A.items[0]; return minIdx;
for (int i=1; i<A.n; ++i) }
if (A.items[ i ] < min) { int minIndex(Array A, int from, int to){
min = A.items[ i ] ; int minIdx = from;
minIdx = i; for (int i=from+1; i<=to; ++i)
} if ( A.items[ i ] < A.items[minIdx] )
return minIdx; minIdx = i;
} return minIdx;
}
//call: // other forms: minPos=minIndex (Arr, fr);
minPos=minIndex (Arr); // minPos=minIndex (Arr, from, to);
 25

• To "delete" an element from the array you have to:

▪ Find the position of element.
▪ Move all higher elements one place down
▪ Reduce the size of array by one
• Example:
bool delElement(Array &A, int pos) bool delElement (int*a, int &n, int pos) {
{ if (pos<0 || pos>=n) return false;
if (pos<0 || pos>=A.n) return false; for (int i = pos; i < n - 1; i++) a[ i ] = a [ i+1 ];
for (int i = pos; i < A.n - 1; i++) n -- ;
A.items[ i ] = A.items[ i+1 ]; return true; //successful
A.n -- ; }
return true; //successful int main() {
} Array Arr = {new int[7] {4,5,3,8,1}, 9, 7};
void printArray (const Array A) { if (delElement (Arr, seqSearch(Arr, 3))
for (int i=0; i<A.n; ++i) printArray ( Arr );
cout << A.items[ i ] << " "; return 0;
} }
 26
• We simply increase the number of elements by 1, and assign the
content to the last element.
• However, the problem is complicated when the number of elements
is equal to array size => You need to expand the array - the array
size must be increase without losing the existing contents.
Normal form Advanced form
bool appendElement bool Extend (Array &A, int Inc=101) {
(Array &A, int x) for ( ; Inc>0; Inc-=10)
if ( realloc(A.items, (A.capacity+Inc)*sizeof(A.a[0]))
{ break;
if (A.n == A. capacity) if (Inc<=0) return false; //can not increase array size
return false; A. capacity += Inc;
return true; //successful
A. items[ A.n ] = x;
}
A.n ++ ; bool appendEle(Array &A, int x) {
return true; //successful if (A.n == A.capacity) // must increase array size
} if ( ! Extend(A) ) return false
A.items[ A.n++ ] = x;
return true; //successful
}
 27
• To "insert" an element into the array you have to:
▪ Know the position and value of new element.
▪ Move all higher elements one place up and increment the number
of valid elements.
• For ex, with array: 3 2 5 1 4 8 3 0 6
0 1 2 3 4 5 6 7 8
=> After inserting 9 to position 3:
3 2 5 9 1 4 8 3 0 6
0 1 2 3 4 5 6 7 8 9
bool addEle(Array &A, int pos, int x) { bool addElement(Array &A, int pos, int x) {
if (pos<0 || pos>=A.n || if (pos<0 || pos>=A.n) return false;
A.n==A. capacity) if (A.n == A.capacity)
return false; if ( ! Extend(A) ) return false;
for (int i = A.n; i > pos; --i) for (int i = A.n; i > pos; --i)
A.items[ i ] = A.items[ i-1 ]; A.items [ i ] = A.items[ i-1 ];
A.items[pos] = x; A. items[pos] = x;
A.n++; A.n ++ ;
return true; //successful return true; //successful
} }
 28
• There are many different sorting algorithms, with various
pros&cons. Selection sort is one of the simplest algorithms.
• The algorithm finds the minimum value, swaps it with the
value in the first position, and repeats these steps for the
remainder of the list.
• We can also do the opposite: finds the maximum element,
swaps it with the last element:
void selectionSort (Array A) { void printArray (const Array A) {
while (A.n--) for (int i=0; i<A.n; ++i)
swap(A.a[maxIndex(A)], A.a[A.n]); cout << A.items[ i ] << " ";
} }
int maxIndex (Array A) { int main() {
int maxIdx = 0; Array Ar = {new int[3] {20,5,11}, 7, 5};
for (int i=1; i<A.n; ++i) selectionSort ( Ar );
if (A.a[i]>A.a[maxIdx]) maxIdx = i; printArray ( Ar );
return maxIdx; }
}
29
 31

• 2d DA (or DA2d) is basically a 1d DA, where every

element is a pointer to another 1d DA.
• Declaration:
+ Normal form:
Type **ptr; // point to 2D array
int rows; // number of rows
int columes; // number of columes
+ Advanced form:
struct Array2D struct Array2D {
{ Type ** a;
Type ** a; int rows; // number of rows
int rows; // number of rows int * row_size; // size of each row
int cols; // number of columes int * row_num; //num of ele. on row
} }
 32

In some cases, each row has a different width (For example,

each line is a class, each class has a different number of students, and
each element is a student). In this case we must store all row
sizes and allocate /process separately.
Example:
int ** table;
int rows = 6;
int *row_num = new int[rows] {4,7,1,3,2,0}; //each row has a different size
table = new int * [rows]; table
for (i=0; i< rows; i++) 12 34 56 78
table[i]=new int[row_num[i]]; table[0] 1 2 3 4 5 6 7
table[1]
for (i=0; i<4;i++) table[0][i] = 12+22*i; table[2]
for (i=0; i<7;i++) table[1][i] = 1+i; table[3] 99
table[2][0] = 99; table[4]
for (i=0; i<3;i++) table[0][i] = 11*(i+1); 11 22 33
table[5]
table[4][0] = 0; table[4][1] = 1;
0 1
 33
struct Array2D {
Type ** a;
int rows; // number of rows
int cols; // number of columes
} Arr;
• Allocation:
Arr.a = new Type *[Arr.rows];
for (int i=0; i < Arr.rows; i++)
Arr.a[i]= new Type[Arr.cols];
• Destruction:
for (int i=0; i < Arr.rows; i++)
delete[ ] Arr.a[i];
delete[ ] Arr.a;
 34

Input Output
void input2dArr(Array2D A) { void output2dArr(Array2D A)
for (int i=0; i<A.rows; i++) { {
for (int j=0; j<A.cols; j++) { for (int i=0; i<A.rows; i++)
cout<< “ a [ "<< i << “ ] [ “ << j << “ ]= "; {
cin>> A.a [ i ] [ j ] ; for (int j=0; j<A.cols; j++)
} cout<<A.a [ i ] [ j ] << “ “;
cout << endl ; cout << endl ;
} }
} }
 35

Largest Element in Row Largest Element in Colume

//return index of the largest value in row //return index of the largest value in col
int maxIndex(Array2D A, int Row) { int maxIndex(Array2D A, int Col) {
int maxIdx = 0; int maxIdx = 0;
int max = A.a [Row] [0]; int max = A.a [0] [Col];
for (int j=1; i<A.cols; ++j) for (int i=1; i<A.rows; ++i)
if (A.a[Row] [ j ] > max) { if (A.a [ i ] [Col]> max) {
max = A.a[Row] [ j ] ; max = A.a [ i ] [Col];
maxIdx = j; maxIdx = i;
} }
return maxIdx; return maxIdx;
} }
 Normal form Advanced form 36

int **createMatrix(int M, int N) { void createlMatrix(Array2D &A, int Rows, int Cols) {
int **a = new int* [M]; A.rows = Rows; A.cols = Cols;
for (int i=0 ; i < M ; i++) A.a = new int *[A.rows];
a [ i ] = new int[N]; for (int i=0; i < A.rows; i++)
return a;
A.a[i]= new int [A.cols];
}
}
void fillMatrix(int** a, int M, int N) {
void fillMatrix (Array2D A) {
for (int i=0 ; i < M; i++)
for (int i=0; i<A.rows; i++)
for(int j=0 ; j < N ; j++)
for (int j=0; j<A.cols; j++)
a [ i ][ j ] = (i+1)*1000 + j+1;
}
A.a[ i ] [ j ] = (i+1)*1000 + j+1;
}
void printMatrix(int** a, int M, int N) {
void printMatrix (Array2D A) {
for (int i=0 ; i < M ; i++) {
for (int i=0; i<A.rows; i++) {
for (int j=0; j<N; j++) cout<<a[ i ][ j ]<<" ";
for (int j=0; j<A.cols; j++) cout<<A.a[ i ] [j]<<“ “;
cout<<endl;
}
cout << endl ;
}
}
}
void main() {
void main() {
int R=3, C=4, **Arr = createMatrix(R, C);
Array2D Arr;
fillMatrix (Arr, R, C);
createMatrix (Arr, 3, 4);
printMatrix (Arr, R, C);
fillMatrix (Arr);
// freeMatrix (Arr, R);
}
printMatrix (Arr); // freeMatrix (Arr);
}
 37

• Advantages of Static Arrays ?

• Advantages of Dynamic Arrays ?
• Restrictions of Static Arrays ?
• Restrictions of Dynamic Arrays ?
=>
• DA and SA are both solid lists, must be stored on a
consecutive memory.
• Changing the size of the DA requires creating a new DA
and then copying all data from the old DA to the new.
• Inserting or Deleting an item inside the array requires
shifting other items.
HEAD NULL

Hi ! How are you?

 39

• Linked structure will overcome limitations of Array.

• Linked structure is a collection of nodes (elements) storing
data items and links to other nodes.

• Linked List (LL) is a sequence of nodes, each node has a

data field and a reference field to the next node.

• Nodes can be located anywhere in memory, not stored at

a contiguous location; they are linked using pointers.

• The first node is usually called pHead, & the last => pTail
 40

• A Linked List (LL) is a series of connected Nodes

A B C 
pHead
• We create a new node (by allocate memory) every time we add
item to List, and remove nodes when item removed from List
node
(and reclaim memory) A
data pointer
• Each node contains 2 parts: data and references (links). In
most basic form, each node consists at least a piece of data and
a pointer to the successor (the last node points to NULL)
 41

• In terms of number of links:

▪ Singly-LL: reference part has only one pointer that point to the next
node in sequence of nodes. A B C 
pHead
▪ Doubly-LL: reference part has 2 pointers, one points to the previous
node and one points to the next.
▪ Multiply-LL: reference part has 2 or more pointers, each pointer
points to a node in the order of a given data field.

• In terms of circle: A B C

pHead
▪ Circularly-LL : the last pointer points to the first node, all nodes are
linked in a continuous circle, without using NULL.

▪ Normaly LL (non-circular): the last pointer points to NULL

 42

• LL can be visualized as a chain of nodes, where every node points to

the next node.
• Each node consists of at least 2 parts: data & pointer to the next node
• In C/C++, we can represent a node of LL using structures or classes.
(In Java and Python, LL can be represented as a class and a Node as a separate
class, the LL class contains a reference of Node class type)

• An example of a linked list node with a float data:

struct Node { // Singly LL Node
float data;
struct Node * Next;
};
 43

• LL can be visualized as a chain of nodes, where every

node points to the next node. pTail

A B C D E
pHead

• As per the above illustration, following are the important

points to be considered.
• LL contains a link element (pHead)
• Each link carries a data field(s) and a link field (pNext)
• Each link is linked with its next node.
• Last node carries a link as null to mark the end of the list.
• LL may have a pointer (pTail) point to the last node.
 44

No pointer to the last node Have a pointer to the last node

// SLL Node: typedel struct tagNode {
struct Node { Type data;
Type data; struct tagNode * pNext;
struct Node * Next; } NODE;
};
// SLL Declaration: typedel struct tagList {
Node * Head; NODE * pHead, * pTail;
// SLL Initiation:
} SLList;
Head = NULL; //LL is empty SLList List = {NULL, NULL};
 45

pTail

A B C D E
pHead
struct tagNode { // Singly LL Node
Type data;
struct tagNode * pNext;
} NODE;
struct SLList{ // Singly LL Type
NODE * pHead, * pTail;
};
SLList List; // Singly LL Declaration
List.pHead = List.pTail = NULL; //Initialize Empty List
 46

A B C D

typedef struct tagDNode { // Doubly LL Node

pHead Type data; pTail
struct tagDNode * pNext, * pPre;
} DNODE;
typedef struct tagDist { // Doubly LL Type
DNODE * pHead, * pTail;
} DLList;
DLList List; // Doubly LL Declaration
List.pHead = List.pTail = NULL; //Initialize an Empty List
 47

A B C D E

typedef struct tagNode { // Circular LL Node

pHead Type data; pTail
struct tagNode * pNext;
} NODE;
typedef struct tagCList { // Circular LL Type
NODE * pHead, * pTail; // pHead==pTail->pNext?!
} CLList;
CLList List; // Circular LL Declaration
List.pHead = List.pTail = NULL; //Initialize Empty List
 48

A B C D

typedel struct tagCDNode { //Circular Doubly LL Node

pHead Type data; pTail
struct tagCDNode * pNext, * pPre;
} CDNODE;
typedel struct tagCDList { // Doubly LL Type
CDNODE * pHead, * pTail,; // need *pTail
} CDLList;
CDLList List; // Doubly LL Declaration
List.pHead = NULL; //Initialize an Empty List
 49

• Traversal: To traverse all the nodes one after another.

• Insertion: To add a node at the given position.

• Deletion: To delete a node.

• Searching: To search an element(s) by value.

• Updating: To update a node.

• Sorting: To arrange nodes in a linked list in a specific order.

• Merging: To merge two linked lists into one.

 50

• LL is a linear data structure that needs to be traversed

starting from the head node until the tail (end) node.
• Unlike arrays, where random access is possible, LL requires
access to its nodes through sequential traversal.
• Traversing a LL is an important operation. We must use it
to print LL, search for a specific node, and perform many
advanced operations on the LL.
• C++ implementation:
NODE * current = List.pHead; // Start with the Head node of the LL
while (current != NULL) { // Continue until no more nodes
Process(current->data); // Access/process current node content
current = current->pNext; // Go to the next node of the LL
}
 51

• Addition
• Prepend
• Append
• After a node
• Before a node
• Deletion
• First node
• After a node
• All node
 52

• Create Node: pTail

newNode = new NODE {X, NULL};
• SLL is empty: pHead X
pHead = pTail = newNode;
• SLL is not empty:
newNode->pNext = pHead;
pHead = newNode;
X
pTail

A B C D E
pHead
 53

pTail

• SLL is empty: pHead X

pHead = pTail = newNode;

• SLL is not empty:

pTail->pNext = newNode; pTail
pTail = newNode;
X

A B C D E
pHead
 54

newNode = new NODE {X, NULL};

newNode->pNext = q->pNext;
q->pNext = newNode;
if (q==pTail)
pTail = newNode;
q

X
pTail

A B C D E
pHead
 55

• If <q> is the first node of SLL (q==Head): see the first case
• Else: find previous node <p> and use the previous case
p = pHead;
while (p->pNext != q) //find previous node of <q>
p = p->pNext;
p->pNext = newNode;
newNode->pNext = q; q

X
pTail

A B C D E
pHead
p
 56

if (pHead == pTail) { //There is only one node

delete pHead;
pHead = pTail = NULL;
} else {
NODE *p = pHead;
pHead = pHead->pNext;
delete p;
}

pTail

A B C D E
pHead
p = pHead
 57

p = q->pNext; // <p> : the node must be delete

if (p != NULL) {
q->pNext = p->pNext;
if (L.pTail==p)
L.pTail = q;
delete p; q
}

pTail

A B C D E
pHead
p = q->pNext
 58
// Singly Linked List Example @THV.2020.05 NODE* updateNode(SLList &L) { // return NULL if not found
// ----------------------------------------- cout<<"Enter the key of node: ";
#include <iostream> int key; cin>>key;
using namespace std; NODE * p = searchNode(L, key);
struct Element { // struct of Element if (p == NULL) return NULL;
int key; cout<<"Enter the new key of node: ";
float xyz; // and_or sth else cin>> p->data.key;
}; cout<<"Enter the new <xyz> of node: ";
typedef struct tagNode { // Singly LL Node cin>> p->xyz;
Element data; return p;
struct tagNode * pNext; }
} NODE; NODE* prependNode(SLList &L, Element X) {// return newNode
typedef struct tagList { // Singly LL Type NODE* newNode = new NODE {X, NULL};
NODE * pHead, * pTail; if (newNode==NULL) return NULL;
} SLList; if (L.pHead==NULL) // SLL is empty
L.pHead = L.pTail = newNode;
void printList(const SLList L) { else {
NODE * current = L.pHead; newNode->pNext = L.pHead;
cout<<"-------------------"<<endl<<" Elements of List: [ "; L.pHead = newNode;
while (current != NULL) { }
cout<< current->data.key <<" "; return newNode;
current = current->pNext; }
} NODE* appendNode(SLList &L, Element X) {/ / return newNode
cout<<"]"<<endl<<"........................."<<endl; NODE* newNode = new NODE {X, NULL};
} if (newNode==NULL) return NULL;
// return a pointer to the node (NULL if not found) if (L.pHead==NULL) // SLL is empty
NODE* searchNode(const SLList L, int key) { L.pHead = L.pTail = newNode;
NODE * current = L.pHead; else {
while (current != NULL && current->data.key != key) L.pTail->pNext = newNode;
current = current->pNext; L.pTail = newNode;
return current; }
} return newNode; }
 59
// insert a new node at position <Pos>, return to newNode void deletetNodeAtPosition(SLList &L, int Pos) {
NODE* insertNode(SLList &L, Element X, int Pos) { if (Pos==0) return deleteFirstNode(L);
if (Pos==0) return prependNode (L, X); NODE* q = L.pHead;
if (Pos==-1) return appendNode (L, X); for (int i=1; i<Pos && q!=NULL; i++) // find node at (Pos-1)
NODE* q = L.pHead; q = q->pNext;
for (int i=1; i<Pos && q!=NULL; i++) // find node at (Pos-1) if (q==NULL) return; // Pos > number of elemens
q = q->pNext; NODE *p = q->pNext; // <p> : the node must be delete
if (q==NULL) return NULL; // Pos > number of elemens if (p == NULL) return;
// insert <newNode> after node <q> q->pNext = p->pNext;
NODE* newNode = new NODE {X, q->pNext}; if (L.pTail==p) L.pTail = q;
if (newNode==NULL) return NULL; delete p;
q->pNext = newNode; }
if (q==L.pTail) L.pTail = newNode; void deleteNodeByKey(SLList &L, int Key) {
return newNode; if (L.pHead==NULL) return;
} if (L.pHead->data.key==Key) return deleteFirstNode(L);
NODE* addNode(SLList &L) { NODE* q = L.pHead, *p = q->pNext;
cout<<"Enter value of node: "; while (p!=NULL && p->data.key != Key) {
Element X; cin>>X.key; q = p; p = p->pNext; // <q> is always the previous of <p>
cout<<"Enter position to insert (-1 for append): "; }
int pos; cin>>pos; if (p==NULL) return; // not found
return insertNode(L, X, pos); q->pNext = p->pNext;
} if (L.pTail==p) L.pTail = q;
void deleteFirstNode(SLList &L) { delete p;
if (L.pHead == L.pTail) { //There is only one node }
delete L.pHead; void deleteNode(SLList &L) {
L.pHead = L.pTail = NULL; cout<<"Enter position to delete or -1 to delete by key): ";
return; int pos; cin>>pos;
} if (pos != -1) return deletetNodeAtPosition(L, pos);
NODE *p = L.pHead; cout<<"Enter the key of node: ";
L.pHead = L.pHead->pNext; int key; cin>> key;
delete p; deleteNodeByKey(L, key); // delete 1st node found
} }
 60
void deleteList(SLList &L) { Head2 = Head2->pNext;
while (L.pHead) deleteFirstNode(L); current->pNext = L.pHead; // prepend <current> to list <L>
} L.pHead = current;
// return number of random elements are made }
int makeRandomList (SLList &L) { }
if (L.pHead != NULL) deleteList (L); void main() {
cout<<"Enter number of elements: "; SLList List = {NULL, NULL}; //Init Empty List
int Num; cin>>Num; while (true) {
L.pHead = L.pTail= NULL; printList(List);
for (int i=0; i<Num; i++) { cout<<"0. Quit"<<endl
int random = (int)rand() % 2020; <<"1. Read Linked List from File"<<endl
Element X = {random, 1.0*random/99}; <<"2. Save Linked List to File"<<endl
if (!prependNode(L,X)) return i; <<"3. Make a random Linked List with N elements"<<endl
} <<"4. Update a node"<<endl
} <<"5. Add a node"<<endl
// reverse List by traverse list L1 and prepend to List L2 <<"6. Delete a node"<<endl
void reverseList (SLList L1, SLList &L2) { <<"7. Sort List"<<endl
if (L1.pHead == NULL) return; <<"8. Reverse List"<<endl
L2.pHead = L2.pTail = NULL; <<"9. Remove duplicate elements"<<endl;
while (L1.pHead != NULL) { cout<< endl<< "Enter operation number: ";
prependNode(L2, L1.pHead->data); int choice; cin>> choice;
L1.pHead = L1.pHead->pNext; switch (choice){
} case 0: deleteList(List); return 0;
deleteList(L1); case 3: makeRandomList(List); break;
} case 4: updateNode(List); break;
void reverseList (SLList &L){ // traverse & prepend to new-list case 5: addNode(List); break;
if (L.pHead == NULL) return; case 6: deleteNode(List); break;
NODE *Head2 = L.pHead->pNext; // mov List to <Head2> case 8: reverseList(List); break; //or reverseList(List, List);
L.pHead->pNext = NULL; default: cout<<"You need to enter a number between 0 & 9";
L.pTail = L.pHead; }
while (Head2 != NULL) { }
NODE * current = Head2; }
 61
#include <iostream> while (p != NULL) {
#define MAX 1234 Num++;
#define _INC 101 p = p->pNext;
using namespace std; }
typedef struct Student { return Num;
char Id[10]; }
char Name[30]; // chuyen mang dong A vao xau L
float Point; // maybe more if you want // tra ve so phan tu chuyen duoc
} Element; int Array2LinkedList(ARRAY A, LIST & L) {
L.pHead = L.pTail = NULL; //tao xau rong
typedef struct Node { for (int i = A.num - 1; i >= 0; --i)
Element data; if (!prependNode(L,A.items[i]))
struct Node * pNext; return A.num - 1 - i;
}NODE; return A.num;
typedef struct { }
Element * items; /*
int capacity; // mang A -> xau L khi co con tro cuoi xau
int num; int Array2LinkedList(ARRAY A, LIST & L) {
}ARRAY; L.pHead = L.pTail = NULL; //tao xau rong
typedef struct { for (int i = 0; i<A.num; i++)
NODE * pHead; if (!appendNode(L, A.items[i]))
NODE * pTail; return i + 1;
}LIST; return A.num;
// Dem so phan tu cua xau L }
int sizeOf(const LIST L) { */
int Num = 0;
NODE * p = L.pHead;
 62
// chuyen xau L vao mang dong A A.items = p;
// giai phong xau L neu co <Free> bat break;
bool List2Array(LIST &L, ARRAY &A, bool Free) { }
A.num = sizeOf(L); }
A.capacity = A.num + _INC; if (Inc <= 0) return false;
A.items = new Element[A.capacity]; A.capacity += Inc;
if (A.items == NULL) { }
A.capacity = A.num = 0; return true; }
return false; // Tao ngau nhien xau <L> voi <n> phan tu
} int makeRandom(LIST &L, int n) {
NODE *p = L.pHead; L.pHead = L.pTail = NULL;
for (int i = 0; i<A.num; i++, p=p->pNext) for (int i = 0; i<n; i++) {
A.items[i] = p->data; Element X = makeRandom();
if (Free) // giai phong xau L if (!prependNode(L, X)) return false;
while (L.pHead) { }
p = L.pHead; return true; }
L.pHead = p->pNext; // Tao ngau nhien mang dong <A> voi <n> phan tu va
delete p; <sz> vi tri, return FALSE neu ko tao duoc
} bool makeRandom(ARRAY &A, int n, int sz=MAX) {
return true; } if (n < MAX) A.capacity = sz;
// Mo rong danh sach them <Inc> phan tu else A.capacity = n + 100;
//IF ko dc: bot 10 den khi dc OR (Inc<=0) A.items = new Element[A.capacity];
bool extendArray(ARRAY &A, int Inc = 101) { if (A.items == NULL) return false;
for (; Inc > 0; Inc -= 10) { A.num = n;
Element* p = (Element*)realloc(A.items, for (int i = 0; i < A.num; i++)
(A.capacity + Inc)*sizeof(Element)); A.items[i] = makeRandom();
if (p != NULL) { return true; }
 63
// Xuat noi dung cua phan tu X ra man hinh
void Print(Element X) // CT chinh minh hoa
{ void main()
cout << "{"<<X.Id<<"# "<< X.Name<<"}"; {
} ARRAY A;
// Xuat mang A theo tung trang 100 hoac P phtu // tao ngau nhien mang dong A
void Print(ARRAY A, int p = 100) if (!makeRandom(A, 50, 1234567)) return;
{ cout << "* MANG DONG:" <<endl;
for (int i = 0; i < A.num; i++) { Print (A, A.num + 1); system("pause");
cout << "\t#" << i + 1 << ". ";
Print(A.items[i]); LIST L;
if (i % num == p - 1) cin.get(); Array2LinkedList(A, L); //
} cout << "* XAU:"<<endl;
cout << endl; Print(L); system("Pause");
}
// Xuat tat ca cac phtu trong xau L ARRAY B;
void Print(const LIST L) LinkedList2Array(L, B, true);
{ cout << "* MANG DONG:" << endl;
NODE * current = L.pHead; Print(B); system("Pause");
int num = 0; }
while (current != NULL) {
cout << "\t#" << ++num << ". ";
Print(current->data);
current = current->pNext;
}
cout << endl;
}
 64
// Tao ngau nhien noi dung cua 1 phan tu
Element makeRandom()
{
Element X;
int random = (int)rand() % 2020;
//strcpy_s(X.Id, 5, "IT20");
_itoa_s(random, X.Id + 0, 5, 10);
X.Point = 10.0*random / 2020;
char * Ho[19] = { "Nguyen", "Tran", "Le", "Pham", "Huynh", "Phan", "Vu", "Vo",
"Dang", "Bui", "Do", "Ho", "Ngo", "Duong", "Ly", "Trinh", "Ha", "Thai", "" };
char * Lot[3] = { "Van", "Thi", "" };
char * Ten[18] = { "Xuan", "Ha", "Thu", "Dong", "Tay", "Nam", "Bac", "Trung", "Dai",
"Cuc", "Mai", "Dao", "Le", "Nho", "Cam", "Quit", "Buoi", "Tac" };
X.Name[0] = 0;
strcat_s(X.Name, Ho[rand() % 18]);
strcat_s(X.Name, " ");
int iTenLot = rand() % 3;
if (iTenLot != 2) strcat_s(X.Name, Lot[iTenLot]);
else {
iTenLot = rand() % 19;
if (strncmp(Ho[iTenLot], X.Name, strlen(Ho[iTenLot])))
strcat_s(X.Name, Ho[rand() % 18]);
}
strcat_s(X.Name, " "); strcat_s(X.Name, Ten[rand() % 18]);
return X;
}
 65

• How to insert to a SLL at a given position ?

• How to insert a node into an ordered SLL ?
• How to delete the last node ?
• How to delete a node before node <q> in SLL ?
• How to delete all nodes at a given data ?
• How to delete N nodes at a given position ?
• How to delete all nodes in SLL ?
• How to merge two ordered SLLs ?
• How to modify above SLL example when the pTail member
is not exist ? Make a new program.
 66

• Addition
• Prepend
• Append
• After a node
• Before a node
• Deletion
• First node
• After a node
 67

• Create Node:
newNode = new NODE {X, NULL, NULL};
• DLL is empty:
pHead = pTail = newNode;
• DLL is not empty:
newNode->pNext = pHead;
pHead->pPre = newNode;
pHead = newNode;
 68

• DLL is empty:
newNode = new NODE {X, NULL, NULL};
pHead = pTail = newNode;

• DLL is not empty:

newNode = new NODE {X, NULL, NULL};
newNode->pPre = pTail;
pTail->Next = newNode;
pTail = newNode;
 69

newNode = new NODE {X, NULL, NULL};

// do not use temporary pointer // use a temporary pointer variable

newNode->pNext = q->pNext; NODE * r = q->pNext;
if (q->pNext != NULL) //=> must insert after <q> and before <r>
q->pNext->pPre = newNode; newNode->pPre = q;
newNode->pPre = q; q->pNext = newNode;
q->pNext = newNode; if (r != NULL) {
if (pTail == q) newNode->pNext = r;
pTail = newNode; r->pPre = newNode;
}
else // <q> == <pTail>
pTail = newNode;
 70

NODE * r = q->pPre; //=> must insert after <r> and before <q>
q->pPre = newNode;
newNode->pNext = q;
if (r != NULL) {
r->pNext = newNode;
newNode->pPre = r;
}
else // <q> == <pHead>
pHead = newNode;
 71

if (pHead == pTail) { //There is only one node

delete pHead;
pHead = pTail = NULL;
} else {
NODE *p = pHead;
pHead = pHead->pNext;
pHead->Pre = NULL;
delete p;
}
 72

NODE *p = q->pNext; // <p> : the node must be delete

if (p == NULL) return; // the node does not exist
NODE * r = q->pNext; // <p> is after <q> and before <r>
q->pNext = r;
if (r != NULL)
r->pPre = q;
else // <q> == <pTail>
pTail = q;
delete p;
73
 74

In DLL:
• How to insert a node at a given position ?
• How to delete the last node ?
• How to delete a node before node <q>?
• How to delete a node at a given data ?
• How to delete a node at a given position ?
• How to delete all nodes ?
 75

• Addition
• Prepend
• Append
• After a node
• Before a node
• Deletion
• First node
• After a node
 76

• CLL is empty:
newNode = new NODE {X, NULL};
newNode->pNext = newNode;
pHead = pTail = newNode;
• CLL is not empty:
newNode = new NODE {X, NULL};
newNode->pNext = pHead;
pHead = newNode;
pTail->pNext = pHead;
 77

• CLL is empty:
newNode = new NODE {X, NULL};
newNode->pNext = newNode;
pHead = pTail = newNode;

• CLL is not empty:

newNode = new NODE {X, NULL};
pTail->pNext = newNode;
pTail->pNext = pHead;
 78

newNode = new NODE {X, NULL};

NODE * r = q->pNext; //=> must insert after <q> and before <r>
q->pNext = newNode;
newNode->pNext = r;
if (q == pTail)
pTail = newNode;
 79

p = pHead;
while (p->pNext != q) //find previous node of <q>
p = p->pNext;
//=> must insert <newNode> after <p> and before <q>
p->pNext = newNode;
newNode ->pNext = q;
if (q == pHead)
pHead = newNode;
 80

if (pHead == pTail) { //There is only one node

delete pHead;
pHead = pTail = NULL;
} else {
NODE *p = pHead;
pHead = pHead->pNext;
pTail->pNext = pHead;
delete p;
}
 81

p = q->pNext; // <p> : the node must be delete

if (p == q) //There is only one node on CLL
pHead = pTail = NULL;
else {
q->pNext = p->pNext;
if (q == pTail)
pHead = pTail->pNext;
}
delete p;
 82

In CLL:

• How to insert a node at a given position ?

• How to delete the last node ?
• How to delete a node before node <q>?
• How to delete a node at a given data ?
• How to delete a node at a given position ?
• How to delete all nodes ?
• How to merge two ordered CLLs ?
 83

• Traversal: To traverse all the nodes one after another.

• Insertion: To add a node at the given position.

• Deletion: To delete a node.

• Searching: To search an element(s) by value.

• Updating: To update a node.

• Sorting: To arrange nodes in a linked list in a specific order.

• Merging: To merge two linked lists into one.

 84

• Header LL (HLL) is one more variant of LL.

• HLLs have a special node present at the beginning of the LL
(If LL is empty then always the header node is available)
• The first utility of a HLL is to simplify the functions: we can
easily perform operations like insertion and deletion
because we don't need to check if the list is empty or not.
• The data part of the header node is always None. Therefor
we can use this part to store some useful information (like
storing the number of nodes, address of the last node,…)
• SLL (without a header node): A B C 
pHead

• HLL (with a header node): # A B C 

pHead
 85

• Create Node:
newNode = new NODE {X, NULL};
• SLL (without a header node):
if (pHead==NULL)
pHead = pTail = newNode;
else {
newNode->pNext = pHead;
pHead = newNode;
}
• HLL (with a header node):
pHead->pNext = newNode;
if (pTail== pHead)
pTail = newNode;
 86

• SLL (without a header node):

if (pHead==NULL)
pHead = pTail = newNode;
else {
pTail->pNext = newNode;
pTail = newNode;
}
• HLL (with a header node):
pTail->pNext = newNode;
pTail = newNode;
 87
• SLL (without a header node):
newNode = new NODE {X, NULL};
if (pHead==q) {
newNode->pNext = pHead;
pHead = newNode;
}
else {
p = pHead;
while (p->pNext != q) //find previous node of <q>
p = p->pNext;
p->pNext = newNode;
newNode->pNext = q;
}
• HLL (with a header node):
p = pHead;
while (p->pNext != q) //find previous node of <q>
p = p->pNext;
p->pNext = newNode;
newNode->pNext = q;
 88

• SLL (without a header node and the tail pointer):

if (pHead == pTail) { //There is only one node
delete pHead;
pHead = NULL;
}
else {
NODE *q = pHead;
pHead = pHead->pNext;
delete q;
}
• HLL (with a header node and the tail pointer):
NODE *q = pHead->pNext;;
pHead->pNext = q->pNext;
delete q;
 89
Comparison Static Array Dynamic Array Linked List
element Index based (Direct or randomly accessed) Reference based (Sequentially
access –> Simple and Fast - O(1) accessed) -> Slow – O(n)
element Could be a primitive type. If it is a struct, it It must be a struct consisting
structure contains only data fields, that can be accessed of 2 parts: data and pointers,
as normally by the {.} operator fields accessed by reference by
the operator {->}
memory Stored consecutively Stored consecutively Stored randomly
location – in Stack – in Heap – in Heap
Size Specified during No need to specify, No specify, easy to grow or
declaration, and fix can grow or shrink shrink
Insert/delete Complex & Slow Simple and Fast
at beginning – O(n) - O(1)
Insert/delete Simple and Fast – O(1) when last node is known
at end O(1) O(n) when thelast is unknown
Searching Linear and Binary search (for ordered array) Linear search
Memory Ineffective Effective Effective
Utilization
 6.
90

STACKS

https://www.proofof.blog/2018/07/01/stack-queue.html
 91

• A “Stack” is an abstract data type (ADT) instance.

A Stack is call a last-in-first-out (LIFO) collection.
This means the last item we added (pussed) is the
first item that gets pulled (popped) off.
• Stack is a sequence of entries that are accessible at
only one end of it.
 92

• There are only two principal operations:

▪ push, which adds an element to the Stack (on the top)
▪ pop, which removes the most recently added element
that was not yet removed (and return it)
• In some cases, there may be additional operations:
▪ isEmpty, a boolean value, true or false if the stack is
empty or not, (note: a runtime error occurs if a pop()
operation is attempted on an empty stack)
▪ size, the number of elements in stack
 93

qua lại khách chờ sông lặng sóng ...

cười nhoẻn mắt ai bóng thướt tha
sóng
ngược xuôi thuyền đợi bến đông người bổng trầm đàn hát tiếng ngân xa
lặng
xa ngân tiếng hát đàn trầm bổng người đông bến đợi thuyền xuôi ngược
sông
tha thướt bóng ai mắt nhoẻn cười sóng lặng sông chờ khách lại qua
chờ
khách
lại
qua
 94

• A stack can be easily implemented either through

an Array or a Linked List.
• Array-Based Stack
▪ top of Stack is back of Array.
▪ In case we do not know the maximum size, Array must
be dynamic to prevent stack overflow.
• LinkedList-Based Stack
▪ top of Stack is front of Linked List.
▪ Linked List does not need to have pTail pointer at the
end.
 95

struct Stack {
bool Push(Stack &S, Element X)
Element * items;
{
int capacity; // max size of stack
if (S.top == S.capacity)
int top; // stack top
}; return false;
void Init(Stack &S, int size) S.items[S.top++] = X;
{
S.items = new Element[size]; return true;
S.capacity = size; }
S.top = 0;
} Element Pop(Stack &S)
bool isEmpty(Stack S) {
{
return (S.top==0); return S.items[--S.top];
}
}
 96

struct Node { bool Push (Stack &S, Element X) {

Element item; NODE *p = new NODE{X, S.pHead};
struct Node *pNext;
if (!p) return false;
} NODE;
S.pHead = p;
struct Stack {
return true;
NODE *pHead;
}
};
Element Pop (Stack &S) {
void Init(Stack &S) { NODE *p = S.pHead;
S.pHead = NULL; Element X = p->item;
} S.pHead = p->pNext;
delete p;
bool isEmpty(Stack S) { return X;
return (S.pHead==NULL);
}
}
 97

• Expression Evaluation and Syntax Parsing

• Back Tracking
• Compile Time Memory Management and Function Call
• Efficient Algorithms
• Security
• ...
 7.
98

QUEUES

https://www.proofof.blog/2018/07/01/stack-queue.html
 99

• A “Queue” is an abstract data type (ADT) instance,

similar to Stacks.
• But unlike Stacks, a queue is open at both its ends.
One end is always used to add data (enqueue) and
the other is used to remove data (dequeue).
• Queue follows first-in first-out methodology
(FIFO): element stored first will be accessed first.
• The end at which elements are added is called the
back, tail, or rear. And the end at which elements
are removed is called the head or front
 100

• There are only two principal operations:

▪ enqueue : adding an element to the rear of the queue
▪ dequeue : removing an element from the front
• In some cases, there may be additional operations:
▪ isEmpty, a boolean value, true or false if the queue is
empty or not, (note: a runtime error occurs if a pop()
operation is attempted on an empty stack)
▪ size, the number of elements in queue
 101

• A queue can be implemented either through

an Array or a Linked List.
• Array-Based Queue
▪ need to keep track of two indices, front and rear.
▪ enqueue an item at the rear and dequeue an item from
the front.
▪ increase front and rear in circular manner
• LinkedList-Based Queue
▪ can use Singly Linked List.
▪ maintain two pointers: the front points the first node
and the rear points to last node.
 102

struct Queue { bool enQueue(Queue& Q, Element X){

Element * items; if (isFull(Q) return false;
int capacity; // max size of queue Q.rear = (Q.rear+1) % Q.capacity;
int front, rear, size;
Q.items[Q.rear] = X;
};
void Init(Queue& Q, int size){ Q.size++;
Q.items = new Element[size]; return true;
Q.capacity = size; }
Q.rear = Q.capacity-1; //inportant
Element deQueue(Queue& Q){
Q.front = Q.size = 0;
} Element X = Q.items[Q.front];
bool isEmpty(Queue Q) { Q.front = (Q.front+1) % Q.capacity;
return (Q.size ==0);
} Q.size--;
bool isFull(Queue Q) {
return X;
return (Q.size == Q.capacity);
}
}
 103

struct Node { bool enQueue (Queue &Q, Element X) {

Element item; NODE *p = new NODE{X, NULL};
struct Node * next; if (!p) return false;
if (isEmpty(Q)) Q.front = Q.rear = p;
} NODE; else {
struct Queue { Q.rear->next = p;
NODE *front, *rear; Q.rear = p;
}
}; return true;
}
void Init(Queue &Q) { Element deQueue ( Queue &Q ) {
Q.front = Q.rear = NULL; NODE *p = Q.front;
} Element X = p->item;
Q.front = p->next;
bool isEmpty(Queue Q) { delete p;
return (Q.front); return X;
} }
 104

• CPU scheduling, Disk Scheduling

• Synchronizing for IO Buffers, pipes, file IO,..
• Print spooling
• Breadth First search in a Graph
• Handling of interrupts
• ...
 105

BT#01: VCT hỗ trợ người dùng thực hiện các phép tính cộng - trừ - nhân - chia
trên 2 phân số sao cho việc sử dụng con trỏ là nhiều nhất có thể.

(con trỏ được dùng ít nhất ở các chỗ: trỏ đến địa chỉ các phân số, trỏ đến tử & mẫu
của mỗi phân số, là tham số của hàm, lưu địa chỉ kết quả của hàm, làm con trỏ hàm)

BT#02: So sánh mảng tĩnh và mảng động 1 chiều; mảng tĩnh và mảng động 2 chiều

BT#03: So sánh các ưu khuyết điểm của

a/ Thao tác Thêm 1 phần tử trên xâu đơn và mảng 1 chiều.

b/ Thao tác Hủy 1 phần tử trên danh sách liên kết đơn và mảng 1 chiều.

c/ Danh sách liên kết đơn và mảng 1 chiều.

BT#04: So sánh các ưu khuyết điểm của

a/ Linked List có và không có con trỏ Tail luôn lưu địa chỉ Node cuối.

b/ Linked List có và không có Header Node.

 106

BT#05: Viết hàm chuyển danh sách sinh viên đang lưu trong một mảng động vào

a) danh sách liên kết đơn không có con trỏ cuối và ngược lại.

b) danh sách liên kết đơn luôn có con trỏ cuối và ngược lại.

c) danh sách liên kết kép và ngược lại.

d) danh sách liên kết vòng và ngược lại.

e) danh sách liên kết kép vòng và ngược lại.

BT#06: Viết hàm thêm 1 phần tử vào

a) mảng động đang có thứ tự.

b) xâu đơn có thứ tự + có và không có con trỏ cuối (2 hàm khác nhau).

c) xâu đơn có thứ tự + có Header node + có và không có con trỏ cuối (2 hàm khác nhau).

d) xâu đơn có thứ tự + có Header node và luôn có địa chỉ node cuối nằm trong các byte đầu
của trường dữ liệu trong Header node.
 107
BT#07: Viết hàm xóa phần tử cuối trên
a) mảng.
b) xâu đơn có và không có con trỏ cuối (2 hàm khác nhau).
c) xâu đơn có Header node + có và không có con trỏ cuối (2 hàm khác nhau).
d) xâu đơn có Header node chứa địa chỉ node cuối trong các byte đầu của trường dữ liệu.

BT#08: Viết hàm xóa phần tử đầu trên

a) mảng.
b) xâu đơn có và không có con trỏ cuối (2 hàm khác nhau).
c) xâu đơn có Header node + có và không có con trỏ cuối (2 hàm khác nhau).
d) xâu đơn có Header node chứa địa chỉ node cuối trong các byte đầu của trường dữ liệu.

BT#09: Viết hàm xóa phần tử có khóa K trên

a) mảng.
b) xâu đơn có và không có con trỏ cuối (2 hàm khác nhau).
c) xâu đơn có Header node + có và không có con trỏ cuối (2 hàm khác nhau).
d) xâu đơn có Header node chứa địa chỉ node cuối trong các byte đầu của trường dữ liệu.
 108

BT#10: So sánh Stack và Queue

BT#11: Viết hàm tạo 2 mảng Index (sắp theo thứ tự tang) trên 2 khóa khác nhau với 1 danh
sách đang lưu ở

a) mảng.

b) xâu.

BT#12: Chỉ ra 1 ví dụ cụ thể cần áp dụng cấu trúc danh sách đa liên kết. Khai báo và viết
hàm xuất danh sách tương ứng.
 109

BT03.a: So sánh ưu khuyết điểm của thao tác Thêm 1 phần tử trên xâu đơn & mảng

* Các ưu khuyết điểm chung

XÂU ĐƠN MẢNG TĨNH MẢNG ĐỘNG

Khả năng thành Không đảm bảo nhưng khá hơn

Chắc chắn Không đảm bảo
công mảng tĩnh (1)
Tốc độ Rất nhanh (2a) Thường sẽ lâu (2b)

Độ phức tạp Cao: có nhiều tr/h ứng Ko thấp: xử lý như mảng tĩnh,
Thấp: Có thể quy
với nhiều cách xử lý khác nhưng khi mảng đầy phải tái cấp
(khi code) về đúng 01 tr/h
nhau phát hơi rắc rối (3)

Dễ gặp (do sót các xử lý Không an toàn lắm vì phải có các

Khả năng xảy ra Khá an toàn, khả
cho những tr/h đặc biệt) thao tác cấp phát & giải phóng phù
sự cố (khi chạy) năng bị lỗi thấp.
(4a) hợp (4b)
Tầm quan trọng Cao Cao (5)
Độ phổ dụng Rất cao Cao
 110

* Các ưu khuyết điểm khi Thêm phần tử vào Đầu danh sách:

XÂU ĐƠN MẢNG TĨNH MẢNG ĐỘNG

Rất nhanh – là tr/h Khá chậm –vì phải dồn Thường chậm hơn hẳn mảng tĩnh
Tốc độ
nhanh nhất toàn bộ phần tử ra sau vì kích thước lớn hơn hẳn

Độ phức tạp Ko đơn giản, phải có xử Hơi phức tạp, nếu phải có thêm
Khá đơn giản
(khi code) lý dồn các phần tử thao tác tái cấp phát khi mảng đầy

Mức độ sử Khá thường xuyên, vì

Không hay dùng Ít dùng
dụng đơn giản & nhanh

Ưu khuyết điểm khi Thêm phần tử vào Cuối danh sách:

XÂU ĐƠN MẢNG TĨNH MẢNG ĐỘNG

Rất nhanh – là tr/h

Không nhanh (do phải Rất nhanh – là tr/h nhanh nhất,
Tốc độ nhanh nhất, ko phải
duyệt từ đầu đến cuối xâu) ko phải dồn mảng
dồn mảng
Độ phức tạp Không đơn giản lắm, phải Rất đơn giản, nếu không gặp
Rất đơn giản
(khi code) xét tr/h đặc biệt tr/h mảng đầy
Mức độ sử Ko thấp (nếu nhiều thì nên
Cao Khá cao
dụng có thêm 1 con trỏ cuối)
 111

Ưu khuyết điểm khi Thêm phần tử vào Sau 1 phần tử trong DS: (ko phải phần tử cuối)
XÂU ĐƠN MẢNG TĨNH MẢNG ĐỘNG

Phải duyệt tìm phần tử Không nhanh do phải Thường chậm hơn mảng
Tốc độ
nhưng cũng khá nhanh dồn mảng tĩnh vì kích thước lớn hơn
Không đơn giản, phải xét Như mảng tĩnh, phức tạp
Độ phức tạp Không phức tạp
các tr/h đặc biệt hơn khi phải tái cấp phát.
Mức độ sử dụng Cao Không cao Không cao

Ưu khuyết điểm khi Thêm phần tử vào Sau 1 phần tử trong DS: (ko phải phần tử cuối)
XÂU ĐƠN MẢNG TĨNH MẢNG ĐỘNG
Phải duyệt tìm phần tử kế Không nhanh do phải Thường chậm hơn mảng
Tốc độ
trước nhưng vẫn nhanh dồn mảng tĩnh vì kích thước lớn hơn
Không đơn giản, phải xét Như mảng tĩnh, phức tạp
Độ phức tạp Không phức tạp
các tr/h đặc biệt hơn khi phải tái cấp phát.
Mức độ sử dụng Thấp Cao Không cao

Ưu khuyết điểm khi Thêm phần tử vào danh sách có thứ tự:
Đây là thao tác tổng hợp – tùy theo giá trị phần tử mà vị trí thêm sẽ là vào đầu, vào cuối, hay
vào sau 1 phần tử; ở mức bình thường thì tr/h hay xảy ra sẽ là thêm vào sau 1 phần tử. Nhìn
chung là tốc độ chạy trên xâu sẽ nhanh hơn hẳn nhưng việc code sẽ hơi phức tạp hơn.
 112

Ghi chú:
(1): Với mảng tĩnh thì ko thể thêm được khi số phần tử của mảng đã bằng với số phần tử tối đa
được khai báo, còn mảng động trong tr/h này phải tái cấp phát và có thể ko còn đủ bộ nhớ để
cấp – nếu đủ thì việc cấp và chép lại mảng sang vị trí mới cũng mất nhiều thời gian. Tr/h khi cấp
phát mảng động có dự phòng cấp dư 1 số phần tử thì thường sẽ thành công.
(2a): Do chỉ phải cập nhật 2 con trỏ + duyệt 1 phần của xâu (số byte phải làm việc khá nhỏ).
(2b): Vì thường phải thực hiện thao tác chép dồn 1 phần mảng và phải làm việc với nhiều byte
hơn (số byte phải làm việc = <kích thước phần tử>*<số phần tử phải dồn> có thể rất lớn)
(3): Cụ thể tr/h thêm vào đầu chính là thêm ở vị trí 0, thêm vào cuối là thêm ở vị trí N (với mảng
có N phần tử), thêm vào sau phần tử K là thêm ở vị trí K+1, thêm vào trước phần tử K là thêm ở
vị trí K-1; và tất cả các tr/h trên đều quy về thao tác thêm phần tử vào vị trí M trên mảng.
(4): Các tr/h đặc biệt chủ yếu là xâu rỗng, thêm vào trước /sau 1 phần tử mà phần tử này là đầu
/cuối xâu & quên cập nhật lại con trỏ đầu /cuối xâu,…
(5): Là thao tác có tính điển hình, có độ quan trọng cao & thường hay gặp trên DS (mà khi nắm
được thì có thể hiểu về cấu trúc và làm được nhiều xử lý khác nhau). Nếu ko thực hiện được thao tác
thêm vào DS thì cũng sẽ không tồn tại DS các phần tử để mà CT có thể xử lý (tức CT ko thể chạy)
End!