Блог

я думаю, что ArrayList имеет сложность O (n) для вставки элементов в начале, потому что он сдвигает остальные элементы на одно место вправо. и LinkedList имеет O (n) для вставки элементов в конце, потому что он должен проходить через каждый элемент. таким образом, время, затраченное на обе вышеуказанные операции, должно быть сравнительным, но когда я сделал это практически, потребовалось 34057 миллисекунд для вставки arraylist в начале и только 41 миллисекунду для вставки LinkedList в конце, в то время как оба имеют O (n) временную сложность. почему это так?

с точки зрения сложности пространства, какой из них лучше?

вот мой код

 public void timeTakenEnd(String name, List<Integer> list) {


    for (int i = 0; i < 1E5; i  ) {
        list.add(i);

    }


    long start = System.currentTimeMillis();
    for (int i = 0; i < 1E5; i  ) {
        list.add(i);

    }

    long end = System.currentTimeMillis();

    System.out.println("time taken for: "   name   " to insert elements in the end is  "   (end - start));

}

public void timeTakenBeg(String name, List<Integer> list) {


    for (int i = 0; i < 1E5; i  ) {
        list.add(i);

    }


    long start = System.currentTimeMillis();
    for (int i = 0; i < 1E5; i  ) {
        list.add(0, i);

    }

    long end = System.currentTimeMillis();

    System.out.println("time taken for: "   name   "to insert elements in the beginning is  "   (end - start));

}

public static void main(String[] args) {

    ArrayList<Integer> alist = new ArrayList<Integer>();
    LinkedList<Integer> llist = new LinkedList<Integer>();

    TimeComplexity demo = new TimeComplexity();

    demo.timeTakenEnd("arrarylist", alist); //25 miliseconds on my machine
    demo.timeTakenEnd("linkedlist", llist);//41 miliseconds on my machine

    demo.timeTakenBeg("arraylist", alist);// 34057 miliseconds on my machine
    demo.timeTakenBeg("linkedlist", llist); //60 miliseconds on my machine

}
  

}

LinkedList является двусвязным списком. Он запоминает свои первый и последний элементы и позволяет перемещаться по списку в обоих направлениях.

Таким образом, добавление элемента в конец — это просто способ создания узла и назначения указателей a last next и a previous . Это O (1).

Обратите внимание, что Java имеет открытый исходный код, а исходный код поставляется с JDK. Вы могли бы легко найти реализацию:

 public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size  ;
    modCount  ;
}
  

Как показывает его имя (и Javadoc), ArrayList он внутренне реализован массивами.

Итак, вставка элемента включает перемещение всех элементов за ним на одну позицию вперед.

С другой стороны, a LinkedList нужно только перенаправить ссылки на элементы, чтобы вставить новый узел, поэтому его время более постоянное.

Список массивов использует непрерывное хранилище, поэтому для вставки в начале требуется либо переместить все существующие элементы на единицу вверх, либо перераспределить весь список. Связанный список может поместить новый элемент в любом месте, если ссылки настроены правильно. Нет необходимости перемещать другие элементы списка, просто настройте несколько ссылок.