添加項目結束鏈表

Question

我爲考試做準備的，這是從舊的測試問題：

我們有一個表頭與下面的聲明單鏈表：

class Node { 
    Object data; 
    Node next; 
    Node(Object d,Node n) { 
     data = d; 
     next = n; 
    } 
} 

編寫一個方法void addLast(Node header, Object x)，在列表的末尾添加x。

我知道，如果我真的有這樣的事情：

LinkedList someList = new LinkedList(); 

我可能只是做項目添加到結束：

list.addLast(x); 

但我怎麼能做到這一點嗎？

Answer 1

class Node { 
    Object data; 
    Node next; 
    Node(Object d,Node n) { 
     data = d ; 
     next = n ; 
     } 

    public static Node addLast(Node header, Object x) { 
     // save the reference to the header so we can return it. 
     Node ret = header; 

     // check base case, header is null. 
     if (header == null) { 
      return new Node(x, null); 
     } 

     // loop until we find the end of the list 
     while ((header.next != null)) { 
      header = header.next; 
     } 

     // set the new node to the Object x, next will be null. 
     header.next = new Node(x, null); 
     return ret; 
    } 
} 

Answer 2

循環於具有未來指向null，則修改下一個指針指向它具有數據=物體和下一指針= NULL

Answer 3

要導航通過一個新的節點鏈表的最後一個元素整個鏈表使用循環並檢查每個節點的「下一個」值。最後一個節點將是下一個值爲空的節點。只需將此節點的下一個值作爲您使用輸入數據創建的新節點即可。

node temp = first; // starts with the first node. 

    while (temp.next != null) 
    { 
     temp = temp.next; 
    } 

temp.next = new Node(header, x); 

這就是基本思想。這當然是僞代碼，但它應該足夠簡單來實現。

Answer 4

這是一個提示，你有一個鏈表中的節點圖，並且你總是保持對頭的引用，它是鏈表中的第一個節點。
下一個指向鏈表中的下一個節點，所以當下一個爲空時，你在列表的末尾。

Answer 5

這裏是一個部分解決您的鏈表類，我已經離開了執行，其餘給你，也留下了很好的建議添加一個尾節點的鏈表，你的一部分，以及。

節點文件：

public class Node 
{ 
    private Object data; 
    private Node next; 

    public Node(Object d) 
    { 
     data = d ; 
     next = null; 
    } 

    public Object GetItem() 
    { 
     return data; 
    } 

    public Node GetNext() 
    { 
     return next; 
    } 

    public void SetNext(Node toAppend) 
    { 
     next = toAppend; 
    } 
} 

這裏是一個鏈接列表文件：

public class LL 
{ 
    private Node head; 

    public LL() 
    { 
     head = null; 
    } 

    public void AddToEnd(String x) 
    { 
     Node current = head; 

     // as you mentioned, this is the base case 
     if(current == null) { 
      head = new Node(x); 
      head.SetNext(null); 
     } 

     // you should understand this part thoroughly : 
     // this is the code that traverses the list. 
     // the germane thing to see is that when the 
     // link to the next node is null, we are at the 
     // end of the list. 
     else { 
      while(current.GetNext() != null) 
       current = current.GetNext(); 

      // add new node at the end 
     Node toAppend = new Node(x); 
      current.SetNext(toAppend); 
     } 
    } 
} 

Answer 6

上述計劃可能會給你的NullPointerException。這是一種將元素添加到linkedList結尾的更簡單的方法。

public class LinkedList { 
    Node head; 

    public static class Node{ 
     int data; 
     Node next; 

     Node(int item){ 
      data = item; 
      next = null; 
     } 
    } 
    public static void main(String args[]){ 
     LinkedList ll = new LinkedList(); 
     ll.head = new Node(1); 
     Node second = new Node(2); 
     Node third = new Node(3); 
     Node fourth = new Node(4); 

     ll.head.next = second; 
     second.next = third; 
     third.next = fourth; 
     fourth.next = null; 

     ll.printList(); 
     System.out.println("Add element 100 to the last"); 
     ll.addLast(100); 
     ll.printList(); 
    } 
    public void printList(){ 
     Node t = head; 
     while(n != null){ 
      System.out.println(t.data); 
      t = t.next; 
     } 

    } 

    public void addLast(int item){ 
     Node new_item = new Node(item); 
     if(head == null){ 
      head = new_item; 
      return; 
     } 
     new_item.next = null; 

     Node last = head; 
     Node temp = null; 
     while(last != null){ 
      if(last != null) 
       temp = last; 
      last = last.next; 
     } 

     temp.next = new_item; 
     return; 
    } 
} 

Answer 7

addLast（）需要一些優化，因爲addLast（）中的while循環具有O（n）複雜性。以下是我的LinkedList實現。使用ll.addLastx（i）運行一次代碼，並再次使用ll.addLast（i）運行代碼，您可以看到它們在使用addLast（）處理addLastx（）的時間方面存在很大差異。

Node.java

package in.datastructure.java.LinkedList; 

/** 
* Created by abhishek.panda on 07/07/17. 
*/ 
public final class Node { 
    int data; 
    Node next; 

    Node (int data){ 
     this.data = data; 
    } 
    public String toString(){ 
     return this.data+"--"+ this.next; 
    } 
} 

LinkedList的。java

package in.datastructure.java.LinkedList; 
import java.util.ArrayList; 
import java.util.Date; 

public class LinkedList { 

    Node head; 
    Node lastx; 
    /** 
    * @description To append node at end looping all nodes from head 
    * @param data 
    */ 
    public void addLast(int data){ 

     if(head == null){ 
      head = new Node(data); 
      return; 
     } 
     Node last = head; 
     while(last.next != null) { 
      last = last.next; 
     } 
     last.next = new Node(data); 
    } 


    /** 
    * @description This keep track on last node and append to it 
    * @param data 
    */ 
    public void addLastx(int data){ 

     if(head == null){ 
      head = new Node(data); 
      lastx = head; 
      return; 
     } 
     if(lastx.next == null){ 
      lastx.next = new Node(data); 
      lastx = lastx.next; 
     } 

    } 

    public String toString(){ 
     ArrayList<Integer> arrayList = new ArrayList<Integer>(10); 
     Node current = head; 
     while(current.next != null) { 
      arrayList.add(current.data); 
      current = current.next; 
     } 
     if(current.next == null) { 
      arrayList.add(current.data); 
     } 
     return arrayList.toString(); 
    } 


    public static void main(String[] args) { 
     LinkedList ll = new LinkedList(); 
     /** 
     * @description Checking the code optimization of append code 
     */ 
     Date startTime = new Date(); 
     for (int i = 0 ; i < 100000 ; i++){ 
      ll.addLastx(i); 
     } 
     Date endTime = new Date(); 
     System.out.println("To total processing time : " + (endTime.getTime()-startTime.getTime())); 
     System.out.println(ll.toString()); 
    } 

}