--- title: "Delete employee from doubly linked list" subject: "Data Structure and Algorithm" chapter: 4 key: "semester_4/data_structure_and_algorithm:doubly-employee-delete" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/doubly-employee-delete site: BCT Engineering --- # Delete employee from doubly linked list Data Structure and Algorithm · Chapter 4: Linked lists - Asked in: 2069 Bhadra, 7 marks - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/doubly-employee-delete - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-4 ## Question Suppose you have a doubly linked list that stores employee information. Explain how an employee with employee ID 165-64 can be deleted from the list with necessary illustrations and pseudo codes. ## Short answer To delete the node with ID 165-64 from a doubly linked list, traverse the list to find it. Once found, update the previous node’s next pointer and the next node’s prev pointer to bypass the target node, then free it. Handle first, middle, and last node cases. ## Answer Assume each employee node is: ```c struct emp { struct emp *prev; char id[10]; /* e.g. "165-64" */ char name[30]; float salary; struct emp *next; }; struct emp *start; /* first node */ ``` #### Idea Search the list for the node whose ID is "165-64"; then make its previous node and next node point to each other, and free it. There are three cases: first node, middle node, last node. #### Illustration ```text Before: start -> [NULL|101-12|*] <-> [*|165-64|*] <-> [*|201-07|NULL] ^ p After: start -> [NULL|101-12|*] <-> [*|201-07|NULL] ``` The first node's `next` is set to the third node, and the third node's `prev` is set to the first node. Node "165-64" is freed. #### Pseudo code ```text DELETE_EMP(start, "165-64") 1. if start == NULL then print "empty list"; return 2. p = start 3. while p != NULL and p->id != "165-64" p = p->next 4. if p == NULL then print "employee not found"; return 5. if p->prev == NULL // deleting first node start = p->next else p->prev->next = p->next 6. if p->next != NULL // not the last node p->next->prev = p->prev 7. free(p) ``` #### C code ```c void delete_emp(struct emp **start, const char *id) { struct emp *p = *start; while (p != NULL && strcmp(p->id, id) != 0) p = p->next; if (p == NULL) { printf("Not found\n"); return; } if (p->prev == NULL) *start = p->next; /* first node */ else p->prev->next = p->next; if (p->next != NULL) p->next->prev = p->prev; free(p); } /* call: delete_emp(&start, "165-64"); */ ``` Cases: if it is the first node, `start` moves to the second node; if it is the only node, `start` becomes `p->next`, which is NULL, and step 6 is skipped; if it is the last node, step 6 is skipped. Time is O(n) for the search and O(1) for the removal. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is the employee with ID 165-64 located? A. Traverse from start comparing id with strcmp until found or NULL B. Access list[165] C. Use the last node D. Sort by name first Answer: A. Linked lists must be searched sequentially. (Key point: Search) 2. For a middle node, which links are changed? A. Only start B. The previous node's next and the next node's prev C. Only the node's own pointers D. All nodes' prev pointers Answer: B. The neighbours bypass p before it is freed. (Key point: Middle case) 3. If p->prev is NULL, what happens? A. start = NULL always B. p->next->next = NULL C. start = p->next D. The list is reversed Answer: C. The deleted node was first, so the head moves. (Key point: First node case) 4. Why is step 6 skipped for the last node? A. The last node cannot be deleted B. prev is always NULL C. free(p) already updates it D. p->next is NULL, so there is no next node whose prev must change Answer: D. A NULL pointer must not be dereferenced. (Key point: Last node case) ## Related in Data Structure and Algorithm - [Doubly linked list: bank customer records](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adoubly-bank-customer) — Data Structure and Algorithm, chapter 4 - [Insert and delete kth node in doubly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adoubly-insert-delete-kth) — Data Structure and Algorithm, chapter 4, asked 2× - [Delete last node of doubly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adelete-end-node-doubly) — Data Structure and Algorithm, chapter 4 - [Delete Kth node from doubly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adoubly-delete-kth) — Data Structure and Algorithm, chapter 4 - [Insert and delete before a node, singly linked](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asingly-insert-delete-before) — Data Structure and Algorithm, chapter 4 - [Doubly vs singly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adoubly-vs-singly-linked) — Data Structure and Algorithm, chapter 4, asked 2× ## Related in other subjects - [Subnet 202.70.64.0/19 for 100-800 hosts](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Asubnetting-202-70-64-19) — Computer Networks and Security, chapter 4, asked 2× - [RA: delete Electrical dept projects](https://www.bctengineer.com/question.md?key=semester_6%2Fdatabase_management_system%3Ara-delete-electrical-projects) — Database Management System, chapter 3 - [Manager derived from person and employee](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Amanager-person-employee) — Object Oriented Programming, chapter 6 - [Map sequence diagram to pseudo code](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Aorder-model-mapping-pseudocode) — Object Oriented Analysis and Design, chapter 4