确定在List的末尾附加值的复杂性

Question

我们知道，在列表前面推送一个元素需要O（1）时间。现在考虑我们想在列表的末尾放置（或追加）一个元素。这项行动的复杂性是什么？

现在考虑，要将一个元素放在列表的末尾，我们需要遍历列表到最后（因为没有prev。指针），需要O（n）时间复杂度。是否有可能在O（1）中做到这一点？

我做了一些实现，在最后附加值时，我在指针中保留下一个位置，可以插入节点。请查看以下内容：

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

我搜索过，但我没有得到任何满意的东西！如果我犯了一些错误，请纠正我！

Answer 1

如果在链表数据结构中保存对front / head元素的引用，则可以在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;
    }
}