University of Science and Technology Houari Boumediene

Faculty of computer science

Algorithmic and Data Structures 2s 2024/2025

TD N° 3: Linked List

Exercise 1 :
Let A(N, M) be a matrix of integers, where N ≤ 20 and M ≤ 30. Write an algorithm that generates two lists from
this matrix:
1. First List (FIFO - Queue): This list contains the maximum values of each row in the matrix. Elements are
stored in First In, First Out (FIFO) order.
2. Second List (LIFO - Stack): This list contains the minimum values of each column in the matrix. Elements
are stored in Last In, First Out (LIFO) order.
Exercise 2 :
Let L be a list of integer values. Implement the following Subroutine:
1. Determine the number of elements in the list.
2. Find the maximum and minimum values in the list..
3. Given a sorted list L and an integer VAL, insert VAL while maintaining the sorted order
4. Delete duplicate elements so that each value appears only once.
5. Find and remove the smallest value from the list.
6. Write the function that returns the address of the middle element of the list.
7. Create the mirror image of L:
8. Separate L into two sublists: -LP (containing positive integers). - LN (containing negative integers). -
**Without creating new lists**,

Exercise 3 :

Let L1 and L2 be two lists of positive integer values:

1. Write a subroutine to check if L1 and L2 are identical (contain the same elements in the same order).
2. Write a subroutine to check if L1 is included in L2 (all elements of L1 are found in L2, order does not
matter).
3. Write a subroutine to check if L1 is a sublist of L2 (L1 appears in L2 in the same order).
4. Write a subroutine to check if L1 and L2 are disjoint (L1 ∩ L2 = Ø).
5. Write a subroutine to move (without allocation or deallocation) even values from L1 to L2 and odd values
from L2 to L1.

Exercise 4 :
A pharmacist wants to manage information about his medication stock using a computer system. These details
are represented as a singly linked list, where each element contains: The name of the medication. The available
quantity (number of boxes). The unit price.
 Define the necessary data structures to represent this stock. Write the subroutine Sell to remove NbBox of
medication Med from stock, if possible. If the quantity reaches zero, the medication must be removed from
the stock.
 Write the subroutine BUY(Med, NbBoites, Pric) to add NbBoites of medication Med with a unit price. If the
medication already exists, update its quantity and set the new price. If it does not exist, insert it into the stock

Exercice 5 (2024 exam)

1. Let L be a list of digits between 1 and 9 representing a strictly positive integer N. Write a subroutine
NUMBER to generate the number N. (See example ①)
2. Let L be a list of digits between 1 and 9. Write a subroutine DETACHMENT to return the address of the
first element of the list L and detach it without deleting. (See example ②)

1 sur 3
 3. Let L be a list of integers and N be a strictly positive integer. Write a subroutine INSERTION to insert N at
the beginning of the list L if N is an even number strictly greater than 10; otherwise, insert it at the end of
the list. (See example ③)
4. Let LM be a list of digits between 1 and 9. Write an algorithm to create a list LC containing all the numbers
generated from a left rotation of the digits of LM. The generated even numbers must be positioned at the
beginning of the list. (See example ④)

① L → 5 → 8 → 7 → 1 → NIL N = 5871

② L → 5 → 8 → 7 → 1 → NIL L → 8 → 7 → 1 → NIL E→5

L → 16 → 24 → 93 → NIL N=8 L → 16 → 24 → 93 → 8 → NIL

5871 LC → 5871 → NIL

7158 LC → 7158 → 5871 → 8715 → NIL

1587 LC → 7158 → 5871 → 8715 → 1587 → NIL

Exercise 6(Replacement Exam 2023)

Let L be a list of students. Each student is defined by:

 Name
 First name
 General average

Each element in the list contains a pointer to a list of the student’s grades.
An element in the grade list contains:

 Coefficient
 Subject average

1. Give the declaration of the two lists (LS for students, LG for grades).
2. Write a subroutine Average to compute the average of a list of grades.
3. Write a subroutine DELIB to compute the general average of each student.
4. Write a subroutine Delete to remove students whose general AV < 5.
5. Write a subroutine RESULTAT to create (without allocation) two lists:
o LP for students who passed.
o LF for students who failed.

Name First MG N FN MG N FN MG NULL

CF CF CF CF CF CF
SAV SAV SAV SAV SAV SAV
Null Null NULL

2 sur 3