Hogyan értékeljük a beszúrás, törlés és keresés műveletek időbeli összetettségét egy láncolt listában?

A láncolt lista műveleteinek időbeli összetettsége attól függ, pontosan mit csinálunk, és van-e hozzáférésünk a szükséges elemhez:

• Beszúrás:

  • A lista elejére — O(1), mivel elegendő a hivatkozásokat módosítani.
  • Egy egysoros láncolt lista végére hivatkozó mutató nélkül — O(n), végig kell menni az egész listán.
  • Végére mutatóval — O(1).
  • Bármilyen helyre (index vagy érték szerint) — O(n), meg kell találni a pozíciót.

• Törlés:

  • Az első elem törlése — O(1).
  • Érték vagy index szerint törlés — O(n), meg kell találni az elemet és az előzőt.

• Keresés:

  • Elem keresése érték szerint — O(n), végig kell menni a listán.

Így a fő műveletek lineáris időt igényelnek, ha nincs közvetlen hozzáférés a szükséges csomópontokhoz. Ez a láncolt listák szekvenciális természetéből adódik.