如何从通用链表中正确删除一个节点？

Question

我试图从通用链表中删除一个节点，而不是删除整个列表。我希望它删除一个类似的项目。我试图找到这样做的正确方法。我还需要它去最后一个节点，准备在删除节点后添加节点。

import java.util.Scanner;


import java.io.*;


class MyGenericList <T extends Comparable<T> >
{
    private  class Node<B>
     {
        T value;
        Node<T>  next;
     }   

     private Node<T> first = null;
     int count = 0;

    public void  add(T element)
     {
         Node<T> newnode = new Node<T>();
         newnode.value = element;
         newnode.next = null;

        if (first == null)
        {
            first = newnode;
        }
        else
        {
            Node<T> lastnode = gotolastnode(first);
            lastnode.next = newnode;
        }
         count++;
     }

    public void remove(T element)
    {
        Node<T> newnode = new Node<T>();
        Node<T> prevnode = new Node<T>();
        Node<T> curnode = new Node<T>();

        prevnode.value = element;
        curnode.next = null;
        int hopcount=0;

        while(hopcount < count)
        {
            if(prevnode == element)
            {
                prevnode.next = first;
                Node<T> lastnode = gotolastnode(first);
                lastnode.next = newnode;
            }

            hopcount++;
        }
        count--;
       }

    public T get(int pos)
    {
         Node<T> Nodeptr = first;
         int hopcount=0;
         while (hopcount < count && hopcount<pos)
         {   if(Nodeptr != null)
             {
                Nodeptr = Nodeptr.next;
             }
             hopcount++;
         }
        return  Nodeptr.value;
    }

    private Node<T> gotolastnode(Node<T> nodepointer) 
    {
       if (nodepointer== null )
        {
          return nodepointer;
        } 
        else
        {
            if (nodepointer.next == null)
               return nodepointer;
            else
                 return gotolastnode( nodepointer.next);

        }

    }
}

class Employee implements Comparable<Employee>
{
    String name;
    int age;
    @Override
    public int compareTo(Employee arg0) 
    {
        // TODO Auto-generated method stub
        return 0;
        // implement compareto method here. 
    }
    Employee( String nm, int a)
    {
        name =nm;
        age = a;
    }
}

class City implements Comparable<City>
{

    String name;
    int population;
    City( String nm, int p)
    {
        name =nm;
        population = p;
    }
    @Override
    public int compareTo(City arg0) {
        // TODO Auto-generated method stub
        return 0;
        // implement compareto method here. 
    }

}
public class GenericLinkedList
{

    public static void main(String[] args) throws IOException
    {
        MyGenericList<Employee> ml = new MyGenericList<>();

        ml.add(new Employee("john", 32));
        ml.add(new Employee("susan", 23));
        ml.add(new Employee("dale", 45));
        ml.add(new Employee("eric", 23));

        Employee e1 = ml.get(0);
       System.out.println(  "Name " + e1.name + " Age "+ e1.age );

       ml.remove(new Employee("john", 32));
       System.out.println(  "Name " + e1.name + " Age "+ e1.age );

       ml.add(new Employee("john", 32));
       System.out.println(  "Name " + e1.name + " Age "+ e1.age );


       MyGenericList<City> citylist = new MyGenericList<>();

        citylist.add(new City("Los Angeles", 320000));
        citylist.add(new City("Santa monica", 230000));
        citylist.add(new City("San Francisco", 450000));
        citylist.add(new City("San Diego", 23000));
        City c= citylist.get(2);
        System.out.println(  "City " + c.name + " Population "+ c.population );
    }
}

我没有删除整个列表，而是删除了一个。

Answer 1

使用数据结构时，在尝试编写代码之前使用实际图表可能特别有用。我们来看看：

我们可以看到，我们只需将prev指向cur之外的节点（我们需要删除的节点）。步骤如下：

1）声明两个节点，第一个指向第一个（prev），第二个指向prev之后的节点。

2）使用while循环将cur和prev增加到正确的位置（cur应该指向要删除的节点）。

3）用一行代码删除节点（prev.next = cur.next）。

4）减少计数，你就完成了。

（如果你需要为addLast操作定位，只需将cur移动到最后一个节点，即cur = cur.next，而cur.next！= null）。

按值删除的完整代码如下：

 public void remove(T element){

    Node<T> cur = first.next;
    Node<T> prev = first;
    Node<T> nn = new Node(element);//I'm assuming you have constructors that accept data
    boolean deleted = false;

    while(cur!=null&&deleted == false){
           if(cur.data.equals(element)){
                         prev.next = cur.next;
                         this.count--;
                         deleted = true;

                     }

        }

prev = gotolastnode(prev);
prev.next = nn;
}

这应该根据您的方法签名进行删除。但是，您可能必须更改gotolastnode方法才能使其正常工作。