University of Science and Technology Houari Boumediene
Faculty of computer science
Algorithmic and Data Structures 2s 2024/2025
TP: Linked List
Exercise 1 :
●Create a linked list: Write a subroutine to create an empty linked list.
● Insert a node at the beginning of a linked list.
●Insert a node at the end of a linked list.
● Insert a node at a given position in a linked list.
●Delete the first node of a linked list.
● Delete the last node of a linked list.
● Delete a node at a given position in a linked list.
●Search for an element in a linked list and return its position.
●Display all elements of a linked list.
●Check if a linked list is sorted in ascending order.
Exercise 2 :
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 3 :
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. Delete duplicate elements so that each value appears only once.
4. Find and remove the smallest value from the list.
5. Write the function that returns the address of the middle element of the list without using the size
.
6. Create the mirror image of L:
7. 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
1 sur 3
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 )
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
L! 16 ! 24 ! 93 ! NIL N = 18 L! 18 ! 16 ! 24 ! 93 ! NIL
5871 LC ! 5871 ! NIL
LM ! 5 ! 8 ! 7 ! 1 ! NIL
8715 LC ! 5871 ! 8715 ! NIL
7158 LC ! 7158 ! 5871 ! 8715 ! NIL
1587 LC ! 7158 ! 5871 ! 8715 ! 1587 ! NIL
1 sur 3
