Data Structures & Algorithms - Lecture 3
1mohamedgamal54
86 views
106 slides
Sep 09, 2024
Slide 1 of 106
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
About This Presentation
Data Structures and Algorithms using C++ programming language.
Slide Content
Data Structures and
Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024
C++
Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024
C++
The topics of today’s lecture:
Agenda
Agenda
The List ADT
–A list is a sequence of elements, A
0, A
1, A
2, …,A
n−1, with size n.
–An empty list has size 0.
–In a non-empty list, A
i follows A
??????−1?????? <?????? and A
??????−1 precedes A
?????? (?????? > 0).
–The first element is A
0, and the last is A
n−1.
–Elements are typically integers but can be of any type.
0 1 2 3 4 5 6
List
–A list is a sequence of elements, A
0, A
1, A
2, …,A
n−1, with size n.
–An empty list has size 0.
–In a non-empty list, A
i follows A
??????−1?????? <?????? and A
??????−1 precedes A
?????? (?????? > 0).
–The first element is A
0, and the last is A
n−1.
–Elements are typically integers but can be of any type.
0 1 2 3 4 5 6
List
Operation Description
printList() Prints the list.
makeEmpty() Empties the list.
find(x) Returns the position of the first occurrence of x.
insert(x, i) Inserts x at position i.
remove(x) Removes the first occurrence of x.
findKth(i) Returns the element at position i.
next(i) Returns the position of the successor of the element at position i.
previous(i) Returns the position of the predecessor of the element at position i.
printList() Prints the list.
makeEmpty() Empties the list.
find(x) Returns the position of the first occurrence of x.
insert(x, i) Inserts x at position i.
remove(x) Removes the first occurrence of x.
findKth(i) Returns the element at position i.
next(i) Returns the position of the successor of the element at position i.
previous(i) Returns the position of the predecessor of the element at position i.
Implementation: Lists can be implemented using arrays, which can dynamically grow using a vector-like
approach to overcome fixed capacity limits.
Operations:
•printList: executes in linear time.
•findKth: executes in constant time.
•Insertion and Deletion: expensive if done at the front or middle, requiring O(n) time due to
shifting elements. In the worst case, inserting or deleting at the front requires shifting the entire
array – O(n).
•High End Operations: If operations occur at the end of the list, insertion and deletion are O(1).
Suitability:
•Suitable for lists with frequent high-end insertions and random access.
•Not suitable for lists with frequent insertions and deletions at the front or middle.
Alternative: Linked lists are a better option for frequent insertions and deletions throughout the list.
Simple Array Implementation of Lists
approach to overcome fixed capacity limits.
Operations:
•printList: executes in linear time.
•findKth: executes in constant time.
•Insertion and Deletion: expensive if done at the front or middle, requiring O(n) time due to
shifting elements. In the worst case, inserting or deleting at the front requires shifting the entire
array – O(n).
•High End Operations: If operations occur at the end of the list, insertion and deletion are O(1).
Suitability:
•Suitable for lists with frequent high-end insertions and random access.
•Not suitable for lists with frequent insertions and deletions at the front or middle.
Alternative: Linked lists are a better option for frequent insertions and deletions throughout the list.
Simple Array Implementation of Lists
const int n = 7;
intarr[n] = { 1, 2, 3, 4, 5, 7, 7 };
1 2 3 4 5 6 7
0 1 2 3 4 5 6
List
const int n = 7;
int *arr = new int[n]; // allocate memory
for(inti = 0; i < n; i++)
arr[i] = i + 1;
delete[] arr; // free memory
intarr[n] = { 1, 2, 3, 4, 5, 7, 7 };
1 2 3 4 5 6 7
0 1 2 3 4 5 6
List
const int n = 7;
int *arr = new int[n]; // allocate memory
for(inti = 0; i < n; i++)
arr[i] = i + 1;
delete[] arr; // free memory
#include <iostream>
using namespace std;
class ArrayList
{
private:
int *arr;
int capacity;
int size;
// Helper function to resize the array when needed
void resize()
{
capacity *= 2;
int *newArr = new int[capacity];
for(inti = 0; i < size; i++) {
newArr[i] = arr[i];
}
delete[] arr;
arr = newArr;
delete[] newArr;
}
public:
// Constructor
ArrayList(int cap = 10)
{
capacity = cap;
size = 0;
arr = new int[capacity];
}
// Destructor
~ArrayList() {
delete[] arr; // free memory
}
// Print the list
void printList() {
for(inti = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Find the element at the kth position
int findKth(int k) {
if (k < 0 || k >= size) {
throw out_of_range("Index out of range");
}
return arr[k];
}
// Insert an element at the specified position
voidinsert(intelement, intposition) {
if (position < 0 || position > size) {
throw out_of_range("Index out of range");
}
if (size == capacity) { // If the array is full, resize it
resize();
}
// Shift elements to the right
for (int i = size; i > position; i--) {
arr[i] = arr[i - 1];
}
arr[position] = element;
size++;
}
// Check if the list is empty
bool isEmpty() {
return size == 0;
}
// Remove the first occurrence of the specified element
void remove(int element) {
int position = -1;
for(inti = 0; i < size; i++) {
if (arr[i] == element) {
position = i;
break;
}
}
if (position == -1) {
cout << "Element not found" << endl;
return;
}
for (int i = position; i < size - 1; i++) {
arr[i] = arr[i + 1];
}
size--;
}
};
int main()
{
ArrayList list; // { 34, 12, 52, 16, 12, 7 }
list.insert(34, 0);
list.insert(12, 1);
list.insert(52, 2);
list.insert(16, 3);
list.insert(12, 4);
list.insert(7, 5);
cout << "List after insertion: ";
list.printList();
cout << "Element at position 2: " << list.findKth(2) << endl;
list.remove(52);
cout << "List after removing 52: " ;
list.printList();
return 0;
}
Array List
C++
implementation
using namespace std;
class ArrayList
{
private:
int *arr;
int capacity;
int size;
// Helper function to resize the array when needed
void resize()
{
capacity *= 2;
int *newArr = new int[capacity];
for(inti = 0; i < size; i++) {
newArr[i] = arr[i];
}
delete[] arr;
arr = newArr;
delete[] newArr;
}
public:
// Constructor
ArrayList(int cap = 10)
{
capacity = cap;
size = 0;
arr = new int[capacity];
}
// Destructor
~ArrayList() {
delete[] arr; // free memory
}
// Print the list
void printList() {
for(inti = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Find the element at the kth position
int findKth(int k) {
if (k < 0 || k >= size) {
throw out_of_range("Index out of range");
}
return arr[k];
}
// Insert an element at the specified position
voidinsert(intelement, intposition) {
if (position < 0 || position > size) {
throw out_of_range("Index out of range");
}
if (size == capacity) { // If the array is full, resize it
resize();
}
// Shift elements to the right
for (int i = size; i > position; i--) {
arr[i] = arr[i - 1];
}
arr[position] = element;
size++;
}
// Check if the list is empty
bool isEmpty() {
return size == 0;
}
// Remove the first occurrence of the specified element
void remove(int element) {
int position = -1;
for(inti = 0; i < size; i++) {
if (arr[i] == element) {
position = i;
break;
}
}
if (position == -1) {
cout << "Element not found" << endl;
return;
}
for (int i = position; i < size - 1; i++) {
arr[i] = arr[i + 1];
}
size--;
}
};
int main()
{
ArrayList list; // { 34, 12, 52, 16, 12, 7 }
list.insert(34, 0);
list.insert(12, 1);
list.insert(52, 2);
list.insert(16, 3);
list.insert(12, 4);
list.insert(7, 5);
cout << "List after insertion: ";
list.printList();
cout << "Element at position 2: " << list.findKth(2) << endl;
list.remove(52);
cout << "List after removing 52: " ;
list.printList();
return 0;
}
Array List
C++
implementation
Linked Lists
–Linked Lists are used to create arrays of unknown (dynamic) size in memory.
– Linked lists can be maintained in sorted order by inserting or deleting an element at the proper
position in the list.
–To avoid the linear cost of insertion and deletion in arrays, linked lists are used.
–A linked list consists of nodes, each containing an element and a link (next pointer) to the next
node.
–The last node's next pointer is nullptr.
Head
Tail
NULL
–Linked Lists are used to create arrays of unknown (dynamic) size in memory.
– Linked lists can be maintained in sorted order by inserting or deleting an element at the proper
position in the list.
–To avoid the linear cost of insertion and deletion in arrays, linked lists are used.
–A linked list consists of nodes, each containing an element and a link (next pointer) to the next
node.
–The last node's next pointer is nullptr.
Head
Tail
NULL
Operation Description
List initialize head and tail to Null (Constructor).
~List destroy all nodes of the list (destructor).
isEmpty determine whether or not the list is empty.
addToHead insert a new node at the front of the list.
addToTail insert a new node at the end of the list.
addNode insert a new node at a particular position.
findNode find a node with a given value.
DeleteNode delete a node with a given value.
List initialize head and tail to Null (Constructor).
~List destroy all nodes of the list (destructor).
isEmpty determine whether or not the list is empty.
addToHead insert a new node at the front of the list.
addToTail insert a new node at the end of the list.
addNode insert a new node at a particular position.
findNode find a node with a given value.
DeleteNode delete a node with a given value.
Operation Description
deleteFromHead delete the first node from the list.
deleteFromTail delete the last node from the list.
printList print all the nodes in the list.
countList print the number of nodes in the list.
deleteFromHead delete the first node from the list.
deleteFromTail delete the last node from the list.
printList print all the nodes in the list.
countList print the number of nodes in the list.
A Linked List:
Deletion from a linked list:
Insertion into a linked list:
Head
Tail
Head
Tail
Head
Tail
Deletion from a linked list:
Insertion into a linked list:
Head
Tail
Head
Tail
Head
Tail
5 7 3 12 1
NULL
Tail
Head
value
NULL
newNode
NULL
Tail
Head
value
NULL
newNode
5 7 3 12 1
NULL
Tail
Head
value
NULL
newNode
NULL
Tail
Head
value
NULL
newNode
5 7 3 12 1
NULL
Tail
Head
value
NULL
newNode
Position 1 Position 2 Position 3 Position 4 Position 5
Current
NULL
Tail
Head
value
NULL
newNode
Position 1 Position 2 Position 3 Position 4 Position 5
Current
5 7 3 12 1
NULL
Tail
Head
Current
data next data next data next data next data next
NULL
Tail
Head
Current
data next data next data next data next data next
5 7 3 12 1
NULL
Tail
Head
Temp
NULL
Tail
Head
Temp
5 7 3 12 1
NULL
Tail
Head
Current
Tail
NULL
NULL
Tail
Head
Current
Tail
NULL
5 7 3 12 1
NULL
Tail
Head
Current
Tail
Previous
NULL
CurrentPrevious
NULL
Tail
Head
Current
Tail
Previous
NULL
CurrentPrevious
# in cl u de < io str eam >
u si ng n am esp ace s td ;
/ / No d e c la ss fo r i ndi vi dua l e le men ts o f t h e lin ke d l ist
c la ss N od e {
p ub lic:
i nt d at a;
N od e* n ext ;
/ / Con str uc tor (C to r)
N od e(i nt v al ue) {
d at a = v al ue;
n ex t = n ul lpt r;
}
};
/ / Li n ke d l ist c la s s
c la ss L in ked Lis t {
p ri vat e:
N od e* h ead ;
N od e* t ail ;
p ub lic:
/ / Con str uc tor
L in ked Lis t( ) {
h ea d = n ul lpt r;
t ai l = n ul lpt r;
}
/ / Des tru ct or
~ Li nke dLi st () {
N od e* c urr ent = h e ad ;
w hi le ( cu rre nt) {
N od e* n ex t = cu rre nt-> ne xt ;
d el ete c ur ren t;
c ur ren t = n ex t ;
}
h ea d = n ul lpt r;
t ai l = n ul lpt r;
}
/ / Che ck if th e lis t i s emp ty
b oo l i sE mp t y( ) {
r et urn h ea d = = n ul lp t r;
}
/ / Add to t he he ad of th e l ist
v oi d a dd To H ead(i nt v al ue) {
N od e* n ew Nod e = n ew N od e(v al ue);
if (i sE mpt y( )) {
h ea d = n ew Nod e;
t ai l = n ew Nod e;
}
e ls e {
n ew Nod e-> ne xt = h ea d;
h ea d = n ew Nod e;
}
}
/ / Add to t ail o f t he li st
v oi d a dd To T ail(i nt v al ue) {
N od e* n ew Nod e = n ew N od e(v al ue);
if (i sE mpt y( )) {
h ea d = n ew Nod e;
t ai l = n ew Nod e;
}
e ls e {
t ai l-> ne xt = n ew Nod e;
t ai l = n ew Nod e;
}
}
/ / Add no de at a sp ec i fi c p osi ti on (1-b as ed ind ex )
v oi d a dd No d e(i nt v al ue, i nt p os iti on) {
if (p os iti on < = 0) {
c er r << " Po si t io n m ust b e p osi ti ve. " << e nd l;
r et urn;
}
N od e* n ew Nod e = n ew N od e(v al ue);
if (p os iti on = = 1) {
a dd ToH ead(v al ue);
}
e ls e { / / po s iti on 3
N od e* c ur r ent = he ad ;
i nt c ur re n tPo si tio n = 1 ;
w hi le (c ur ren tPo si ti o n < p os it i on - 1 & & c ur r en t) {
c ur re n t = c urr en t-> ne xt;
c ur re n tPo si tio n+ +;
}
if ( cu rre nt) {
n ew No d e-> ne xt = c ur ren t-> ne xt ;
c ur re n t-> ne xt = n ew Nod e;
if ( cu rre nt == t a il ) {
t ai l = n ew No d e;
}
}
e ls e {
c er r << " Po sit io n e xce ed s t he nu mbe r o f ele me nts ." << e nd l;
}
}
}
/ / Fin d n od e w it h a g i ve n v alu e
N od e* f in dNo de(i nt v al ue) {
N od e* c urr ent = h e ad ;
w hi le ( cu rre nt && cu rr en t-> da ta != v al ue) {
c ur ren t = c ur r en t-> ne xt ;
}
r et urn c ur ren t;
}
/ / Del ete n ode f rom h e ad
v oi d d el et e Fro mH ead( ) {
if (!i sE mp t y( )) {
N od e* t em p = he ad;
h ea d = he ad-> ne xt;
d el ete t em p;
/ / If lis t is em pty af te r d ele ti on
if ( !h ead ) {
t ai l = n ul lp t r;
}
}
e ls e {
c er r << " Li st is em pty ." << e nd l;
}
}
/ / Del ete n ode f rom t a il
v oi d d el et e Fro mT ail( ) {
if (!i sE mp t y( )) {
/ / If onl y on e n ode in t he lis t
if ( he ad == ta il ) {
d el et e h ea d;
h ea d = n ul lp t r;
t ai l = n ul lp t r;
}
e ls e {
N od e* c ur r en t = he ad ;
w hi le ( cu rre nt-> ne xt != ta il) {
c ur re n t = c urr en t-> ne xt;
}
d el et e t ai l;
t ai l = cu rr ent ;
t ai l-> ne xt = n ul lpt r;
}
}
e ls e {
c er r << " Li st is em pty ." << e nd l;
}
}
/ / Del ete n ode w ith a gi ven va lu e
v oi d d el et e Nod e(i nt v al ue) {
N od e* c urr ent = h e ad ;
N od e* p rev iou s = n ul lpt r;
w hi le ( cu rre nt && cu rr en t-> da ta != v al ue) {
p re vio us = cu r re nt;
c ur ren t = c ur r en t-> ne xt ;
}
if ( cu rre nt) {
if ( cu rre nt == h e ad ) {
d el et e Fro mH ead( );
}
e ls e if ( cu rr e nt == ta il ) {
d el et e Fro mT ail( );
}
e ls e {
p re vi o us-> ne xt = c ur re n t-> ne xt;
d el et e c ur re n t;
}
}
e ls e {
c er r << " No de wi t h val ue " << v al ue << " n ot fo u nd ." << e nd l;
}
}
/ / Pri nt al l n od es in th e l ist
v oi d p ri nt L ist( ) {
N od e* c urr ent = h e ad ;
w hi le ( cu rre nt) {
c ou t << c ur re n t-> da ta << " ";
c ur ren t = c ur r en t-> ne xt ;
}
c ou t << e nd l;
}
/ / Cou nt nu mbe r of no d es in th e li s t
i nt c ou ntL ist( ) {
i nt c ou nt = 0 ;
N od e* c urr ent = h e ad ;
w hi le ( cu rre nt) {
c ou nt+ +;
c ur ren t = c ur r en t-> ne xt ;
}
r et urn c ou nt;
}
};
i nt m ai n()
{
L in ked Li s t m yL ist;
m yL ist .a d dT oTa il( 10 );
m yL ist .a d dT oTa il( 20 );
m yL ist .a d dT oTa il( 30 );
m yL ist .a d dT oHe ad( 5) ;
c ou t << " Li st: ";
m yL ist .p r in tLi st( );
c ou t << " Nu mbe r o f no d es : " << m yL ist .co un tLi st( ) << e nd l;
m yL ist .a d dN ode( 15 , 3 );
m yL ist .d e le teN od e( 20 );
c ou t << " Li st aft er a d di ng 15 at po sit io n 3 a nd del et ing 2 0: ";
m yL ist .p r in tLi st( );
c ou t << " Nu mbe r o f no d es af ter o per ati on s: " << m yL ist .c o un tLi st( ) << e nd l;
N od e* f ou nd N od e = m yL ist .fi nd Nod e( 10 );
if (f ou ndN ode)
c ou t << " No de wit h va l ue " << f ou ndN od e-> da ta << " f oun d." << e nd l;
e ls e
c ou t << " No de wit h va l ue 15 no t fo u nd. " << e nd l;
r et urn 0;
}
Singly Linked List
C++
implementation
u si ng n am esp ace s td ;
/ / No d e c la ss fo r i ndi vi dua l e le men ts o f t h e lin ke d l ist
c la ss N od e {
p ub lic:
i nt d at a;
N od e* n ext ;
/ / Con str uc tor (C to r)
N od e(i nt v al ue) {
d at a = v al ue;
n ex t = n ul lpt r;
}
};
/ / Li n ke d l ist c la s s
c la ss L in ked Lis t {
p ri vat e:
N od e* h ead ;
N od e* t ail ;
p ub lic:
/ / Con str uc tor
L in ked Lis t( ) {
h ea d = n ul lpt r;
t ai l = n ul lpt r;
}
/ / Des tru ct or
~ Li nke dLi st () {
N od e* c urr ent = h e ad ;
w hi le ( cu rre nt) {
N od e* n ex t = cu rre nt-> ne xt ;
d el ete c ur ren t;
c ur ren t = n ex t ;
}
h ea d = n ul lpt r;
t ai l = n ul lpt r;
}
/ / Che ck if th e lis t i s emp ty
b oo l i sE mp t y( ) {
r et urn h ea d = = n ul lp t r;
}
/ / Add to t he he ad of th e l ist
v oi d a dd To H ead(i nt v al ue) {
N od e* n ew Nod e = n ew N od e(v al ue);
if (i sE mpt y( )) {
h ea d = n ew Nod e;
t ai l = n ew Nod e;
}
e ls e {
n ew Nod e-> ne xt = h ea d;
h ea d = n ew Nod e;
}
}
/ / Add to t ail o f t he li st
v oi d a dd To T ail(i nt v al ue) {
N od e* n ew Nod e = n ew N od e(v al ue);
if (i sE mpt y( )) {
h ea d = n ew Nod e;
t ai l = n ew Nod e;
}
e ls e {
t ai l-> ne xt = n ew Nod e;
t ai l = n ew Nod e;
}
}
/ / Add no de at a sp ec i fi c p osi ti on (1-b as ed ind ex )
v oi d a dd No d e(i nt v al ue, i nt p os iti on) {
if (p os iti on < = 0) {
c er r << " Po si t io n m ust b e p osi ti ve. " << e nd l;
r et urn;
}
N od e* n ew Nod e = n ew N od e(v al ue);
if (p os iti on = = 1) {
a dd ToH ead(v al ue);
}
e ls e { / / po s iti on 3
N od e* c ur r ent = he ad ;
i nt c ur re n tPo si tio n = 1 ;
w hi le (c ur ren tPo si ti o n < p os it i on - 1 & & c ur r en t) {
c ur re n t = c urr en t-> ne xt;
c ur re n tPo si tio n+ +;
}
if ( cu rre nt) {
n ew No d e-> ne xt = c ur ren t-> ne xt ;
c ur re n t-> ne xt = n ew Nod e;
if ( cu rre nt == t a il ) {
t ai l = n ew No d e;
}
}
e ls e {
c er r << " Po sit io n e xce ed s t he nu mbe r o f ele me nts ." << e nd l;
}
}
}
/ / Fin d n od e w it h a g i ve n v alu e
N od e* f in dNo de(i nt v al ue) {
N od e* c urr ent = h e ad ;
w hi le ( cu rre nt && cu rr en t-> da ta != v al ue) {
c ur ren t = c ur r en t-> ne xt ;
}
r et urn c ur ren t;
}
/ / Del ete n ode f rom h e ad
v oi d d el et e Fro mH ead( ) {
if (!i sE mp t y( )) {
N od e* t em p = he ad;
h ea d = he ad-> ne xt;
d el ete t em p;
/ / If lis t is em pty af te r d ele ti on
if ( !h ead ) {
t ai l = n ul lp t r;
}
}
e ls e {
c er r << " Li st is em pty ." << e nd l;
}
}
/ / Del ete n ode f rom t a il
v oi d d el et e Fro mT ail( ) {
if (!i sE mp t y( )) {
/ / If onl y on e n ode in t he lis t
if ( he ad == ta il ) {
d el et e h ea d;
h ea d = n ul lp t r;
t ai l = n ul lp t r;
}
e ls e {
N od e* c ur r en t = he ad ;
w hi le ( cu rre nt-> ne xt != ta il) {
c ur re n t = c urr en t-> ne xt;
}
d el et e t ai l;
t ai l = cu rr ent ;
t ai l-> ne xt = n ul lpt r;
}
}
e ls e {
c er r << " Li st is em pty ." << e nd l;
}
}
/ / Del ete n ode w ith a gi ven va lu e
v oi d d el et e Nod e(i nt v al ue) {
N od e* c urr ent = h e ad ;
N od e* p rev iou s = n ul lpt r;
w hi le ( cu rre nt && cu rr en t-> da ta != v al ue) {
p re vio us = cu r re nt;
c ur ren t = c ur r en t-> ne xt ;
}
if ( cu rre nt) {
if ( cu rre nt == h e ad ) {
d el et e Fro mH ead( );
}
e ls e if ( cu rr e nt == ta il ) {
d el et e Fro mT ail( );
}
e ls e {
p re vi o us-> ne xt = c ur re n t-> ne xt;
d el et e c ur re n t;
}
}
e ls e {
c er r << " No de wi t h val ue " << v al ue << " n ot fo u nd ." << e nd l;
}
}
/ / Pri nt al l n od es in th e l ist
v oi d p ri nt L ist( ) {
N od e* c urr ent = h e ad ;
w hi le ( cu rre nt) {
c ou t << c ur re n t-> da ta << " ";
c ur ren t = c ur r en t-> ne xt ;
}
c ou t << e nd l;
}
/ / Cou nt nu mbe r of no d es in th e li s t
i nt c ou ntL ist( ) {
i nt c ou nt = 0 ;
N od e* c urr ent = h e ad ;
w hi le ( cu rre nt) {
c ou nt+ +;
c ur ren t = c ur r en t-> ne xt ;
}
r et urn c ou nt;
}
};
i nt m ai n()
{
L in ked Li s t m yL ist;
m yL ist .a d dT oTa il( 10 );
m yL ist .a d dT oTa il( 20 );
m yL ist .a d dT oTa il( 30 );
m yL ist .a d dT oHe ad( 5) ;
c ou t << " Li st: ";
m yL ist .p r in tLi st( );
c ou t << " Nu mbe r o f no d es : " << m yL ist .co un tLi st( ) << e nd l;
m yL ist .a d dN ode( 15 , 3 );
m yL ist .d e le teN od e( 20 );
c ou t << " Li st aft er a d di ng 15 at po sit io n 3 a nd del et ing 2 0: ";
m yL ist .p r in tLi st( );
c ou t << " Nu mbe r o f no d es af ter o per ati on s: " << m yL ist .c o un tLi st( ) << e nd l;
N od e* f ou nd N od e = m yL ist .fi nd Nod e( 10 );
if (f ou ndN ode)
c ou t << " No de wit h va l ue " << f ou ndN od e-> da ta << " f oun d." << e nd l;
e ls e
c ou t << " No de wit h va l ue 15 no t fo u nd. " << e nd l;
r et urn 0;
}
Singly Linked List
C++
implementation
Variations of Linked Lists
1)Singly Linked List
–it’s difficult to go back and move through the list.
2)Doubly Linked List
–The list can be traversed in both directions, making sorting easier.
–Since the entire list can be accessed using either a forward link or a backward link, if one link fails, the list
can be rebuilt using the other link. This is particularly useful in case of equipment failure.
3)Circular Linked List
NULLA
0 A
1 A
2 A
3
NULLHead
A
0
Head A
1 A
2 A
3
NULL
Tail
A
0
Head A
1 A
2 A
3
Tail
1)Singly Linked List
–it’s difficult to go back and move through the list.
2)Doubly Linked List
–The list can be traversed in both directions, making sorting easier.
–Since the entire list can be accessed using either a forward link or a backward link, if one link fails, the list
can be rebuilt using the other link. This is particularly useful in case of equipment failure.
3)Circular Linked List
NULLA
0 A
1 A
2 A
3
NULLHead
A
0
Head A
1 A
2 A
3
NULL
Tail
A
0
Head A
1 A
2 A
3
Tail
# in cl u de <i ost re am >
u si ng na m es pac e st d ;
/ / No d e c la ss fo r i ndi vi dua l e le men ts o f t h e dou bl y l ink ed l i st
c la ss No d e
{
p ub li c :
i nt da ta ;
N od e* p re v;
N od e* ne x t;
N od e(i nt va lue ) {
d at a = va lu e;
p re v = n ul lpt r;
n ex t = n ul lpt r;
}
};
/ / Do u bl y l ink ed l i st cl ass
c la ss D ou bly Lin ke dLi st
{
p ri va t e:
N od e* he a d;
N od e* ta i l;
p ub li c :
/ / Con st r uc tor
D ou bly Li n ke dLi st( ) {
h ea d = n ul lpt r;
t ai l = n ul lpt r;
}
/ / Des tr u ct or
~D ou bly Lin ke dL i st( ) {
N od e* cur re nt = hea d;
w hi le (cu rr ent ) {
N od e* nex t = c ur ren t-> ne xt;
d el ete cu rr en t ;
c ur ren t = n ex t ;
}
h ea d = n ul lpt r;
t ai l = n ul lpt r;
}
/ / Che ck if th e li s t i s emp ty
b oo l i sE mpt y( ) {
r et urn he ad == n ul lpt r;
}
/ / Add t o h ead o f t he li st
v oi d a dd ToH ead( in t v alu e) {
N od e* n ew Nod e = n ew Nod e( val ue );
i f (i sE mpt y( )) {
h ea d = n ew Nod e;
t ai l = n ew Nod e;
}
e ls e {
n ew Nod e-> ne xt = h ea d;
h ea d->p re v = n ew Nod e;
h ea d = n ew Nod e;
}
}
/ / Add t o t ail o f t he li st
v oi d a dd ToT ail( in t v alu e) {
N od e* n ew Nod e = n ew Nod e( val ue );
i f (i sE mpt y( )) {
h ea d = n ew Nod e;
t ai l = n ew Nod e;
}
e ls e {
n ew Nod e->p re v = t ail ;
t ai l-> ne xt = n ew Nod e;
t ai l = n ew Nod e;
}
}
/ / Add n o de at a s p ec i fi c p osi ti on (1-b as ed ind ex )
v oi d a dd Nod e( in t v alu e, i n t pos iti on ) {
i f (po sit io n < = 0) {
c er r < < "P o si t io n m us t b e p os iti ve . " << e nd l;
r et urn ;
}
N od e* n ew Nod e = n ew Nod e( val ue );
i f (po sit io n = = 1) {
a dd ToH ead( va lue );
}
e ls e {
N od e* cur re nt = hea d;
i nt c ur ren tPo si ti o n = 1 ;
w hi le (c ur ren tPo si ti o n < p osi tio n - 1 & & c ur r en t) {
c ur ren t = c ur r en t-> ne xt ;
c ur ren tPo si ti o n+ +;
}
i f (cu rre nt ) {
n ew Nod e-> ne xt = c ur ren t-> ne xt;
n ew Nod e->p re v = c urr ent ;
i f (cu rre nt-> ne xt) {
c ur re n t-> ne xt->p re v = n ew Nod e;
}
c ur ren t-> ne xt = n ew Nod e;
i f (cu rre nt = = t ail ) {
t ai l = n ew No d e;
}
}
e ls e {
c er r < < "Po si t io n e xc ee d s t he nu mbe r of el em e nt s ." << e nd l;
}
}
}
/ / Fin d n od e w it h g iv e n val ue
N od e* f in dN o de( in t v alu e) {
N od e* cur re nt = hea d;
w hi le (cu rr ent & & c ur r en t-> da ta != va lue ) {
c ur ren t = c ur r en t-> ne xt;
}
r et urn cu rr ent ;
}
/ / Del et e n ode w it h g i ve n v alu e
v oi d d el ete Nod e( in t v alu e) {
N od e* cur re nt = hea d;
w hi le (cu rr ent & & c ur r en t-> da ta != va lue ) {
c ur ren t = c ur r en t-> ne xt;
}
i f (cu rre nt ) {
i f (cu rre nt = = h ead ) {
d el ete Fro mH ea d( );
}
e ls e i f ( cu rr e nt == ta il ) {
d el ete Fro mT ai l( );
}
e ls e {
c ur ren t->p re v-> ne xt = c ur ren t-> ne xt;
i f (cu rre nt-> ne xt) {
c ur re n t-> ne xt->p re v = c urr ent->p re v;
}
d el ete cu rr en t ;
}
}
e ls e {
c er r < < "N o de wi th va lue " << va lu e < < " n ot fou nd ." << e nd l;
}
}
/ / Del et e n ode f ro m h e ad
v oi d d el ete Fro mH ea d( ) {
i f (!i sE mp t y( )) {
N od e* tem p = h ea d;
h ea d = he ad-> ne xt ;
i f (he ad) {
h ea d->p re v = n ul lpt r;
}
e ls e {
t ai l = n ul lpt r;
}
d el ete te mp ;
}
e ls e {
c er r < < "L i st is em pt y." << e nd l;
}
}
/ / Del et e n ode f ro m t a il
v oi d d el ete Fro mT ai l( ) {
i f (!i sE mp t y( )) {
i f (he ad == t a il ) {
d el ete he ad ;
h ea d = n ul lpt r;
t ai l = n ul lpt r;
}
e ls e {
N od e* tem p = t ai l;
t ai l = ta il->p re v;
t ai l-> ne xt = n ul lpt r;
d el ete te mp ;
}
}
e ls e {
c er r < < "L i st is em pt y." << e nd l;
}
}
/ / Pri nt al l n od es in th e l ist f rom h ead t o t ail
v oi d p ri ntL ist( ) {
N od e* cur re nt = hea d;
w hi le (cu rr ent ) {
c ou t < < cu r re n t-> da ta << " ";
c ur ren t = c ur r en t-> ne xt;
}
c ou t < < e nd l;
}
/ / Pri nt al l n od es in th e l ist f rom t ail t o h ead
v oi d p ri ntL ist Re ve r se( ) {
N od e* cur re nt = tai l;
w hi le (cu rr ent ) {
c ou t < < cu r re n t-> da ta << " ";
c ur ren t = c ur r en t->p re v;
}
c ou t < < e nd l;
}
/ / Cou nt nu mbe r of no d es in th e lis t
i nt c ou ntL ist( ) {
i nt co unt = 0;
N od e* cur re nt = hea d;
w hi le (cu rr ent ) {
c ou nt+ +;
c ur ren t = c ur r en t-> ne xt;
}
r et urn co un t;
}
};
i nt m a in ( )
{
D ou bly Li n ke dLi st m yL ist;
m yL ist .a d dT oTa il( 10 );
m yL ist .a d dT oTa il( 20 );
m yL ist .a d dT oTa il( 30 );
m yL ist .a d dT oHe ad( 5) ;
c ou t < < "Li st (h ea d t o t ail ): ";
m yL ist .p r in tLi st( );
c ou t < < "Li st (t ai l t o h ead ): ";
m yL ist .p r in tLi st Re v er s e( );
c ou t < < "Nu mbe r of no des : " < < m yL ist .co un tLi st( ) << e nd l;
m yL ist .a d dN ode( 15 , 3 );
m yL ist .d e le teN od e( 20 );
c ou t < < "Li st af te r a ddi ng 15 at po si tio n 3 a nd de le t in g 2 0: ";
m yL ist .p r in tLi st( );
c ou t < < "Nu mbe r of no des af te r o per at ion s: " << m yL ist .c o un tLi st( ) << e nd l;
r et urn 0 ;
}
Doubly Linked List
C++
implementation
u si ng na m es pac e st d ;
/ / No d e c la ss fo r i ndi vi dua l e le men ts o f t h e dou bl y l ink ed l i st
c la ss No d e
{
p ub li c :
i nt da ta ;
N od e* p re v;
N od e* ne x t;
N od e(i nt va lue ) {
d at a = va lu e;
p re v = n ul lpt r;
n ex t = n ul lpt r;
}
};
/ / Do u bl y l ink ed l i st cl ass
c la ss D ou bly Lin ke dLi st
{
p ri va t e:
N od e* he a d;
N od e* ta i l;
p ub li c :
/ / Con st r uc tor
D ou bly Li n ke dLi st( ) {
h ea d = n ul lpt r;
t ai l = n ul lpt r;
}
/ / Des tr u ct or
~D ou bly Lin ke dL i st( ) {
N od e* cur re nt = hea d;
w hi le (cu rr ent ) {
N od e* nex t = c ur ren t-> ne xt;
d el ete cu rr en t ;
c ur ren t = n ex t ;
}
h ea d = n ul lpt r;
t ai l = n ul lpt r;
}
/ / Che ck if th e li s t i s emp ty
b oo l i sE mpt y( ) {
r et urn he ad == n ul lpt r;
}
/ / Add t o h ead o f t he li st
v oi d a dd ToH ead( in t v alu e) {
N od e* n ew Nod e = n ew Nod e( val ue );
i f (i sE mpt y( )) {
h ea d = n ew Nod e;
t ai l = n ew Nod e;
}
e ls e {
n ew Nod e-> ne xt = h ea d;
h ea d->p re v = n ew Nod e;
h ea d = n ew Nod e;
}
}
/ / Add t o t ail o f t he li st
v oi d a dd ToT ail( in t v alu e) {
N od e* n ew Nod e = n ew Nod e( val ue );
i f (i sE mpt y( )) {
h ea d = n ew Nod e;
t ai l = n ew Nod e;
}
e ls e {
n ew Nod e->p re v = t ail ;
t ai l-> ne xt = n ew Nod e;
t ai l = n ew Nod e;
}
}
/ / Add n o de at a s p ec i fi c p osi ti on (1-b as ed ind ex )
v oi d a dd Nod e( in t v alu e, i n t pos iti on ) {
i f (po sit io n < = 0) {
c er r < < "P o si t io n m us t b e p os iti ve . " << e nd l;
r et urn ;
}
N od e* n ew Nod e = n ew Nod e( val ue );
i f (po sit io n = = 1) {
a dd ToH ead( va lue );
}
e ls e {
N od e* cur re nt = hea d;
i nt c ur ren tPo si ti o n = 1 ;
w hi le (c ur ren tPo si ti o n < p osi tio n - 1 & & c ur r en t) {
c ur ren t = c ur r en t-> ne xt ;
c ur ren tPo si ti o n+ +;
}
i f (cu rre nt ) {
n ew Nod e-> ne xt = c ur ren t-> ne xt;
n ew Nod e->p re v = c urr ent ;
i f (cu rre nt-> ne xt) {
c ur re n t-> ne xt->p re v = n ew Nod e;
}
c ur ren t-> ne xt = n ew Nod e;
i f (cu rre nt = = t ail ) {
t ai l = n ew No d e;
}
}
e ls e {
c er r < < "Po si t io n e xc ee d s t he nu mbe r of el em e nt s ." << e nd l;
}
}
}
/ / Fin d n od e w it h g iv e n val ue
N od e* f in dN o de( in t v alu e) {
N od e* cur re nt = hea d;
w hi le (cu rr ent & & c ur r en t-> da ta != va lue ) {
c ur ren t = c ur r en t-> ne xt;
}
r et urn cu rr ent ;
}
/ / Del et e n ode w it h g i ve n v alu e
v oi d d el ete Nod e( in t v alu e) {
N od e* cur re nt = hea d;
w hi le (cu rr ent & & c ur r en t-> da ta != va lue ) {
c ur ren t = c ur r en t-> ne xt;
}
i f (cu rre nt ) {
i f (cu rre nt = = h ead ) {
d el ete Fro mH ea d( );
}
e ls e i f ( cu rr e nt == ta il ) {
d el ete Fro mT ai l( );
}
e ls e {
c ur ren t->p re v-> ne xt = c ur ren t-> ne xt;
i f (cu rre nt-> ne xt) {
c ur re n t-> ne xt->p re v = c urr ent->p re v;
}
d el ete cu rr en t ;
}
}
e ls e {
c er r < < "N o de wi th va lue " << va lu e < < " n ot fou nd ." << e nd l;
}
}
/ / Del et e n ode f ro m h e ad
v oi d d el ete Fro mH ea d( ) {
i f (!i sE mp t y( )) {
N od e* tem p = h ea d;
h ea d = he ad-> ne xt ;
i f (he ad) {
h ea d->p re v = n ul lpt r;
}
e ls e {
t ai l = n ul lpt r;
}
d el ete te mp ;
}
e ls e {
c er r < < "L i st is em pt y." << e nd l;
}
}
/ / Del et e n ode f ro m t a il
v oi d d el ete Fro mT ai l( ) {
i f (!i sE mp t y( )) {
i f (he ad == t a il ) {
d el ete he ad ;
h ea d = n ul lpt r;
t ai l = n ul lpt r;
}
e ls e {
N od e* tem p = t ai l;
t ai l = ta il->p re v;
t ai l-> ne xt = n ul lpt r;
d el ete te mp ;
}
}
e ls e {
c er r < < "L i st is em pt y." << e nd l;
}
}
/ / Pri nt al l n od es in th e l ist f rom h ead t o t ail
v oi d p ri ntL ist( ) {
N od e* cur re nt = hea d;
w hi le (cu rr ent ) {
c ou t < < cu r re n t-> da ta << " ";
c ur ren t = c ur r en t-> ne xt;
}
c ou t < < e nd l;
}
/ / Pri nt al l n od es in th e l ist f rom t ail t o h ead
v oi d p ri ntL ist Re ve r se( ) {
N od e* cur re nt = tai l;
w hi le (cu rr ent ) {
c ou t < < cu r re n t-> da ta << " ";
c ur ren t = c ur r en t->p re v;
}
c ou t < < e nd l;
}
/ / Cou nt nu mbe r of no d es in th e lis t
i nt c ou ntL ist( ) {
i nt co unt = 0;
N od e* cur re nt = hea d;
w hi le (cu rr ent ) {
c ou nt+ +;
c ur ren t = c ur r en t-> ne xt;
}
r et urn co un t;
}
};
i nt m a in ( )
{
D ou bly Li n ke dLi st m yL ist;
m yL ist .a d dT oTa il( 10 );
m yL ist .a d dT oTa il( 20 );
m yL ist .a d dT oTa il( 30 );
m yL ist .a d dT oHe ad( 5) ;
c ou t < < "Li st (h ea d t o t ail ): ";
m yL ist .p r in tLi st( );
c ou t < < "Li st (t ai l t o h ead ): ";
m yL ist .p r in tLi st Re v er s e( );
c ou t < < "Nu mbe r of no des : " < < m yL ist .co un tLi st( ) << e nd l;
m yL ist .a d dN ode( 15 , 3 );
m yL ist .d e le teN od e( 20 );
c ou t < < "Li st af te r a ddi ng 15 at po si tio n 3 a nd de le t in g 2 0: ";
m yL ist .p r in tLi st( );
c ou t < < "Nu mbe r of no des af te r o per at ion s: " << m yL ist .c o un tLi st( ) << e nd l;
r et urn 0 ;
}
Doubly Linked List
C++
implementation
# in cl u de < io str eam >
u si ng n am esp ace s td ;
/ / No d e c la ss fo r i ndi vi dua l e le men ts o f t h e cir cu lar li nk ed li s t
c la ss N od e
{
p ub lic:
i nt d at a;
N od e* n ext ;
N od e(i nt v al ue) {
d at a = v al ue;
n ex t = n ul lpt r;
}
};
/ / Ci r cu l ar li nk ed lis t cla ss
c la ss C ir cul arL in ked Li st
{
p ri vat e:
N od e* h ead ;
p ub lic:
/ / Con str uc tor
C ir cul arL in ked Li st( ) {
h ea d = n ul lpt r;
}
/ / Des tru ct or
~C ir cul arL in ke d Li st( ) {
if (!i sE mp t y( )) {
N od e* c ur r ent = he ad-> ne xt ;
w hi le ( cu rre nt != he ad ) {
N od e* t em p = cu rre nt ;
c ur re n t = c urr en t-> ne xt;
d el et e t em p;
}
d el ete h ea d;
}
h ea d = n ul lpt r;
}
/ / Che ck if th e lis t i s emp ty
b oo l i sE mp t y( ) {
r et urn h ea d = = n ul lp t r;
}
/ / Add to h ead o f t he li st
v oi d a dd To H ead(i nt v al ue) {
N od e* n ew Nod e = n ew N od e(v al ue);
if (i sE mpt y( )) {
h ea d = n ew Nod e;
h ea d-> ne xt = h ea d;
}
e ls e {
N od e* t em p = he ad;
w hi le ( te mp-> ne xt != he ad) {
t em p = te mp-> ne xt;
}
t em p-> ne xt = n ew Nod e;
n ew Nod e-> ne xt = h ea d;
h ea d = n ew Nod e;
}
}
/ / Add to t ail o f t he li st
v oi d a dd To T ail(i nt v al ue) {
N od e* n ew Nod e = n ew N od e(v al ue);
if (i sE mpt y( )) {
h ea d = n ew Nod e;
h ea d-> ne xt = h ea d;
}
e ls e {
N od e* t em p = he ad;
w hi le ( te mp-> ne xt != he ad) {
t em p = te mp-> ne xt;
}
t em p-> ne xt = n ew Nod e;
n ew Nod e-> ne xt = h ea d;
}
}
/ / Add no de at a sp ec i fi c p osi ti on (1-b as ed ind ex )
v oi d a dd No d e(i nt v al ue, i nt p os iti on) {
if (p os iti on < = 0) {
c er r << " Po si t io n m ust b e p osi ti ve. " << e nd l;
r et urn;
}
N od e* n ew Nod e = n ew N od e(v al ue);
if (p os iti on = = 1 | | i sE mpt y( )) {
a dd ToH ead(v al ue);
}
e ls e {
N od e* c ur r ent = he ad ;
i nt c ur re n tPo si tio n = 1 ;
w hi le (c ur ren tPo si ti o n < p os it i on - 1 & & c ur r en t-> ne xt != he ad) {
c ur re n t = c urr en t-> ne xt;
c ur re n tPo si tio n+ +;
}
n ew Nod e-> ne xt = c ur ren t-> ne xt;
c ur ren t-> ne xt = n ew Nod e;
}
}
/ / Fin d n od e w it h g iv e n val ue
N od e* f in dNo de(i nt v al ue) {
if (i sE mpt y( )) {
r et urn n ul lpt r;
}
N od e* c urr ent = h e ad ;
do {
if ( cu rre nt-> da ta == v al ue) {
r et ur n c ur re n t;
}
c ur ren t = c ur r en t-> ne xt ;
} w hi le ( cu rr e nt != he ad );
r et urn n ul lpt r;
}
/ / Del ete n ode w ith g i ve n v alu e
v oi d d el et e Nod e(i nt v al ue) {
if (i sE mpt y( )) {
c er r << " Li st is em pty ." << e nd l;
r et urn;
}
N od e* c urr ent = h e ad ;
N od e* p rev iou s = n ul lpt r;
/ / Tra ver se u n ti l t he no de wit h th e v alu e i s fou nd or ba ck to he ad
do {
if ( cu rre nt-> da ta == v al ue) {
b re ak;
}
p re vio us = cu r re nt;
c ur ren t = c ur r en t-> ne xt ;
} w hi le ( cu rr e nt != he ad );
/ / If fou nd , d el ete th e nod e
if ( cu rre nt == he ad ) {
/ / If hea d is th e o nly n od e
if ( cu rre nt-> ne xt == he ad) {
d el et e h ea d;
h ea d = n ul lp t r;
}
e ls e {
/ / Mo v e h ea d t o the ne xt n o de an d u pd ate th e las t nod e's n ex t po in ter
N od e* l as t = he ad;
w hi le ( la st-> ne xt != he ad) {
l as t = l a st-> ne xt;
}
l as t-> ne xt = h ea d-> ne xt;
d el et e h ea d;
h ea d = la st-> ne xt;
}
}
e ls e if ( cu rr e nt) {
/ / Del ete t he no de and u pd a te th e p re vio us no de ' s nex t p oi nte r
p re vio us-> ne xt = c ur ren t-> ne xt ;
d el ete c ur ren t;
}
e ls e {
c er r << " No de wi t h val ue " << v al ue << " n ot fo u nd ." << e nd l;
}
}
/ / Del ete n ode f rom h e ad
v oi d d el et e Fro mH ead( ) {
if (!i sE mp t y( )) {
N od e* t em p = he ad;
if ( he ad-> ne xt == he ad) {
h ea d = n ul lp t r;
}
e ls e {
N od e* l as t = he ad;
w hi le ( la st-> ne xt != he ad) {
l as t = l a st-> ne xt;
}
l as t-> ne xt = h ea d-> ne xt;
h ea d = he ad-> ne xt;
}
d el ete t em p;
}
e ls e {
c er r << " Li st is em pty ." << e nd l;
}
}
/ / Pri nt al l n od es in th e l ist
v oi d p ri nt L ist( ) {
if (i sE mpt y( )) {
c ou t << " Li st is em pty ." << e nd l;
r et urn;
}
N od e* c urr ent = h e ad ;
do {
c ou t << c ur re n t-> da ta << " ";
c ur ren t = c ur r en t-> ne xt ;
} w hi le ( cu rr e nt != he ad );
c ou t << e nd l;
}
/ / Cou nt nu mbe r of no d es in th e li s t
i nt c ou ntL ist( ) {
if (i sE mpt y( )) {
r et urn 0;
}
i nt c ou nt = 0 ;
N od e* c urr ent = h e ad ;
do {
c ou nt+ +;
c ur ren t = c ur r en t-> ne xt ;
} w hi le ( cu rr e nt != he ad );
r et urn c ou nt;
}
};
i nt m ai n()
{
C ir cul ar L in ked Li st m yL ist;
m yL ist .a d dT oTa il( 10 );
m yL ist .a d dT oTa il( 20 );
m yL ist .a d dT oTa il( 30 );
m yL ist .a d dT oHe ad( 5) ;
c ou t << " Li st: ";
m yL ist .p r in tLi st( );
c ou t << " Nu mbe r o f no d es : " << m yL ist .co un tLi st( ) << e nd l;
m yL ist .a d dN ode( 15 , 3 );
m yL ist .d e le teN od e( 20 );
c ou t << " Li st aft er a d di ng 15 at po sit io n 3 a nd del et ing 2 0: ";
m yL ist .p r in tLi st( );
c ou t << " Nu mbe r o f no d es af ter o per ati on s: " << m yL ist .c o un tLi st( ) << e nd l;
r et urn 0;
}
Circular Linked List
C++
implementation
u si ng n am esp ace s td ;
/ / No d e c la ss fo r i ndi vi dua l e le men ts o f t h e cir cu lar li nk ed li s t
c la ss N od e
{
p ub lic:
i nt d at a;
N od e* n ext ;
N od e(i nt v al ue) {
d at a = v al ue;
n ex t = n ul lpt r;
}
};
/ / Ci r cu l ar li nk ed lis t cla ss
c la ss C ir cul arL in ked Li st
{
p ri vat e:
N od e* h ead ;
p ub lic:
/ / Con str uc tor
C ir cul arL in ked Li st( ) {
h ea d = n ul lpt r;
}
/ / Des tru ct or
~C ir cul arL in ke d Li st( ) {
if (!i sE mp t y( )) {
N od e* c ur r ent = he ad-> ne xt ;
w hi le ( cu rre nt != he ad ) {
N od e* t em p = cu rre nt ;
c ur re n t = c urr en t-> ne xt;
d el et e t em p;
}
d el ete h ea d;
}
h ea d = n ul lpt r;
}
/ / Che ck if th e lis t i s emp ty
b oo l i sE mp t y( ) {
r et urn h ea d = = n ul lp t r;
}
/ / Add to h ead o f t he li st
v oi d a dd To H ead(i nt v al ue) {
N od e* n ew Nod e = n ew N od e(v al ue);
if (i sE mpt y( )) {
h ea d = n ew Nod e;
h ea d-> ne xt = h ea d;
}
e ls e {
N od e* t em p = he ad;
w hi le ( te mp-> ne xt != he ad) {
t em p = te mp-> ne xt;
}
t em p-> ne xt = n ew Nod e;
n ew Nod e-> ne xt = h ea d;
h ea d = n ew Nod e;
}
}
/ / Add to t ail o f t he li st
v oi d a dd To T ail(i nt v al ue) {
N od e* n ew Nod e = n ew N od e(v al ue);
if (i sE mpt y( )) {
h ea d = n ew Nod e;
h ea d-> ne xt = h ea d;
}
e ls e {
N od e* t em p = he ad;
w hi le ( te mp-> ne xt != he ad) {
t em p = te mp-> ne xt;
}
t em p-> ne xt = n ew Nod e;
n ew Nod e-> ne xt = h ea d;
}
}
/ / Add no de at a sp ec i fi c p osi ti on (1-b as ed ind ex )
v oi d a dd No d e(i nt v al ue, i nt p os iti on) {
if (p os iti on < = 0) {
c er r << " Po si t io n m ust b e p osi ti ve. " << e nd l;
r et urn;
}
N od e* n ew Nod e = n ew N od e(v al ue);
if (p os iti on = = 1 | | i sE mpt y( )) {
a dd ToH ead(v al ue);
}
e ls e {
N od e* c ur r ent = he ad ;
i nt c ur re n tPo si tio n = 1 ;
w hi le (c ur ren tPo si ti o n < p os it i on - 1 & & c ur r en t-> ne xt != he ad) {
c ur re n t = c urr en t-> ne xt;
c ur re n tPo si tio n+ +;
}
n ew Nod e-> ne xt = c ur ren t-> ne xt;
c ur ren t-> ne xt = n ew Nod e;
}
}
/ / Fin d n od e w it h g iv e n val ue
N od e* f in dNo de(i nt v al ue) {
if (i sE mpt y( )) {
r et urn n ul lpt r;
}
N od e* c urr ent = h e ad ;
do {
if ( cu rre nt-> da ta == v al ue) {
r et ur n c ur re n t;
}
c ur ren t = c ur r en t-> ne xt ;
} w hi le ( cu rr e nt != he ad );
r et urn n ul lpt r;
}
/ / Del ete n ode w ith g i ve n v alu e
v oi d d el et e Nod e(i nt v al ue) {
if (i sE mpt y( )) {
c er r << " Li st is em pty ." << e nd l;
r et urn;
}
N od e* c urr ent = h e ad ;
N od e* p rev iou s = n ul lpt r;
/ / Tra ver se u n ti l t he no de wit h th e v alu e i s fou nd or ba ck to he ad
do {
if ( cu rre nt-> da ta == v al ue) {
b re ak;
}
p re vio us = cu r re nt;
c ur ren t = c ur r en t-> ne xt ;
} w hi le ( cu rr e nt != he ad );
/ / If fou nd , d el ete th e nod e
if ( cu rre nt == he ad ) {
/ / If hea d is th e o nly n od e
if ( cu rre nt-> ne xt == he ad) {
d el et e h ea d;
h ea d = n ul lp t r;
}
e ls e {
/ / Mo v e h ea d t o the ne xt n o de an d u pd ate th e las t nod e's n ex t po in ter
N od e* l as t = he ad;
w hi le ( la st-> ne xt != he ad) {
l as t = l a st-> ne xt;
}
l as t-> ne xt = h ea d-> ne xt;
d el et e h ea d;
h ea d = la st-> ne xt;
}
}
e ls e if ( cu rr e nt) {
/ / Del ete t he no de and u pd a te th e p re vio us no de ' s nex t p oi nte r
p re vio us-> ne xt = c ur ren t-> ne xt ;
d el ete c ur ren t;
}
e ls e {
c er r << " No de wi t h val ue " << v al ue << " n ot fo u nd ." << e nd l;
}
}
/ / Del ete n ode f rom h e ad
v oi d d el et e Fro mH ead( ) {
if (!i sE mp t y( )) {
N od e* t em p = he ad;
if ( he ad-> ne xt == he ad) {
h ea d = n ul lp t r;
}
e ls e {
N od e* l as t = he ad;
w hi le ( la st-> ne xt != he ad) {
l as t = l a st-> ne xt;
}
l as t-> ne xt = h ea d-> ne xt;
h ea d = he ad-> ne xt;
}
d el ete t em p;
}
e ls e {
c er r << " Li st is em pty ." << e nd l;
}
}
/ / Pri nt al l n od es in th e l ist
v oi d p ri nt L ist( ) {
if (i sE mpt y( )) {
c ou t << " Li st is em pty ." << e nd l;
r et urn;
}
N od e* c urr ent = h e ad ;
do {
c ou t << c ur re n t-> da ta << " ";
c ur ren t = c ur r en t-> ne xt ;
} w hi le ( cu rr e nt != he ad );
c ou t << e nd l;
}
/ / Cou nt nu mbe r of no d es in th e li s t
i nt c ou ntL ist( ) {
if (i sE mpt y( )) {
r et urn 0;
}
i nt c ou nt = 0 ;
N od e* c urr ent = h e ad ;
do {
c ou nt+ +;
c ur ren t = c ur r en t-> ne xt ;
} w hi le ( cu rr e nt != he ad );
r et urn c ou nt;
}
};
i nt m ai n()
{
C ir cul ar L in ked Li st m yL ist;
m yL ist .a d dT oTa il( 10 );
m yL ist .a d dT oTa il( 20 );
m yL ist .a d dT oTa il( 30 );
m yL ist .a d dT oHe ad( 5) ;
c ou t << " Li st: ";
m yL ist .p r in tLi st( );
c ou t << " Nu mbe r o f no d es : " << m yL ist .co un tLi st( ) << e nd l;
m yL ist .a d dN ode( 15 , 3 );
m yL ist .d e le teN od e( 20 );
c ou t << " Li st aft er a d di ng 15 at po sit io n 3 a nd del et ing 2 0: ";
m yL ist .p r in tLi st( );
c ou t << " Nu mbe r o f no d es af ter o per ati on s: " << m yL ist .c o un tLi st( ) << e nd l;
r et urn 0;
}
Circular Linked List
C++
implementation
Linked lists are more complex to code and manage than arrays, but they have some
distinct advantages.
•Dynamic: a linked list can easily grow and shrink in size.
•We don’t need to know how many nodes will be in the list. They are created in memory as needed.
•In contrast, the size of a C++ array is fixed at compilation time.
•Easy and fast insertions and deletions
•To insert or delete an element in an array, we need to copy to temporary variables to make room
for new elements or close the gap caused by deleted elements.
•With a linked list, no need to move other nodes. Only need to reset some pointers.
Array versus Linked Lists
distinct advantages.
•Dynamic: a linked list can easily grow and shrink in size.
•We don’t need to know how many nodes will be in the list. They are created in memory as needed.
•In contrast, the size of a C++ array is fixed at compilation time.
•Easy and fast insertions and deletions
•To insert or delete an element in an array, we need to copy to temporary variables to make room
for new elements or close the gap caused by deleted elements.
•With a linked list, no need to move other nodes. Only need to reset some pointers.
Array versus Linked Lists
Stack (LIFO)
–A stack is a linear data structure that can be accessed only at one of its ends for storing
and retrieving data.
–The stack is called a LIFO (last in, first out) structure.
–The last item in is the first one out of a stack.
2
4
1
3
6
Top
Push
Pop
–A stack is a linear data structure that can be accessed only at one of its ends for storing
and retrieving data.
–The stack is called a LIFO (last in, first out) structure.
–The last item in is the first one out of a stack.
2
4
1
3
6
Top
Push
Pop
Operation Description
clear Clear the stack.
isEmpty Check to see if the stack is empty.
push Put the element el on the top of the stack.
pop Takes the topmost element from the stack.
top Returns the topmost element in the stack without removing it.
size Returns the number of elements currently in the stack.
Stack
(LIFO)
clear Clear the stack.
isEmpty Check to see if the stack is empty.
push Put the element el on the top of the stack.
pop Takes the topmost element from the stack.
top Returns the topmost element in the stack without removing it.
size Returns the number of elements currently in the stack.
Stack
(LIFO)
Stack Applications
–The stack is a very frequently used ADT, in fact, most computer architectures implement a stack at the
very core of their instruction sets — both push and pop are assembly code instructions.
–Stack operations are very useful that there is a stack built into every program running on your PC — the
stack is a memory block that gets used to store the state of memory when a function is called, and to
restore it when a function returns (aka Call Stack).
–Converting and evaluating mathematical expressions (prefix, infix, postfix, …, etc.).
–Parsing syntax and checking for balanced symbols in compilers.
–Implementing undo/redo functionalities.
–Implementing back/forward navigation in web browsers.
–Expression Matching: Checking for balanced symbols in expressions (e.g., parentheses, brackets, …, etc.).
–The stack is a very frequently used ADT, in fact, most computer architectures implement a stack at the
very core of their instruction sets — both push and pop are assembly code instructions.
–Stack operations are very useful that there is a stack built into every program running on your PC — the
stack is a memory block that gets used to store the state of memory when a function is called, and to
restore it when a function returns (aka Call Stack).
–Converting and evaluating mathematical expressions (prefix, infix, postfix, …, etc.).
–Parsing syntax and checking for balanced symbols in compilers.
–Implementing undo/redo functionalities.
–Implementing back/forward navigation in web browsers.
–Expression Matching: Checking for balanced symbols in expressions (e.g., parentheses, brackets, …, etc.).
2 + 3 * 4 – 6 = 8{ [ ( ) ] }
Stack Drawbacks
–No random access. You get the top, or nothing.
–No walking through the stack at all — you can only reach an element by popping all the
elements higher up off first
–No searching through a stack.
–No random access. You get the top, or nothing.
–No walking through the stack at all — you can only reach an element by popping all the
elements higher up off first
–No searching through a stack.
#include <iostream>
using namespace std;
class Stack
{
private:
static const int MAX_SIZE = 100;
int arr[MAX_SIZE];
int topIndex;
public:
// Constructor
Stack() : topIndex(-1) {}
// Removes all elements from the stack
void clear() {
topIndex = -1;
}
// Checks if the stack is empty
bool isEmpty() const {
return topIndex == -1;
}
// Adds an element to the top of the stack
void push(int value) {
if (topIndex >= MAX_SIZE - 1)
throw overflow_error("Stack overflow");
arr[++topIndex] = value;
}
// Removes and returns the top element of the stack
int pop() {
if (isEmpty())
throw underflow_error("Stack underflow");
return arr[topIndex--];
}
// Returns the top element of the stack without removing it
int top() const {
if (isEmpty())
throw underflow_error("Stack is empty");
return arr[topIndex];
}
// Returns the number of elements in the stack
int size() const {
return topIndex + 1;
}
// Prints all elements of the stack
void printStack() const {
for(inti = topIndex; i >= 0; i--)
cout << arr[i] << endl;
cout << endl;
}
};
int main()
{
Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);
cout << "Stack elements:" << endl;
stack.printStack(); // Should print 30, 20, 10
cout << "Top element: " << stack.top() << endl; // Should print 30
cout << "Stack size: " << stack.size() << endl; // Should print 3
cout << "Popped element: " << stack.pop() << endl; // Should print 30
cout << "Top element after pop: " << stack.top() << endl; // Should print 20
cout << "Stack size after pop: " << stack.size() << endl; // Should print 2
stack.clear();
cout << "Stack size after clear: " << stack.size() << endl; // Should print 0
cout << "Is stack empty: " << (stack.isEmpty() ? "Yes" : "No") << endl; // Should print Yes
return 0;
}
Stack (LIFO)
C++
implementation
using namespace std;
class Stack
{
private:
static const int MAX_SIZE = 100;
int arr[MAX_SIZE];
int topIndex;
public:
// Constructor
Stack() : topIndex(-1) {}
// Removes all elements from the stack
void clear() {
topIndex = -1;
}
// Checks if the stack is empty
bool isEmpty() const {
return topIndex == -1;
}
// Adds an element to the top of the stack
void push(int value) {
if (topIndex >= MAX_SIZE - 1)
throw overflow_error("Stack overflow");
arr[++topIndex] = value;
}
// Removes and returns the top element of the stack
int pop() {
if (isEmpty())
throw underflow_error("Stack underflow");
return arr[topIndex--];
}
// Returns the top element of the stack without removing it
int top() const {
if (isEmpty())
throw underflow_error("Stack is empty");
return arr[topIndex];
}
// Returns the number of elements in the stack
int size() const {
return topIndex + 1;
}
// Prints all elements of the stack
void printStack() const {
for(inti = topIndex; i >= 0; i--)
cout << arr[i] << endl;
cout << endl;
}
};
int main()
{
Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);
cout << "Stack elements:" << endl;
stack.printStack(); // Should print 30, 20, 10
cout << "Top element: " << stack.top() << endl; // Should print 30
cout << "Stack size: " << stack.size() << endl; // Should print 3
cout << "Popped element: " << stack.pop() << endl; // Should print 30
cout << "Top element after pop: " << stack.top() << endl; // Should print 20
cout << "Stack size after pop: " << stack.size() << endl; // Should print 2
stack.clear();
cout << "Stack size after clear: " << stack.size() << endl; // Should print 0
cout << "Is stack empty: " << (stack.isEmpty() ? "Yes" : "No") << endl; // Should print Yes
return 0;
}
Stack (LIFO)
C++
implementation
Queues (FIFO)
–Just like the Stack ADT, a Queue is a linear data structure that is accessed in First-In, First-Out (FIFO)
order.
–Stack is a FIFO(First in First Out) data structure, which means that element inserted first will be
removed first, the second item put in is then removed, and so on.
–The process to add an element into queue is called Enqueue and the process of removal of an
element from queue is called Dequeue.
–A queue does not allow random access of any specific item.
–A linked list-based queue dynamically adjusts its size but comes with additional memory overhead for
storing pointers/references.
–Just like the Stack ADT, a Queue is a linear data structure that is accessed in First-In, First-Out (FIFO)
order.
–Stack is a FIFO(First in First Out) data structure, which means that element inserted first will be
removed first, the second item put in is then removed, and so on.
–The process to add an element into queue is called Enqueue and the process of removal of an
element from queue is called Dequeue.
–A queue does not allow random access of any specific item.
–A linked list-based queue dynamically adjusts its size but comes with additional memory overhead for
storing pointers/references.
Queue Applications
–Queue, as the name suggests is used in everyday life whenever we need to manage any group of
objects in an order in which the first one coming in, also gets out first while the others wait for
their turn, like in the following scenarios:
•Ticket counter, lines at a bank or a fast-food restaurants.
•Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
•Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is
free.
–Used in many programming situations such as simulations, event or appointment scheduling (e.g.,
Gant chart), and I/O buffering.
–A whole branch of mathematics known as queuing theory deals with computing, probabilistically,
how long users expect to wait on a line, how long the line gets, and other such questions.
–Queue, as the name suggests is used in everyday life whenever we need to manage any group of
objects in an order in which the first one coming in, also gets out first while the others wait for
their turn, like in the following scenarios:
•Ticket counter, lines at a bank or a fast-food restaurants.
•Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
•Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is
free.
–Used in many programming situations such as simulations, event or appointment scheduling (e.g.,
Gant chart), and I/O buffering.
–A whole branch of mathematics known as queuing theory deals with computing, probabilistically,
how long users expect to wait on a line, how long the line gets, and other such questions.
Operation Description
clear Clear the queue.
isEmpty Check to see if the queue is empty.
enqueue Put the element on the front of the queue.
dequeue Takes the front (first) element from the queue.
getFront Returns the topmost element in the queue without removing it.
size Returns the number of elements currently in the queue.
1 2 3 4 5 6 7
Front Rear
0 1 2 3 4 5 6
clear Clear the queue.
isEmpty Check to see if the queue is empty.
enqueue Put the element on the front of the queue.
dequeue Takes the front (first) element from the queue.
getFront Returns the topmost element in the queue without removing it.
size Returns the number of elements currently in the queue.
1 2 3 4 5 6 7
Front Rear
0 1 2 3 4 5 6
1 2 3 4 5 6
Front Rear
0 1 2 3 4 5 6
Front Rear
0 1 2 3 4 5 6
1 2 3 4 5 6
Front Rear
0 1 2 3 4 5 6
Front Rear
0 1 2 3 4 5 6
#include <iostream>
#include <stdexcept>
using namespace std;
class LinearQueue
{
private:
static const int MAX_SIZE = 100; // Maximum size of the queue
int arr[MAX_SIZE]; // Array to store queue elements
int front; // Index of the front element
int rear; // Index of the rear element
int count; // Number of elements in the queue
public:
// Constructor
LinearQueue() : front(0), rear( -1), count(0) {}
// Clear the queue
void clear() {
front = 0;
rear = -1;
count = 0;
}
// Check to see if the queue is empty
bool isEmpty() const {
return count == 0;
}
// Put the element on the front of the queue
void enqueue(int value) {
if (count == MAX_SIZE) {
throw overflow_error("Queue overflow");
}
rear = (rear + 1) % MAX_SIZE;
arr[rear] = value;
count++;
}
// Takes the front (first) element from the queue
int dequeue() {
if (isEmpty()) {
throw underflow_error("Queue underflow");
}
int value = arr[front];
front = (front + 1) % MAX_SIZE;
count--;
return value;
}
// Returns the topmost element in the queue without removing it
int getFront() const {
if (isEmpty()) {
throw underflow_error("Queue is empty");
}
return arr[front];
}
// Returns the number of elements currently in the queue
int size() const {
return count;
}
};
int main()
{
LinearQueue queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
cout << "Front element: " << queue.getFront() << endl; // Should print 10
cout << "Queue size: " << queue.size() << endl; // Should print 3
cout << "Dequeued element: " << queue.dequeue() << endl; // Should print 10
cout << "Front element after dequeue: " << queue.getFront() << endl; // Should print 20
cout << "Queue size after dequeue: " << queue.size() << endl; // Should print 2
queue.clear();
cout << "Queue size after clear: " << queue.size() << endl; // Should print 0
cout << "Is queue empty: " << (queue.isEmpty() ? "Yes" : "No") << endl; // Should print Yes
return 0;
}
Linear Queue
C++
implementation
#include <stdexcept>
using namespace std;
class LinearQueue
{
private:
static const int MAX_SIZE = 100; // Maximum size of the queue
int arr[MAX_SIZE]; // Array to store queue elements
int front; // Index of the front element
int rear; // Index of the rear element
int count; // Number of elements in the queue
public:
// Constructor
LinearQueue() : front(0), rear( -1), count(0) {}
// Clear the queue
void clear() {
front = 0;
rear = -1;
count = 0;
}
// Check to see if the queue is empty
bool isEmpty() const {
return count == 0;
}
// Put the element on the front of the queue
void enqueue(int value) {
if (count == MAX_SIZE) {
throw overflow_error("Queue overflow");
}
rear = (rear + 1) % MAX_SIZE;
arr[rear] = value;
count++;
}
// Takes the front (first) element from the queue
int dequeue() {
if (isEmpty()) {
throw underflow_error("Queue underflow");
}
int value = arr[front];
front = (front + 1) % MAX_SIZE;
count--;
return value;
}
// Returns the topmost element in the queue without removing it
int getFront() const {
if (isEmpty()) {
throw underflow_error("Queue is empty");
}
return arr[front];
}
// Returns the number of elements currently in the queue
int size() const {
return count;
}
};
int main()
{
LinearQueue queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
cout << "Front element: " << queue.getFront() << endl; // Should print 10
cout << "Queue size: " << queue.size() << endl; // Should print 3
cout << "Dequeued element: " << queue.dequeue() << endl; // Should print 10
cout << "Front element after dequeue: " << queue.getFront() << endl; // Should print 20
cout << "Queue size after dequeue: " << queue.size() << endl; // Should print 2
queue.clear();
cout << "Queue size after clear: " << queue.size() << endl; // Should print 0
cout << "Is queue empty: " << (queue.isEmpty() ? "Yes" : "No") << endl; // Should print Yes
return 0;
}
Linear Queue
C++
implementation
Queues Variations
1)Linear Queue
–In a Linear queue, once the queue is completely full, it's not possible to insert more elements. Even if we dequeue the queue
to remove some of the elements, until the queue is reset, no new elements can be inserted.
2)Circular Queue
–In case of a circular queue, head pointer will always point to the front of the queue, and tail pointer
will always point to the end of the queue.
1 2 3 4 5 6 7
Front Rear
1)Linear Queue
–In a Linear queue, once the queue is completely full, it's not possible to insert more elements. Even if we dequeue the queue
to remove some of the elements, until the queue is reset, no new elements can be inserted.
2)Circular Queue
–In case of a circular queue, head pointer will always point to the front of the queue, and tail pointer
will always point to the end of the queue.
1 2 3 4 5 6 7
Front Rear
#include <iostream>
#include <stdexcept>
using namespace std;
class CircularQueue
{
private:
static const int MAX_SIZE = 100; // Maximum size of the queue
int arr[MAX_SIZE]; // Array to store queue elements
int front; // Index of the front element
int rear; // Index of the rear element
int count; // Number of elements in the queue
public:
// Constructor
CircularQueue() : front(0), rear(0), count(0) {}
// Clear the queue
void clear() {
front = 0;
rear = 0;
count = 0;
}
// Check to see if the queue is empty
bool isEmpty() const {
return count == 0;
}
// Put the element at the rear of the queue
void enqueue(int value) {
if (count == MAX_SIZE) {
throw overflow_error("Queue overflow");
}
arr[rear] = value;
rear = (rear + 1) % MAX_SIZE;
count++;
}
// Takes the front (first) element from the queue
int dequeue() {
if (isEmpty()) {
throw underflow_error("Queue underflow");
}
int value = arr[front];
front = (front + 1) % MAX_SIZE;
count--;
return value;
}
// Returns the front element in the queue without removing it
int getFront() const {
if (isEmpty()) {
throw underflow_error("Queue is empty");
}
return arr[front];
}
// Returns the number of elements currently in the queue
int size() const {
return count;
}
};
int main()
{
CircularQueue queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
cout << "Front element: " << queue.getFront() << endl; // Should print 10
cout << "Queue size: " << queue.size() << endl; // Should print 3
cout << "Dequeued element: " << queue.dequeue() << endl; // Should print 10
cout << "Front element after dequeue: " << queue.getFront() << endl; // Should print 20
cout << "Queue size after dequeue: " << queue.size() << endl; // Should print 2
queue.clear();
cout << "Queue size after clear: " << queue.size() << endl; // Should print 0
cout << "Is queue empty: " << (queue.isEmpty() ? "Yes" : "No") << endl; // Should print Yes
return 0;
}
Circular Queue
C++
implementation
#include <stdexcept>
using namespace std;
class CircularQueue
{
private:
static const int MAX_SIZE = 100; // Maximum size of the queue
int arr[MAX_SIZE]; // Array to store queue elements
int front; // Index of the front element
int rear; // Index of the rear element
int count; // Number of elements in the queue
public:
// Constructor
CircularQueue() : front(0), rear(0), count(0) {}
// Clear the queue
void clear() {
front = 0;
rear = 0;
count = 0;
}
// Check to see if the queue is empty
bool isEmpty() const {
return count == 0;
}
// Put the element at the rear of the queue
void enqueue(int value) {
if (count == MAX_SIZE) {
throw overflow_error("Queue overflow");
}
arr[rear] = value;
rear = (rear + 1) % MAX_SIZE;
count++;
}
// Takes the front (first) element from the queue
int dequeue() {
if (isEmpty()) {
throw underflow_error("Queue underflow");
}
int value = arr[front];
front = (front + 1) % MAX_SIZE;
count--;
return value;
}
// Returns the front element in the queue without removing it
int getFront() const {
if (isEmpty()) {
throw underflow_error("Queue is empty");
}
return arr[front];
}
// Returns the number of elements currently in the queue
int size() const {
return count;
}
};
int main()
{
CircularQueue queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
cout << "Front element: " << queue.getFront() << endl; // Should print 10
cout << "Queue size: " << queue.size() << endl; // Should print 3
cout << "Dequeued element: " << queue.dequeue() << endl; // Should print 10
cout << "Front element after dequeue: " << queue.getFront() << endl; // Should print 20
cout << "Queue size after dequeue: " << queue.size() << endl; // Should print 2
queue.clear();
cout << "Queue size after clear: " << queue.size() << endl; // Should print 0
cout << "Is queue empty: " << (queue.isEmpty() ? "Yes" : "No") << endl; // Should print Yes
return 0;
}
Circular Queue
C++
implementation
Queue Drawbacks
–Fixed Size Limitation (Array-based Implementation)
•If a queue is implemented using a fixed-size array, there is a limitation on the number of elements it can
hold. This can lead to either unused space (if the array is too large) or overflow (if the array is too small).
–Memory Overhead (Linked List-based Implementation)
•A linked list-based queue dynamically adjusts its size but comes with additional memory overhead for
storing pointers/references. Each node requires extra space to store the pointer to the next node.
–Complexity in Circular Queue Implementation
•Implementing a circular queue can be more complex than a linear queue, as it requires handling wrap-
around logic for both the front and rear pointers.
–Fixed Size Limitation (Array-based Implementation)
•If a queue is implemented using a fixed-size array, there is a limitation on the number of elements it can
hold. This can lead to either unused space (if the array is too large) or overflow (if the array is too small).
–Memory Overhead (Linked List-based Implementation)
•A linked list-based queue dynamically adjusts its size but comes with additional memory overhead for
storing pointers/references. Each node requires extra space to store the pointer to the next node.
–Complexity in Circular Queue Implementation
•Implementing a circular queue can be more complex than a linear queue, as it requires handling wrap-
around logic for both the front and rear pointers.
Queue Drawbacks (Cont.)
–In a Linear queue, once the queue is completely full, it's not possible to insert more
elements. Even if we dequeue the queue to remove some of the elements, until the
queue is reset, no new elements can be inserted. Why?
•When we dequeue any element to remove it from the queue, we are actually moving the front of the
queue forward, thereby reducing the overall size of the queue. And we cannot insert new elements,
because the rear pointer is still at the end of the queue.
21 33 4 12 67 78 93
Front Rear
4 12 67 78 93
Front Rear
Queue
is full
Queue is full
(Even after removing )
2 elements
–In a Linear queue, once the queue is completely full, it's not possible to insert more
elements. Even if we dequeue the queue to remove some of the elements, until the
queue is reset, no new elements can be inserted. Why?
•When we dequeue any element to remove it from the queue, we are actually moving the front of the
queue forward, thereby reducing the overall size of the queue. And we cannot insert new elements,
because the rear pointer is still at the end of the queue.
21 33 4 12 67 78 93
Front Rear
4 12 67 78 93
Front Rear
Queue
is full
Queue is full
(Even after removing )
2 elements
Basic Terminology – Map
–A map associates unique keys with values (i.e., <key, value> pairs).
Key Value
“Ahmed” $5000
“Mohamed” $4700
“Mona” $6100
“Gamal” $7000
–A map associates unique keys with values (i.e., <key, value> pairs).
Key Value
“Ahmed” $5000
“Mohamed” $4700
“Mona” $6100
“Gamal” $7000
#include <iostream>
#include <string>
using namespace std;
template <typename K, typename V>
class Map {
private:
K* keys;
V* values;
int size;
int capacity;
void expand() {
capacity *= 2;
K* newKeys = new K[capacity];
V* newValues = new V[capacity];
for(inti = 0; i < size; i++) {
newKeys[i] = keys[i];
newValues[i] = values[i];
}
delete[] keys;
delete[] values;
keys = newKeys;
values = newValues;
}
public:
Map() : size(0), capacity(10) {
keys = new K[capacity];
values = new V[capacity];
}
~Map() {
delete[] keys;
delete[] values;
}
void add(const K& key, const V& value) {
if (size == capacity)
expand();
keys[size] = key;
values[size] = value;
size++;
}
bool isEmpty() const {
return size == 0;
}
V& operator[](const K& key) {
for(inti = 0; i < size; i++)
if (keys[i] == key)
return values[i];
// If key is not found, add it with a default value
if (size == capacity)
expand();
keys[size] = key;
values[size] = V(); // Default value for type V
size++;
return values[size - 1];
}
void deleteKey(const K& key) {
for(inti = 0; i < size; i++) {
if (keys[i] == key) {
for (int j = i; j < size - 1; j++) {
keys[j] = keys[j + 1];
values[j] = values[j + 1];
}
size--;
return;
}
}
}
void print() const {
for(inti = 0; i < size; i++)
cout << "<" << keys[i] << "," << values[i] << ">" << endl;
}
};
int main(void) {
Map<string, int> salaries;
salaries["Ahmed"] = 5000;
salaries["Mohamed"] = 4700;
salaries["Mona"] = 6100;
salaries["Gamal"] = 7000;
salaries.print();
return 0;
}
Map
C++
implementation
Method #1
#include <string>
using namespace std;
template <typename K, typename V>
class Map {
private:
K* keys;
V* values;
int size;
int capacity;
void expand() {
capacity *= 2;
K* newKeys = new K[capacity];
V* newValues = new V[capacity];
for(inti = 0; i < size; i++) {
newKeys[i] = keys[i];
newValues[i] = values[i];
}
delete[] keys;
delete[] values;
keys = newKeys;
values = newValues;
}
public:
Map() : size(0), capacity(10) {
keys = new K[capacity];
values = new V[capacity];
}
~Map() {
delete[] keys;
delete[] values;
}
void add(const K& key, const V& value) {
if (size == capacity)
expand();
keys[size] = key;
values[size] = value;
size++;
}
bool isEmpty() const {
return size == 0;
}
V& operator[](const K& key) {
for(inti = 0; i < size; i++)
if (keys[i] == key)
return values[i];
// If key is not found, add it with a default value
if (size == capacity)
expand();
keys[size] = key;
values[size] = V(); // Default value for type V
size++;
return values[size - 1];
}
void deleteKey(const K& key) {
for(inti = 0; i < size; i++) {
if (keys[i] == key) {
for (int j = i; j < size - 1; j++) {
keys[j] = keys[j + 1];
values[j] = values[j + 1];
}
size--;
return;
}
}
}
void print() const {
for(inti = 0; i < size; i++)
cout << "<" << keys[i] << "," << values[i] << ">" << endl;
}
};
int main(void) {
Map<string, int> salaries;
salaries["Ahmed"] = 5000;
salaries["Mohamed"] = 4700;
salaries["Mona"] = 6100;
salaries["Gamal"] = 7000;
salaries.print();
return 0;
}
Map
C++
implementation
Method #1
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
// map<key_type, value_type> map_name;
map<string, int> salaries = {
{"Ahmed", 5000},
{"Mohamed", 4700},
{"Mona", 6100},
{"Gamal", 7000}
};
// Add new element
salaries["Ali"] = 5500;
// Iterator to the first element
map<string, int>::iterator it = salaries.begin();
// Iterate over the map
while (it != salaries.end()) {
cout << "Key: " << it->first << ",\t Value: " << it->second << endl;
it++;
}
return 0;
}
Map
C++
implementation
Method 2
#include <map>
#include <string>
using namespace std;
int main() {
// map<key_type, value_type> map_name;
map<string, int> salaries = {
{"Ahmed", 5000},
{"Mohamed", 4700},
{"Mona", 6100},
{"Gamal", 7000}
};
// Add new element
salaries["Ali"] = 5500;
// Iterator to the first element
map<string, int>::iterator it = salaries.begin();
// Iterate over the map
while (it != salaries.end()) {
cout << "Key: " << it->first << ",\t Value: " << it->second << endl;
it++;
}
return 0;
}
Map
C++
implementation
Method 2
Basic Terminology – Hashing
–A hash table uses a hash function to map general keys to corresponding indices in a table.
<key, value>
Key Value
“Ahmed” $5000
“Mohamed” $4700
“Mona” $6100
“Gamal” $7000
Hash
Function
??????
Hash
Value
Item
0
1
2 (Gamal, 5000)
3
4
5 (Mona, 5000)
6
7
8
9 (Ahmed, 5000)hash value = sum ASCII codes % size
Size = 10
–A hash table uses a hash function to map general keys to corresponding indices in a table.
<key, value>
Key Value
“Ahmed” $5000
“Mohamed” $4700
“Mona” $6100
“Gamal” $7000
Hash
Function
??????
Hash
Value
Item
0
1
2 (Gamal, 5000)
3
4
5 (Mona, 5000)
6
7
8
9 (Ahmed, 5000)hash value = sum ASCII codes % size
Size = 10
Simple hash function
–You can use any other hashing function of your choice.
–In the previous slide we used a simple hash function as follows
Hash Value = Sum ASCII Codes % Size
–You can use any hash function of your choice, though.
Ahmed
A h m e d
65 104 109 101 100
Sum = 65 + 104 + 109 + 101 + 100 = 479
Hash Value = 479 % 10 = 9
–You can use any other hashing function of your choice.
–In the previous slide we used a simple hash function as follows
Hash Value = Sum ASCII Codes % Size
–You can use any hash function of your choice, though.
Ahmed
A h m e d
65 104 109 101 100
Sum = 65 + 104 + 109 + 101 + 100 = 479
Hash Value = 479 % 10 = 9
#include <iostream>
#include <string>
using namespace std;
int hashFunction(string name) {
int ascii_sum = 0;
for(inti = 0; i < name.size(); i++)
ascii_sum += int(name[i]);
return (ascii_sum % 10);
}
int main(void) {
string name = "Ahmed";
cout << "Hash value for " << name << " is " << hashFunction(name) << endl;
return 0;
}
Hash Function
#include <string>
using namespace std;
int hashFunction(string name) {
int ascii_sum = 0;
for(inti = 0; i < name.size(); i++)
ascii_sum += int(name[i]);
return (ascii_sum % 10);
}
int main(void) {
string name = "Ahmed";
cout << "Hash value for " << name << " is " << hashFunction(name) << endl;
return 0;
}
Hash Function
class Hashing {
private:
Map<string, int> hashTable[10];
int hashFunction(string name) {
int ascii_sum = 0;
for(inti = 0; i < name.size(); i++)
ascii_sum += int(name[i]);
return (ascii_sum % 10);
}
public:
void add(const string& key, const int& value) {
int hashValue = hashFunction(key);
hashTable[hashValue][key] = value;
}
int get(const string& key) {
int hashValue = hashFunction(key);
return hashTable[hashValue][key];
}
void remove(const string& key) {
int hashValue = hashFunction(key);
hashTable[hashValue].deleteKey(key);
}
void print() {
for(inti = 0; i < 10; i++) {
if (hashTable[i].isEmpty())
continue;
cout << "Hash value " << i << ": ";
hashTable[i].print();
}
}
};
Hashing Class
C++
implementation
private:
Map<string, int> hashTable[10];
int hashFunction(string name) {
int ascii_sum = 0;
for(inti = 0; i < name.size(); i++)
ascii_sum += int(name[i]);
return (ascii_sum % 10);
}
public:
void add(const string& key, const int& value) {
int hashValue = hashFunction(key);
hashTable[hashValue][key] = value;
}
int get(const string& key) {
int hashValue = hashFunction(key);
return hashTable[hashValue][key];
}
void remove(const string& key) {
int hashValue = hashFunction(key);
hashTable[hashValue].deleteKey(key);
}
void print() {
for(inti = 0; i < 10; i++) {
if (hashTable[i].isEmpty())
continue;
cout << "Hash value " << i << ": ";
hashTable[i].print();
}
}
};
Hashing Class
C++
implementation
#i ncl ud e <i ost r eam >
#i ncl ud e <s tri n g>
us ing na m es pa ce st d ;
te mpl at e <ty p en am e K, ty p en am e V>
cl ass Ma p {
pr i va te:
K* key s ;
V* val u es;
in t si z e;
in t ca p ac it y;
vo i d ex pan d () {
ca p ac it y *= 2 ;
K* ne wKe y s = ne w K[c a pa ci ty ];
V* ne wVa l ues = ne w V[c a pa ci ty ];
fo r(in ti = 0 ; i < s ize ; i+ + ) {
ne w Ke ys[i] = k e ys[i];
ne w Va lu es[i] = v a lue s [i];
}
de l et e[] ke ys ;
de l et e[] va lu es ;
ke y s = ne wKe y s;
va l ue s = ne wVa l ues;
}
pu b li c:
Ma p () : s ize ( 0) , ca pac i ty (10 ) {
ke y s = ne w K[c a pa ci ty ];
va l ue s = ne w V[c a pa ci ty ];
}
~M a p( ) {
de l et e[] ke ys ;
de l et e[] va lu es ;
}
vo i d ad d(co nst K& ke y, co nst V& va l ue) {
if (s ize == c ap aci t y)
ex p an d( );
ke y s[ si ze ] = ke y;
va l ue s[ si ze] = va lue;
si z e+ +;
}
bo o l is Emp t y() co nst {
re t ur n si ze = = 0 ;
}
V& op era t or[ ](co n st K& ke y) {
fo r(in ti = 0 ; i < s ize ; i+ + )
if (k eys [i] = = ke y)
re t ur n va lue s [i];
// If k ey is no t fo und , a dd i t w i th a d efa u lt va l ue
if (s ize == c ap aci t y)
ex p an d( );
ke y s[ si ze ] = ke y;
va l ue s[ si ze] = V() ; // De fa ul t v a lu e fo r t y pe V
si z e+ +;
re t ur n va lue s [si z e - 1] ;
}
vo i d de let e Key(co nst K& ke y) {
fo r(in ti = 0 ; i < s ize ; i+ + ) {
if (k eys [i] = = ke y) {
fo r (in t j = i; j < s iz e - 1; j+ +) {
ke y s[ j] = ke y s[ j + 1];
va l ue s[ j] = v al ue s[ j + 1] ;
}
si z e--;
re t ur n;
}
}
}
vo i d pr int ( ) co nst {
fo r(in ti = 0 ; i < s ize ; i+ + )
co u t << "< " << ke ys [i] << ", " << va lu es [i] << "> " << en dl;
}
};
cl ass Ha s hi ng {
pr i va te:
Ma p<st r in g, in t> ha shT a ble[1 0 ];
in t ha s hF un ct ion(st rin g na m e) {
in t as c ii _s um = 0 ;
fo r(in ti = 0 ; i < na m e.s i ze () ; i++ )
as c ii _s um += in t(na me[i]);
re t ur n (as c ii _s um % 1 0) ;
}
pu b li c:
vo i d ad d(co nst st rin g& ke y, co n st in t& va lue) {
in t ha s hV al ue = ha s hF un ct ion(ke y);
ha s hT ab le[ha s hV al ue][ke y] = va l ue;
}
vo i d re mov e (co n st st r in g& ke y) {
in t ha s hV al ue = ha s hF un ct ion(ke y);
ha s hT ab le[ha s hV al ue].de let e Key(ke y);
}
in t ge t (co n st st r in g& ke y) {
in t ha s hV al ue = ha s hF un ct ion(ke y);
re t ur n ha shT a ble[ha shV a lue][ke y];
}
vo i d pr int ( ) {
fo r(in ti = 0 ; i < 1 0; i ++) {
if (ha s hT ab le[i].is Emp t y() )
co n ti nu e;
co u t << "H a sh v al ue " << i << ": ";
ha s hT ab le[i]. pri n t() ;
}
}
};
in t ma i n( ) {
Ha s hi ng ha s hi ng;
ha s hi ng .a dd("A h me d", 500 0 );
ha s hi ng .a dd("M o ha me d", 470 0 );
ha s hi ng .a dd("M o na ", 6 10 0) ;
ha s hi ng .a dd("G a ma l", 700 0 );
ha s hi ng .p rin t() ;
co u t << "A h me d' s sal a ry i s " << ha s hi ng .g et("A h me d") << en d l;
re t ur n 0;
}
All put together
C++
implementation
#i ncl ud e <s tri n g>
us ing na m es pa ce st d ;
te mpl at e <ty p en am e K, ty p en am e V>
cl ass Ma p {
pr i va te:
K* key s ;
V* val u es;
in t si z e;
in t ca p ac it y;
vo i d ex pan d () {
ca p ac it y *= 2 ;
K* ne wKe y s = ne w K[c a pa ci ty ];
V* ne wVa l ues = ne w V[c a pa ci ty ];
fo r(in ti = 0 ; i < s ize ; i+ + ) {
ne w Ke ys[i] = k e ys[i];
ne w Va lu es[i] = v a lue s [i];
}
de l et e[] ke ys ;
de l et e[] va lu es ;
ke y s = ne wKe y s;
va l ue s = ne wVa l ues;
}
pu b li c:
Ma p () : s ize ( 0) , ca pac i ty (10 ) {
ke y s = ne w K[c a pa ci ty ];
va l ue s = ne w V[c a pa ci ty ];
}
~M a p( ) {
de l et e[] ke ys ;
de l et e[] va lu es ;
}
vo i d ad d(co nst K& ke y, co nst V& va l ue) {
if (s ize == c ap aci t y)
ex p an d( );
ke y s[ si ze ] = ke y;
va l ue s[ si ze] = va lue;
si z e+ +;
}
bo o l is Emp t y() co nst {
re t ur n si ze = = 0 ;
}
V& op era t or[ ](co n st K& ke y) {
fo r(in ti = 0 ; i < s ize ; i+ + )
if (k eys [i] = = ke y)
re t ur n va lue s [i];
// If k ey is no t fo und , a dd i t w i th a d efa u lt va l ue
if (s ize == c ap aci t y)
ex p an d( );
ke y s[ si ze ] = ke y;
va l ue s[ si ze] = V() ; // De fa ul t v a lu e fo r t y pe V
si z e+ +;
re t ur n va lue s [si z e - 1] ;
}
vo i d de let e Key(co nst K& ke y) {
fo r(in ti = 0 ; i < s ize ; i+ + ) {
if (k eys [i] = = ke y) {
fo r (in t j = i; j < s iz e - 1; j+ +) {
ke y s[ j] = ke y s[ j + 1];
va l ue s[ j] = v al ue s[ j + 1] ;
}
si z e--;
re t ur n;
}
}
}
vo i d pr int ( ) co nst {
fo r(in ti = 0 ; i < s ize ; i+ + )
co u t << "< " << ke ys [i] << ", " << va lu es [i] << "> " << en dl;
}
};
cl ass Ha s hi ng {
pr i va te:
Ma p<st r in g, in t> ha shT a ble[1 0 ];
in t ha s hF un ct ion(st rin g na m e) {
in t as c ii _s um = 0 ;
fo r(in ti = 0 ; i < na m e.s i ze () ; i++ )
as c ii _s um += in t(na me[i]);
re t ur n (as c ii _s um % 1 0) ;
}
pu b li c:
vo i d ad d(co nst st rin g& ke y, co n st in t& va lue) {
in t ha s hV al ue = ha s hF un ct ion(ke y);
ha s hT ab le[ha s hV al ue][ke y] = va l ue;
}
vo i d re mov e (co n st st r in g& ke y) {
in t ha s hV al ue = ha s hF un ct ion(ke y);
ha s hT ab le[ha s hV al ue].de let e Key(ke y);
}
in t ge t (co n st st r in g& ke y) {
in t ha s hV al ue = ha s hF un ct ion(ke y);
re t ur n ha shT a ble[ha shV a lue][ke y];
}
vo i d pr int ( ) {
fo r(in ti = 0 ; i < 1 0; i ++) {
if (ha s hT ab le[i].is Emp t y() )
co n ti nu e;
co u t << "H a sh v al ue " << i << ": ";
ha s hT ab le[i]. pri n t() ;
}
}
};
in t ma i n( ) {
Ha s hi ng ha s hi ng;
ha s hi ng .a dd("A h me d", 500 0 );
ha s hi ng .a dd("M o ha me d", 470 0 );
ha s hi ng .a dd("M o na ", 6 10 0) ;
ha s hi ng .a dd("G a ma l", 700 0 );
ha s hi ng .p rin t() ;
co u t << "A h me d' s sal a ry i s " << ha s hi ng .g et("A h me d") << en d l;
re t ur n 0;
}
All put together
C++
implementation
Collision Handling
–For two distinct keys k1 and k2, we may have the same hash value (i.e., h(k1) = h(k2)).
–We call this a collision.
–Collisions complicate our procedure of performing insertions, search and deletion
operations.
–There are multiple collision handling schemes, including separate chaining and linear
probing.
Separate chaining
Linear probing
–For two distinct keys k1 and k2, we may have the same hash value (i.e., h(k1) = h(k2)).
–We call this a collision.
–Collisions complicate our procedure of performing insertions, search and deletion
operations.
–There are multiple collision handling schemes, including separate chaining and linear
probing.
Separate chaining
Linear probing
Operation List
Hash Table
Expected Worst Case
Get item O(n) O(1) O(n)
Set item O(n) O(1) O(n)
Delete item O(n) O(1) O(n)
Length O(1) O(1) O(1)
Iterating O(n) O(n) O(n)
Hash Tables – Complexity
Hash Table
Expected Worst Case
Get item O(n) O(1) O(n)
Set item O(n) O(1) O(n)
Delete item O(n) O(1) O(n)
Length O(1) O(1) O(1)
Iterating O(n) O(n) O(n)
Hash Tables – Complexity
Trees – Basic Terminology
– A tree is an acyclic graph
–For our purposes, a tree is a collection of nodes (that can hold keys, data, …, etc.) that are connected by edges
– Trees are also oriented; each node has a parent and children.
– A node with no parents is the root of the tree, all child nodes are oriented downward.
– Nodes not immediately connected can have an ancestor, descendant or cousin relationship.
– A node with no children is called a leaf.
– A tree such that all nodes have at most two children is called a binary tree.
–A binary tree is also oriented horizontally: each node may have a left and/or a right
child.
–A binary tree is complete (also called full or perfect) if all nodes are present at
all levels, 0 up to its depth ‘d’.
–A path in a tree is a sequence nodes connected by edges.
– A tree is an acyclic graph
–For our purposes, a tree is a collection of nodes (that can hold keys, data, …, etc.) that are connected by edges
– Trees are also oriented; each node has a parent and children.
– A node with no parents is the root of the tree, all child nodes are oriented downward.
– Nodes not immediately connected can have an ancestor, descendant or cousin relationship.
– A node with no children is called a leaf.
– A tree such that all nodes have at most two children is called a binary tree.
–A binary tree is also oriented horizontally: each node may have a left and/or a right
child.
–A binary tree is complete (also called full or perfect) if all nodes are present at
all levels, 0 up to its depth ‘d’.
–A path in a tree is a sequence nodes connected by edges.
Trees – Basic Terminology (Cont.)
–The length of a path in a tree is the number of edges in the path (which equals the number of nodes in the
path minus one).
–A path is simple if it does not traverse nodes more than once (this is the default type of path)
–The depth of a node ‘u’ is the length of the (unique) path from the root to ‘u’.
–The depth of the root is 0.
–The depth of a tree is the maximal depth of any node in the tree (sometimes the term height is used).
–All nodes of the same depth are considered to be at the same level.
–The height of a node u is the number of edges on the longest path from the
node ‘u’ to a leaf.
–The length of a path in a tree is the number of edges in the path (which equals the number of nodes in the
path minus one).
–A path is simple if it does not traverse nodes more than once (this is the default type of path)
–The depth of a node ‘u’ is the length of the (unique) path from the root to ‘u’.
–The depth of the root is 0.
–The depth of a tree is the maximal depth of any node in the tree (sometimes the term height is used).
–All nodes of the same depth are considered to be at the same level.
–The height of a node u is the number of edges on the longest path from the
node ‘u’ to a leaf.
Depth of the whole tree is 3.
Tree height = 4
No. nodes = 16.
No. edges = No. nodes – 1 = 16 – 1 = 15
Lvl 0
Lvl 1
Lvl 2
Lvl 3
Root
Leaf Leaf
LeafLeafLeafLeafLeafLeaf
LeafLeaf
Node Height Depth
A 3 0
B 0 1
C 0 1
D 1 1
… … …
Tree height = 4
No. nodes = 16.
No. edges = No. nodes – 1 = 16 – 1 = 15
Lvl 0
Lvl 1
Lvl 2
Lvl 3
Root
Leaf Leaf
LeafLeafLeafLeafLeafLeaf
LeafLeaf
Node Height Depth
A 3 0
B 0 1
C 0 1
D 1 1
… … …
Operation Description
search Search for a particular element/key.
add
Adding an element
▪Add at most shallow available spot.
▪Add at a random leaf.
▪Add internally, shift nodes down by some criteria.
remove
Removing an element
▪Removing a leaf.
▪Removing elements with one child.
▪Removing elements with two children.
countNodes Compute the total number of nodes in the tree.
countLeaves Compute the total number of leaves in a tree.
findDepth Given a specific node, compute its depth.
search Search for a particular element/key.
add
Adding an element
▪Add at most shallow available spot.
▪Add at a random leaf.
▪Add internally, shift nodes down by some criteria.
remove
Removing an element
▪Removing a leaf.
▪Removing elements with one child.
▪Removing elements with two children.
countNodes Compute the total number of nodes in the tree.
countLeaves Compute the total number of leaves in a tree.
findDepth Given a specific node, compute its depth.
Binary (search) Trees Properties
–In a binary tree, all nodes are connected by exactly one unique path.
– The maximum number of nodes at any level ‘k’ is 2
??????
.
–The maximum number of nodes ‘n’ for any binary tree of
depth ‘d’ is
–The Binary Tree can be considered as a special form
of Linked List.
–A binary tree is considered balanced if, for every node in the tree, the height
difference between the left and right subtrees is at most one.
Binary Tree
Lvl 0
Lvl 1
Lvl 2
Lvl 3
Lvl 4
Lvl 5
–In a binary tree, all nodes are connected by exactly one unique path.
– The maximum number of nodes at any level ‘k’ is 2
??????
.
–The maximum number of nodes ‘n’ for any binary tree of
depth ‘d’ is
–The Binary Tree can be considered as a special form
of Linked List.
–A binary tree is considered balanced if, for every node in the tree, the height
difference between the left and right subtrees is at most one.
Binary Tree
Lvl 0
Lvl 1
Lvl 2
Lvl 3
Lvl 4
Lvl 5
Binary (search) Tree
– Each node has an associated key.
–For every node u with key uk in T
–Every node in the left-sub-tree of u has keys less than uk
–Every node in the right-sub-tree of u has keys greater than or equal to uk
– Duplicate keys can be handled, but you must be consistent and not guaranteed to be contiguous.
–Inductive property: all sub-trees are also binary search trees.
–In Sorted Binary Trees, elements on the right side of the root element are always greater than the
ones on the left.
– Each node has an associated key.
–For every node u with key uk in T
–Every node in the left-sub-tree of u has keys less than uk
–Every node in the right-sub-tree of u has keys greater than or equal to uk
– Duplicate keys can be handled, but you must be consistent and not guaranteed to be contiguous.
–Inductive property: all sub-trees are also binary search trees.
–In Sorted Binary Trees, elements on the right side of the root element are always greater than the
ones on the left.
Balanced vs. Unbalanced Binary Tree
1
2 3
4 5
df = 1
df = 0 df = 0
df = 0 df = 0
1
2 3
4 5
5
df = 2
df = 1 df = 0
df = 0 df = 1
df = 0
df = height of left child−height of right child
Balanced Unbalanced
1
2 3
4 5
df = 1
df = 0 df = 0
df = 0 df = 0
1
2 3
4 5
5
df = 2
df = 1 df = 0
df = 0 df = 1
df = 0
df = height of left child−height of right child
Balanced Unbalanced
Binary Tree – Representing Algebraic Expressions
a – b a – b/c a – b * c
a – b a – b/c a – b * c
Tree Traversal
–Level order traversal
–Pre-order traversal:
•Visits nodes in the following order: root; left-sub-tree; right-sub-tree.
–In-order traversal
•Visits nodes in the following order: left-sub-tree; root; right-sub-tree.
–Post-order traversal
•Visits nodes in the following order: left-sub-tree; right-sub-tree; root.
–Level order traversal
–Pre-order traversal:
•Visits nodes in the following order: root; left-sub-tree; right-sub-tree.
–In-order traversal
•Visits nodes in the following order: left-sub-tree; root; right-sub-tree.
–Post-order traversal
•Visits nodes in the following order: left-sub-tree; right-sub-tree; root.
F
B G
A
D
C E
I
H
Tree Traversal:
•Level Order (Breadth first)
•Depth-first
»Pre-order
»In-order (sorted)
»Post-order
B G
A
D
C E
I
H
Tree Traversal:
•Level Order (Breadth first)
•Depth-first
»Pre-order
»In-order (sorted)
»Post-order
F
B G
A
D
C E
I
H
•Level Order: F,
B G
A
D
C E
I
H
•Level Order: F,
F
B G
A
D
C E
I
H
•Level Order: F, B
B G
A
D
C E
I
H
•Level Order: F, B
F
B G
A
D
C E
I
H
•Level Order: F, B, G
B G
A
D
C E
I
H
•Level Order: F, B, G
F
B G
A
D
C E
I
H
•Level Order: F, B, G, A
B G
A
D
C E
I
H
•Level Order: F, B, G, A
F
B G
A
D
C E
I
H
•Level Order: F, B, G, A, D
B G
A
D
C E
I
H
•Level Order: F, B, G, A, D
F
B G
A
D
C E
I
H
•Level Order: F, B, G, A, D, I
B G
A
D
C E
I
H
•Level Order: F, B, G, A, D, I
F
B G
A
D
C E
I
H
•Level Order: F, B, G, A, D, I, C
B G
A
D
C E
I
H
•Level Order: F, B, G, A, D, I, C
F
B G
A
D
C E
I
H
•Level Order: F, B, G, A, D, I, C, E
B G
A
D
C E
I
H
•Level Order: F, B, G, A, D, I, C, E
F
B G
A
D
C E
I
H
•Level Order: F, B, G, A, D, I, C, E, H
DONE!
B G
A
D
C E
I
H
•Level Order: F, B, G, A, D, I, C, E, H
DONE!
F
B G
A
D
C E
I
H
•Pre-order: F
B G
A
D
C E
I
H
•Pre-order: F
F
B G
A
D
C E
I
H
•Pre-order: F, B
B G
A
D
C E
I
H
•Pre-order: F, B
F
B G
A
D
C E
I
H
•Pre-order: F, B, A
B G
A
D
C E
I
H
•Pre-order: F, B, A
F
B G
A
D
C E
I
H
•Pre-order: F, B, A, D
B G
A
D
C E
I
H
•Pre-order: F, B, A, D
F
B G
A
D
C E
I
H
•Pre-order: F, B, A, D, C
B G
A
D
C E
I
H
•Pre-order: F, B, A, D, C
F
B G
A
D
C E
I
H
•Pre-order: F, B, A, D, C, E
B G
A
D
C E
I
H
•Pre-order: F, B, A, D, C, E
F
B G
A
D
C E
I
H
•Pre-order: F, B, A, D, C, E, G
B G
A
D
C E
I
H
•Pre-order: F, B, A, D, C, E, G
F
B G
A
D
C E
I
H
•Pre-order: F, B, A, D, C, E, G, I
B G
A
D
C E
I
H
•Pre-order: F, B, A, D, C, E, G, I
F
B G
A
D
C E
I
H
•Pre-order: F, B, A, D, C, E, G, I, H
DONE!
B G
A
D
C E
I
H
•Pre-order: F, B, A, D, C, E, G, I, H
DONE!
F
B G
A
D
C E
I
H
•In-order (sorted): A
B G
A
D
C E
I
H
•In-order (sorted): A
F
B G
A
D
C E
I
H
•In-order (sorted): A, B
B G
A
D
C E
I
H
•In-order (sorted): A, B
F
B G
A
D
C E
I
H
•In-order (sorted): A, B, C
B G
A
D
C E
I
H
•In-order (sorted): A, B, C
F
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D
F
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D, E
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D, E
F
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D, E, F
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D, E, F
F
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D, E, F, G
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D, E, F, G
F
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D, E, F, G, H
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D, E, F, G, H
F
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D, E, F, G, H, I
DONE!
B G
A
D
C E
I
H
•In-order (sorted): A, B, C, D, E, F, G, H, I
DONE!
F
B G
A
D
C E
I
H
•Post-order: A
B G
A
D
C E
I
H
•Post-order: A
F
B G
A
D
C E
I
H
•Post-order: A, C
B G
A
D
C E
I
H
•Post-order: A, C
F
B G
A
D
C E
I
H
•Post-order: A, C, E
B G
A
D
C E
I
H
•Post-order: A, C, E
F
B G
A
D
C E
I
H
•Post-order: A, C, E, D
B G
A
D
C E
I
H
•Post-order: A, C, E, D
F
B G
A
D
C E
I
H
•Post-order: A, C, E, D, B
B G
A
D
C E
I
H
•Post-order: A, C, E, D, B
F
B G
A
D
C E
I
H
•Post-order: A, C, E, D, B, H
B G
A
D
C E
I
H
•Post-order: A, C, E, D, B, H
F
B G
A
D
C E
I
H
•Post-order: A, C, E, D, B, H, I
B G
A
D
C E
I
H
•Post-order: A, C, E, D, B, H, I
F
B G
A
D
C E
I
H
•Post-order: A, C, E, D, B, H, I, G
B G
A
D
C E
I
H
•Post-order: A, C, E, D, B, H, I, G
F
B G
A
D
C E
I
H
•Post-order: A, C, E, D, B, H, I, G, F
DONE!
B G
A
D
C E
I
H
•Post-order: A, C, E, D, B, H, I, G, F
DONE!
#include <iostream>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
};
// New node creation
struct node* newNode(int data)
{
struct node* node = (struct node*) malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// Pre-order Traversal
void traversePreOrder(struct node* temp)
{
if (temp != NULL) {
cout << " " << temp->data;
traversePreOrder(temp->left);
traversePreOrder(temp->right);
}
}
// In-order Traversal
voidtraverseInOrder(structnode* temp)
{
if (temp != NULL) {
traverseInOrder(temp->left);
cout << " " << temp->data;
traverseInOrder(temp->right);
}
}
// Post-order Traversal
voidtraversePostOrder(structnode* temp)
{
if (temp != NULL) {
traversePostOrder(temp->left);
traversePostOrder(temp->right);
cout << " " << temp->data;
}
}
int main()
{
structnode* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
cout << "Pre-order traversal: ";
traversePreOrder(root);
cout << "\nIn-order traversal: ";
traverseInOrder(root);
cout << "\nPost-order traversal: ";
traversePostOrder(root);
}
Binary Tree
C++
implementation
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
};
// New node creation
struct node* newNode(int data)
{
struct node* node = (struct node*) malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// Pre-order Traversal
void traversePreOrder(struct node* temp)
{
if (temp != NULL) {
cout << " " << temp->data;
traversePreOrder(temp->left);
traversePreOrder(temp->right);
}
}
// In-order Traversal
voidtraverseInOrder(structnode* temp)
{
if (temp != NULL) {
traverseInOrder(temp->left);
cout << " " << temp->data;
traverseInOrder(temp->right);
}
}
// Post-order Traversal
voidtraversePostOrder(structnode* temp)
{
if (temp != NULL) {
traversePostOrder(temp->left);
traversePostOrder(temp->right);
cout << " " << temp->data;
}
}
int main()
{
structnode* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
cout << "Pre-order traversal: ";
traversePreOrder(root);
cout << "\nIn-order traversal: ";
traverseInOrder(root);
cout << "\nPost-order traversal: ";
traversePostOrder(root);
}
Binary Tree
C++
implementation
Trees Applications
–File Systems where directories and files are organized in a hierarchical structure.
–Expression Parsing and Evaluation.
–Searching (Binary Search Trees (BST), AVL Trees, Red-Black Trees, …, etc.).
–Network Routing (Spanning Trees).
–Databases (B-trees, B+ trees, …, etc.) for database indexing.
–Artificial Intelligence (Decision Trees, Minimax Trees, …, etc.).
–File Systems where directories and files are organized in a hierarchical structure.
–Expression Parsing and Evaluation.
–Searching (Binary Search Trees (BST), AVL Trees, Red-Black Trees, …, etc.).
–Network Routing (Spanning Trees).
–Databases (B-trees, B+ trees, …, etc.) for database indexing.
–Artificial Intelligence (Decision Trees, Minimax Trees, …, etc.).
Dictionary of Algorithms and
Data Structures
Data Structures
End of lecture 3
Thank You!
Thank You!
Download
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 86
- Slides 106
- Age 451 days
Related Slideshows
11
8-top-ai-courses-for-customer-support-representatives-in-2025.pptx
JeroenErne2
49 views
10
7-essential-ai-courses-for-call-center-supervisors-in-2025.pptx
JeroenErne2
48 views
13
25-essential-ai-courses-for-user-support-specialists-in-2025.pptx
JeroenErne2
37 views
11
8-essential-ai-courses-for-insurance-customer-service-representatives-in-2025.pptx
JeroenErne2
35 views
21
Know for Certain
DaveSinNM
23 views
17
PPT OPD LES 3ertt4t4tqqqe23e3e3rq2qq232.pptx
novasedanayoga46
26 views