Kas ir izlaišanas saraksts?

Izlaist saraksts ir varbūtības datu struktūra. Izlaist sarakstu izmanto, lai saglabātu sakārtotu elementu vai datu sarakstu ar saistīto sarakstu. Tas ļauj efektīvi skatīt elementu vai datu procesu. Vienā solī tas izlaiž vairākus visa saraksta elementus, tāpēc to sauc par izlaišanas sarakstu.

Izlaišanas saraksts ir saistītā saraksta paplašināta versija. Tas ļauj lietotājam ļoti ātri meklēt, noņemt un ievietot elementu. Tas sastāv no pamata saraksta, kas ietver elementu kopu, kas uztur turpmāko elementu saišu hierarhiju.

Izlaist saraksta struktūru

Tas ir veidots divos slāņos: zemākais slānis un augšējais slānis.

Izlaižamā saraksta zemākais slānis ir parasts sakārtots saistīto saraksts, un izlaižamā saraksta augšējie slāņi ir kā “ātrā līnija”, kurā elementi tiek izlaisti.

Izlaist saraksta sarežģītības tabula

Izlaist saraksta darbība

Ņemsim piemēru, lai izprastu izlaišanas saraksta darbību. Šajā piemērā mums ir 14 mezgli, tādējādi šie mezgli ir sadalīti divos slāņos, kā parādīts diagrammā.

Apakšējais slānis ir kopēja līnija, kas savieno visus mezglus, un augšējais slānis ir ātrā līnija, kas savieno tikai galvenos mezglus, kā redzams diagrammā.

Pieņemsim, ka šajā piemērā vēlaties atrast 47. Jūs sāksiet meklēšanu no pirmā ātrās līnijas mezgla un turpināsiet darboties ātrās līnijas rindā, līdz atrodat mezglu, kas ir vienāds ar 47 vai vairāk par 47.

Piemērā var redzēt, ka 47 ekspresrindā neeksistē, tāpēc jūs meklējat mezglu, kas ir mazāks par 47, kas ir 40. Tagad jūs pārejat uz parasto rindu, izmantojot 40, un meklējat 47, kā parādīts diagrammā.

Piezīme. Kad atrodat šādu mezglu uz 'ātrās līnijas', jūs pārejat no šī mezgla uz 'parasto joslu', izmantojot rādītāju un meklējot mezglu parastajā rindā.

Izlaist sarakstu Pamatdarbības

Izlaižamajā sarakstā ir šādi darbību veidi.

Ievietošanas darbība:To izmanto, lai konkrētā vietā pievienotu jaunu mezglu konkrētā situācijā.Dzēšanas darbība:To izmanto, lai dzēstu mezglu konkrētā situācijā.Meklēšanas darbība:Meklēšanas darbība tiek izmantota, lai meklētu noteiktu mezglu izlaišanas sarakstā.

Ievietošanas operācijas algoritms

 Insertion (L, Key) local update [0...Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] lvl = random_Level() if lvl > L → level then for i = L → level + 1 to lvl do update[i] = L → header L → level = lvl a = makeNode(lvl, Key, value) for i = 0 to level do a → forward[i] = update[i] → forward[i] update[i] → forward[i] = a 

Dzēšanas darbības algoritms

 Deletion (L, Key) local update [0... Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] if a → key = Key then for i = 0 to L → level do if update[i] → forward[i] ? a then break update[i] → forward[i] = a → forward[i] free(a) while L → level > 0 and L → header → forward[L → level] = NIL do L → level = L → level - 1 

Meklēšanas operācijas algoritms

 Searching (L, SKey) a = L → header loop invariant: a → key level down to 0 do. while a → forward[i] → key forward[i] a = a → forward[0] if a → key = SKey then return a → value else return failure 

1. piemērs: Izveidojiet izlaižamo sarakstu, mēs vēlamies ievietot šos taustiņus tukšajā izlaišanas sarakstā.

1. 6 ar 1. līmeni.
2. 29 ar 1. līmeni.
3. 22 ar 4. līmeni.
4. 9 ar 3. līmeni.
5. 17 ar 1. līmeni.
6. 4 ar 2. līmeni.

Gadi:

1. darbība: Ievietojiet 6 ar 1. līmeni

2. darbība: Ievietojiet 29 ar 1. līmeni

3. darbība: Ievietojiet 22 ar 4. līmeni

4. darbība: Ievietojiet 9 ar 3. līmeni

5. darbība: Ievietojiet 17 ar 1. līmeni

6. darbība: Ievietojiet 4 ar 2. līmeni

2. piemērs: Apsveriet šo piemēru, kur mēs vēlamies meklēt 17. atslēgu.

Gadi:

Izlaistā saraksta priekšrocības

1. Ja vēlaties ievietot jaunu mezglu izlaižamajā sarakstā, tas ievietos mezglu ļoti ātri, jo izlaišanas sarakstā nav rotāciju.
2. Izlaižamo sarakstu ir vienkārši ieviest, salīdzinot ar jaucējtabulu un bināro meklēšanas koku.
3. Sarakstā ir ļoti vienkārši atrast mezglu, jo tas saglabā mezglus sakārtotā veidā.
4. Izlaižamo sarakstu algoritmu var ļoti viegli modificēt konkrētākā struktūrā, piemēram, indeksējamos izlaižamos sarakstos, kokos vai prioritārās rindās.
5. Izlaist saraksts ir stabils un uzticams saraksts.

Izlaistā saraksta trūkumi

1. Tas prasa vairāk atmiņas nekā līdzsvarots koks.
2. Apgrieztā meklēšana nav atļauta.
3. Izlaistajā sarakstā mezgls tiek meklēts daudz lēnāk nekā saistītajā sarakstā.

Izlaist saraksta lietojumprogrammas

1. To izmanto izplatītajās lietojumprogrammās, un tas attēlo norādes un sistēmu izplatītajās lietojumprogrammās.
2. To izmanto, lai ieviestu dinamisku elastīgu vienlaicīgu rindu ar zemu bloķēšanas strīdu.
3. To izmanto arī ar QMap veidņu klasi.
4. Izlaišanas saraksta indeksēšana tiek izmantota, lai palaistu vidējās problēmas.
5. Izlaišanas saraksts tiek izmantots delta kodējuma publicēšanai Lucene meklēšanā.