Определение сложности добавления значения в конце списка

Question

Как мы знаем, для выталкивания элемента в начало списка требуется O (1) время.Теперь рассмотрим, что мы хотим поместить (или добавить) элемент в конец списка.Какова сложность этой операции?

Теперь рассмотрим, чтобы поместить элемент в конец списка, нам нужно пройти по списку до конца (из-за отсутствия предварительного указателя), требуется 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);
    }
}

Я искал в SO, но ничего не получил для своего удовлетворения!Поправь меня, если я сделал какую-то ошибку!

Answer 1

Вы можете поместить элемент в начало связанного списка за O (1) раз, если вы сохранили ссылку на элемент front / head в структуре данных связанного списка.

Аналогично, вы можете сохранить ссылку на элемент 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;
    }
}