java - 确定在列表末尾 append 值的复杂性

Question

众所周知，将一个元素压入列表的前面需要 O(1) 时间。现在考虑我们想要在列表末尾放置(或追加)一个元素。这个操作的复杂度是多少？

现在考虑一下，要将一个元素放在列表的末尾，我们需要遍历列表直到末尾(因为没有 prev. 指针)，需要 O(n) 时间复杂度。有可能在 O(1) 内完成这个任务吗？

我做了一些实现，在末尾 append 值时，我保留了指针中可以插入节点的下一个位置。请检查以下内容:

import java.util.*;

class List{

    int data;
    List next;
    List(int data){
       this.data = data;
    }
}

class Driver{

    List head, temp;

    Driver(){
       head = null;
       temp = head;
    }

    void push(int item){

       if(head == null){
          head = new List(item);
          temp = head;
       } else {
          temp.next = new List(item);
          temp = temp.next;         
       }
    }
}

class AppendInList{

    public static void main(String [] args){

       Driver obj = new Driver();
       obj.push(5);
       obj.push(66);
    }
}

我在SO中搜索，但没有得到任何让我满意的东西!如果我做错了请纠正我!

Answer 1

如果您在链表数据结构中保存对前/头元素的引用，则可以在 O(1) 时间内将元素推送到链表的前面。

类似地，您可以维护对 last 元素的引用，使用它可以在 O(1) 时间内将元素添加到最后一个元素。每次添加元素时，您都必须更新 last 指针。

数据结构如下所示:

class List{
    ListNode head;//ListNode class stores next reference and value of the node
    ListNode tail;//last element
    void pushToLast(ListNode newElement){
         //TODO : Take care of corner cases
         tail.next = newElement;
         tail = newElement;
    }
}