Почему удаление и вставка в список ссылок быстрее, чем Arraylist?

Question

Я пытаюсь понять, почему вставка и удаление в LinkList - это O (1), а не O (N), как в ArrayLists. Общее объяснение состоит в том, что, поскольку LL формируется из двусвязного списка, вам просто нужно изменить ссылки. Но разве вам все равно не нужно искать место, куда вы вставляете или удаляете? Разве вы не пересекаете LL, чтобы достичь рассматриваемого адреса, прежде чем вы сможете даже изменить следующую и предыдущую ссылки, сделав это временем O (N)?

Answer 1

Но разве вам все равно не нужно искать место, куда вы вставляете или удаляете? Разве вы не проходите LL, чтобы достичь рассматриваемого адреса, прежде чем вы сможете изменить следующую и предыдущую ссылки, сделав это временем O (N)?

Не всегда . Во многих случаях структура данных может содержать ссылку (или указатель / итератор) непосредственно на узел списка. Этот справочник помогает алгоритмам быстро удалить узел позже (в O(1), без какого-либо обхода). Например, это может иметь место на сетевом сервере, обрабатывающем список клиентов: структура данных, содержащая контекстную информацию о клиенте, может ссылаться на узел, чтобы быстро удалить клиента из списка после того, как клиент отключен (чтобы масштабировать ну с количеством активных клиентов). В этом случае полный обход не требуется.