Saistītais saraksts ir lineāra datu struktūra, kurā elementi netiek glabāti blakus esošā vietā, bet gan ir saistīti, izmantojot rādītājus. Saistītais saraksts veido savienotu mezglu sēriju, kur katrs mezgls saglabā datus un nākamā mezgla adresi.
Mezgla struktūra: Saistītā saraksta mezgls parasti sastāv no diviem komponentiem:
Dati: Tajā ir faktiskā vērtība vai dati, kas saistīti ar mezglu.
Nākamais rādītājs: Tas saglabā secības nākamā mezgla atmiņas adresi (atsauci).
Galva un aste: Saistītajam sarakstam var piekļūt, izmantojot galveno mezglu, kas norāda uz pirmo mezglu sarakstā. Pēdējais mezgls sarakstā norāda uz NULL vai nullptr, norādot saraksta beigas. Šis mezgls ir pazīstams kā astes mezgls.
Kāpēc nepieciešama saistītu sarakstu datu struktūra?
Tālāk ir norādītas dažas saistītā saraksta priekšrocības. Tas palīdzēs jums saprast, kāpēc tas ir jāzina.
- Dinamiskā datu struktūra: Atmiņas lielumu var piešķirt vai atcelt darbības laikā, pamatojoties uz operācijas ievietošanu vai dzēšanu.
- Vienkārša ievietošana/dzēšana: Elementu ievietošana un dzēšana ir vienkāršāka nekā masīvus, jo pēc ievietošanas un dzēšanas neviens elements nav jāpārvieto, ir jāatjaunina tikai adrese.
- Efektīva atmiņas izmantošana: Kā mēs zinām, saistītais saraksts ir dinamiska datu struktūra, kuras lielums palielinās vai samazinās atbilstoši prasībām, lai tādējādi izvairītos no atmiņas izšķērdēšanas.
- Īstenošana: Izmantojot saistītu sarakstu, piemēram, steku, rindu, grafiku, jaucējkartes utt., var ieviest dažādas uzlabotas datu struktūras.
Piemērs:
Sistēmā, ja mēs uzturam sakārtotu ID sarakstu masīvā id [] = [1000, 1010, 1050, 2000, 2040].
Ja vēlamies ievietot jaunu ID 1005, tad, lai saglabātu sakārtoto secību, visi elementi ir jāpārvieto pēc 1000 (izņemot 1000).
Dzēšana ir dārga arī ar masīviem, līdz tiek izmantotas īpašas metodes. Piemēram, lai dzēstu 1010 id[], viss pēc 1010 ir jāpārvieto, tāpēc tiek veikts tik daudz darba, kas ietekmē koda efektivitāti.
Saistīto sarakstu veidi :
Saistītie saraksti galvenokārt ir trīs veidu:
- Viens saistīts saraksts
- Divkārši saistīts saraksts
- Apļveida saistīts saraksts
1. Viens saistīts saraksts :
Atsevišķi saistītā sarakstā katrs mezgls satur atsauci uz nākamo secības mezglu. Atsevišķi saistīta saraksta šķērsošana tiek veikta virzienā uz priekšu.
Viens saistīts saraksts
2. Divkāršais saraksts :
Divkāršā sarakstā katrs mezgls satur atsauces gan uz nākamo, gan uz iepriekšējo mezglu. Tas ļauj pārvietoties gan uz priekšu, gan atpakaļ, bet tai ir nepieciešama papildu atmiņa atpakaļgaitas atsaucei.
Divkāršais saraksts
3. Apļveida saistīts saraksts :
Apļveida saistītā sarakstā pēdējais mezgls norāda atpakaļ uz galveno mezglu, izveidojot apļveida struktūru. Tas var būt vai nu atsevišķi, vai divreiz saistīts.
pārdēvējiet Linux direktoriju
Apļveida saistīts saraksts
Darbības saistītajos sarakstos
- Ievietošana : Jauna mezgla pievienošana saistītajam sarakstam ietver esošo mezglu rādītāju pielāgošanu, lai saglabātu pareizu secību. Ievietošanu var veikt saraksta sākumā, beigās vai jebkurā vietā
- Dzēšana : Lai noņemtu mezglu no saistītā saraksta, ir jāpielāgo blakus esošo mezglu norādes, lai pārvarētu dzēstā mezgla atstāto atstarpi. Dzēšanu var veikt saraksta sākumā, beigās vai jebkurā vietā.
- Meklēšana : Konkrētas vērtības meklēšana saistītajā sarakstā ietver saraksta šķērsošanu no galvenā mezgla, līdz tiek atrasta vērtība vai tiek sasniegts saraksta beigas.
Saistītā saraksta sarežģītības analīze :
- Laika sarežģītība: O(n)
- Palīgtelpa: O(n)
Saistīto sarakstu priekšrocības
- Dinamiskais izmērs: Saistītie saraksti var dinamiski augt vai sarukt, jo atmiņas piešķiršana tiek veikta izpildlaikā.
- Ievietošana un dzēšana: Saistītā saraksta elementu pievienošana vai noņemšana no tā ir efektīva, īpaši lieliem sarakstiem.
- Elastība: Saistītos sarakstus var viegli reorganizēt un modificēt, neprasot blakus esošu atmiņas bloku.
Saistīto sarakstu trūkumi
- Brīvpiekļuve: Atšķirībā no masīviem saistītie saraksti neļauj tieši piekļūt elementiem pēc indeksa. Lai sasniegtu noteiktu mezglu, ir nepieciešama šķērsošana.
- Papildu atmiņa: Saistītajiem sarakstiem, salīdzinot ar masīviem, ir nepieciešama papildu atmiņa rādītāju glabāšanai.
Secinājums:
Saistītie saraksti ir daudzpusīgas datu struktūras, kas nodrošina dinamisku atmiņas piešķiršanu un efektīvas ievietošanas un dzēšanas darbības. Saistīto sarakstu pamatu izpratne ir būtiska ikvienam programmētājam vai datorzinātņu entuziastam. Izmantojot šīs zināšanas, jūs varat ieviest saistītos sarakstus, lai atrisinātu dažādas problēmas un paplašinātu izpratni par datu struktūrām un algoritmiem.