concept · INFO-CS-ADS-048Deletion in Linked Lists
Deletion in a linked list is the process of removing a node and reconnecting the remaining nodes. The operation may remove the first node, final node, or a node at a specified position.
Explanation
Overview
Linked-list deletion removes a node from the logical sequence by changing the references that connect it to neighboring nodes. The removed node must also be handled according to the programming language's memory-management rules.
Purpose
Deletion allows a linked list to shrink dynamically and supports applications in which elements are frequently removed or replaced.
Key concepts
name: Core idea; description: The central focus of deletion in linked lists is the capability described here: Deletion in a linked list is the process of removing a node and reconnecting the remaining nodes. The operation may remove the first node, final node, or a node at a specified position.; name: Problem context; description: Deletion in Linked Lists is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using deletion in linked lists, check its assumptions, input requirements, expected output, and resource constraints.
Time complexity
deleteAtHead: O(1); deleteAtTailSingly: O(n); deleteAtTailDoublyWithTailReference: O(1); deleteKnownNodeDoubly: O(1); deleteByValue: O(n); deleteAtIndex: O(n) in the general case because the target or predecessor must be located
Space complexity
O(1) auxiliary space for a typical single-node deletion, excluding any temporary storage required by a particular implementation.
Example
initialList: 10 → 20 → 30 → 40 → NULL; operation: Delete the node containing 30.; result: 10 → 20 → 40 → NULL; explanation: The node containing 20 is updated to point directly to the node containing 40.
Advantages
Removes elements without shifting an entire sequence of nodes.; Supports dynamic reduction in list size.; Deletion at the head is constant time.; Deletion of a known node can be efficient in a doubly linked list.
Example or application
Initial List
10 → 20 → 30 → 40 → NULL
Operation
Delete the node containing 30.
Result
10 → 20 → 40 → NULL
Explanation
The node containing 20 is updated to point directly to the node containing 40.
Definition
Linked-list deletion removes a node from the logical sequence by changing the references that connect it to neighboring nodes. The removed node must also be handled according to the programming language's memory-management rules.
Purpose
Deletion allows a linked list to shrink dynamically and supports applications in which elements are frequently removed or replaced.
Deletion Locations
Beginning: Remove the current head.
End: Remove the final node.
Middle: Remove a node between two existing nodes.
By value: Find and remove a node containing a specified value.
By position: Remove the node at a specified index.
General Procedure
Identify the node to remove.
Locate its predecessor when required.
Reconnect the surrounding nodes.
Update the head or tail if necessary.
Release or otherwise manage the removed node's memory.
Verify that the remaining list is connected correctly.
Delete From Beginning
Steps
Check whether the list is empty.
Store the current head if it must be released explicitly.
Move the head to the second node.
Release or discard the removed node according to the language's memory model.
Special Case
If the removed node was the only node, the head and tail must both become empty.
Delete From End
Steps
Check whether the list is empty.
Locate the node immediately before the tail.
Set its next reference to null.
Update the tail reference.
Handle the single-node case separately.
Complexity
O(n) for a singly linked list because the predecessor must generally be located through traversal.
Delete From Middle
Steps
Locate the target node and its predecessor.
Set the predecessor's next reference to the target node's successor.
Handle the removed node's memory according to the language.
Complexity
O(1) after the predecessor and target are known; O(n) when traversal is required.
Doubly Linked Deletion
In a doubly linked list, connect the target node's predecessor to its successor and connect the successor back to the predecessor. Update the head or tail when the target is at either boundary.
Circular Linked Deletion
In a circular linked list, deletion must preserve the final-node-to-head connection. Removing the head, tail, or only node requires corresponding updates to the circular references.
Advantages
Removes elements without shifting an entire sequence of nodes.
Supports dynamic reduction in list size.
Deletion at the head is constant time.
Deletion of a known node can be efficient in a doubly linked list.
Limitations
Finding the target node may require sequential traversal.
Singly linked deletion generally requires access to the predecessor.
Incorrect updates can disconnect the remaining list.
Manual memory management requires careful handling of removed nodes.
Time Complexity
Delete At Tail Singly
O(n)
Delete At Tail Doubly With Tail Reference
O(1)
Delete Known Node Doubly
O(1)
Delete At Index
O(n) in the general case because the target or predecessor must be located
Space Complexity
O(1) auxiliary space for a typical single-node deletion, excluding any temporary storage required by a particular implementation.
Implementation Considerations
Check for an empty list before deletion.
Handle deletion of the only node.
Update the head and tail references correctly.
Avoid dereferencing a node after it has been released.
Update both previous and next references in doubly linked lists.
Preserve circular connections in circular lists.
Common Applications
Removing completed tasks
Managing browser-history entries
Updating playlists
Maintaining dynamic collections
Removing graph edges from adjacency lists
Learning Objectives
Understand how deletion changes node connections.
Describe deletion at the beginning, end, and middle.
Explain the role of a predecessor in singly linked lists.
Compare deletion in singly and doubly linked lists.
Analyze deletion complexity and memory-management requirements.
Key Takeaways
Deletion removes a node from the logical sequence.
The surrounding nodes must be reconnected.
Deleting the head takes O(1) time.
Deleting the tail of a singly linked list generally takes O(n).
Removed nodes must be handled safely according to the language's memory model.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of deletion in linked lists is the capability described here: Deletion in a linked list is the process of removing a node and reconnecting the remaining nodes. The operation may remove the first node, final node, or a node at a specified position. |
Problem context | Deletion in Linked Lists is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using deletion in linked lists, check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of deletion in linked lists? | Deletion in a linked list is the process of removing a node and reconnecting the remaining nodes. The operation may remove the first node, final node, or a node at a specified position. |
What should be checked before applying deletion in linked lists? | For deletion in linked lists, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of deletion in linked lists be validated? | Trace a representative deletion in linked lists case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures