从链表java中删除元素

Remove element from linked list java

提问by Violet

HI :) I have a program about linked lists and we're supposed to be able to delete two numbers if they are the same.. and i know how to do it from the start but how do you delete two numbers if they are in the middle of the linked list?? All 3 run together Heres my numbers program

嗨:) 我有一个关于链表的程序，如果两个数字相同，我们应该能够删除它们。我从一开始就知道如何做，但是如果两个数字在链表的中间？？所有 3 个一起运行 这是我的数字程序

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());
       }
    }

}

Here is the node program

这是节点程序

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;
    }
}

And here is linked lists program

这是链表程序

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;
    }

}

采纳答案by Moishe Lettvin

To remove an item in the middle of the linked list, set the previous item's "link" pointer to the "link" pointer of the object you want to remove. For instance, you could add something like this to your LinkedList class:

要删除链表中间的项目，请将前一项的“链接”指针设置为要删除的对象的“链接”指针。例如，您可以在 LinkedList 类中添加如下内容：

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

To think about this better, draw a picture.

为了更好地思考这个问题，画一张图。

 N1 -> N2 -> N3 -> N4

N1's "link" is N2, etc. If you want to remove N2, just set N1's "link" to N3.

N1的“链接”是N2，等等。如果要去掉N2，只要把N1的“链接”设置为N3即可。

 N1 -> N3 -> N4

回答by OscarRyz

One approach it to perform a brute force look up.

一种方法是执行蛮力查找。

• For each element you search if is repeated in the list.
• If it is, you remove it
• and go with the next.

• 对于您搜索的每个元素，是否在列表中重复。
• 如果是，您将其删除
• 和下一个去。

As you may see these three steps may be coded quite easy, the point here is to first understand if they do what you want.

正如您可能看到的，这三个步骤可能很容易编码，这里的重点是首先了解它们是否按照您的意愿行事。

This is the pseudo-code for these three points:

这是这三点的伪代码：

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

This approach will allow you to remove all the repeated elements.

这种方法将允许您删除所有重复的元素。

Just remember to remove one item, you have to make sure you don't lose the reference it has. So if you have:

请记住删除一项，您必须确保不会丢失它的引用。所以如果你有：

n1 -> n2 -> n3

at some point you have to have n1and n2pointing to n3( that way n1 keeps the reference n2 has )

在某些时候你必须拥有 n1并n2指向n3（这样 n1 保持引用 n2 有）

n1 -> n3  n2 ->n3

and then remove n2 which leaves you:

然后删除 n2 留下你：

n1 -> n3

Now how to code that with your specific data structure is a task you have to perform ;)

现在，如何使用您的特定数据结构对其进行编码是您必须执行的任务；)

回答by Avik Chakraborty

Here is a way to do it.

这是一种方法。

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;
        }

}
}