Lab on Data Structure: Practical Unit 2
Table of Contents
1. Task 3: Singly Linked List Implementation
Lab Assignment: Implement Singly Linked List using templates. Include functions for insertion, deletion, search, reversing the list, and concatenation.
The implementation requires a Node class/struct that stores data of type T and a pointer to the next node. Key functions to implement:
- Insertion: At the beginning, end, or after a specific node.
- Deletion: Remove a node by its value.
- Search: Traverse the list to find a specific element.
- Reverse: Flip the pointers so the last node becomes the head.
2. Task 4: Doubly Linked List Implementation
Lab Assignment: Implement Doubly Linked List using templates. Include functions for insertion, deletion, search, and reverse.
A Doubly Linked List (DLL) node contains two pointers: prev and next.
template <typename T>
struct Node {
T data;
Node *next, *prev;
};
struct Node {
T data;
Node *next, *prev;
};
Logic Note: When inserting or deleting in a DLL, you must update four pointers for middle elements to maintain the bidirectional link.
3. Task 5: Circular Linked List Implementation
Lab Assignment: Implement Circular Linked List using templates with functions for insertion, deletion, search, and reverse.
In a Circular Linked List, the last node points back to the head node instead of NULL.
- Traversal Warning: Be careful with loops. Use
do-whileor check if the current node returns toheadto avoid infinite loops. - Reverse Logic: Reversing is slightly more complex as you must also update the connection between the new tail and new head.
4. Special Feature: Operator Overloading (+)
The lab syllabus requires overloading the + operator to concatenate two linked lists.
Utility: List3 = List1 + List2; This makes the code more intuitive by treating lists like mathematical entities. LinkedList<T> operator+(LinkedList<T>& other) {
LinkedList<T> result = *this;
result.concatenate(other);
return result;
}
LinkedList<T> result = *this;
result.concatenate(other);
return result;
}
5. Exam-Oriented Practical Tips
Common Pitfalls
- Memory Leaks: Always write a Destructor to delete all nodes when the list object goes out of scope.
- Head Pointer: Ensure the
headpointer is updated correctly when inserting at the 0th position. - Empty List: Always test your functions (especially deletion and search) with an empty list to prevent segmentation faults.
Complexity for Lab Viva
| Operation | Singly List | Doubly List |
|---|---|---|
| Search | O(n) | O(n) |
| Insertion (at Head) | O(1) | O(1) |
| Reverse | O(n) | O(n) |