Вставка после определенного узла в связанном списке

Question

Вот мой полный исходный код Java для реализации отдельно связанного списка. Я видел много учебников, где они говорили о вставке узла в начале. Итак, я решил добавить в мой код метод insertAfterNode(int y), где я могу добавлять данные внутри узла после определенного узла.

/* 
* To change this license header, choose License Headers in Project Properties. 
* To change this template file, choose Tools | Templates 
* and open the template in the editor. 
*/ 
package datastructures; 

/** 
* 
* @author Administrator 
*/ 
public class Link { 

    int data; 

    Link next; 

    public Link(int d) { 

     this.data = d; 
    } 

    public void display() { 

     System.out.println(data); 
    } 


    public static class LinkedList { 

     Link first; 

     public void insertItemFirst(int x){ 

      Link newLink = new Link(x); 

      newLink.next = first; 
      first = newLink; 


     } 



     public Link deleteFirst() { 

      Link temp = first; 
      first = first.next; 
      return temp; 
     } 

     public void displayList() { 

      Link current = first; 

      while (current != null) { 

       current.display(); 
       current = current.next; 

      } 

     } 

     // START Of METHOD 


     public void insertAfterNode(int y) { 

      // Considering LinkedList is Sorted 
      Link newNode = new Link(y); 

      Link current = first; 

      while (current != null) { 

       while (current.data < y) { 

        current = current.next; 
        newNode.next = current; 
        current = newNode; 

       } 

      } 

     } 





     //END Of METHOD 

    } 



    public static void main(String[] args) { 

     LinkedList addelements = new LinkedList(); 

     addelements.insertItemFirst(20); 
     addelements.insertItemFirst(30); 
     addelements.insertItemFirst(40); 
     addelements.insertItemFirst(50); 
     addelements.insertAfterNode(44); 



     addelements.displayList(); 

     System.out.println("After Calling Deletion Method Once "); 

     addelements.deleteFirst(); 



     addelements.displayList(); 

    } 

} 

Этот код продолжает работать в Netbeans, и мне пришлось остановить сборку, чтобы выйти из нее. Я считаю, что что-то не так с моей реализацией метода. Пожалуйста, дайте мне знать, что не так в моем следующем методе:

public void insertAfterNode(int y) { 

      // Considering LinkedList is Sorted 
      Link newNode = new Link(y); 

      Link current = first; 

      while (current != null) { 

       while (current.data < y) { 

        current = current.next; 
        newNode.next = current; 
        current = newNode; 

       } 

      } 

     } 

Код работает просто отлично, без метода выше.

Answer 1

current Ссылка ссылки изменяется только в том случае, если значение y больше, чем current.data. Если fist.data, скажем, 10, а y равно 5, ваш код никогда не будет завершен.

Вы должны изменить свой цикл while(current != null). Не используйте внутренний while.

Link newNode = new Link(y); 
// "first" requires a special treatment, as we need to replace the "first" value 
if(first.data > y){ 
    // insert the new Link as first element 
    newNode.next = first; 
    first = newNode; 
} else { 
    // we need the previous Link, because previous.next will be set to the newNode 
    Link previous = first; 
    Link current = first.next; 

    while (current != null) { 
     if(current.data < y) { 
      previous = current; 
      current = current.next; 
     } else { 
      // we insert newNode between previous and current 
      // btw. what should happen if current.data == y? 
      previous.next = newNode; 
      newNode.next = current; 
      break; // we are done, quit the cycle 
     } 
    } 
    // if the newNode.next is null at this point, means we have not inserted it yet. 
    // insert it as the last element in the list. previous is pointing at it. 
    if(newNode.next == null){ 
     previous.next = newNode; 
    } 
} // end of else 

P.S. Я надеюсь, что это работает, я не проверял код :)