preface

I have a one-way linked list. Given a head pointer and a node pointer, how can I delete the node in O(1) time? This article shares an implementation approach to solve this problem, and invites interested developers to read it.

Thought analysis

In a one-way linked list, the first way to delete a node is to start from the head node of the list and search for the node to be deleted in sequence. After finding the node, change the pointer to complete the node deletion.

Walk through the linked list and delete the node

Next, let’s take an example of a linked list and delete node 10. The deletion process would look like this:

  • Follow the pointer by traversing the list head
  • Find a pointer to node 9 pointing to node 10 (the node to be deleted)
  • Gets node 13 to which the pointer to node 10 points
  • Change the pointer of node 9 to node 13 to complete the deletion of node 10

In this way, we do delete a given node, but we need to traverse the list from scratch to find the node in order n time. It doesn’t work if it doesn’t.

Overwrite the node to achieve deletion

Now, let’s switch to another way of thinking, since the most time-consuming part is going to be traversing to find the nodes, we’re not going to traversal, and we’re going to take advantage of what they’ve given us and think about it further.

After reviewing the problem again, we find that it gives the pointer to the node to be deleted, so we can get the value that the pointer points to. With this value, we can:

  • Overwrite the values of nodes to be deleted
  • Modify pointer to delete its next node

Let’s continue with the example from the previous section, which is executed as shown below:

Note: When the next value of the node to be deleted is the last value, we simply point the pointer to the node to be deleted to NULL.

If there is a node after the next node, we just need to get that node and point its pointer to the obtained node, as shown below:

We delete the given node in O(1), but there is still a problem: if the node to be deleted is at the end of the linked list, then it has no next node. At this point, we can not use this method, but can only get the preceding nodes of the node in sequence and complete the deletion operation.

Time complexity analysis: For n-1 non-tail nodes, we can use the node coverage method to achieve deletion in O(1) time, but for tail nodes, we still need to delete nodes sequentially, the time complexity is O(n). So, the total time complexity is: [(n-1) * O(1) + O(n)] / n, and the final result is still O(1).

If there is only one node in the list and we want to remove the head node (which is also the tail node) of the list, then we need to set the head node of the list to NULL after deleting the node.

The implementation code

With that in mind, we can happily write code like this:

  • If there is only one node in the linked list, return nuL directly and the caller can delete the head node of the linked list
  • If the node to be deleted has no next node, the node to be deleted is traversed to find its last node and the pointer is null
  • Using the overwriting node method, the node is deleted
type ListNode = { element: number; next: ListNode | null };

export class DeleteLinkedListNode {
  deleteNode(listHead: ListNode, toBeDeleted: ListNode): ListNode | null {
    If there is only one node in the list, null is returned
    if (listHead.next == null) {
      return null;
    }
    // If the node to be deleted is at the end, the node is traversed sequentially to delete the node
    if (toBeDeleted.next == null) {
      let curNode = listHead.next;
      // Find the last node of the node to be deleted
      while( curNode.next ! =null&& curNode.next.element ! == toBeDeleted.element ) { curNode = curNode.next; }// The last node was found
      curNode.next = null;
      return listHead;
    }

    // If there are still nodes to be deleted, the overwrite method is adopted to achieve the purpose of deletion
    // Change the value of the node to be deleted to the value of its next node
    toBeDeleted.element = toBeDeleted.next.element;
    // The pointer of the node to be deleted points to the next node of the node to be deleted
    toBeDeleted.next = toBeDeleted.next.next;
    returnlistHead; }}Copy the code

The test case

Finally, let’s verify that the code executes correctly using the examples in the previous section.

import { DeleteLinkedListNode } from ".. /DeleteLinkedListNode.ts";
import LinkedList from ".. /lib/LinkedList.ts";

const listNode = new LinkedList();
listNode.push(3);
listNode.push(5);
listNode.push(7);
listNode.push(9);
listNode.push(10);
listNode.push(13);
listNode.push(15);

const deleteLinkedListNode = new DeleteLinkedListNode();
// Get the list header pointer and the pointer to node 10
const result = deleteLinkedListNode.deleteNode(
  listNode.getHead(),
  listNode.getElementAt(4));if (result == null) {
  // Delete the first node of the list
  listNode.removeAt(0);
}
console.log("After node 10 is deleted, the remaining nodes of the linked list are:", listNode.toString());

Copy the code

The running result is as follows:

The LinkedList class in the above code is self-implemented, and developers interested in this should move on: implementation of linked lists and variant linked lists.

The sample code

The complete code for this article example is as follows:

  • DeleteLinkedListNode.ts

  • deleteLinkedListNode-test.ts

  • LinkedList.ts

Write in the last

At this point, the article is shared.

I’m an amazing programmer, a front-end developer.

If you are interested in me, please visit my personal website for further information.

  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in the magic programmer public number, without permission to prohibit reprinting 💌