java - 从头开始排序插入单链表

Question

我一直在尝试从头开始创建一个仅接受字符串的排序链表，但在插入时对其进行排序。这是我当前的代码:

import java.util.Arrays;

public class SortedLinkedList {

    private StringNode head = null;

    /**
     * Default Constructor for a sorted linked list
     */
    public SortedLinkedList() {}

    /**
     * Will add a new node with the specified data to the correctly sorted 
     * position in the list
     */
    public void add(String data) {

        if (head == null) {
            head = new StringNode(data);
        }

        StringNode temp = new StringNode(data);
        StringNode current = head;

        if (current != null) {
            while (current.getNext() != null) {
                if (current.getData().toString().compareTo(current.getNext().getData().toString()) < 0) {
                    temp.setNext(current.getNext());
                    current.setNext(temp);
                } else
                    current.setNext(temp);
            }
        }
    }

    /**
     * Will remove the node that matches the specified data from the list.
     * Returns true if node is found, otherwise will return false
     */
    public boolean remove(String data) {
        StringNode current = head;

        if (head != null) {

            while (current.getNext() != null) {

                if (current.getData().toString().equals(data)) {
                    current.setNext(current.getNext().getNext());
                    return true;
                }

                current = current.getNext();
            }
        }
        return false;
    }

    /**
     * Will cycle through the list and display each item on a new line
     */
    public void display() {

        if (head != null) {

            StringNode current = head.getNext();
            System.out.print("[");

            while (current.getNext() != null) {
                System.out.print(current.getData().toString() + ", ");
                current = current.getNext();
            }

            System.out.print("]");
        }
    }

    // Inner Class 

    class StringNode {

        String data;
        StringNode next;

        public StringNode(String nodeData) {
            next = null;
            data = nodeData;
        }

        /**
         * Getter of Data
         */
        public String getData() {
            return data;
        }

        /**
         * Getter of Next
         */
        public StringNode getNext() {
            return next;
        }

        /**
         * Setter of Data
         */
        public void setData(String newData) {
            data = newData;
        }

        /**
         * Setter of Next
         */
        public void setNext(StringNode nextNode) {
            next = nextNode;
        }
    }

}

我能够在不进行插入排序的情况下进行添加，但是，在我尝试使用插入编码进行编码后，它崩溃了。似乎不再增加任何值(value)。我的驱动程序当前的输出:

public class Driver {
    public static void main(String[] args) {
        SortedLinkedList name = new SortedLinkedList();

        name.add("v");
        name.add("a");
        name.add("b");

        name.display();
    }
}

是我的显示方法中的空指针异常，第70行，这是我的while循环的创建。我完全迷失了，需要一些指导。谢谢。

Answer 1

您实际上想检查 current == null 是否，因为最后一个元素的 .getNext() 为 null。

while (current != null)

重构一下:

// should print [] for empty SLL; no dangling comma
public void display() {

  String out = "[";
  StringNode current = head;

  while(current != null) {
      out = out + current.getData();
      current = current.getNext();
      if (current != null)
        out = out + ", ";
  }
  out += "]";
  System.out.print(out);
}

编辑:此外，您的添加/删除方法需要重新设计...尝试在纸上逐步完成算法，然后将条件/操作转换为 Java。

示例:

/**
 * Will add a new node with the specified data to the correctly sorted 
 * position in the list
 */
public void add(String data) {
  StringNode temp = new StringNode(data);

  if(head == null) {
      head = temp;
      return; // only adding one node
  }

  StringNode previous = head;

  if (data.compareTo(previous.getData()) < 0) {
     head = temp; // temp < head, so we add it to the beginning
     head.setNext(previous);
     return; // done
  }

  StringNode current = previous.getNext();

  while (current != null) {
      if (data.compareTo(current.getData()) < 0) {
          temp.setNext(current);
          previous.setNext(temp);
          return; // done
      } else {
          previous = current;
          current = previous.getNext();
      }
  }
  // current == null, so we reached the end of the list;
  previous.setNext(temp);
}