Past exam question: 2066 Jestha (Back), Q3
Open in the Padhaiko appWhat are the types of linked list? Discuss the consideration that has to be taken while developing algorithm/program with a linked list. Why alias variables are dangerous in a linked list? Write an algorithm to delete the first node in a singly linked list.
Solution
Types of Linked List & Design Considerations:
- Types: Singly Linked List (SLL), Doubly Linked List (DLL), Circular Linked List (CLL), and Circular Doubly Linked List.
- Key Programming Considerations:
- Null-Pointer Guards: Always check
head == NULLorptr == NULLbefore dereferencingptr->dataorptr->next. - Boundary Cases: Explicitly handle empty lists, single-node lists, and operations at head vs. tail.
- Memory Management: Check
mallocfailure (NULL) on insertion andfree()detached nodes to prevent memory leaks. - Link Update Order: Save references (
temp = ptr->next) before overwriting pointers so the remaining list is not lost.
- Null-Pointer Guards: Always check
Why Alias Variables Are Dangerous in a Linked List: An alias occurs when two pointer variables (e.g., p and q) point to the exact same node in memory. If one pointer frees the node (free(p)) or alters its next field, the other pointer q becomes a dangling pointer—dereferencing q later causes undefined behavior, corrupt data, or crashes (segmentation faults), and freeing q causes a double-free error.
Algorithm to Delete the First Node in a Singly Linked List:
Algorithm DELETE_FIRST(head):
1. If head == NULL:
Print "List Underflow"
Return NULL
2. temp = head
3. head = head->next
4. Free(temp)
5. Return headLinked lists include singly, doubly, and circular variants. Safe code checks NULL boundaries, frees removed nodes, and preserves links before overwriting. Aliases risk dangling pointers and double-frees when two pointers share one node. DELETE_FIRST sets temp = head; head = head->next; Free(temp).