添加项目结束链表

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

}