✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-048

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.

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.

Complexity

O(1)

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 Head

O(1)

Delete At Tail Singly

O(n)

Delete At Tail Doubly With Tail Reference

O(1)

Delete Known Node Doubly

O(1)

Delete By Value

O(n)

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.

Related Topics

  • Singly Linked Lists

  • Doubly Linked Lists

  • Circular Linked Lists

  • Insertion in Linked Lists

  • Searching and Traversing Linked Lists

  • References and Pointers

Key Concepts

NameDescription

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

QuestionAnswer

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