从链表中删除元素Java

Question

你好 :) 我有一个关于链表的程序，我们需要能够删除两个相同的数字。我知道如何从开头删除它们，但如果这两个数字在链表中间，该怎么办呢？所有数字都连在一起了。以下是我的数字程序：

import java.util.Scanner;

public class Numbers {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner reader = new Scanner (System.in);
        LinkedList link=new LinkedList();
        LinkedList link2= new LinkedList();
        System.out.println("Enter in 5 numbers to put in your list");
        int num1, num2, num3, num4, num5;
        num1 = reader.nextInt();
        link.addToStart(num1);
        num2 = reader.nextInt();
        link.addToStart(num2);
        num3 = reader.nextInt();
        link.addToStart(num3);
        num4 = reader.nextInt();
        link.addToStart(num4);
        num5 = reader.nextInt();
        link.addToStart(num5);

        link2.addToStart(num5);
        link2.addToStart(num4);
        link2.addToStart(num3);
        link2.addToStart(num2);
        link2.addToStart(num1);

        System.out.println("The size of the linked list is " + link.size());

        System.out.print("Here is the list ");
        link2.outputList();
        System.out.println();
        System.out.print("Here is the list in reverse order ");
        link.outputList( );
        System.out.println();

        if (num1==num2){
             link2.deleteHeadNode(num1);
             link2.deleteHeadNode(num2);
             System.out.println("Here is the list with the removed numbers");
            link2.outputList();
            System.out.println();
            System.out.println("Here is its size");
            System.out.println(link2.size());
        }
        else if (num2==num3){
            link2.deleteHeadNode(num2);
            link2.deleteHeadNode(num3);
            System.out.println("Here is the list with the removed numbers");
           link2.outputList();
           System.out.println();
           System.out.println("Here is its size");
           System.out.println(link2.size());
       }
    }

}

这是一个Node程序。

public class Node1
{
    private Object item;
    private int count;
    private Node1 link;

    public Node1( )
    {
        link = null;
       item = null;
        count = 0;
    }

    public Node1(int num, int newCount, Node1 linkValue)
    {
        setData(num, newCount);
        link = linkValue;
    }

    public void setData(int num, int newCount)
    {
        item = num;
        count = newCount;
    }

    public void setLink(Node1 newLink)
    {
        link = newLink;
    }

    public Object getItem( )
    {
        return  item;
    }

    public int getCount( )
    {
        return count;
    }

    public Node1 getLink( )
    {
        return link;
    }
}

这是一个链表程序

public class LinkedList
{
    private Node1 head;

    public LinkedList( )
    {
        head = null;
    }

    /**
     Adds a node at the start of the list with the specified data.
     The added node will be the first node in the list.
    */
    public void addToStart(int num)
    {
        head = new Node1(num, num, head);
    }

    /**
     Removes the head node and returns true if the list contains at least
     one node. Returns false if the list is empty.
     * @param num1 
    */
    public boolean deleteHeadNode(int num1 )
    {
        if (head != null)
        {
            head = head.getLink( );
            return true;
        }
        else
            return false;
    }

    /**
     Returns the number of nodes in the list.
    */
    public int size( )
    {
        int count = 0;
        Node1 position = head;

        while (position != null)
        {
            count++;
            position = position.getLink( );
        }
        return count;
    }

    public boolean contains(String item)
    {
        return (find(item) != null);
    }

    /**
     Finds the first node containing the target item, and returns a
     reference to that node. If target is not in the list, null is returned.
    */
    private Node1 find(String target)
    {
        Node1 position = head;
        Object itemAtPosition;
        while (position != null)
        {
            itemAtPosition = position.getItem( );
            if (itemAtPosition.equals(target))
                return position;
            position = position.getLink( );
        }
        return null; //target was not found
    }

    public void outputList( )
    {
        Node1 position = head;
        while (position != null)
        {
            System.out.print(position.getItem( ) + " ");
            position = position.getLink( );
        }
    }

    public boolean isEmpty( )
    {
        return (head == null);
    }

    public void clear( )
    {
        head = null;
    }

}

- Violet

---

应该打上作业标签，并且你应该学习循环。;-) - Nicolas Buduroi

Answer 1

为了从链表中删除一个元素，需要将前一个元素的“link”指针设置为要删除的对象的“link”指针。例如，您可以在LinkedList类中添加以下内容：

public void removeNode(Node previousNode, Node nodeToRemove) {
  if (previousNode != null) {
    previousNode.setLink(nodeToRemove.getLink());
  }
}

为了更好地理解，可以画个图。

 N1 -> N2 -> N3 -> N4

N1的“链接”是N2，如果你想要移除N2，只需要将N1的“链接”设置为N3。

 N1 -> N3 -> N4

- Moishe Lettvin

---

我经常听说删除LinkedList的时间复杂度是O(1)，但是为了能够传入“nodeToRemove”，我们需要遍历LinkedList，这不会使时间复杂度变成O(n)吗？ - Declan McKenna

Answer 2

一种方法是进行暴力查找。

• 对于每个元素，您搜索是否在列表中重复。
• 如果是，则删除它。
• 并继续下一个。

正如您所看到的，这三个步骤可以很容易地编码，关键在于首先了解它们是否符合您的要求。

这是这三个点的伪代码：

forEach( Element a : inList ) do
    // e is the element we want to find repeated.
    forEach( Element b : inList ) do  
         // b is the element in the list.
         if( a == b ) then // repeated
             inList.remove( a ) 
             break;
         endIf
     endFor
 endFor

这种方法可以帮助您删除所有重复的元素。

只需记住，如果要删除一个项，您必须确保不会丢失其引用。因此，如果您有：

n1 -> n2 -> n3

在某个时刻，您需要让n1和n2指向n3（这样n1就保留了n2的引用）。

n1 -> n3  n2 ->n3

然后移除 n2，这将使你得到：

n1 -> n3

现在如何使用您特定的数据结构编写代码是您需要执行的任务 ;)

- OscarRyz

Answer 3

这是一种做法。

public void delete(int item)
{
        while(head.data==item)              //For deleting head
    {

        head=head.link;

    }
    // For middle elements..................
    Node ptr, save;
    save=head;
    ptr=head.link;
    while(ptr!=null)
    {
        if(ptr.data==item)
        {
        Node next=ptr.link;
        save.link=next;
        ptr=next;
        }
        else
        {
            save=ptr;
            ptr=ptr.link;
        }

}
}

- Avik Chakraborty