java - 实现单链表

Question

我正在尝试学习数据结构，但我遇到了可怕的 NullPointerException而且我不确定如何修复它。

我的 SinglyLinkedList<E>类实现一个接口(interface)，LinkedList ，我在这里重新定义了一些方法，例如 add(), get(), contains() ，等等。

NullPointerException当我使用 clear() 时发生方法。它指向方法 removeLast()在 nodeBefore.setNext(null) 下.它还指向 clear() remove(head.getElement())下的方法.

此外，如果我的代码有任何可以改进的地方，请告诉我。

public class SinglyLinkedList<E> implements LinkedList<E> {

    private class Node<E> {

        public Node<E> next;
        public E element;

        public Node(E element) {

            this.element = element;
        }

        public Node (E element, Node<E> next) {

            this.element = element;
            this.next = next;
        }

        public E getElement() {

            return element;
        }

        public Node<E> getNext() {

            return next;
        }

        public void setElement(E element) {

            this.element = element;
        }

        public void setNext(Node<E> next) {

            this.next = next;
        }

        public String toString() {

            return ("[" + element + "] ");
        }
    }

    public Node<E> head;
    public Node<E> tail;
    public int total;      

    public SinglyLinkedList() {

        this.head = null;
        this.tail = null; 
        this.total = 0;
    }

    public E get(int index) {

        if (index < 0 || index > size()) {
            return null;
        }

        if (index == 0) {
            return head.getElement();
        }

        Node<E> singly = head.getNext();

        for (int i = 1; i < index; i ++) {

            if (singly.getNext() == null) {
              return null;
            }       

            singly = singly.getNext();      
        }

        System.out.println("\n" + singly.getElement());

        return singly.getElement(); 
    }

    public void add(E element) {
        Node<E> singlyAdd = new Node<E>(element);

        if (tail == null) {
            head = singlyAdd;
            tail = singlyAdd;
        } else {
            tail.setNext(singlyAdd);
            tail = singlyAdd;
        }     

        total++;
    }             

    public void display() {
        if (head == null) {
            System.out.println("empty list");
        } else {
            Node<E> current = head;
            while (current != null) {
                System.out.print(current.toString());
                current = current.getNext();
            }
        }

    }

    public boolean contains(E data) {

        if (head == null) {
            return false;
        }

        if (head.getElement() == data) {
            System.out.println(head);
            return true;                                
        }

        while (head.getNext() != null) {
            head = head.getNext();

            if (head.getElement() == data) {
                System.out.println(head);                
                return true;                               
            }             

        } 

        return false;         
    }       

    private Node<E> removeFirst() {
        if (head == null) {
            System.out.println("We cant delete an empty list");
        }    

        Node<E> singly = head;            
        head = head.getNext();
        singly.setNext(null);
        total--;

        return singly;     
    } 

    private Node<E> removeLast() {

        Node<E> nodeBefore;
        Node<E> nodeToRemove;     

        if (size() == 0) {
            System.out.println("Empty list");
        }    

        nodeBefore = head;

        for (int i = 0; i < size() - 2; i++) {
          nodeBefore = nodeBefore.getNext();
        }    

        nodeToRemove = tail;    

        nodeBefore.setNext(null);
        tail = nodeBefore;
        total--;

        return nodeToRemove;
    }       

    public E remove(int index) {      

        E hold = get(index);     

        if (index < 0 || index >= size()) {
            return null;
        } else if (index == 0) { 

            removeFirst();    
            return hold;
        } else {

            Node<E> current = head;
            for (int i = 1; i < index; i++) {                
                current = current.getNext();
            }  

            current.setNext(current.getNext().getNext());
            total--; 
            return hold;
        }       
    }       

    public int size() {
        return getTotal();
    }

    public boolean remove(E data) {      

        Node<E> nodeBefore, currentNode; 

        if (size() == 0) {
            System.out.println("Empty list");
        }            

        currentNode = head;

        if (currentNode.getElement() == data) {
            removeFirst();
        }

        currentNode = tail;
        if (currentNode.getElement() == data) {
            removeLast();
        }

        if (size() - 2 > 0) {
            nodeBefore = head;
            currentNode = head.getNext();
            for (int i = 0; i < size() - 2; i++) {
                if (currentNode.getElement() == data) {

                    nodeBefore.setNext(currentNode.getNext());
                    total--;
                    break;
                }

                nodeBefore = currentNode;
                currentNode = currentNode.getNext();
            } 
        } 

        return true;
    }

    public void clear() {

        while (head.getNext() != null) {    
            remove(head.getElement());    
        }

        remove(head.getElement());    
    }

    private int getTotal() {
        return total;
    } 
}

Answer 1

对于您的 clear 方法，我没有看到您对每个元素进行任何清理，并且返回类型是 void，所以您只需要一个空列表.最简单的方法是简单地清除所有内容，就像在构造函数中一样:

public void clear() {
    this.head = null;
    this.tail = null; 
    this.total = 0;
}

另一个评论:

在包含中，你做

while (head.getNext() != null) {
        head = head.getNext();

        if (head.getElement() == data) {
            System.out.println(head);                
            return true;                               
        }             
    } 

这可能有两个问题(第一个适用于整个类(class))，

1. 您与比较引用的 == data 进行比较，您可能希望将值与 .equals(data) 进行比较>

编辑:即n.getElement().equals(data) 而不是 n.getElement() == data。

(或者，如果 n 和 data 可能是 null，类似于 (data != null ? data.equals( n.getElement()) : 数据 == n.getElement())

1. 您使用属性head 作为修改列表状态的扫描变量。你真的想要那个吗？