TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Chapter 2. Basic data structures

Michel Toulouse & Nguyễn Khánh Phương

Computer Science department
School of Information and Communication technology
E-mail: phuongnk@[Link]
Contents
2.1. Array
2.2. Record
2.3. Linked List
2.4. Stack
2.5. Queue

2
 Variable declaration
• This first program (basic1.c)
#include <stdio.h> has a single variable, this
#include <stdlib.h> variable has a memory cell
address
int main(){ • The second program
int myvar; (basic1-1.c) assigned the
printf("addr myvar %8u\n",&myvar); number 16 to the 4 memory
} cells starting at addr of
myvar
#include <stdio.h> – Now there is data in the next 4
#include <stdlib.h> cells starting at the address of
myvar
int main(){
int myvar;

myvar = 16;

printf("addr myvar %8u, and value stored at

the addr of myvar %d\n",&myvar,myvar);
} 3
 Computer memory
• Computer memory is made of a
long sequence of memory cells,
each 8 bits (one byte) long
• Associated with each memory
cell is an address
• Variable names in a program are
addresses, i.e. the cell where
the data is stored
– int myvar;
• The type of a variable “int”
defines the number of
consecutive memory cells used
to store the data
– int means 4 consecutive cells are
reserved to store the data of myvar

4
 Variable assignment
#include <stdio.h> • This program (basic3.c)
#include <stdlib.h> copies the value stored
in memory cells starting
at addr var1 into
memory cells starting at
int main(){ the addr of var2
int var1;
int var2;
var1 = 16;
var2= var1;
printf("addr var1 %8u, value var1 %d, value var2 %d\n",
&var1,var1,var2);
}

5
 Example
• This program (basic2.c)
#include <stdio.h> shows that the "type", "int"
#include <stdlib.h> "double", etc, in front of a
int main(){ variable name specifies the
int var1; number of consecutive
double var2; memory cells reserved for
int var3[5]; the variable
printf("addr var1 int %8u\n",&var1); • Print the addr of
printf("addr var2 double %8u\n",&var2); – The first cell of var1
printf("addr var3 array of int %8u\n",&var3); – The first cell of var2
– The first cell of the array var3

6
 Array storage
#include <stdio.h> • This program (basic4.c)
#include <stdlib.h> declares 3 variables, two of
int main(){ them are arrays
int var1; • It shows the consecutive
memory cells used by arrays
int array1[3];
int array2[3];

printf("addr var1%8u\n",&var1);
printf("addr array1 %8u\n",&array1);
printf("addr array2 %8u\n",&array2);

7
How computers compute index addresses
#include <stdio.h> • (basic5.c) array1 is the address
#include <stdlib.h> of the memory cell where this
int main(){ data structure starts
int var1; • However, array1 has storage for
3 int
int array1[3];
• In order to store the value stored
int array2[3];
in var1 in array1[2], the
var1 = 16; computer needs to find the addr
array1[2] = var1; of the memory cell where the
third int starts
printf("addr var1 %8u value var1 %d\ • This is array1 + 8
n",&var1,var1);
printf("addr array1 %8u, addr
array1[2] %8u, value array1[2] %d\
n",&array1, &array1[2],array1[2]);
}
8
 Pointers
• Memory cells may also store
addresses
• In this case we declare a
variable of type pointer
– int* mypointer;
• The previous declaration said
that the cells starting at addr
mypointer will contain the addr
of a memory cell which is the
beginning of an int

9
 Example: pointers
• Print the addr of the memory cells for the var “pointer” and “var1”.
• Print the contain of memory cell “pointer”, empty. Assign the addr of the
memory cell “vars” to the cell of pointer
• Print the contain of memory cell “pointer” and the contain of the addr
stored in memory cell “pointer” (basic6.c)

#include <stdio.h>
#include <stdlib
int main(){
int var1 = 16;
int* pointer;

printf("addr of the memory cell for pointer %8u\n\n",&pointer);

printf("addr of the memory cell for var1 %8u\n\n",&var1);
printf("value stored in the memory cell pointer %8u\n\n",pointer);

pointer = &var1;
printf("value stored in the memory cell pointer %8u\n\n",pointer);
printf("value of the addr stored in memory cell pointer %8u\n",*pointer);
} 10
 Dynamic memory allocation
int main(){
int var1 = 16; • (basic7.c) array2 is of type
int *array2 = NULL; pointer
• malloc allocate consecutive
printf("first array2 %8u\n",array2); memory cells to the program for
3 integers
array2 = (int*)malloc(3*sizeof(int)); • malloc returns the addr of the
first cell of the consecutive
printf("addr array2 %8u\n",array2); memory cells for the integers
• Print
array2[2] = var1; – The addr of the first cell of array2
– The addr of the first cell of the third
integer in array2 (array2[2])
printf("addr array2 %8u, array2[2]
– The value stored in the array2[2]
%8u, value array2[2] %d\
n",&array2[0],&array2[2],array2[2]);
}

11
 ARRAY

• An array is always a sequence of

consecutive memory cells
• The number of memory cells is
– size of array * sizeof(type)

12
2.1. Array
• Imagine that we have 100 scores. We need to read them, process them and print
them. We must also keep these 100 scores in memory for the duration of the
program. We can define a hundred variables, each with a different name, as shown
in Figure1.

Figure 1 A hundred individual variables Figure 2 Processing individual variables

• But having 100 different names creates other problems. We need 100 references to
read them, 100 references to process them and 100 references to write them. Figure
2 shows a diagram that illustrates this problem.

13
2.1. Array
• An array is a sequenced of elements, normally of the same data type, although some
programming languages accept arrays in which elements are of different types.
• We can refer to the elements in the array as the first element, the second element
and so forth, until we get to the last element.

Figure 3. Arrays with indexes

14
2.1. Array
Basic definitions
• An array is a fixed size sequential collection of elements of identical types.
• Array: a set of pairs (index and value)
– data structure: for each index, there is a value associated with that index.
– representation: implemented by using consecutive memory.
• In C/C++/Java: the element in an array are indexed by the integers 0 to n- 1, where
n is the size of the array

15
Array name versus element name
In an array we have two types of identifiers:
• the name of the array
• the name of each individual element.
The name of the array is the name of the whole structure, while the name of an element
allows us to refer to that element.
Example:

the name of the array is scores, and name of each element is the name of the array
followed by the index, for example, scores[0], scores[1], and so on.

16
Array types in C
C supports two types of arrays:
 Fixed Length Arrays : The programmer “hard codes” the length of
the array, which is fixed at run-time.
 Variable-Length Arrays : The programmer doesn’t know the
array’s length until run-time.

17
Declaring an one-dimensional array
To declare an array, we need to specify its data type, the array’s identifier and the
size:

type arrayName [arraySize];

Example: declare int A[5];

to create an array A having 5 elements of integer type (4 bytes for each element)

• The arraySize can be a constant (for fixed length arrays) or a variable (for
variable-length arrays)
– Example: double A[10];
int n;
double A[n];

• Before using an array (even if it is a variable-length array), we must declare and

initialize it!

18
Declaration example: fixed length array

19
Declaring a one-dimensional array
• We can initialize fixed-length array elements when we
define an array.
• If we initialize fewer values than the length of the array, C
assigns zeroes to the remaining elements.

20
Declaring an Array
 So what is actually going on when you set up an array?
Memory:
 Each element is held in the next location along in memory
 Essentially what the computer is doing is looking at the
FIRST address (which is pointed to by the variable p) and
then just counts along.

21
Accessing Elements
To access an array’s element, we need to provide an integral
value to identify the index we want to access.
• We can do this using a constant: scores[0];
• We can also use a variable:
for(i = 0; i < 9; i++)
scoresSum += scores[i];

22
Example
Write a C program that gives the address of each element of an 1D array:
#include <stdio.h>
int main()
Result in DevC
{ int A[ ] = {5, 10, 12, 15, 4}; (sizeof(int)=4)
int rows=5;
/* print the address of 1D array using pointer */
int *ptr = A;
printf("Address Contents\n");
for (int i=0; i < rows; i++)
printf("%8u %5d\n", ptr+i, *(ptr+i));
}

ptr+i : address of element A[i]

*(ptr+i) : content of element A[i] Result in turboC
(sizeof(int)=2)
Memory Location(A[i]) = start_address + W*i
Address Contents
5 10 12 15 4 65516 5
65518 10
65520 12
65522 15
65524 4
start_address=6487536
Arrays in C
int list[5], *plist[5];
list[5]: five integers
list[0], list[1], list[2], list[3], list[4]
*plist[5]: five pointers to integers
plist[0], plist[1], plist[2], plist[3], plist[4]
Implementation of 1-D array
list[0] start address = 
list[1]  + sizeof(int)
list[2]  + 2*sizeof(int)
list[3]  + 3*sizeof(int)
list[4]  + 4*sizeof(int)

• Compare int *list1 and int list2[5]:

Same: list1 and list2 are pointers.
Difference: list2 reserves five locations.
Notations:
list2 : a pointer to list2[0]
(list2 + i) : a pointer to list2[i] (&list2[i])
*(list2 + i) : content of list2[i]
Declaring two-dimensional array
• How to declare:
<element-type> <arrayName> [size1][size2];
Example: double a[3][4];
may be shown as a table

• Using the two-dimensional array initializer

Example: int a[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12};
• Access to element of array: a[2] [1]; a[0][0] = 1 a[0][1]=2 a[0][2]=3 a[0][3]=4

a[1][0] = 5 a[1][1]=6 a[1][2]=7 a[1][3]=8

a[2][0] = 9 a[2][1]=10 a[2][2]=11 a[2][3]=12

Representation of Arrays
• Multidimensional arrays are usually implemented by one
dimensional array via either row major order or column
major order.
Row-Major Mapping (e.g. Pascal, C/C++)
 Row- major order is a method of representing multi-dimensional array in sequential memory. In
this method, elements of an array are arranged sequentially row by row. Thus, elements of the first
row occupies the first set of memory locations reserved for the array, elements of the second row
occupies the next set of memory and so on.
Elements of Elements of Elements of Elements of
…. ……..
Row 0 Row 1 Row 2 Row i

 Example: int a[4][3]

in ascending direction of memory address

a[0][0] a[0][1] a[0][2]

row 0 row 1 row 2 row 3

Two Dimensional Array Row Major Order

Col 0 Col 1 Col 2 Col c

Row 0 X X X X

Row 1 X X X X

Row r X X X X

c c
elements elements

Row 0 Row 1 Row i Row r

i * c element
Column-Major Mapping (e.g. Matlab, Fortran)
 In this method, elements of an array are arranged sequentially column by
column. Thus, elements of the first column occupies the first set of memory
locations reserved for the array, elements of the second column occupies the
next set of memory and so on.
Elements of Elements of Elements of Elements of
…. ……..
column 0 column 1 column 2 column i

 Example 3 x 4 array:
abcd
efgh
i jkl
Convert into 1D array Y by collecting elements by columns.
 Within a column elements are collected from top to bottom.
 Columns are collected from left to right.

Thus, we get Y[ ] =
{a, e, i, b, f, j, c, g, k, d, h, l}
Row- and Column-Major Mappings
2D array: r rows, c columns
Example: int a[3][6]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};
a[0][0]=0 a[0][1]=1 a[0][2]=2 a[0][3]=3 a[0][4]=4 a[0][5]=5
a[1][0]=6 a[1][1]=7 a[1][2]=8 a[1][3]=9 a[1][4]=10 a[1][5]=11
a[2][0]=12 a[2][1]=13 a[2][2]=14 a[2][3]=15 a[2][4]=16 a[2][5]=17

Memory: row-major order

c elements of c elements of c elements of c Elements of
…. ……..
Row 0 Row 1 Row 2 Row r

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

6 elements of row 0 6 elements of row 1 6 elements of row 2

Memory: column-major order

r Elements of r Elements of r Elements of r Elements of
…. ……..
column 0 column 1 column 2 column i

0 6 12 1 7 13 2 8 14 3 9 15 4 10 16 5 11 17

3 elements of col 0 3 elements of col 5

Locating Element x[i][j]: row-major order
 Assume x:
 has r rows and c columns (thus, each row has c elements)

c elements of c elements of c elements of c Elements of

…. ……..
Row 0 Row 1 Row 2 Row r-1

 Locating element x[i][j]:

 i rows to the left of row 0  so i*c elements to the left of x[i][0]
 x[i][j] is mapped to position: i*c + j of the 1D array
 The location of element x[i][j]:

Location(x[i][j]) =start_address + W * (i*c + j)

Where
• start_address: the address of the first element (x[0][0]) in the array
• W: is the size of each element
• c: number of columns in the array
Example
Write a C program that gives the address of each element of a 2D array:
Result in DevC
#include <stdio.h>
(sizeof(int)=4)
int main()
{ int a[3] [4] = {1,2,3,4,5,6,7,8,9,10,11,12};
int rows=3, cols =4;
/* print the address of 2D array by using pointer */
int *ptr = a;
printf("Address Contents\n");
for (int i=0; i < rows; i++)
for (int j=0; j < cols; j++)
printf("%8u %5d\n", ptr +((i*cols)+j), *(ptr + ((i*cols)+j)) );}

Memory Location(a[i][j]) = start_address + W*[(i*cols) + j]

1 2 3 4 5 6 7 8 9 10 11 12

Location(a[1][2]) = ?
start_address=6487488
Example row-major order: Memory allocation for 2D array (type int)

• Address (location) of elements in General: Declare

2D array: int a[m][n];
int a[4][3] • Assume: the address of the first
a[0][0] address =  element (a[0][0]) is .
a[0][1]  + 1*sizeof(int) • Then, the address of element a[i]
a[0][2]  + 2*sizeof(int) [j] is:
a[1][0]  + 3*sizeof(int)  + (i*n + j)*sizeof(int)
a[1][1]  + 4*sizeof(int)
a[1][2]  + 5*sizeof(int)
a[2][0]  + 6*sizeof(int)
...
Locating Element x[i][j]: column-major order
r Elements r Elements r Elements r Elements of
 Assume x: ….. of column 0 of column 1 of column 2 …. columns i …….

 has r rows and c columns (thus, each column has r elements)

 Locating element x[i][j]:
 j columns to the left of column 0  so j*r elements to the left of x[0][j]
 x[i][j] is mapped to position: j*r + i of the 1D array
 The location of element x[i][j]:

Location(x[i][j]) = start_address + W * (j*r + i)

Where
• start_address: the address of the first element in the array
• W: is the size of each element
• c: number of columns in the array

Example: array : int a[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};

Determine the address of the element a[1][2] if start_address = 6487488

Example 1: Row- and Column-Major Mappings
2D array: a[0][0] = 1 a[0][1]=2 a[0][2]=3 a[0][3]=4

int a[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12}; a[1][0] = 5 a[1][1]=6 a[1][2]=7 a[1][3]=8

a[2][0] = 9 a[2][1]=10 a[2][2]=11 a[2][3]=12

Memory: row-major order

Location(a[i][j]) = start_address + W*[(i*cols) + j]
1 2 3 4 5 6 7 8 9 10 11 12

start_address=6487488 Location(a[1][2]) = ?

Memory: column-major order

Location(a[i][j]) = start_address + W*[(j*rows) + i]
1 5 9 2 6 10 3 7 11 4 8 12

Location(a[1][2]) = ?
start_address=6487488
Example 2: Row- and Column-Major Mappings
2D array: r rows, c columns
Example: int a[3][6]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};
a[0][0]=0 a[0][1]=1 a[0][2]=2 a[0][3]=3 a[0][4]=4 a[0][5]=5
a[1][0]=6 a[1][1]=7 a[1][2]=8 a[1][3]=9 a[1][4]=10 a[1][5]=11
a[2][0]=12 a[2][1]=13 a[2][2]=14 a[2][3]=15 a[2][4]=16 a[2][5]=17

Memory: row-major order start_address = 1000  Location(a[1][4]) = ?

c elements of c elements of c elements of c Elements of
…. ……..
Row 0 Row 1 Row 2 Row r

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

6 elements of row 0 6 elements of row 1 6 elements of row 2

Memory: column-major order

r Elements of r Elements of r Elements of r Elements of
…. ……..
column 0 column 1 column 2 column i

0 6 12 1 7 13 2 8 14 3 9 15 4 10 16 5 11 17

3 elements of col 0 3 elements of col 5

Example: Memory mapping
• char A[3][4]; // row-major
• logical structure physical structure
0 1 2 3 A[0][0]
0 A[0][1]
1 A[0][2]
A[0][3]
2
A[1][0]
A[2][1] A[1][1]
A[1][2]
A[1][3]

Mapping (location):
Location(A[i][j]) = Location(A[0][0])+ i*4+j
Assume I declare a 2-dimensional array int A[2]
[7]={1,2,3,4,5,6,7,8,9,10,11,12,13,14}. Let also assume that an "int" is
4 bytes long.

1. List the elements of A as they will appear in the computer memory if

the language stores the array A in row-major order
2. The array A is stored in row-major order starting at address 0 in the
computer memory. What is the address of A[1][3]?
3. The array A is stored in row-major order starting at address 0 in the
computer memory. Which value of A is stored at address 32?
4. List the elements of A as they appear in the computer memory if the
language stored the array A in column-major order
5. The array A is stored in column-major order starting at address 0 in
the computer memory. What is the address of A[1][3]?
6. The array A is stored in column-major order starting at address 0 in
the computer memory. Which value is stored at address 20?

11.
38
Operations on the array
• The common operations on arrays are searching, insertion, deletion,
retrieval and traversal.
Example: Given an array S consists of n integers: S[0], S[1], …, S[n-1]
– Search operation: search a value whether appears in the array S or not
function Search(S,value) returns true if value appears in S; false
otherwise
– Retrieval operation: get the value of the element at index i of the array S
function Retrieve(S, i): returns the value S[i] if 0 <= i <= n-1
– Traversal operation: print the value of all elements in the array S
function PrintArray(S, n)
– Insert operation: insert a value into the array S
– Delete operation: delete the element at index i of the array S
• Although searching, retrieval and traversal of an array is an easy job,
insertion and deletion is time consuming. The elements need to be
shifted down before insertion and shifted up after deletion.
Inserting an element into an array
• Assume we need to insert 8 into an array already be sorted in ascending order:

1 3 3 7 12 14 17 19 22 30

• We can do it by shifting to the right one cell for all the elements after the mark
– It thus need to remove 30 from the array

1 3 3 7 8 12 14 17 19 22 30

• Moving all elements of the array is a slow operation (requires linear time O(n)
where n is the size of array)
Deleting an element from an array
• In order to delete an element, we need to shift to the left all previous elements

1 3 3 7 8 12 14 17 19 22

1 3 3 7 12 14 17 19 22 ?

• Delete operation is a slow operation.

• Regular implementation of this operation is undesirable.
• Delete operation makes the last index free
– How we could mark the last index of the array being free?
• We need variable to store the size of the array
Example: variable size is used to store the size of the array. Before
deletion, size = 10. After deletion, we need to update the value of size:
size = 10 – 1 = 9
Operations on the array
Thinking about the operations discussed in the previous
section gives a clue to the application of arrays. If we have a
list in which a lot of insertions and deletions are expected
after the original list has been created, we should not use an
array. An array is more suitable when the number of
deletions and insertions is small, but a lot of searching and
retrieval activities are expected.

i
An array is a suitable structure when a small number of
insertions and deletions are required, but a lot of
searching and retrieval is needed.
Represent Matrices based on arrays
• m x n matrix is a table with m rows and n columns, but numbering begins at 1
rather than 0.
• M(i,j) denotes the element in row i and column j.
• Common matrix operations
– transpose
– addition
– Multiplication

• Shortcomings Of Using A 2D Array For A Matrix:

• Indexes are off by 1.
• C arrays do not support matrix operations such as add, transpose, multiply,
and so on.
– Suppose that x and y are 2D arrays. Can’t do x + y, x –y, x * y, etc. in C.
We need to develop functions to support all matrix operations.
Sparse Matrix

col1 col2 col3 col4 col5 col6

row1  15 0 0 22 0  15
row2
 0 11 3 0 0 0 
 
row3  0 0 0  6 0 0
 
row4  0 0 0 0 0 0 
row5
 91 0 0 0 0 0
 
5*3 row6  0 0 28 0 0 0 6*6

15/15 8/36

sparse matrix
data structure?
Sparse Matrix
(1) Represented by a two-dimensional array (e.g. int M[6][6];)
• Sparse matrix wastes space.
(2) Each element is characterized by <row, col, value>.
• The terms in A should be ordered based on <row, col>
col1 col2 col3 col4 col5 col6 row col value
row1  15 0 0 22 0  15 A [0] 1 1 15 A[0][0] = 1;
row2
 0 11 3 0 0 0  [1] 1 4 22
A[0][1] = 1;
  A[0][2] = 15
row3  0 0 0  6 0 0 [2] 1 6 -15
  [3] 2 2 11
row4  0 0 0 0 0 0 [4] 2 3 3

row5 91 0 0 0 0 0 [5] 3 4 -6 A[5][0] = 3;
  [6] 5 1 91
A[5][1] = 4;
row6  0 0 28 0 0 0 6*6 A[5][2] = -6;
[7] 6 2 28
/* Array representation of sparse matrix
//[ ][0] represents row
//[ ][1] represents col
//[ ][2] represents value */
int MAX = 8; //number of elements != 0 in sparse matrix
int A[MAX][3];
Diagonal Matrix
1000
0200
0030
0004
• An n x n matrix in which all nonzero terms are on the diagonal.
• M(i, j) is on diagonal iff i = j
• number of diagonal elements in an n x n matrix is n
• non diagonal elements are zero
• Store diagonal only vs n2 whole:
• int M[5];
• int M[5][5];
Triangular Matrix
100 0
230 0
456 0
7 8 9 10
• An n x n matrix in which all nonzero terms are either on or below the diagonal.
– M(i,j) is part of lower triangle iff i >= j
• Number of elements in lower triangle is
1 + 2 + … + n = n(n+1)/2
• Store n2 whole vs only the lower triangle:
• Store n2 whole:
• Use 2D array A[n][n]
• Store only the lower triangle by:
• Option 1: Map lower triangular into a 1D array
• Option 2: Irregular 2D array
Option 1: Map Lower Triangular Array into a 1D array

Use row-major order, but omit terms that are not part
of the lower triangle.

For the matrix

10 0 0
23 0 0
45 6 0
7 8 9 10
we get 1D array:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Index of element M(i,j) in 1D array
For the matrix M4x4
10 0 0 Row 1
23 0 0
45 6 0
7 8 9 10
we get 1D array:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
0 1 3 6
r 1 r2 r3 … row i

• Order is: row 1, row 2, row 3, …

• Row i is preceded by rows 1, 2, …, i-1
• Size of row i (number of elements in row i ) is i
• Number of elements that precede row i is
1 + 2 + 3 + … + i-1 = i(i-1)/2
 So element M(i, j) is at position i(i-1)/2 + j-1 of the 1D array
• Example: M(3, 2) is at position 3(3-1)/2 + 2-1 = 4
Option 2: Map Lower Triangular Array into Irregular 2D Arrays

x[] Store only the lower triangle:

1 100 0
2 3 230 0
456 0
4 5 6
7 8 9 10
7 8 9 l0

Irregular 2-D array: the length of rows is not required to be the same.
Creating and Using Irregular 2D Arrays
// STEP 1: declare a two-dimensional array variable
int ** iArray = new int*[numberOfRows];
OR:
int ** iArray;
malloc(iArray, numberOfRows*sizeof(*iArray));
//STEP 2: allocate the desired number of rows
// now allocate space for elements in each row
for (int i = 0; i < numberOfRows; i++)
iArray[i] = new int [length[i]];
OR:
for (int i = 0; i < numberOfRows; i++)
malloc(iArray[i], length[i]*sizeof(int));
// STEP 3: use the array like any regular array:
iArray[2][3] = 5;
iArray[4][6] = iArray[2][3]+2;
iArray[1][1] += 3;
Contents
2.1. Array
2.2. Record
2.3. Linked List
2.4. Stack
2.5. Queue

52
Record
• A record is an array where the elements have different types
• In C, the declaration of a variable of type record starts with the reserved
word “struct”
• Then the type and the name of the fields in the record are defined
• Finally, the name of the variable record is given
• To assign a value to a field of a record, we must first name the record and
then the field (record1.c)

int main(){
struct {
int num;
int deno;
}fraction;
[Link] = 13;
[Link] = 17;
printf("num %d, deno %d\n", [Link], [Link]);
} 53
 Records: consecutive memory cells
• Show that record is made of consecutive memory cells like for
arrays (record2.c)
• The difference is the fields have different types and names
• In a program we refer to those fields using names but actually the
computer find the addr of cells in those fields in the same way as for
arrays
• To find the addr of field x
– Addr of the first cell of the record + number of bytes used by all the
fields before x (number of bytes depend on the type of each field)

int main(){
struct {
int num;
int deno;
}fraction;
printf("addr fraction %8u, addr num %8u, addr deno %8u\
n",&fraction,&[Link],&[Link]);
54
}
A second example of record (record3.c)
int main(){
struct {
int id;
char* name; /*string of characters*/
char grade;
}student;

printf("addr student %8u, addr id %8u, addr name %8u, addr grade %8u\
n",&student,&[Link],&[Link],&[Link]);

[Link] = 2021;
[Link] = "Big-X";
[Link]= 'A';

printf("id %d, name %s, grade %c\n",[Link], [Link], [Link]);

55
 An array of records
• Print the addr of the first cell of each record (record4.c)
• Print the addr of the second and third field of each record
• Assig values to different fields and different records and print the assigned values
int main(){
struct {
int id;
char* name;
char grade;
}student[3];
printf("addr of student records, student[0] %8u, student[1] %8u, student[2] %8u\n\
n",&student[0],student[1],student[2]);
printf("addr of fields in student[0], name %8u, grade %8u\n\n",&student[0].name,&student[0].grade);
printf("addr of fields in student[1], name %8u, grade %8u\n\n",&student[1].name,&student[1].grade);
printf("addr of fields in student[2], name %8u, grade %8u\n\n",&student[2].name,&student[2].grade);
student[0].id = 2021;
student[1].name = "Big-X";
student[2].grade= 'A’;
printf("id %d, name %s, grade %c\n",student[0].id, student[1].name, student[2].grade);
}

56
 Typedef & dynamic memory allocation for rec
• Now student is a type (not a variable), does not have a memory addr (record5.c)
• Minh is a pointer, will store the addr of the first cell of a record of type student
• malloc allocate memory cells for a data structure of type student
• Print the addrs of Minh and the fields in the record. Assign values to the fields and print those values
• Since Minh is a pointer, we must reference the fields of the object to which it points using “->”

int main(){
typedef struct {
int id;
char* name;
char grade;
}student;
student* Minh;
Minh = (student*)malloc(sizeof(student));

printf("addr Minh %8u addr Minh id %8u, addr Minh name %8u, addr Minh grade %8u\n\
n",&Minh,&Minh->id,&Minh->name,&Minh->grade);

Minh->id = 2021;
Minh->name = "Minh";
Minh->grade= 'A';
printf("id %d, name %s, grade %c\n",Minh->id, Minh->name, Minh->grade);
} 57
2.2. Record
• A record is a collection of related elements, possibly of different types, having a
single name.
• Each element in a record is called a field:
– A field has a type and exists in memory.
– Fields can be assigned values, which in turn can be accessed for selection or
manipulation.
• Example: Figure below contains two examples of records.
– The first example: fraction has two fields: numerator and denominator, both of
which are integers.
– The second example: student has three fields (id, name, grade) made up of three
different types.

58
2.2. Record
• Example:

struct {
int numerator;
int denominator;
} fraction;
[Link] = 13;
[Link] = 17;

59
Record name vs. field name
Just like in an array, we have two types of identifier in a record:
• the name of the record, and
• the name of each individual field inside the record.
The name of the record is the name of the whole structure, while the name of each field
allows us to refer to that field.
Example: in the student record:
• the name of the record is student,
• the name of the fields are [Link], [Link] and [Link].
Most programming languages use a period (.) to separate the name of the structure
(record) from the name of its components (fields).

60
Comparison of records and arrays
We can compare an array with a record. This helps us to understand when we should
use an array and when to use a record:
• An array defines a combination of elements, while a record defines the identifiable
parts of an element.
• For example, an array can define a class of students (40 students), but a record
defines different attributes of a student, such as id, name or grade.
• Array of records: If we need to define a combination of elements and at the same
time some attributes of each element, we can use an array of records. For example,
in a class of 30 students, we can have an array of 30 records, each record
representing a student.

61
Figure 1. Array of records
Contents
2.1. Array
2.2. Record
2.3. Linked List
2.4. Stack
2.5. Queue

62
2.3. Linked list
• Singly linked list

10 8 20
head

• Doubly linked list

10 8 20
head

• Circular linked list

head

10 8 20
 Create the first record of type node
• Define a type record name node. The second field is a pointer to an object of type
node
• Declare a variable “head” that is a pointer to an object of type node
• Then dynamically allocate memory for a record of type node. The addr of the first cell
of this object is stored in head
• Print the addr of head, of fields data and next (linklist1.c)

int main(){
typedef struct {
int data;
struct node* next;
}node;
node* head;
head = (node*)malloc(sizeof(node));

printf("addr head %8u addr head data %8u, addr head next %8u\n\n",head,&head-
>data,&head->next);
}
64
 Create a second record of type node
• (linklist2.c)

int main(){
typedef struct {
int data;
struct node* next;
}node;
node* head;
node* secondNode;
head = (node*)malloc(sizeof(node));
secondNode = (node*)malloc(sizeof(node));

printf("addr head %8u addr head data %8u, addr head next %8u\n\n",head,&head-
>data,&head->next);
printf("addr secondNode %8u addr secondNode data %8u, addr secondNode next
%8u\n\n",secondNode,&secondNode->data,&secondNode->next);
65
 Create a link list of 2 nodes
• A link list of two nodes is generated (linklist3.c)
• Assign memory addresses for two object of type node
• Connect the first node to the second one: head->next = secondNode;
• i.e., place the addr of the second node into the next field of the first node
• The link list starts with the head pointer which points to the addr of the first node
• The link list ends with the next pointer of secondNode which is NULL

node* head;
node* secondNode;
head = (node*)malloc(sizeof(node));
secondNode = (node*)malloc(sizeof(node));

head->data = 1;
head->next = secondNode;
secondNode->data = 2;
secondNode->next = NULL;
} 66
Add a third node to the link list (linklist4.c)
node* head;
node* secondNode;
node* thirdNode;

head = (node*)malloc(sizeof(node));
secondNode = (node*)malloc(sizeof(node));
thirdNode = (node*)malloc(sizeof(node));

head->data = 1;
head->next = secondNode;
secondNode->data = 2;
secondNode->next = thirdNode;
thirdNode->data = 3;
thirdNode->next = NULL;

67
Singly Linked list
• A singly linked list is a sequences of nodes, each node contains 2 parts: data and
reference (address) to the next node.
• Example: Figure shows a singly linked list contains four nodes:

• Keeping track of a singly linked list:

– Must know the pointer to the first element of the list (called start, head, etc.)
– If head is NULL, the singly linked list is empty

10 8 20
head
Singly Linked list
• A singly linked list is a sequences of nodes, each node contains 2 parts: data and
reference (address) to the next node.
• Example: Figure shows a singly linked list contains four nodes:

• Keeping track of a singly linked list:

– Must know the pointer to the first element of the list (called start, head, etc.)
– If head is NULL, the singly linked list is empty
head
a1 a2 ... an NULL

list
Declare singly linked list in C programming language

..
• List of integer numbers:

7 17 4 24
• List of students with data: student’s ID, grade of math and physics

2001 8.5 6.5 2002 7 4.5 … 4001 6.5 9

• List of contacts with data: name, phone number

Crainic 0903210433 Michel 0941341043 … Gendreau 0894312098

 Need to declare:
– the type of data in the node first,
– then the singly linked list consists of (1) data of the node, and (2) the pointer to
store the address of the next node in the list
DECLARE SINGLY LINKED LIST

typedef struct {
..... Define the type of data of the node
}NodeType;

typedef struct {
NodeType data; Define the singly linked list
struct node* next;
}node;
node* head;
This declaration define node which is a record consisting of 2 fields:
• data : stores data of node, has the type NodeType (which was defined in typedef…NodeType,
and could consist of several attributes)
• next : the pointer which stores the address of the next node in the list
Pointer head : store address of the first node in the list
Example1: List of students with data: id of student, marks of 2 subjects: math, physics
typedef struct{
char id[15]; Define the type of data of the node
float math, physics;
}student; data
typedef struct {
student data; next
struct node* next; id math physics
}node;
node* head; A node
DECLARE SINGLY LINKED LIST

typedef struct {
..... Define the type of data of the node
}NodeType;

typedef struct {
NodeType data; Define the singly linked list
struct node* next;
}node;
node* head;
This declaration define node which is a record consisting of 2 fields:
• data : stores data of node, has the type NodeType (which was defined in typedef…NodeType,
and could consist of several attributes)
• next : the pointer which stores the address of the next node in the list
Pointer head : store address of the first node in the list
Example2: List of integer numbers
7 17 4 24
typedef struct {
int data; “int” is the type of node, so do not need to use
struct node* next; “typedef….NodeType” to define the type
}node;
node* head;
data
A node
DECLARE SINGLY LINKED LIST

typedef struct {
..... Define the type of data of the node
}NodeType;

typedef struct {
NodeType data; Define the singly linked list
struct node* next;
}node;
node* head;
This declaration define node which is a record consisting of 2 fields:
• data : stores data of node, has the type NodeType (which was defined in typedef…NodeType,
and could consist of several attributes)
• next : the pointer which stores the address of the next node in the list
Pointer head : store address of the first node in the list
Example 3: List of contacts with data: name and phone number
typedef struct{
char name[15]; Define the type of data of the node
char phone[20];
}contact; data
typedef struct {
contact data; next
struct node* next; name phonenumber
}node;
node* head; A node
Important elements of singly linked list
• head: store the address of the first node in the linked list
• NULL: value of the pointer of the last node in the linked list
• cur: the pointer stored the address of current node
cur
head (or root)

NULL
• Allocate memory for a new node pointed by the pointer newNode in the list:
node *newNode = (node *) malloc(sizeof(node));
• Access to the data of the node pointed by pointer newNode :
newNode->data
• Free memory allocated for node pointed by pointer newNode :
free(newNode); newNode
74
Operations on singly linked Lists
• Traverse the singly linked list
• Insert a node into the singly linked list
• Delete a node from the singly linked list
• Search data in the singly linked list
Operations on singly linked Lists
• Traverse the singly linked list
• Insert a node into the singly linked list
• Delete a node from the singly linked list
• Search data in the singly linked list
Traversing a singly linked list
for ( cur = head; cur != NULL; cur = cur->next )
showData_Of_Current_Node( cur->data );

cur

head NULL
• Change the value of the pointer cur
• Finish to browse the list when the NULL value is encountered

cur

77
head NULL
Exercise 1
• A sequence of integers is stored by a singly linked list.
typedef struct Node{
int data;
struct Node *next;
}Node;
Node *head;

a. Create a list stored 3 integers: 1, 2, 3

b. Print the list of these 3 integers

head

1 2 3
NULL
78
head secon third
d

1 2 3
NULL
cur

Data = 1
Data = 2
Data = 3

79
Operations on singly linked lists
• Traverse the singly linked list
• Insert a node into the singly linked list
• Delete a node from the singly linked list
• Search data in the singly linked list
Operations on singly linked list: Insertion
Insert a new node :
• At the beginning of the list
• After the position pointed by the pointer cur
• Before the position pointed by the pointer cur
• At the end of the list

cur
head

…
Operations on singly linked list: Insertion
Insert a new node:
• At the beginning of the list
<create a new node new_node>;
new_node ->next = head;
head= new_node;

head

…
node *Insert_ToHead(node *head, NodeType X)
{ node *new_node;
new_node = (node *) malloc(sizeof(node));
new_node->data = X;
new_nod new_node->next = head;
head=new_node;
e return head;
}

82
Operations on singly linked list: Insertion
Insert a new node :
• At the beginning of the list
• After the position pointed by the pointer cur
• Before the position pointed by the pointer cur
• At the end of the list

cur
head

…
Operations on singly linked list: Insertion
• Insert a new node after the node pointed by the pointer cur:
<create a new node new_node>;
new_node ->next = cur->next;
cur->next = new_node;

cur
head

new_nod 84
Operations on singly linked list: Insertion
• Insert a new node after the node pointed by the pointer cur:
<create a new node new_node>;
new_node ->next = cur->next;
cur->next = new_node;

Write a function to insert a node with data = X (having the type «NodeType » after the
node pointed by the pointer cur. The function returns the address of the new node:

node *Insert_After(node *cur, NodeType X)

{ node *new_node;
new_node = (node *) malloc(sizeof(node)); //(1)
new_node -> data = X; //(1)
new_node->next = cur->next; //(2)
cur->next = new_node; //(3)
return new_node;
}

85
Operations on singly linked list: Insertion
• Insert a new node after the node pointed by the pointer cur:
<create a new node new_node>; ?? Empty list
new_node ->next = cur->next;
cur->next = new_node;
// wrong implementation:
cur->next = new_node;
new_node ->next = cur->next;
cur
head

new_nod 86
Operations on singly linked list: Insertion
• Insert a new node after the node pointed by the pointer cur:
<create a new node new_node>;
?? Empty list
new_node ->next = cur->next;
cur->next = new_node;

<create a new node new_node>;

if (head == NULL) { /* list does not have any node yet */
head = new_node;
cur = head;
}
else {
new_node ->next = cur->next;
cur->next = new_node;
}

87
Operations on singly linked list: Insertion
Insert a new node :
• At the beginning of the list
• After the position pointed by the pointer cur
• Before the position pointed by the pointer cur
• At the end of the list

cur
head

…
Operations on singly linked list: Insertion
Insert a new node before the node pointed by the pointer cur
<create a new node new_node>; ?? List does not have any node yet
prev->next = new_node;
new_node>next = cur; ?? cur is the first node in the list

prev cur
head
…

Insert a new 89
node:
Operations on singly linked list: Insertion
Insert a new node before the node pointed by the pointer cur
<create a new node new_node>; ?? List does not have any node yet
prev->next = new_node;
new_node->next = cur; ?? cur is the first node in the list

<create a new node new_node>;

if (head == NULL) { /* list does not have any node yet */
head = new_node;
cur = head;
}
else if (cur == head) { //cur us the first node in the list
head = new_node;
new_node->next = cur;
}
else {
prev->next = new_node;
new_node->next = cur;
}

90
Operations on singly linked list: Insertion
Insert a new node: head
• At the beginning
• After the node pointed by cur
• Before the node pointed by cur
…
• At the end of the list
<create a new node new_node>;
if (head == NULL) { /* list does not have any node yet*/
head = new_node;
}
else {
//move the pointer to the end of the list:
node *last =head;
while (last->next != NULL) last = last->next;
//Change the pointer next of the last node:
last->next = new_node;
}
node *Insert_ToLast(node *head, NodeType X)
{ node *new_node;
new_node = (node *) malloc(sizeof(node));
new_node->data = X;
if (head == NULL) head = new_node;
else
{
.… Complexity is node *last;
last=head;
while (last->next != NULL) // move to the last node
last = last->next;
last->next = new_node;
}
return head; 91
}
Operations on singly linked Lists
• Traverse the singly linked list
• Insert a node into the singly linked list
• Delete a node from the singly linked list
• Search data in the singly linked list
Operations on singly linked lists: Deletion
• Delete a node
• Delete all nodes of the list
Operations on singly linked lists: Deletion
Delete a node:
• The first node of the list
head
≡del

• Middle/last node of the list

del
head

94
Delete the first node of the list
• Delete the node del that is currently the first node of the list:
head = del->next;
free(del);

del

head NULL

95
Delete the node in the middle/end of the list
Delete node del that is currently the middle/last node of the list:
<Determine the pointer prev pointed to the previous node of del>;
prev->next = del->next; //modify the link
free(del); //delete node del to free memory

prev del
head

prev del
head

NULL
96
Delete the node at the middle/end of the list
Delete node del that is currently the middle/last node of the list:

<Determine the pointer prev pointed to the previous node of del>;

prev->next = del->next; //modify the link
free(del); //delete node del to free memory)

Node *prev =head;

while (prev->next != del) prev = prev->next;

prev del
head

…
97
Delete the node at the middle/end of the list
Delete node del that is currently the middle/last node of the list:

<Determine the pointer prev pointed to the previous node of del>;

prev->next = del->next; //modify the link
free(del); //delete node del to free memory)

Node *prev =head;

while (prev->next != del) prev = prev->next;

prev del
head

…
98
Delete a node pointed by the pointer del
Write the function node *Delete_Node(node *head, node *del)
to delete a node pointed by the pointer “del” of the list with the first node pointed by the pointer “head”.
The function returns the address of the first node in the list after deletion:

node *Delete_Node(node *head, node *del)

{
if (head == del) //del is the first node of the list:
{
head = del->next;
free(del);
}
else{
node *prev = head;
while (prev->next != NULL) prev = prev->next;
prev->next =del->next;
free(del);
}
return head;
} 99
Operations on singly linked lists: Deletion
• Delete a node
• Delete all nodes of the list
Freeing all nodes of a list

del = head ;
while (del != NULL)
{
head = head->next;
free(del);
del = head;
}

Traverse elements one by one from the head till the end
head

1 2 3

del
10
1
Freeing all nodes of a list

del = head ;
while (del != NULL)
{
head = head->next;
free(del);
del = head;
}

head

2 3

del
10
2
Freeing all nodes of a list

del = head ;
while (del != NULL)
{
head = head->next;
free(del);
del = head;
}

head

2 3

del
10
3
Freeing all nodes of a list

del = head ;
while (del != NULL)
{
head = head->next;
free(del);
del = head;
}

head

3 NULL

del
10
4
Freeing all nodes of a list
Write the function node* deleteList(node* head)
to delete all the node in the list having the first node pointed by the pointer head
The function returns the pointer head after deletion
node* deleteList(node* head)
{
node *del = head ;
while (del != NULL)
{
head = head->next;
free(del);
del = head;
}
return head;
}
Check whether the singly linked list is empty or not
Write the function int IsEmpty(node *head)
to check whether the singly linked list is empty or not (the pointer head pointed to the
first node of the list).
The function returns 1 if the list is empty; 0 otherwise

int IsEmpty(node *head) {

if (head == NULL)
return 1;
else return 0;
}
Operations on singly linked Lists
• Traverse the singly linked list
• Insert a node into the singly linked list
• Delete a node from the singly linked list
• Search data in the singly linked list
Searching
• To search for an element, we traverse from head until we locate the object or we reach the end
of the list.
Example: Given a linked list consisting of integer numbers. Count the number of nodes with data
field equal to number x.
int countNodes(int x){
typedef struct { int count = 0;
int data; node* e = head;
struct node* next; while(e != NULL){
}node; if(e->data == x) count++;
node* head; e = e->next;
}
return count;
}

int Result1 = countNodes(24);

Result1 = ?
int a =7; Result2 = ?
int Result2 = countNodes(a);
Time Complexity: Singly-linked lists vs. 1D-arrays

Operation ID-Array Complexity Singly-linked list Complexity

Insert at beginning O(n) O(1)
Insert at end O(1) O(1) if the list has tail reference
O(n) if the list has no tail reference

Insert at middle* O(n) O(n)

Delete at beginning O(n) O(1)
Delete at end O(1) O(n)
Delete at middle* O(n): O(n):
O(1) access followed by O(n) O(n) search, followed by O(1) delete
shift
Search O(n) linear search O(n)
O(log n) Binary search

Indexing: What is O(1) O(n)

the element at a
given position k?

* middle: neither at the beginning nor at the end

Singly-linked lists vs. 1D-arrays

ID-array Singly-linked list

Fixed size: Resizing is expensive Dynamic size

Insertions and Deletions are inefficient: Elements Insertions and Deletions are efficient: No shifting
are usually shifted

Random access i.e., efficient indexing No random access

 Not suitable for operations requiring
accessing elements by index such as sorting

No memory waste if the array is full or almost Extra storage needed for references; however
full; otherwise may result in much memory uses exactly as much memory as it needs
waste.

Sequential access is faster because of greater Sequential access is slow because of low locality
locality of references [Reason: Elements in of references [Reason: Elements not in
contiguous memory locations] contiguous memory locations]
2.3. Linked list
• Singly linked list

10 8 20
head

• Doubly linked list

10 8 20
head
tail
Doubly linked list
• A Doubly Linked List (DLL) contains an extra pointer, typically called previous
pointer, together with next pointer and data which are there in singly linked list

tail

• 2 special nodes: tail and head

– head has pointer prev = null
– tail has pointer next = null
• Basic operations are considered similar as in the singly linked list
Doubly linked list
• Declare doubly linked list to store integer numbers:

10 8 20

head tail

typdedef struct {
int number;
struct dllist *next;
struct dllist *prev;
} dllist;
dllist *head, *tail;
Doubly linked list
• Declare doubly linked list store data of students: ID, marks of math and physics

2001 8.5 6.5 2002 8 5

… 4002 5.5 9.5

head tail
typedef struct{
char id[15];
float math, physics;
}student;

typedef struct {
student data;
struct ddlist* next;
struct ddlist* prev;
}dllist;
dllist *head, *tail;
DOUBLY LINKED LIST – EXAMPLE

typedef struct {
char data;
struct dblist *prev;
struct dblist *next;
}dblist;
dblist node1, node2, node3;

[Link]=‘a’;
[Link]=‘b’;
[Link]=‘c’;
[Link]=NULL; c
NULL a b NULL
[Link]=node2;
[Link]=node1;
[Link]=node3;
[Link]=node2;
[Link]=NULL; 115
Delete a node pointed by the pointer p
void Delete_Node (ddlist *p){
if (head == NULL) printf(”Empty list”);
else {
if (p==head) head = head->next; //Delete first element

else p->prev->next = p->next;

if (p->next!=NULL) p->next->prev = p->prev;
else tail = p->prev;
free(p);
}
}
8 5 12 5

p
head tail
116
Delete a node pointed by the pointer p
void Delete_Node (ddlist *p){
if (head == NULL) printf(”Empty list”);
else {
if (p==head) head = head->next; //Delete first element

else p->prev->next = p->next;

if (p->next!=NULL) p->next->prev = p->prev;
else tail = p->prev;
free(p);
}
}
8 5 12 5

p
head tail
117
Delete a node pointed by the pointer p
void Delete_Node (ddlist *p){
if (head == NULL) printf(”Empty list”);
else {
if (p==head) head = head->next; //Delete first element

else p->prev->next = p->next;

if (p->next!=NULL) p->next->prev = p->prev;
else tail = p->prev;
free(p);
}
}
8 5 12 5

p
head tail
118
Insert a node after the node pointed by pointer p
void Insert_Node (NodeType X, ddlist *p){
if (head == NULL){ // List is empty
head =(ddlist*)malloc(sizeof(ddlist));
head->data = X;
head->prev =NULL;
head->next =NULL;
}
else{
ddlist *newNode;
newNode=(ddlist*)malloc(sizeof(ddlist));
newNode->data = X;
newNode->next = NULL;

newNode->next = p->next;
newNode->prev=p;
if (p->next!=NULL)
p->next->prev=newNode; 12
p->next = newNode;
}
}

8 5 5
119
p
Exercise 2: Create a double linked list store integer numbers
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef struct {
int number;
struct dllist *next;
struct dllist *prev;
} dllist;
dllist *head, *tail;

/* Insert a new node p at the end of the list */

void append_node(dllist *p);
/* Insert a new node p after a node pointed by the pointer after */
void insert_node(dllist *p, dllist *after);
/* Delete a node pointed by the pointer p */
void delete_node(dllist *p);

120
/* Insert a new node p at the end of the list */
void append_node(dllist *p) {
if(head == NULL)
{
head = p;
p->prev = NULL;
}
else {
tail->next = p;
p->prev = tail;
}
tail = p;
p->next = NULL;
}
/* Insert a new node p after a node pointed by the pointer after */
void insert_node(dllist *p, dllist *after) {
p->next = after->next;
p->prev = after;
if(after->next != NULL)
after->next->prev = p;
else
tail = p;
after->next = p;
}
/* Delete a node pointed by the pointer p */
void delete_node(dllist *p) {
if(p->prev == NULL)
head = p->next;
else p->prev->next = p->next;
if(p->next == NULL)
tail = p->prev;
else p->next->prev = p->prev;
}
 int main( ) {
dllist *tempnode; int i;
/* add some numbers to the double linked list */
for(i = 1; i <= 5; i++) {
tempnode = (dllist *)malloc(sizeof(dllist));
tempnode->number = i;
append_node(tempnode);
}
/* print the dll list forward */
printf(" Traverse the dll list forward \n");
for(tempnode = head; tempnode != NULL; tempnode = tempnode->next)
printf("%d\n", tempnode->number);

/* print the dll list backward */

printf(" Traverse the dll list backward \n");
for(tempnode = tail; tempnode != NULL; tempnode = tempnode->prev)
printf("%d\n", tempnode->number);
/* destroy the dll list */
while(head != NULL) delete_node(head);
return 0;
}
Several variants of linked lists
• Some common variants of linked list:
– Circular Linked Lists
– Circular Doubly Linked Lists
– Linked Lists of Lists
• Basic operations on these variants are built similarly to the singly linked list
and the doubly linked list that we consider above.
Circular linked list

list

typedef struct {
NodeType data;
struct node * next; Store data

}next;
Circular Doubly Linked Lists

list

typedef struct {
NodeType data;
struct node * prev;
Store data

struct node * next;

}node;
Linked Lists of Lists
list

Data1 Data2 Data3

DataA DataB DataC

Linked list of lists Application – Sparse matrix
To represent sparse matrix, we could use linked list of lists which consists two lists:
• one list is used to represent the rows and each row contains the list of triples: Column index,
Value(non – zero element) and address field, for non – zero elements.
For the best performance both lists should be stored in order of ascending keys.

// Node to represent triples

typdedef struct
{
int column_index;
int value;
struct value_list *next;
}value_list;

typedef struct
{
int row_number;
struct row_list *link_down;
struct value_list *link_right;
} row_list;
Exercise: Polynomial Addition
Polynomials: defined by a list of coefficients and exponents
- degree of polynomial = the largest exponent in the polynomial

Example:
Polynomials A(x) = 3x10+2x5+6x4+4
B(x) = x4+10x3+3x2+1
To represent a polynomial, the easiest way is to use array a[i] to store the coefficient of xi.
Operations with polynomials such as: Add two polynomials, Multiply two polynomials, ..., are
thus possible to install simply.
Array a ~A(x) a[10] a[9] a[8] a[7] a[6] a[5] a[4] a[3] a[2] a[1] a[0]
3 0 0 0 0 2 6 0 0 0 4

Array b ~B(x) b[4] b[3] b[2] b[1] b[0]

1 10 3 0 1

C(x) = A(x) + B(x) = 3x10+2x5+7x4+3x2+5

c[10] c[9] c[8] c[7] c[6] c[5] c[4] c[3] c[2] c[1] c[0]
Array c
~C(x) =a[10] =a[9] =a[8] =a[7] =a[6] =a[5] =a[4]+b[4] =a[3]+b[3] =a[2]+b[2] =a[1]+b[1] =a[0]+b[0]
=3 =0 =0 =0 =0 =2 =6+1=7 =0+10=10 =0+3=3 =0+0=0 =4+1=5
Exercise: Polynomial Addition
A(x)=2x1000 + x3
B(x)=x4+10x3+3x2+1
Use an array to keep track of the coefficients for all exponents:

… 2 … 0 1 0 0 0 A

… 0 … 1 10 3 0 1 B
1000 … 4 3 2 1 0

A(x) + B(x) = advantage: easy implementation

disadvantage: waste space when sparse
In the case of sparse polynomial (with many coefficients equal to 0), we could
represent polynomial by the linked list: We will build a list containing only the
coefficients with the value not equal to zero together with the exponent.
However, it is more complicated to implement the operations.
Contents
2.1. Array
2.2. Record
2.3. Linked List
2.4. Stack
2.5. Queue

131
What is a stack?
• A stack is a data structure that only allows items to be inserted and removed at one end
– We call this end the top of the stack
– The other end is called the bottom
• Access to other items in the stack is not allowed
• The last element to be added is the first to be removed (LIFO: Last In, First Out)
Operation on stack
• Push: the operation to place a new item at the top of the stack
• Pop: the operation to remove the next item from the top of the stack

M
C C C
R push(M) R item = pop() R
item = M
X X X
A A A
What Are Stacks Used For?
• Real life (Pile of books, Plate trays, etc.)
• More applications related to computer science
– Program execution stack: Most programming languages use a “call stack” to implement
function calling
• When a method is called, its line number and other useful information are pushed
(inserted) on the call stack
• When a method ends, it is popped (removed) from the call stack and execution
restarts at the indicated line number in the method that is now at the top of the stack

1. main pushed onto call stack, before invoking methodA

2. methodA pushed onto call stack, before invoking methodB
3. methodB pushed onto call stack, before invoking methodC
4. methodC pushed onto call stack, invoked then popped out from
the call stack when completes
5. methodB popped out from call stack when completes.
6. methodA popped out from the call stack when completes.
7. main popped out from the call stack when completes. Program
exits.
– Evaluating expressions (e.g. (4/(2-2+3))*(3-4)*2)
What Are Stacks Used For?
• More applications related to computer science
– compilers
• parsing data between delimiters (brackets)
• Check: each “(”, “{”, or “[” has to pair with “)”, “}”, or “]”
Example:
– correct: ( )(( )){([( )])}
– correct: ((( )(( )){([( )])}
– incorrect: )(( )){([( )])}
– incorrect: ({[ ])}
– incorrect: (
– virtual machines
• manipulating numbers
– pop 2 numbers off stack, do work (such as add)
– push result back on stack and repeat
– artificial intelligence
• finding a path
Example: Reversing a Word
• We can use a stack to reverse the letters in a word.
• How?
• Example: READ

Push(R)

Push(E)

Push(A)

D Push(D)
A
• Read each letter in the word and push it onto the stack
E
R
Example: Reversing a Word
• We can use a stack to reverse the letters in a word.
• How?
• Example: READ

Push(R) Pop(D)
Push(E)

Push(A)
Pop(A)

Pop(E)
DA E R
D Push(D) Pop(R)
A
• Read each letter in the word and push it onto the stack
E • When you reach the end of the word, pop the letters off
R the stack and print them out
Implementing a Stack
• At least two different ways to implement a stack
– array
– linked list
• Which method to use depends on the application
– what advantages and disadvantages does each implementation have?
Stack: Array Implementation
• If an array is used to implement a stack what is a good index for the top item?
– Is it position 0?
– Is it position numItems-1?
• Note that push and pop must both work in O(1) time as stacks are usually
assumed to be extremely fast
• Implementing a stack using an array is fairly easy:
– The bottom of the stack is at S[0]
– The top of the stack is at S[numItems-1]
– push onto the stack at S[numItems]
– pop off of the stack at S[numItems-1]

…
S
0 1 2 numItems N
Stack: Array Implementation
Basic operations: typedef .... Item;
static Item *s;
• void STACKinit(int); static int maxSize;//maximum number of elements that the stack could have
static int numItems; //current number of elements on stack
• int STACKempty(); void STACKinit(int maxSize)
{
• void STACKpush(Item); s = (Item *) malloc(maxSize*sizeof(Item));
• numItems = 0;
Item STACKpop(); }
int STACKempty(){return numItems==0;}
int STACKfull() {return numItems==maxSize;}

void STACKpush(Item item)

{
if (Stackfull()) ERROR(“Stack is full”);
else
{ s[numItems] = item;
numItems++;
}
}
Item STACKpop()
{
if (STACKempty()) ERROR(“Stack is empty”)
else
{
numItems--;
return s[numItems+1];
}
}
Array Implementation Summary
• Advantages
– Easy to implement
– best performance: push and pop can be performed in O(1) time
• Disadvantage
– fixed size: the size of the array must be initially specified because
• The array size must be known when the array is created and is fixed, so that the right
amount of memory can be reserved
• Once the array is full no new items can be inserted
• If the maximum size of the stack is not known (or is much larger than the expected
size) a dynamic array can be used
– But occasionally push will take O(n) time

…
S
0 1 2 numItems maxSize
maxSize: maximum number of elements in the array
Stack overflow
• The condition resulting from trying to push an element onto a full stack.
if(STACKfull())
STACKpush(item);
Stack underflow
• The condition resulting from trying to pop an empty stack.
if (STACKempty())
STACKpop(item);
Implementing a Stack: using linked list
• Store the items in the stack in a linked list
• The top of the stack is the head node, the bottom of the stack is the end
of the list
• push by adding to the front of the list
• pop by removing from the front of the list
4.1 2.4 8.9 2.3 NULL

top
3.3
3.3 4.1 2.4 8.9 2.3 NULL
4.1
typedef struct {
2.4 top float item;
struct StackNode *next;
8.9 } StackNode;
typedef struct {
2.3 StackNode *top;
}Stack;
Operations
1. Init:
Stack *StackConstruct();
2. Check empty:
int StackEmpty(Stack* s);
3. Check full:
int StackFull(Stack* s);
4. Insert a new item into stack (Push): insert a new item at the top of stack
int StackPush(Stack* s, float* item);
5. Remove an item from stack (Pop): remove and return the item at the top of stack:
float pop(Stack* s);
6. Print out all items of stack
void Disp(Stack* s);
Initialize stack
Stack *StackConstruct() {
Stack *s;
s = (Stack *)malloc(sizeof(Stack));
if (s == NULL) {
return NULL; // No memory
}
s->top = NULL;
return s;
}

/**** Destroy stack *****/

void StackDestroy(Stack *s) {
while (!StackEmpty(s)) {
StackPop(s);
}
free(s);
}
145
Display all items in the stack
void disp(Stack* s) {
StackNode* node;
int ct = 0; float m;
printf("\n\n List of all items in the stack \n\n");
if (StackEmpty(s))
printf("\n\n >>>>> EMPTY STACK <<<<<\n");
else {
node = s->top;
do {
m = node->item;
printf("%8.3f \n", m);
node = node->next;
} while (!(node == NULL));
}
}
/*** Check empty ***/
int StackEmpty(const Stack *s) {
return (s->top == NULL);
}

/*** Check full ***/

int StackFull() {
printf("\n NO MEMORY! STACK IS FULL");
return 1;
}

147
Push
Need to do the following steps:
(1) Create new node: allocate memory and assign data for new node
(2) Link this new node to the top (head) node
(3) Assign this new node as top (head) node
int StackPush(Stack *s, float item) {
StackNode *node;
node = (StackNode *)malloc(sizeof(StackNode)); //(1)
if (node == NULL) {
StackFull(); return 1; // overflow: out of memory
}
node->item = item; //(1)
node->next = s->top; //(2)
s->top = node; //(3)
return 0;
}
Pop
1. Check whether the stack is empty
2. Memorize address of the current top (head) node
3. Memorize data of the current top (head) node
4. Update the top (head) node: the top (head) node now points to its next node
5. Free the old top (head) node
6. Return data of the old top (head) node

float StackPop(Stack *s) {

float data;
StackNode *node;
if (StackEmpty(s)) //(1)
return NULL; // Empty Stack, can't pop
node = s->top; //(2)
data = node->item; //(3)
s->top = node->next; //(4)
free(node); //(5)
return data; //(6)
}
Experimental program
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <alloc.h>
// all above functions of stacks are put here
int main() {
int ch,n,i; float m;
Stack* stackPtr;
while(1)
{ printf("\n\n======================\n");
printf(“ STACK TEST PROGRAM \n");
printf("======================\n");
printf(" [Link]\n [Link]\n [Link]\n [Link]\n [Link]\n");
printf("----------------------\n");
printf(“Input number to select the appropriate operation: ");
scanf("%d",&ch); printf("\n\n");

150
 switch(ch) {
case 1: printf(“INIT STACK");
stackPtr = StackConstruct(); break;
case 2: printf(“Input float number to insert into stack: ");
scanf("%f",&m);
StackPush(stackPtr, m); break;
case 3: m=StackPop(stackPtr);
if (m != NULL)
printf("\n Data Value of the popped node: %8.3f\n",m);
else {
printf("\n >>> Empty Stack, can't pop <<<\n");}
break;
case 4: disp(stackPtr); break;
case 5: printf("\n Bye! Bye! \n\n");
exit(0); break;
default: printf("Wrong choice");
} //switch
} // end while
} //end main
Implementing a Stack: using linked list
• Advantages:
– always constant time to push or pop an element
– can grow to an infinite size
• Disadvantages
– Difficult to implement
Application 1: Parentheses Matching
Check for balanced parentheses in an expression:
Given an expression, write a program to examine whether the pairs match and the order
is correct of “{“,”}”,”(“,”)”,”[“,”]”.
For example, the program should print true for expression = “[()]{}{[()()]()}” and false
for expression = “[(])”

Algorithm:
1) Declare a character stack S.
2) Now traverse the string expression
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
b) If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack
and if the popped character is the matching starting bracket then fine else parenthesis
are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not
balanced”
Application 2: HTML Tag Matching
In HTML, each <name> has to pair with </name>

<body>
<center>
<h1> The Little Boat </h1>
</center>
The Little Boat
<p> The storm tossed the little
boat like a cheap sneaker in an The storm tossed the little boat
old washing machine. The three like a cheap sneaker in an old
drunken fishermen were used to washing machine. The three
such treatment, of course, but drunken fishermen were used to
not the tree salesman, who even as such treatment, of course, but not
a stowaway now felt that he the tree salesman, who even as
had overpaid for the voyage. </p>
a stowaway now felt that he had
<ol>
<li> Will the salesman die? </li> overpaid for the voyage.
<li> What color is the boat? </li>
<li> And what about Naomi? </li> 1. Will the salesman die?
</ol> 2. What color is the boat?
</body> 3. And what about Naomi?
Application 3: Finding a Path using stack
• Consider the following graph of flights

: city
Z
flight goes from W to S
W S
Y

W S

R P T

X Q
Application 3: Finding a Path using stack
• If it exists, we can find a path from any city C1 to another city C2 using a stack
– place the starting city on the bottom of the stack
• mark it as visited
• pick any arbitrary arrow out of the city
– city cannot be marked as visited
• place that city on the stack
– also mark it as visited
• if that’s the destination, we’re done
• otherwise, pick an arrow out of the city currently at
– next city must not have been visited before
– if there are no legitimate arrows out, pop it off the stack and go back to
the previous city
• repeat this process until the destination is found or all the cities have been
visited
Application 3: Finding a Path using stack
• Consider the following graph of flights

: city
Z
flight goes from W to S
W S
Y
• Want to go from P to Y
– push P on the stack and mark it as visited
W S – pick R as the next city to visit (random select)
• push it on the stack and mark it as visited
– pick X as the next city to visit (only choice)
R P T • push it on the stack and mark it as visited
– no available arrows out of X – pop it
– no more available arrows from R – pop it
X Q – pick W as next city to visit (only choice left)
• push it on the stack and mark it as visited
– pick Y as next city to visit (random select)
• this is the destination – all done
Contents
2.1. Array
2.2. Record
2.3. Linked List
2.4. Stack
2.5. Queue

158
What is a Queue?
Queues
• What is a queue?
– A data structure of ordered items such that items can be inserted only at one end and
removed at the other end.

Back/rear/tail Queue Front/head

Elements enter 4 3 2 1 Elements exit

no changes of order
Example: A line at the supermarket
• What can we do with a queue?
– Enqueue - Add an item to the queue
– Dequeue - Remove an item from the queue
These operations are also called insert and getFront in order to simplify things.
• A queue is called a FIFO (First in-First out) data structure.

Add/ (Remove/Dequeue)
Enqueue
Back/Rear Front/Head
Queue specification
Definitions: (provided by the user)
– maxSize: Max number of items that might be on the queue
– ItemType: Data type of the items on the queue
Operations:
• Q = init(); initialize empty queue Q
• isEmpty(Q); returns "true“ if queue Q is empty
• isFull(Q); returns "true“ if Q is full, indicates that we already use the maximum memory for
queue; otherwise returns “false”
• frontQ(Q); returns the item that is in front (head) of queue Q or returns error if queue Q is
empty.
• enqueue(Q,x); inserts item x into the back (rear) of queue Q. If before making insertion, the
queue Q is full, then give the notification about that.
• x = dequeue(Q); deletes the element at the front (head) of the queue Q, then returns x which
is the data of this element. If the queue Q is empty before dequeue, then give the error notification.
• print(Q); gives the list of all elements in the queue Q in the order from the front to the back.
• sizeQ(Q); returns the number of elements currently in the queue Q.
FIFO
Add/ (Remove/Dequeue)
Enqueue
Back/Rear Front/Head

C rear E rear
B rear B C rear C
rear front B
A A A front B front front
front
enqueue(Q, A) enqueue(Q, B) enqueue(Q, C) dequeue(Q) enqueue(Q, E)
Queues
• What are some applications of queues?
– Round-robin scheduling in processors
– Input/Output processing
– Queueing of packets for delivery in networks
Example -
Given the sequence of operations on queue Q as following. Determine the output and the data
on the queue Q after each operation:

Operation Output Queue Q

1 enqueue(5) - (5)
2 enqueue(Q,3) - (5, 3)
3 dequeue(Q) 5 (3)
4 enqueue(Q,7) - (3, 7)
5 dequeue(Q) 3 (7)
6 front(Q) 7 (7)
7 dequeue(Q) 7 ()
8 dequeue(Q) error ()
9 isEmpty(Q) true ()
10 size(Q) 0 ()
11 enqueue(Q,9) - (9)
12 enqueue(Q,7) - (9, 7)
13 enqueue(Q,3) - (9, 7, 3)
14 enqueue(Q,5) - (9, 7, 3, 5)
15 dequeue(Q) 9 (7, 3, 5)
Stack

Data structure with Last-In First-Out (LIFO) behavior

In Out

C B A B C
Queue

Data structure with First-In First-Out (FIFO) behavior

In Out

C B A B A
Implementing a Queue
• Just like a stack, we can implementing a queue in two ways:
– Using an array
– Using a linked list
Implementing a Queue: using Array
• Using an array to implement a queue is significantly harder than using an array
to implement a stack. Why?
– A stack: we add and remove at the same end,
– A queue: we add to one end and remove from the other.

QUEUE
Array implementation of queues

• An array “Q” of size n

• Two pointers each representing one end of the queue
– front: the end side where items are removed from the queue
– rear: the end side where items are added to the queue

0 1 2 3 4 5 6
7
Q: 17 23 97 44

front = 0 rear = 3

• Enqueue(Q,x): put item x in the queue

– rear++; Q[rear] = x
• Dequeue(Q): remove item x from the queue
– Dequeue Q[front]; front++;
169
Array implementation of queues

front = 0 rear = 3

Initial queue: 17 23 97 44

After insertion: 17 23 97 44 333

After deletion: 23 97 44 333

front = 1 rear = 4

• Notice the content of the array moves to the right as items

are inserted and deleted
• This will be a problem after a while!
170
Circular arrays
• We can treat the array holding the queue elements as
circular (joined at the ends)

0 1 2 3 4 5 6
7
Q: 44 55 11 22 33

rear = 1 front = 5

• Elements were added to this queue in the order 11, 22,

33, 44, 55, and will be removed in the same order
• Dequeue(Q) : Dequeue Q[front]; front = (front +
1) % n;
• Enqueue(Q,x): rear = (rear + 1) % n; Q[rear] =
171
x;
 Queue full or empty
• If the queue become completely full, it would look like this:

0 1 2 3 4 5 6
Q: 7
44 55 66 77 88 11 22 33

rear = 4 front = 5
• If we remove all eight items, making the queue completely
empty, it would look like this:
0 1 2 3 4 5 6
7
Q:

rear = 4 front = 5
• Can’t tell whether the queue is full or empty 172
Queues full or empty: solutions
• Solution 1: Keep an additional variable count which
stores the current number of items in the queue
0 1 2 3 4 5 6
7
Q: 44 55 66 77 88 11 22 33

count = 8 rear = 4 front = 5

• Solution 2: Keep a gap between elements: consider the
queue full when it has n-1 elements

0 1 2 3 4 5 6
7
Q: 44 55 66 77 11 22 33

rear = 3 front = 5
173
 Implementation of solution 1:
• Solution 1: Keep an additional variable
0 1 2 3 4 5 6
7
Q: 44 55 66 77 88 11 22 33

count = 8 rear = 4 front = 5

• Dequeue(Q) : if (count == 0) return ‘queue is
empty’;
else Dequeue Q[front]; front =
(front + 1) % n; count--;
• Enqueue(Q,x): if (count == n) return ‘queue is
full’;
else rear = (rear + 1) % n;
Q[rear] = x; count++; 174
 Implementation of solution 2:
• Solution 2: the front pointer always point to the gap entry
in the array
0 1 2 3 4 5 6
7
Q: 44 55 66 77 11 22 33

rear = 3 front = 4
• Dequeue(Q) : if (rear == front) return ‘queue
is empty’;
else front = (front + 1) % n;
Dequeue Q[front];
• Enqueue(Q,x): if (rear+1 == front) return
‘queue is full’;
else rear = (rear + 1) % n;
Q[rear] = x; 175
Implementing a Queue using Array: Examples
• Q[front]: the first item of the queue
• Circular queue [“wrap around”] • Q[rear]: the last item of the queue
• Add item to the Q (Enqueue): rear+=1;Q[rear]=item;
Example 1: The array used to represent queue has maxSize = 4 • Remove item from Q (Dequeue): remove Q[front];
then front+=1
initialize: Q is empty: front = 0; rear = -1;
enqueue(Q,2) enqueue(Q,3) enqueue(Q,5) dequeue(Q) dequeue(Q) enqueue(Q,10)

rear ++; rear++; rear++; Dequeue Q[front] Dequeue Q[front] rear++;

Q[rear] = 2; Q[rear] = 3; Q[rear] = 5; Q = (3, 5) Q = (5) Q[rear] = 10;
Q = (2) Q = (2, 3) Q = (2, 3, 5) front++; Q = (5,10)
front++;
enqueue(Q,20) ???
Let the queue elements
“wrap around”

If (rear == maxSize -1)

rear = 0;
else
rear ++; rear = rear +1;
Q[rear] = 20;
Q = (5,10, 20) Circular queue
 rear = 4 = maxSize Or
 Array Q over flow rear = (rear + 1) % maxSize;
Implementing a Queue: using Array
• Q[front]: the first item of the queue
• Circular queue [“wrap around”] • Q[rear]: the last item of the queue
• Add item to the Q (Enqueue): rear+=1;Q[rear]=item;
Example 2: The array used to represent queue has maxSize = 4 • Remove item from Q (Dequeue): remove Q[front];
then front+=1
Q consists of 3 elements: Q = (5, 10, 20)
enqueue(Q,30) enqueue(Q,50) ?? When Q is full already

The queue Q is full!!!

What is the condition to determine that the queue is full ?

rear + 1 == front

rear++; rear++;
Q[rear] = 30; Q[rear] = 50; We can not distinguish between
Q = (5, 10, 20, 30)  rear = 2 = front the two cases: EMPTY and
FULL !!!!!
dequeue(Q) dequeue(Q) dequeue(Q) dequeue(Q)

The queue Q is empty!!!

What is the condition for an empty queue ?
rear + 1 == front

Dequeue Q[front] Dequeue Q[front]

Q = (20, 30)
Dequeue Q[front] Dequeue Q[front]
Q = (10, 20, 30) front++; Q = (30) Q = empty
front++; => front = 4=maxSize front++;
=> “wrap around” front++;
Þ front = 0
Implementing a Queue: using Array
• Circular queue [“wrap around”]
Solution 2: Make front point to the element preceding the front element in the queue (one
memory location will be wasted).
Make front point to the element preceding the front element in the queue (one memory
location will be wasted).
Example 3: illustration for solution 2
Solution 2: Make enqueue(Q, 30)
front point to the
element preceding The queue Q is full!!!
the front element in What is the condition to
the queue (one determine that the queue
memory location will is full ?
be wasted).
Make front point to rear + 1 == front
the element
Q = (10, 20) preceding the Q = (10, 20) rear++; Q[rear] = 30;
front element in the Q = (10, 20, 30)
queuedequeue(Q)
(one dequeue(Q) dequeue(Q)
memory location
will be wasted).
The queue Q is empty!!!
What is the condition for an
empty queue ?

rear == front

Q = (10, 20, 30) front++; front++; front++;

Dequeue Q[front] Þ front = 4 = maxSize Dequeue Q[front]
Q = (20, 30) Þ wrap around: front = 0 Q = empty
Dequeue Q[front]
Q = (30)
Based on this solution 1, one memory location on the array Q is wasted!!!
Implementing a Queue: using Array
• Circular queue [“wrap around”]
Solution 2: Make front point to the element preceding the front element in the queue (one
memory location will be wasted).
Then what are the initial values for front and rear ?
front = rear = maxSize – 1;

Make front point to the element preceding the front element in the queue (one memory
• Q[front+1]:
location the first item of the queue
will be wasted).
• Q[rear]: the last item of the queue
• Add item to the Q (Enqueue): rear+=1; Q[rear]=item
• Remove item from Q (Dequeue): front+=1; then remove Q[front] from queue
Example 4: The array used to represent queue has maxSize = 4
Initialize: front = rear = maxSize – 1 = 3; illustration for solution 1
Queue Q is empty

Init: front = rear = 3; enqueue(Q, 2) enqueue(Q, 3) enqueue(Q, 5) dequeue(Q)

rear++; rear++; rear++; front++;

Q[rear] = 2; Q[rear] = 3; Q[rear] = 5; => front = 4 = maxSize
Q= (2) Q= (2, 3) Q= (2, 3, 5) => wrap around : front = 0
Dequeue Q[front]
Q= (3, 5)
rear + 1 == front
Queue Q full!!!
dequeue(Q) enqueue(Q, 10) enqueue(Q, 20)
In general:
(rear + 1)% maxSize == front

enqueue(Q, 30) ??

ERROR: Queue is full

front++; rear++; rear++;

dequeue Q[front] Q[rear] =10; Q[rear] =20;
Q= (5) Q= (5, 10) Q= (5, 10, 20)
Example 4: The array used to represent queue has maxSize = 4
Initialize: front = rear = maxSize – 1 = 3; illustration for solution 1
Queue Q is empty

dequeue(Q) dequeue(Q) dequeue(Q)

Q= (5, 10, 20) front++; front++; front++;

Dequeue Q[front] Dequeue Q[front] =>front = 4 = maxSize
Q= (20) => wrap around: front =0
Q= (10, 20)
Dequeue Q[front]
Q empty

Queue Q is empty now !!!

rear == front
Implementing a Queue: using Array
• Circular queue [“wrap around”]
Solution 2: Make front point to the element preceding the front element in the queue (one
memory location will be wasted).
• The initial values for front and rear :
front = rear = maxSize – 1;
• Q[front+1]: the first item of the queue
• Q[rear]: the last item of the queue
• Add item to the Q (Enqueue):
– rear+=1; if (rear == maxSize) rear = 0;
– Q[rear]=item
• Remove item from Q (Dequeue):
– front = (front + 1) % maxSize;
– then remove Q[front] from queue
• Detect queue is empty: rear == front
• Detect queue is full: (rear + 1) % maxSize == front
ke front point to the element preceding the front element in the queue (one memory
location will be wasted).
Solution 2: Make front point to the element preceding the front element in the queue
(one memory location will be wasted)
isEmpty(Q) // returns "true“ if queue Q is empty
{
if (rear == front) return true;
else return false;
}
isFull(Q) /*returns "true“ if Q is full, indicates that we already use the maximum memory for queue;
otherwise returns “false” */
{
if ((rear + 1) % maxSize == front) return true;
else return false;
}
frontQ(Q) //returns the item that is in front (head) of queue Q or returns error if queue Q is empty.
{
return Q[front + 1];
}

184
Solution 2: Make front point to the element preceding the front element in the queue
(one memory location will be wasted)
enqueue(Q,x) /*inserts item x into the back (rear) of queue Q. If the queue is full before making insertion, then give the
notification about that*/
{
if (isFull(Q)) ERROR(“Queue is FULL”);
else
{ rear ++;
if (rear == maxSize) rear = 0;
Q[rear] = x;
}
}
enqueue(Q,x)
{
if (isFull(Q)) ERROR(“Queue is FULL”);
else
{ rear = (rear + 1) % maxSize;
Q[rear] = x;
}
} 185
Solution 2: Make front point to the element preceding the front element in the queue
(one memory location will be wasted)
dequeue(Q) /*deletes the element at the front (head) of the queue Q, then returns x which is the data of this element. If the queue Q is empty
before dequeue, then give the error notification*/
{
if (isEmpty(Q)) ERROR(“Queue is EMPTY”);
else
{ front = (front + 1);
if (front == maxSize) front = 0;
return Q[front];
}
}
dequeue(Q)
{ if (isEmpty(Q)) ERROR(“Queue is EMPTY”);
else
{ front = (front + 1) % maxSize;
return Q[front];
}
} front = front + 1;
=>front = 4 = maxSize
Dequeue (Q)
=> wrap around: front =0
Dequeue Q[front]
Q empty 186
Implementing a Queue: using Array
• Circular queue [“wrap around”]
Solution 2: Make front point to the element preceding the front element in the queue (one
memory location will be wasted).
Solution 3: Make rear point to the element posterior the rear element in the queue (one memory
location will be wasted).
Make front point to the element preceding the front element in the queue (one memory
location will be wasted).
Example 5: illustration for solution 3
Solution 3: Make enqueue(Q, 30)
rear point to the
element posterior of The queue Q is full!!!

? ?
the rear element in What is the condition to
the queue (one determine that the queue
memory location will is full ?
be wasted).
Make front point to rear + 1 == front
the element
Q = (10, 20) Q = (10, 20) Q[rear] = 30; rear++;
preceding the
Q = (10, 20, 30)
front element in the
queue (onedequeue(Q)
dequeue(Q) dequeue(Q)
memory location
will be wasted).

? ? ?
The queue Q is empty!!!
What is the condition for an empty queue ?

rear == front

front++; front++; front++;

Þ front = 4 = maxSize Q = (30) Q = empty
Þ wrap around: front = 0
Q = (20, 30)

Based on this solution 3, one memory location on the array Q is wasted!!!

Implementing a Queue: using Array
• Circular queue [“wrap around”]
Solution 1: Make front point to the element preceding the front element in the queue (one
memory location will be wasted).
Then for solution 1: what are the initial values for front and rear ?
front = rear = maxSize – 1;
Solution 3: Make rear point to the element posterior the rear element in the queue (one memory
location will be wasted).
Then for solution 3: what are the initial values for front and rear ?
front = rear = 0;

Make front point to the element preceding the front element in the queue (one memory
location will be wasted).
Example 6: The array used to represent queue has maxSize = 4
Initialize: front = rear = 0; illustration for solution 3
Queue Q is empty

Init: front = rear = 0; enqueue(Q, 2) enqueue(Q, 3) enqueue(Q, 5) dequeue(Q)

? ?
Q[rear] = 2; Q[rear] = 3; Q[rear] = 5; Dequeue Q[front]
rear++; rear++; rear++; front++;
Q= (2) Q= (2, 3) Q= (2, 3, 5) Q= (3, 5)

(rear + 1) % maxSize == front

Queue Q full!!!
dequeue(Q) enqueue(Q, 10) enqueue(Q, 20)

? ? enqueue(Q, 30) ??

ERROR: Queue is full

dequeue Q[front] Q[rear] =10; Q[rear] =20;

front++; rear++; rear++;
Q= (5) Q= (5, 10) Q= (5, 10, 20)
Example 6: The array used to represent queue has maxSize = 4
Initialize: front = rear = 0; illustration for solution 3
Queue Q is empty

dequeue(Q) dequeue(Q) dequeue(Q)

?
Q= (5, 10, 20) Dequeue Q[front] Dequeue Q[front] Dequeue Q[front]
front++; front++; front++;
=>front = 4 =maxSize Q empty
Q= (10, 20) => wrap around: front =0
Q= (20)

Queue Q is empty now !!!

rear == front
Solution 3: Make rear point to the element posterior the rear element in the queue (one
memory location will be wasted)

Exercise: Write following functions for queue Q in the case of Solution 3

• isEmpty(Q); returns "true“ if queue Q is empty
• isFull(Q); returns "true“ if Q is full, indicates that we already use the maximum memory for queue; otherwise
returns “false”
• frontQ(Q); returns the item that is in front (head) of queue Q or returns error if queue Q is empty.
• enqueue(Q,x); inserts item x into the back (rear) of queue Q. If before making insertion, the queue Q is full,
then give the notification about that.
• x = dequeue(Q); deletes the element at the front (head) of the queue Q, then returns x which is the data of this
element. If the queue Q is empty before dequeue, then give the error notification.
• sizeQ(Q); returns the number of elements currently in the queue Q.

192
Application 1: recognizing palindromes
• A palindrome is a string that reads the same forward and backward.
Example: NOON, DEED, RADAR, MADAM
Able was I ere I saw Elba
• How to recognize a given string is a palindrome or not:
– Step 1: We will put all characters of the string into both a stack and a
queue.
– Step 2: Compare the contents of the stack and the queue character-by-
character to see if they would produce the same string of characters:
• If yes: the given string is a palindrome
• Otherwise: not palindrome
Example 1: Whether “RADAR” is a palindrome or not
Step 1: Put “RADAR” into Queue and Stack:

Current Queue Stack

character (front on the left, (top on the left)
rear on the right)
R R R
A RA AR
D RAD DAR
A RADA ADAR
R RADAR RADAR
front rear top
Example 1: Whether “RADAR” is a palindrome or not
Step 2: Delete “RADAR” from Queue and Stack:
• Dequeue until the queue is empty
• Pop the stack until the stack is empty
Queue Front of Top of Stack
(front on the left) Queue Stack (top on the left)

RADAR R R RADAR
ADAR A A ADAR
DAR D D DAR
AR A A AR
R R R R
empty empty empty empty

Conclusion: String "RADAR" is a palindrome

Example 2: recognizing palindromes

Able was I ere I saw Elba

Application 2: Convert a string of digits into a decimal number
The algorithm is described as following:

// Convert sequence of digits stored in queue Q into decimal number n

// Remove empty space if any
do { dequeue(Q, ch)
} until ( ch != blank)
// ch is now the first digit of the given string
// Calculate n from sequence of digit in the queue
n = 0;
done = false;
do { n = 10 * n + decimal number that ch represents;
if (! isEmpty(Q) )
dequeue(Q,ch)
else
done = true
} until ( done || ch != digit)
// Result: n is the decimal number need to be found
197
Implementing a Queue
• Just like a stack, we can implementing a queue in two ways:
– Using an array
– Using a linked list
Implementing a Queue: using a linked list
typedef struct {
DataType element;
struct node *next;
} node;
typedef struct {
node *front;
node *rear;
} queue;
where DataType is data type of the object need to store in the queue;
DataType need to be declared before declaring the queue.
• Implementing a queue using a linked list:
– Front of the queue is stored as the head node of the linked list, rear of the
queue is stored as the tail node.
– Enqueue by adding to the end of the list
– Dequeue by removing from the front of the list.