Data Structure And Algorithm Assignment
Course Title : Data Structure and Algorithm
Submission date: 08/09/2025
SUBMITTED TO:
Teacher’s name: Dr.Umma Khatuna Jannat
SUBMITTED BY:
Student’s name: Umme Habiba Koheli
Student id: 04324205101107
Section: 3B
Semester: Autumn-2025
Batch : 56
Department: CSE
1. Ex 1: Traversal
Answer:
In the given linked list, each node contains one character of the word and a link to the next node. The node
table is:
INFO LINK
M 2
A 3
N 4
Traversal Algorithm:
1. Start from the first node.
2. Read the INFO field of the current node.
3. Move to the next node usining the LINK field.
4. Repeat steps 2–3 until LINK = NULL.
5. The collected characters form the required word.
Traversal Process:
Node 1 → INFO = M
Node 2 → INFO = A
Node 3 → INFO = N
LINK = NULL → Stop
Reconstructed Word: MAN.
Example 2: Dynamic student Data
A library maintains student records (ID, Name, BorrowedBooks). Students frequently borrow and return
books. Why is a linked list more efficient than an array for this scenario? Show the steps of inserting a new
student record at the end of the list.
Answer:
A library maintains student records containing ID, Name, and BorrowedBooks. Since students frequently
borrow and return books, records are often inserted and deleted.
Why linked list is more efficient than array?
1. Dynamic Size: Unlike arrays (fixed size), a linked list can grow or shrink as students borrow/return
books.
2. Efficient Insertion/Deletion: In a linked list, inserting or deleting a student record only requires
updating a few pointers. In an array, shifting many elements may be required.
3. Memory Utilization: Linked lists allocate memory as needed, avoiding wasted space from unused
array elements.
Hence, linked lists are more suitable for this scenario.
Steps to Insert a new Student Record at the end of the list:
1. Create a new node with fields (ID, Name, BorrowedBooks).
2. Set the link of the new node to NULL (since it will be the last node).
3. Check if the list is empty:
If empty → make the new node the first node.
4.If the list is not empty:
1. Traverse the list until the last node (where LINK = NULL).
2. Update the last node’s LINK to point to the new node.
5.Now the new student record is successfully added at the end.
Conclusion:
Using a linked list makes student data management more efficient in a library system where records are frequently
updated.
Example 3: Deletion
Scenario: A hospital maintains a queue of patients. Sometimes a patient may leave before checkup.
How to Delete from the Middle of a Linked List:
1. Traverse the list to locate the node just before the patient’s record.
2. Change the LINK of this node to point to the node after the patient’s record.
3. Free (delete) the patient’s node from memory.
Why Array Deletion is Inefficient:
In an array, deleting a record requires shifting all elements after the deleted position, which is time-
consuming.
In a linked list, deletion only requires pointer adjustment → much faster.
Example 4: Web Browser Navigation
Scenario: Users can move forward and backward between visited pages.
Most Appropriate Linked List:
Doubly Linked List
Why:
Each page node contains links to both the previous and next pages.
This allows movement forward (next) and backward (previous) efficiently, just like browser
navigation.
Scenario: Books (Title, Author, ISBN) may be added or removed.
Why Linked List is Better than Array:
Arrays have fixed size → difficult to manage frequent additions/removals.
Linked lists allow flexible size and easy insertion/deletion.
Steps to Insert at End:
1. Create a new node with (Title, Author, ISBN).
2. Set its LINK = NULL.
3. If the list is empty, make this node the head.
4. Otherwise, traverse to the last node and set its LINK to the new node.
Photo viewer application
Most Appropriate Linked List:
Doubly Linked List
Explanation:
A photo viewer requires moving forward (next image) and backward (previous image).
A doubly linked list supports both directions because each node has two links: next and previous.
Example 5: Online Navigation
Scenario: Products (ID, Name, Price) are frequently added and removed.
Why Linked List is More Suitable:
Arrays have fixed size and require shifting elements during insertion/deletion.
Linked lists allow dynamic size and efficient insertion/deletion without shifting.
Steps to Insert After a Given Node:
1. Create a new node with (ProductID, Name, Price).
2. Set the new node’s LINK to the LINK of the given node.
3. Change the given node’s LINK to point to the new node.
4. Now the product is inserted after the given node.
Example 6:
Hospital Patient Records
Patients may be admitted/discharged anytime, so records frequently change.
Why Linked List is Better than Array:
o Arrays have fixed size → difficult when number of patients changes often.
o Insertion/Deletion in arrays requires shifting → time-consuming.
o Linked lists allow dynamic size and efficient insertion/deletion.
Steps to Insert a New Patient at the Beginning:
1. Create a new node with (Name, PatientID, MedicalHistory).
2. Set the new node’s LINK to the current head of the list.
3. Update head pointer to point to the new node.
4. The new patient is now the first record.
Undo/Redo in Text Editor:
Suitable Linked List: Doubly Linked List
Reason: Allows moving backward (undo) and forward (redo) efficiently since each node stores links
to both previous and next operations.
Example 7:
Company Employee Records
Employees frequently join and leave, so updates are common.
Why Linked List is Better than Array:
o Dynamic → no need for resizing.
o Efficient insertion/deletion compared to arrays (no shifting).
Steps to Delete Employee from Middle:
1. Traverse to the node just before the employee record.
2. Change its LINK to point to the node after the employee.
3. Free the employee’s node from memory.
Video Streaming Playlist:
Suitable Linked List: Doubly Linked List
Reason: User can switch both to the next video or the previous video, which requires two-way
traversal.
Example 8:
University Course Records
New courses are introduced and old ones removed every semester.
Why Linked List is Better than Array:
o Flexible size → handles frequent additions/removals easily.
o Insertion/deletion is efficient without shifting elements.
Steps to Insert New Course at End:
1. Create a new node with (CourseCode, Title, CreditHours).
2. Set its LINK = NULL.
3. If list is empty → make this node the head.
4. Otherwise → traverse to the last node and set its LINK to new node.
Game Inventory System:
Suitable Linked List: Doubly Linked List
Reason: Players need to move forward (next item) and backward (previous item). Doubly linked
list supports both directions efficiently.
Example 9:
Node Table:
Node INFO LINK
1 9
2 O 14
3 Q 13
4 L 7
5 C 2
6 0 0
7 D 0
8 A 10
9 4
10 G 1
11 N 5
12 8
13 M 6
14 T 11
Start → 5
Traverse:
Node 5: INFO = C → LINK = 2
Node 2: INFO = O → LINK = 14
Node 14: INFO = T → LINK = 11
Node 11: INFO = N → LINK = 5 → (Stop, already visited)
Sequence = COTN
Example 10:
Node Table:
Node INFO LINK
1 F 12
2 14
3 Z 9
4 10
5 P 2
6 0 0
7 T 0
8 R 6
9 M 4
10 1
11 U 5
12 L 11
13 A 7
14 B 8
Start → 5
Traverse:
Node 5: INFO = P → LINK = 2
Node 2: (blank) → LINK = 14
Node 14: INFO = B → LINK = 8
Node 8: INFO = R → LINK = 6 → (NULL, stop)
Sequence: PBR
Example 11:
Node Table:
Node INFO LINK
1 H 9
2 13
3 X 10
Node INFO LINK
4 R 7
5 G 2
6 0 0
7 0
8 S 12
9 C 4
10 N 1
11 5
12 T 11
13 O 8
14 D 6
Start → 5
Traverse:
Node 5: INFO = G → LINK = 2
Node 2: (blank) → LINK = 13
Node 13: INFO = O → LINK = 8
Node 8: INFO = S → LINK = 12
Node 12: INFO = T → LINK = 11
Node 11: (blank) → LINK = 5 → (Stop, cycle detected)
Sequence = GOST
Example 12:
Node Table:
Node INFO LINK
1 M 9
2 14
3 R 12
4 C 7
5 A 2
6 0 0
7 0
8 T 11
9 E 4
10 L 1
11 O 5
12 10
13 P 6
14 G 8
Start → 5
Traverse:
Node 5: INFO = A → LINK = 2
Node 2: (blank) → LINK = 14
Node 14: INFO = G → LINK = 8
Node 8: INFO = T → LINK = 11
Node 11: INFO = O → LINK = 5 → (Stop, visited)
Sequence = AGTO
