From Passion to Profession
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use

Data Structure - Delete a Node from a Single Linked List

10/6/2013

0 Comments

 
Picture
When you're asked to delete a node from a given single linked list. Here's my thought process:
  1. Define the contract for the function.
  2. Check on boundary conditions.
  3. Code for the generic case.

This code snippet below demonstrates a quick way of removing a middle node from a single linked list:
public class LinkedList{                                           
  ...
  public boolean deleteNode(LinkedListNode n) {

    if (n == null){                                                       
      return true;
    }

    if (n.next == null){           // to remove the last node
      // deal with this boundary case separately
      // might require iterating through the whole list to get the previous node
      // ...
      return true;
    }


    // generic case, replace given node with its next node
    LinkedListNode next = n.next;
    n.data = next.data;
    n.next = next.next;

    return true;
  }
  ...
}


#1) Define the contract for the function

I'd assume I have a LinkedList class, I want to have a function that, given a node, remove/delete the given node from the linked list it belongs to and return a boolean to indicate success or failure.
  public boolean deleteNode(LinedListNode n)

#2) Check on boundary conditions

The first boundary condition to check is whether the passed-in node n is null. If so, there's nothing to delete, and you may consider the delete-a-node operation is successful or failed at your discretion.

The second boundary condition to check is if the given node to be deleted is the last node, that is, n.next == null. As such, the #1 approach won't work but to code extra to deal with this scenario.

#3) Code for the generic case

To quickly remove a node from the linked list, modify the given node to hold data of its next node, then return either true or false of the removal operation. The GC will remove the orphaned next node of the given node eventually.
0 Comments



Leave a Reply.

    Categories

    All
    Algorithm
    Concurrency
    CQ
    Data Structure
    Design Pattern
    Developer Tool
    Dynamic Programming
    Entrepreneur
    Functional Programming
    IDE
    Java
    JMX
    Marketing
    Marklogic
    Memory
    OSGI
    Performance
    Product
    Product Management
    Security
    Services
    Sling
    Social Media Programming
    Software Development

    Feed Widget

    Archives

    May 2020
    March 2020
    April 2018
    March 2018
    February 2018
    December 2017
    March 2017
    November 2016
    June 2016
    May 2016
    April 2016
    October 2015
    September 2015
    August 2015
    September 2014
    July 2014
    June 2014
    May 2014
    March 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013
    August 2013
    July 2013
    June 2013

    RSS Feed

in loving memory of my mother  and my 4th aunt
Photos from net_efekt, schani, visnup, Dan Zen, gadl, bobbigmac, Susana López-Urrutia, jwalsh, Philippe Put, michael pollak, oskay, Creative Tools, Violentz, Kyknoord, mobilyazilar