Удалить элемент из связанного списка Java

Question

HI :) У меня есть программа о связанных списках, и мы должны быть в состоянии удалить два числа, если они совпадают ... и я знаю, как это сделать с самого начала, но как удалить два числа, если они находятся в середине связанного списка ?? Все 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());
       }
    }

}

Вот программа узла

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

}

Answer 1

Чтобы удалить элемент в середине связанного списка, установите указатель «ссылка» предыдущего элемента на указатель «ссылка» объекта, который вы хотите удалить. Например, вы можете добавить что-то вроде этого в свой класс 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

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

Теперь, как закодировать, что с вашей конкретной структурой данных - это задача, которую вы должны выполнить;)

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

}
}