Mekkora az időbeli komplexitása az elemek beszúrásának, törlésének és keresésének egy egysínű láncolt listában?

Egyszerű láncolt listában a műveletek a következő időbeli összetettséggel rendelkeznek:

• Beszúrás:

  • A lista elejére — O(1), mivel elegendő megváltoztatni a fej mutatóját.
  • A végére vagy tetszőleges helyre — O(n), mivel végig kell menni a listán a kívánt pozícióig.

• Törlés:

  • Az első elem törlése — O(1).
  • Egy elem törlése érték vagy pozíció szerint — O(n), mivel meg kell találni az elemet és az előző csomópontot.

• Keresés:

  • Egy elem keresése érték szerint — O(n), mivel végig kell menni a listán szekvenciálisan.

Ezért a lista elejére történő beszúrás és törlés nagyon gyors, míg a többi lineáris időt igényel a lista átvitelének szükségessége miatt.