按字母顺序排列的双链表实现

Question

我试图在Java中建立一个按字母顺序组织的链表，但是到目前为止我的实现看起来像在插入和重新排列链表的逻辑上遇到了麻烦，数据包含一个用于组织的名称获取器它在列表中的位置：

    class Node
{

   private Data data;
   private Node nextNode;

   public Node (Data data, Node nextElement)
   {
      this.nextNode = nextElement;
      this.data = data;
   }

   public Node getNextNode ()
   {
      return nextNode;
   }

   public void setNextNode (Node nextNode)
   {
      this.nextNode = nextNode;
   }

   public Data getData ()
   {
      return data;
   }

   public void setData (Data data)
   {
      this.data = data;
   }
}

然后我的链表类别如下：

public class LinkedList {
    private Node head = null;
    private int size = 0; 

    public void addData(Data c){
        this.size++;

        //empty case
        if(this.head == null){
            this.head = new Node(c, null);
            return;
        }



        Node current = this.head;
        Node previous = null;

        while(current.getNextNode()!=null&&previous.getData().getFirstName().compareTo(c.getFirstName())<=1){
            previous = current; // hold last element 
            current = current.getNextNode(); //move to next element
           }

        //insert into list
        if(current.getNextNode()==null){
            current.setNextNode(new Node(c,null)); //append end of List 
            previous = new Node(current.getData(), current);
        }else{
            Node insert = new Node(c, current); //prepend infront
            current.setNextNode(insert);
        }

我尝试的一切似乎都给了我的nullpointer异常，但也许我在这里没有得到正确的概念。我首先检查列表是否为空，并在其前面添加一个指向null的节点。给定新节点后，我将遍历当前列表，直到找到一个位置并将先前的指针设置为当前指针，而当前指针将成为指向列表中下一项的新节点（假设我们不在末尾）列表中，它只是指向null）。

我现在很迷失，我的this.head去哪儿了？或者在所有极端情况下我都必须这样做？任何理解的帮助将不胜感激

Answer 1

您的实现是Double-LinkedList，它不包含对先前节点的引用。

这里如何顺序插入

        public void addData(Data c) {
            Node newNode = new Node(c, null);

            if (head == null) {
                head = newNode;
                size++;
                return;
            }

            Node current = head;
            Node prev = null;
            int comparison;

            while (current != null) {
                comparison = c.getFirstName().compareTo(current.getData().getFirstName());
                if (comparison == 0) {
                    return;
                } else if (comparison > 0) { /// greater than
                    if (current.nextNode == null) { // check if reach tail of the linked list add and break
                        current.nextNode = newNode;
                        break;
                    }
                } else { // less then
                    if (prev == null) { // check if it should be first then put and break
                        Node oldHead = head;
                        head = newNode;
                        head.nextNode = oldHead;
                        break;
                    }
                    prev.nextNode = newNode;
                    newNode.nextNode = current;
                    break;
                }
                prev = current;
                current = current.nextNode;
            }
            size++;
        }

Answer 2

public void addData(Data c) {
    this.size++;

    //empty case
    if (this.head == null) {
        this.head = new Node(c, null);
        return;
    }


    Node current = this.head;
    Node previous = null;

    //change in Code
    while (current.getNextNode() != null && current.getData().getFirstName().compareTo(c.getFirstName()) <= 1) {
        previous = current; // hold last element
        current = current.getNextNode(); //move to next element
    }

    //insert into list
    if (current.getNextNode() == null) {
        current.setNextNode(new Node(c, null)); //append end of List
        previous = new Node(current.getData(), current);
    } else {
        Node insert = new Node(c, current); //prepend infront
        current.setNextNode(insert);
    }

}