Chèn nút vào giữa Danh sách được liên kết và vô tình chèn nút rỗng cũng

Question

Tôi đang làm việc trên một chương trình không sử dụng lớp được xây dựng trong Danh sách liên kết của Java; Tôi đang xây dựng nó từ đầu. Tôi đã thành công với mọi thứ ngoại trừ việc viết một phương thức chèn một Node vào một vị trí cụ thể của danh sách liên kết.

Tôi có một phương pháp đặt một nút cụ thể làm nút "hiện tại". Vì vậy, ví dụ, tôi có một danh sách liên kết trông như thế này: mèo ->chó ->làm ->tốt ->vật nuôi, và "hiện tại" bằng 2; điều đó có nghĩa là nút "hiện tại" là "chó".

Từ đây, giả sử tôi muốn chèn Nút mới ở vị trí "hiện tại" có trường thông tin đọc và. Nếu được thực hiện một cách chính xác, danh sách liên kết cuối cùng sẽ là: mèo ->và ->chó ->làm ->tốt ->vật nuôi; "và" sẽ thay thế "chó" tại vị trí 2.

Vì vậy, đây là vấn đề của tôi: phương pháp của tôi hoạt động để chèn một Nút mới ở vị trí thứ hai, nhưng đã xảy ra lỗi khi liên kết nút mới được tạo với các nút đã tồn tại trước đó. Tôi không chỉ chèn nút mới vào danh sách, mà còn chèn một nút không có thông tin trước "chó". Như mã của tôi hiện đang chạy, đầu ra trông như thế này: mèo ->và -> (trống) ->chó ->làm ->tốt ->vật nuôi.

Tôi chắc chắn 99,9% vấn đề nằm trong phần (nếu hiện tại! = Null) của mã, tôi không thể tìm ra cách khắc phục.

Bất kỳ suy nghĩ nào về lý do tại sao tôi chèn một nút trống ngoài nút mà tôi thực sự muốn thêm?

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(); 
    } 
} 

EDIT

Toàn bộ chương trình là khá dài, nhưng ở đây là "setline" phương pháp mà bộ hiện nay tương đương với bất cứ vị trí người dùng muốn chèn Node của họ tại. Nó lấy một tham số "int line" được lấy thông qua một dấu nhắc người dùng.

public Node setLine(int line) { 

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

Answer 1

Đây là mã chèn nút đúng cách. Đây sẽ là điểm khởi đầu tốt, chúc may mắn (bạn có thể đọc thêm tại đây: 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;  
        }  
      }  
     }  
} 

Answer 2

Bạn có thể tham khảo phương pháp sau chèn nút ở giữa, dựa trên chỉ mục.

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; 
}