在Java中实现链表(查找/删除节点)

Question

我一直在编写一些代码来实现java中的(编辑:单向)链表。我的主要问题是当涉及到查找和删除节点时，即使用Find(data)告诉用户节点是否存在于列表中;Delete(data)实际上是在找到节点后将其从列表中删除(或者在未找到节点时不执行任何操作)。Find(data)和Delete(data)使用相同的if-else逻辑，所以现在我只是将Find方法中的代码复制到Delete方法中，并在Delete方法中使用适当的指针来"跳过"已删除的节点。

我想知道是否有更有效的方法来做这件事。我想在删除块中使用布尔值，例如:

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()方法不返回任何结果，因此不能在Delete()方法中使用它。要集中Find()和Delete()的代码，请创建另一个私有方法- getPreviousNode(int data)，它返回所需节点的前一个节点。

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"是对getPreviousNode(4)返回的节点a的引用

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

node = b;//prevNode。nextNode是'b'

  prevNode.nextNode = node.nextNode;

上一页。NextNode = c;//节点。nextNode是'c'

现在LinkedList是:

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

现在节点A有一个引用节点C作为nextNode。所以节点B从LinkedList中没有链接但没有完全从LinkedList中删除，因为节点B仍然有节点C的引用作为NextNode。所以你必须删除这个引用，以从LinkedList中完全删除节点B。

所以下面的语句是必要的

node.nextNode = null;

现在LinkedList是:

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

B[data = 4 | nextNode = null]从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( ) );
         }
      }
   }