Байланыштуу тизмедеги элементтерди кошуу, өчүрүү жана издөө операцияларынын убакыттык татаалдыгын кантип баалоо кылса болот?

Байланыштуу тизмедеги операциялардын убакыттык кыйынчылыгы биз эмне кылып жатканыбызга жана керектүү элементке жетүүбүзгө жараша болот:

• Кошуу:

  • Тизмектин башында — O(1), анткени шилтемелерди өзгөртүү жетиштүү.
  • Бир багыттуу байланган тизмектин акыркысына — O(n), бүт тизмекти өтүшүбүз керек.
  • Акыркыга көрсөткүч менен — O(1).
  • Ар бир жерге (индекс же мааниге жараша) — O(n), ордун табышыбыз керек.

• Өчүрүү:

  • Биринчи элементти өчүрүү — O(1).
  • Мааниге же индекске жараша өчүрүү — O(n), элементти жана анын мурункусун табышыбыз керек.

• Издөө:

  • Мааниге жараша элементти издөө — O(n), тизмекти өтүшүбүз керек.

Ошондуктан, негизги операциялар керектүү түйүндүн түздөн-түз жеткиликтүүлүгү болбосо, сызыктык убакыт талап кылынат. Бул байланган тизмектердин үзгүлтүксүз табиятынан келип чыгат.