在链表中间插入节点，不小心插入空节点

Question

我在做一个程序，没有使用Java的内置链表类；我在从头开始做。除了编写一个将节点插入链表的特定位置的方法外，我在所有方面都取得了成功。

我有一个方法将一个特定的节点设置为“当前”节点。所以，例如，我有一个链表，看起来是这样的：猫-->狗-->使-->好-->宠物，“当前”等于2；这意味着“当前”节点是“狗”。

从这里开始，假设我想在“current”的位置插入一个新节点，它的info字段为AND。如果做得正确，最后的链表将是：猫-->和-->狗-->使-->好-->宠物；“和”将取代位置2的“狗”。

所以我的问题是：我的方法在位置2插入一个新节点，但是在将新创建的节点链接到先前存在的节点时会出错。我不仅在列表中插入了我的新节点，而且还在“dogs”之前插入了一个没有信息的节点。当我的代码当前运行时，输出看起来是这样的:cats-->and-->（空白）-->dogs-->make->good-->pets。

我99.9%确定问题出在代码的（如果当前！=null)部分，我只是不知道如何修复它。

有什么想法，为什么我要插入一个空白节点之外，我实际上想要添加的节点？

public void insert () {

    System.out.println("Please enter the text you wish to insert, or type \"end\" if you are done inserting.");
    String theString;
    theString = console.nextLine();

    while (!theString.equals("end")){
        newNode = new Node ();
        newNode.info = theString;
        newNode.next = null;

        if (first == null){
            first = newNode;
            last = newNode;
        } else if (current != null){
            Node p = new Node (current.info, current.next);
            current.info = newNode.info;
            current.next = p;
        }
        else {
            last.next = newNode;
            last = newNode;
        }

        System.out.println("Please enter the text you wish to insert, or type \"end\" if you are done inserting.");
        theString = console.nextLine();
    }   
}

编辑

整个程序相当长，但这里是“setline”方法，它将当前值设置为用户希望插入节点的任何位置。它采用一个参数“int line”，该参数是通过用户提示获得的。

public Node setLine(int line) {

    int index = 0;
    current = first;
    while (index < line) {
        previous = current;
        current = current.next;
        index++;
    }
    return current;
}

Answer 1

您可以参考以下方法，该方法基于索引在中间插入节点。

public boolean insertInMiddle(int index, int data){

    boolean isInserted = false;

    Node node = new Node(data);
    Node temp = head;
    int i=0;
    if(index >= 0 && index <= size()){
        isInserted = true;
        if(index == 0){
            if(head !=null){
                node.nextNode = head;
                head.prevNode = node;
                head = node;
            }else{
                head = node;
                tail=node;
            }
        }else{
            while(i<index){
                temp = temp.nextNode;
                i++;
            }               
            if(temp == null){
                node.nextNode = temp;
                node.prevNode = tail;
                node.prevNode.nextNode = node;
                tail=node;
            }else{
                node.nextNode = temp;
                node.prevNode = temp.prevNode;
                temp.prevNode = node;
                node.prevNode.nextNode = node;
            }
        }
    }       
    return isInserted;
}

//Method to get the size
public int size(){
    int size = 0;

    Node node = head;
    if(node !=null){
        while (node !=null){
            size++;
            node = node.nextNode;
        }
    }

    return size;
}

Answer 2

下面是正确插入节点的代码。这应该是一个很好的起点，祝你好运（你可以在这里阅读更多内容:http://www.algolist.net/data_structures/singly-linked_list/insertion)。

public class SinglyLinkedList {

      public void addLast(SinglyLinkedListNode newNode) {    
            if (newNode == null)    
                  return;    
            else {    
                  newNode.next = null;    
                  if (head == null) {    
                        head = newNode;    
                        tail = newNode;    
                  } else {    
                        tail.next = newNode;    
                        tail = newNode;    
                  }    
            }    
      }

      public void addFirst(SinglyLinkedListNode newNode) {    
            if (newNode == null)    
                  return;    
            else {    
                  if (head == null) {    
                        newNode.next = null;    
                        head = newNode;    
                        tail = newNode;    
                  } else {    
                        newNode.next = head;    
                        head = newNode;    
                  }    
            }    
      }

      public void insertAfter(SinglyLinkedListNode previous,    
                  SinglyLinkedListNode newNode) {    
            if (newNode == null)    
                  return;    
            else {    
                  if (previous == null)    
                        addFirst(newNode);    
                  else if (previous == tail)   
                        addLast(newNode);    
                  else {    
                        SinglyLinkedListNode next = previous.next;    
                        previous.next = newNode;    
                        newNode.next = next;    
                  }    
            }    
      }    
}