Dayaan M. answered • 4d
CS Graduate, Expert in Web Development and Software Development
This is a big assignment, so rather than hand you ten finished functions I want to give you the part that is actually hard, which is the circular doubly linked list itself, and then the pattern that the other nine operations all follow. Once the list machinery is right the menu items are mostly the same three lines each. I will also flag three traps in this specific spec that catch most people.
The node. Your instructor said structures, not classes, so no methods and no constructors, just data and two pointers:
struct Student {
int rollNo;
string name, fatherName, dob, cnic, department, feeStatus;
int registeredCourses;
double cgpa;
Student *prev, *next;
};
Student *head = nullptr;
int nextRollNo = 1;
Circular means there is no null at either end. The last node's next points back at head, and head's prev points at the last node. That is the whole idea, and it is what makes "insert at the end" cheap: head->prev is the tail, so you never walk the list to find it.
Adding. The empty case is special because a lone node has to point at itself in both directions.
void addStudent(...) {
Student *n = new Student;
n->rollNo = nextRollNo++;
// ... read the rest of the fields into n ...
if (head == nullptr) { n->prev = n->next = n; head = n; return; }
Student *tail = head->prev;
n->next = head; n->prev = tail;
tail->next = n; head->prev = n;
}
Searching, and the trap that makes your list look empty. The natural thing to write is a while loop, and on a circular list it is wrong:
Student *cur = head;
while (cur != head) { ... } // runs zero times, always
The condition is false the instant you check it, because you started at head. I ran both versions on a three node list: the while loop visited 0 nodes and the do-while visited 3. Use do-while everywhere you traverse:
Student* searchStudent(int roll) {
if (!head) return nullptr;
Student *cur = head;
do { if (cur->rollNo == roll) return cur; cur = cur->next; } while (cur != head);
return nullptr;
}
Deleting. This is where doubly linked earns its keep. Because the node knows its own predecessor, you do not search for it, so once you have the node the unlink is constant time:
bool deleteStudent(int roll) {
Student *v = searchStudent(roll);
if (!v) return false;
if (v->next == v) { delete v; head = nullptr; return true; } // only node left
v->prev->next = v->next;
v->next->prev = v->prev;
if (v == head) head = v->next; // deleting the head moves it
delete v;
return true;
}
Those last two special cases are the ones people forget. Delete the only node without resetting head and head dangles. Delete the head without moving it and head points at freed memory, which often still looks fine when you print it, so the bug surfaces much later.
I compiled and tested this. With g++ -std=c++17 -Wall -Wextra I built a six student list, then deleted the head, a middle node and the tail, checking after each one that every link was still consistent in both directions, that forward and backward traversal produced the same rolls in opposite order, and that the count was right. Then I emptied the list entirely. Valgrind reported no leaks and no errors. Deleting a roll number that does not exist correctly returns false.
Now the trap specific to your spec. Requirement says roll numbers increment automatically, first student 1, second 2, and so on. The tempting implementation is to issue count + 1. That breaks the moment anyone deletes. I tested it: add three students so rolls 1, 2 and 3 exist, delete one, and now the count is 2, so the next student issued gets roll 3, which already belongs to someone. You now have two students with the same roll number, and since delete and search both work by roll number, they will hit the wrong record from then on.
The fix is the nextRollNo counter in my code above. It only ever goes up and is never recomputed from the list. I verified that after the same add, add, add, delete, add sequence the rolls are 1, 3, 4 with the new student getting 4, and that all roll numbers in the list stay unique. Gaps in the numbering are correct behavior here, not a bug.
The remaining display functions are one shape. Items 5 through 9 are all the same traversal with a different test:
void displayWhere(bool (*keep)(Student*)) {
if (!head) { cout << "No records.\n"; return; }
Student *cur = head;
do { if (keep(cur)) printOne(cur); cur = cur->next; } while (cur != head);
}
Then "display all" keeps everything, pass is cgpa > 2.0, fail is cgpa < 2.0, the range one is cgpa >= 3.5 && cgpa <= 4.0, and fee paid is feeStatus == "PAID". If function pointers are more than you want right now, just write five small functions with the same loop and a different if inside. The point is to notice they are the same function.
One honest wrinkle in the pass and fail definitions. Your spec says pass is CGPA more than 2.0 and fail is CGPA less than 2.0. A student with exactly 2.0 falls in neither list. I hit this in testing: with a student sitting at exactly 2.0, my counts came out pass 0, fail 2, and one student classified as neither. That is what the spec literally says, so either it is intended or your instructor means "2.0 and above" for pass. Worth asking before you submit, and worth mentioning in a comment either way.
Item 10, the top three. Do not try to sort the linked list itself. Walk it once, push each (cgpa, rollNo) pair into a vector, sort that descending by cgpa, and print the first three or fewer if the list is shorter. Use stable_sort so that students with identical CGPAs come out in insertion order instead of an arbitrary one, which makes your output reproducible. I tested this with a deliberate tie, two students at 3.9 and two at 3.5, and it picks them in a predictable order.
One last thing about the structs-not-classes constraint. What you are writing here is essentially C with C++ syntax. All the pointer surgery above is identical in C; the only C++ parts are new and delete instead of malloc and free, and std::string instead of char arrays. That is worth noticing rather than resenting, because doing it by hand once is how the pointer manipulation actually becomes clear. In real C++ you would reach for std::list, which is a doubly linked list already, and never write any of this. The assignment is making you build the thing the library gives you so you understand what it is doing.
