在 Java（Finding/Deleting 个节点）中实现链表

Question

我一直在编写一些代码来实现 java 中的（编辑：单向）链表。我的主要问题是在查找和删除节点时出现的，也就是说，使用 Find(data) 告诉用户列表中是否存在节点； Delete(data) 实际上是在找到节点后从列表中删除该节点（如果找不到该节点，则不执行任何操作）。 Find(data) 和 Delete(data) 使用相同的 if-else 逻辑，所以现在我只是将 Find 方法中的代码复制到 delete 方法中，并在 delete 方法中使用适当的指针指向 "hop over" 已删除的节点。

我想知道是否有更有效的方法。我想到了在删除块中使用布尔值，例如：

public void Delete(data)
{
    if Find(data) 
    { 
        //code to delete node
    }
}

但是因为当前节点可能位于头部、尾部或中间某处，您仍然需要循环逻辑来检查您所在的位置，以便您可以设置适当的引用。例如，如果用户要删除尾部的节点，则前一个节点的下一个节点将被设置为空。但是，在中间，您必须运行一个 while 循环来遍历列表，即

while (iter.NextNode !=null)
        {
            if (iter.NextNode.data == data)
            {
                iter.NextNode = iter.NextNode.NextNode;
                System.out.println(data + " was found in the list and removed"

                break;

            }
            else if (iter.NextNode.NextNode == null && iter.NextNode.data == data) 
            {//this is kinda weird. I couldn't use an else block, because either 
             //the code would never exit the loop, or it would keep running
                iter.NextNode = null;
                System.out.println(data + " was found in the list and removed. ");
                break;
            }

        iter = iter.NextNode;

        if (node.NextNode == null && node.data != data) 
        {//i guess I could have just put this if statement inside
         //the else block
            System.out.println(data + " was not found in the list.");
            break;
        }


        }

上面的代码块处理了这两种情况。

下面的代码块是我的 Find(data) 方法：

public void Find(int data)
{
    Node node = head;
    if (head == null)
    {
        System.out.println("No nodes found. ");

    }


    else if (node.NextNode==null)
    {
        if (node.data == data)
        {
            System.out.println( data + " was found in the list.");

        }
        else
        {
            System.out.println("That value was not found in the list.");

        }
    }
    else
    {
        while (node.NextNode !=null)
        {
            if (node.data == data)
            {
                System.out.println(data + " was found in the list.");
                break;

            }
            else if (node.NextNode.NextNode == null && node.NextNode.data == data)
            {
                System.out.println(data + " was found in the list.");
                break;
            }
            else    
            {
                node = node.NextNode;
            }
            if (node.NextNode == null && node.data != data)
            {
                System.out.println(data + " was not found in the list.");
                break;
            }
        }

    }

}

如果问题不清楚：有没有办法在删除块中使用我的 Find(data) 方法，并删除所有逻辑？

感谢您的指导。非常感谢！

Answer 1

由于您的 Find() 方法 returns 什么都没有，您不能在 Delete() 方法中使用它。要集中 Find() 和 Delete() 的代码，请创建另一个私有方法 - getPreviousNode(int data)，其中 returns 所需节点的前一个节点。

private Node getPreviousNode(int data) {
    Node iter = head;

    while (iter.NextNode != null) {
        if (iter.NextNode.data == data) {
            return iter;
        }

        iter.nextNode = iter.nextNode.nextNode;
    }

    return null;
}

在 Find() 和 Delete() 方法中调用此方法。

void Find(int data) {
    // Code to handle head & tail conditions

    Node prevNode = getPreviousNode(data);

    if (prevNode != null) {
        System.out.println("Found");
    }

    ...
}

void Delete(int data) {
    // Code to handle head & tail conditions

    Node prevNode = getPreviousNode(data);

    if (prevNode != null) {
        Node node = prevNode.nextNode;
        prevNode.nextNode = node.nextNode;
        node.nextNode = null;
        System.out.println("Found & Deleted");
    }

    ...
}

回复您的评论：
只写 "prevNode.nextNode = prevNode.NextNode.NextNode" 是不够的。

考虑以下链表：

A[data = 1 | nextNode = b] --> B[data = 4 | nextNode = c] --> C[data = 55 | nextNode = null]

其中，
A、B、C：节点
a, b, c : 分别引用节点 A, B 和 C。

B：要删除的节点

现在考虑删除节点的代码：

Node prevNode = getPreviousNode(data);

prevNode = a; // "a" is a reference to Node A returned by getPreviousNode(4)

if (prevNode != null) 
  node = prevNode.nextNode;

node = b; // prevNode.nextNode is 'b'

  prevNode.nextNode = node.nextNode;

prev.NextNode = c; // node.nextNode is 'c'

现在 LinkedList 是：

A[data = 1 | nextNode = c] B[data = 4 | nextNode = c] --> C[data = 55 | nextNode = null]

现在节点 A 将节点 C 引用为下一个节点。因此节点 B 与 LinkedList 解除链接但没有完全从 LinkedList 中删除，因为节点 B 仍然引用节点 C 作为下一个节点。因此，您必须删除此引用才能从 LinkedList 中完全删除节点 B。

所以下面的语句是必要的

node.nextNode = null;

现在 LinkedList 是：

A[data = 1 | nextNode = c] --> C[data = 55 | nextNode = null]

B[data = 4 | nextNode = null] is removed from LinkedList.

Answer 2

您可以按照@SanjayChavan 的建议分享findPrevious，但是当您练习编写链表代码时，您会发现它已经很干净了，分享findPrevious 并没有使它变得更好：

boolean Delete(int data)
{
    Node prev = null, node = null;
    for (node = head; node!=null; node=(prev=node).nextNode)
    {
        if (node.data == data)
        {
            if (prev!=null)
                prev.nextNode = node.nextNode;
            else
                head = node.nextNode;
            node.nextNode = null;
            return true;
        }
    }
    return false; 
}

Node Find(int data)
{
    for (Node node = head; node != null; node = node.nextNode)
    {
        if (node.data==data)
            return node;
    }
    return null;
}

一旦 Sanjay 的代码被修复以便它可以找到并删除 head 节点，它将比这更长更复杂。

Answer 3

   public static ListNode search( List list, int target )
   {
      ListNode cursor = list.getFirst( );

      while( cursor != null )
      {
         if( cursor.getInfo( ) == target )
            return cursor;

         cursor = cursor.getLink( );
      }

      return cursor;
   }

   public void remove( int element )
   {
      ListNode cursor;
      ListNode target = search( this, element );

      if( isEmpty( ) )
         System.out.println( "There are no elements in this list." );

      if( target == null )
         System.out.println( element+" is not in this list." );
      else
      {
         if( head.getInfo( ) == element )
         {
            if( head.getLink( ) == null )
               head = null;
            else if( head == tail )
               tail = null;
            else
               head = head.getLink( );
         }
         else if( tail.getInfo( ) == element )
         { 
            for( cursor = head; cursor.getLink( ).getInfo( ) != element; cursor = cursor.getLink( ) )
            { }

            cursor.setLink( null );
            tail = cursor;
         }
         else
         {
            for( cursor = head; cursor.getLink( ).getInfo( ) != element; cursor = cursor.getLink( ) )
            { }

            cursor.setLink( cursor.getLink( ).getLink( ) );
         }
      }
   }

在 Java（Finding/Deleting 个节点）中实现链表

Implementing a linked list in Java (Finding/Deleting Nodes)

java

linked-list