链表实现java

Question

我已经在 J​​ava 中实现了一个链表。我已经创建了所有内容，但是我很难删除具有特定数据的特定节点。它正在抛出一个NullPointerException. 我相信，我得到的是NullPointerException因为下一个节点为空。如果有人可以请指出我正确的方向，那就太好了。

输入

anything
one
two
three

例外：

Exception in thread "main" java.lang.NullPointerException
    at LinkedList.remove(LinkedList.java:28)
    at Main.main(Main.java:29)

类：链表类

public class LinkedList {

    // fields
    private Node head;
    private Node last;
    private int size = 0;

    // constructor, used when the class is first called
    public LinkedList() {
        head = last = new Node(null);
    }

    // add method
    public void add(String s) {
        last.setNext(new Node(s));
        last = last.getNext();
        size++;
    }

    // remove method, if it returns false then the specified index element doens not exist
    // otherwise will return true
    public boolean remove(String data) {
        Node current = head;
        last = null;
        while(current != null) {
            if(current.getData().equals(data)) {
                current = current.getNext();
                if(last == null) {
                    last = current;
                }else {
                    last.getNext().setNext(current);
                    size--;
                    return true;
                }
            }else {
                last = current;
                current = current.getNext();
            }
        }
        return false;
    }
    //will return the size of the list - will return -1 if list is empty
    public int size() {
        return size;
    }

    // will check if the list is empty or not
    public boolean isEmpty() {
        return true;
    }

    // @param (index) will get the data at specified index
    public String getData(int index) {

        if(index <= 0) {
            return null;
        }

        Node current = head.getNext();
        for(int i = 1;i < index;i++) {
            if(current.getNext() == null) {
                return null;
            }
            current = current.getNext();
        }

        return current.getData();
    }

    //@param will check if the arguement passed is in the list
    // will return true if the list contains arg otherwise false
    public boolean contains(String s) {
        for(int i = 1;i<=size();i++) {
            if(getData(i).equals(s)) {
                return true;
            }
        }
        return false;
    }

    //@return contents of the list - recursively 
    public String toString() {
        Node current = head.getNext();
        String output = "[";
        while(current != null) {
            output += current.getData()+",";
            current = current.getNext();
        }
        return output+"]";
    }

    //@return first node
    public Node getHead() {
        return head;
    }

    // @return (recursively) list
    public void print(Node n) {
        if(n == null) {
            return;
        }else {
            System.out.println(n.getData());
            print(n.getNext());
        }
    }
}

主要的

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException{
        LinkedList list = new LinkedList(); // declaring main linked list
        LinkedList b_List = new LinkedList(); // declaring the backup list

        String input = null;
        // getting input from user, will stop when user has entered 'fin'
        while(!(input = br.readLine()).equals("fin")) {
            list.add(input); // adding to main list
            b_List.add(input);
        }

        list.print(list.getHead().getNext());

        System.out.println("Input Complete.");
        if(list.size() == 1) {
            System.out.println("You have entered only one name. He/She is the survior");
        }else {
            System.out.println("Enter the name(s) would like to remove: ");
            while(b_List.size() != 1) {
                String toRemove = br.readLine();
                b_List.remove(toRemove);
            }
        }
        System.out.println("The contestants were: ");
        list.print(list.getHead().getNext());
    }
}

节点

public class Node {

    // Fields
    private String data;
    private Node next;

    // constructor
    public Node(String data) {
        this(data,null);
    }

    // constructor two with Node parameter
    public Node(String data, Node node) {
        this.data = data;
        next = node;
    }

    /**
     * Methods below return information about fields within class
     * */

    // @return the data
    public String getData() {
        return data;
    }

    // @param String data to this.data
    public void setData(String data) {
        this.data = data;
    }

    // @return next
    public Node getNext() {
        return next;
    }
    // @param Node next set to this.next
    public void setNext(Node next) {
        this.next = next;
    }

}

Answer 1

首先，你的头只是一个before-first标记，所以你不应该从它开始删除检查。

其次，remove如果节点数据是null

第三 - 您的实现无论如何都被破坏了，因为last.getNext().setNext(current)- 它不会将前一个节点与下一个链接，它将当前链接到下一个（即什么都不做）

第四 - 由于神秘的操作，它仍然无法删除第一个元素last......

的正确实现是remove这样的：

public boolean remove(String data){
    Node previous = head;
    Node current = head.getNext();
    while (current != null) {
        String dataOld = current.getData();
        if ((dataOld == null && data == null) || (dataOld != null && dataOld.equals(data))) {
            Node afterRemoved = current.getNext();
            previous.setNext(afterRemoved);
            if (afterRemoved == null) { // i.e. removing last element
                last = previous;
            }
            size--;
            return true;
        } else {
            previous = current;
            current = current.getNext();
        }
    }
    return false;
}