logo

TechCodeview

Omite lista în Structura datelor

Ce este o listă sărită?

O listă de ignorare este o structură de date probabilistică. Lista de ignorare este utilizată pentru a stoca o listă sortată de elemente sau date cu o listă legată. Permite vizualizarea eficientă a procesului elementelor sau datelor. Într-un singur pas, omite mai multe elemente din întreaga listă, motiv pentru care este cunoscută ca o listă de omis.

Lista de ignorare este o versiune extinsă a listei legate. Acesta permite utilizatorului să caute, să elimine și să introducă elementul foarte rapid. Constă dintr-o listă de bază care include un set de elemente care menține ierarhia de legături a elementelor ulterioare.

Omiteți structura listei

Este construit în două straturi: stratul cel mai de jos și stratul superior.

Stratul cel mai de jos al listei de ignorare este o listă comună sortată, iar straturile superioare ale listei de omitere sunt ca o „linie expresă” în care elementele sunt sărite.

Tabelul de complexitate al listei Skip

Da nu Complexitate Caz mediu Cel mai rău caz
1. Complexitatea accesului O(logn) Pe)
2. Complexitatea căutării O(logn) Pe)
3. Ștergeți complexitatea O(logn) Pe)
4. Introduceți complexitate O(logn) Pe)
5. Complexitatea spațială - O(nlogn)

Funcționarea listei Skip

Să luăm un exemplu pentru a înțelege funcționarea listei de ignorare. În acest exemplu, avem 14 noduri, astfel încât aceste noduri sunt împărțite în două straturi, așa cum se arată în diagramă.

Stratul inferior este o linie comună care leagă toate nodurile, iar stratul superior este o linie expresă care leagă doar nodurile principale, așa cum puteți vedea în diagramă.

Să presupunem că doriți să găsiți 47 în acest exemplu. Veți începe căutarea de la primul nod al liniei expres și veți continua să rulați pe linia rapidă până când găsiți un nod care este egal cu 47 sau mai mult decât 47.

Puteți vedea în exemplu că 47 nu există în linia expresă, așa că căutați un nod mai mic de 47, care este 40. Acum, mergeți la linia normală cu ajutorul lui 40 și căutați 47, așa cum se arată în diagramă.

Omite lista în Structura datelor

Notă: Odată ce găsiți un nod ca acesta pe „linia expresă”, treceți de la acest nod la o „bandă normală” folosind un pointer și când căutați nodul în linia normală.

Omite lista de operațiuni de bază

Există următoarele tipuri de operații în lista de omitere.

    Operație de inserare:Este folosit pentru a adăuga un nou nod într-o anumită locație într-o anumită situație.Operatie de stergere:Este folosit pentru a șterge un nod într-o situație specifică.Operațiune de căutare:Operația de căutare este utilizată pentru a căuta un anumit nod dintr-o listă de omis.

Algoritmul operației de inserare 

 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

Algoritmul operației de ștergere 

 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

Algoritmul operației de căutare 

 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

Exemplul 1: Creați o listă de ignorare, dorim să inserăm următoarele taste în lista de omitere goală.

  1. 6 cu nivelul 1.
  2. 29 cu nivelul 1.
  3. 22 cu nivelul 4.
  4. 9 cu nivelul 3.
  5. 17 cu nivelul 1.
  6. 4 cu nivelul 2.

Ani:

Pasul 1: Inserați 6 cu nivelul 1

Omite lista în Structura datelor

Pasul 2: Inserați 29 cu nivelul 1

Omite lista în Structura datelor

Pasul 3: Inserați 22 cu nivelul 4

Omite lista în Structura datelor

Pasul 4: Introduceți 9 cu nivelul 3

Omite lista în Structura datelor

Pasul 5: Inserați 17 cu nivelul 1

Omite lista în Structura datelor

Pasul 6: Introduceți 4 cu nivelul 2

Omite lista în Structura datelor

Exemplul 2: Luați în considerare acest exemplu în care dorim să căutăm cheia 17.

Omite lista în Structura datelor

Ani:

Omite lista în Structura datelor

Avantajele listei Skip

  1. Dacă doriți să inserați un nou nod în lista de omitere, atunci acesta va insera nodul foarte rapid deoarece nu există rotații în lista de omitere.
  2. Lista de ignorare este ușor de implementat în comparație cu tabelul hash și arborele de căutare binar.
  3. Este foarte simplu să găsești un nod în listă deoarece stochează nodurile în formă sortată.
  4. Algoritmul listei de ignorare poate fi modificat foarte ușor într-o structură mai specifică, cum ar fi listele de ignorare indexabile, arbori sau cozi de prioritate.
  5. Lista de ignorare este o listă robustă și de încredere.

Dezavantajele listei Skip

  1. Necesită mai multă memorie decât arborele echilibrat.
  2. Căutarea inversă nu este permisă.
  3. Lista de omitere caută nodul mult mai lent decât lista legată.

Aplicații ale listei Skip

  1. Este folosit în aplicațiile distribuite și reprezintă pointerii și sistemul în aplicațiile distribuite.
  2. Este folosit pentru a implementa o coadă concurent elastică dinamică cu o concurență scăzută de blocare.
  3. Este, de asemenea, utilizat cu clasa șablon QMap.
  4. Indexarea listei de ignorare este utilizată în rularea problemelor mediane.
  5. Lista de ignorare este utilizată pentru postarea cu codificare delta în căutarea Lucene.