単独でリンクされたリストのlastNodeを削除する

Question

をチェックすることはできますか？単一のリンクされたリストから最後のノードを削除するにはどうすればよいですか？

最初のノードを削除する方法と同じですか？

これはあなただけの尾前に、ノードに到達するために、リストを反復処理する必要があります単独でリンクされたリストであるので

def deleteAtTail(self): 
    prev = None 
    temp = self.tail 
    self.tail= self.tail.prev 
    delete temp 

Answer 1

先頭からtailに戻る必要があります。 テールは次の番号のない最初のノードです：next is None。 最後の次の番号（temp）を追跡し、そのnextをNoneに設定します。 Noneからtemp.nextの設定

def deleteAtTail(self): # remove_last would likely be a better name 
    """ removes the last element of the singly linked list 
    """ 
    temp = self.head 
    while(temp.next is not None): 
     temp = temp.next 
    temp.next = None 

単独リンクリスト内のテール・ノード（それはそれへの他の参照が存在しない場合はガベージコレクトされます）

Answer 2

を最後のノードを削除

def deleteAtHead(self): 
    temp = self.head 
    self.head = self.head.next 
    delete temp 

最初のノードを削除します。私はあなたの関数は、単に一時はちょうどリストの最後の前のノードと同じであるので、我々はself.tail = tempを設定

def deleteAtTail(self): 
    temp = self.head 
    while(temp.next != None): 
     if temp.next == tail: #finds the node just before tail 
      break 
     temp = temp.next 
    temp.next = None 
    self.tail = temp 

する必要があるだろうと思います。したがって、tempを削除し（最後の参照を削除して）、リストの2番目のノードから最後のノードに指定されたnodeと同じtailを設定します。これは実際にリストの新しい終わりになります。

EDIT：

この回答へのコメントのいくつかの懸念に対処するために。単一または二重リンクリストを扱うときは、head,tailおよびcurrentポインタを維持することをお勧めします。テールがどこにあるかを知ることは、計算上妥当なものをあなたのリストに挿入するために非常に貴重です。

これはあなたの挿入方法は、ここから行くことができることを意味します

def insert(value): 
    self.tail.next = Node() 
    self.tail.next.value = value 
    self.tail = self.tail.next 

、実質的に、より有利な時間複雑性を有するものです。このまでの時間の複雑性O（n）を持ってい

def insert(value): 
    temp = self.head 
    while(temp.next != None): 
     temp = temp.next 
    temp.next = Node() 
    temp.next.value = value 

O（1）の

Answer 3

以前のリストノードの参照がないため、O（n）= cの複雑さを持つ単一リンクリストでの削除操作はできません。現在のノードと以前のノードを覚えているリストの最後まで移動し、次に削除しようとしているノードの次のノードへの参照から前のノードをトリムする必要があります。これは、単一リンクリストでは常にO（n）= nの複雑さを持ちます。