在恆定時間內添加在單向鏈表的末尾

Question

我正在嘗試編寫一個方法，用於在恆定時間內添加單個鏈表的末尾。我不知道如何在常量時間內指定列表中最後一個節點的指針。這種方法在0（n）的運行：

public void insertEnd(Object obj) { 
if (head == null) { 
    head = new SListNode(obj); 
} else { 
    SListNode node = head; 
    while (node.next != null) { 
    node = node.next; 
    } 
    node.next = new SListNode(obj); 
} 
size++; 
} 

這是我的新方法的開端：

public void addLast(SListNode obj){ 
    //if the list is empty, the new element is head and tail 
    if(tail == null){ 
     obj.next = null; 
     head = tail = obj; 
    }else{ -----> here I'm confused 

    } 
} 

這是我SLIST類：

public class SList { 
    private SListNode head; 
    private SListNode tail; 
    private int size; 

    public SList() { 
    size = 0; 
    head = null; 
    tail = null; 

} 

Answer 1

我認爲這應該覆蓋它：（應該在else）

tail.next = obj; // have (the current tail).next point to the new node 
tail = obj; // assign 'tail' to point to the new node 
obj.next = null; // may not be required 

Answer 2

您必須實現Double Ended Queue允許插入您的名單的頭部或尾部

如果您的名單是空的，頭部和尾部是空的，如果它包含一個元素head == tail

public void addLast(SListNode obj){ 
//if the list is empty, the new element is head and tail 
if(tail == null){ 
    obj.next = null; 
    head = tail = obj; 
}else{ -----> here I'm confused 
    tail.next = obj; 
    tail = obj; 
}