Krajnji čvor povezanog popisa koji ima petlju odnosit će se na drugi čvor na istom popisu, a ne na NULL. Ako postoji čvor na povezanom popisu kojemu se može više puta pristupiti praćenjem sljedećeg pokazivača, kaže se da popis imati ciklus.
Obično se zadnji čvor povezanog popisa odnosi na NULL referencu koja označava zaključak popisa. Međutim, u povezanom popisu s petljom, završni čvor popisa odnosi se na početni čvor, interni čvor ili samog sebe. Stoga, u takvim okolnostima, moramo identificirati i prekinuti petlju postavljanjem reference sljedećeg čvora na NULL. Dio otkrivanja petlje na povezanom popisu objašnjen je u ovom članku.
U C++-u postoje brojni načini za pronalaženje petlji na povezanom popisu:
Pristup temeljen na hash tablici : Ovaj pristup pohranjuje adrese posjećenih čvorova u hash tablicu. Petlja u povezanom popisu postoji ako je čvor već prisutan u hash tablici kada se ponovno posjeti.
Floydov ciklusni pristup : Algoritam 'kornjače i zeca', općenito poznat kao Floydov algoritam za pronalaženje ciklusa: Ova tehnika koristi dva pokazivača, jedan se kreće sporije od drugog, a drugi se kreće brže. Brži pokazivač će u konačnici prestići sporiji pokazivač ako postoji petlja na povezanom popisu, otkrivajući postojanje petlje.
Rekurzivna metoda : Ova metoda prolazi kroz povezani popis pozivajući samu sebe iznova i iznova. Povezani popis sadrži petlju ako je trenutni čvor već posjećen.
Pristup temeljen na stogu : Ovaj pristup pohranjuje adrese posjećenih čvorova u hrpu. Petlja na povezanom popisu prisutna je ako je čvor već tamo u stogu kada se ponovno posjeti.
Objasnimo detaljno svaki pristup kako bismo razumjeli koncept.
Pristup 1: HashSet pristup
Korištenje hashiranja je najjednostavnija metoda. Ovdje prolazimo kroz popis jedan po jedan, zadržavajući hash tablicu s adresama čvorova. Stoga postoji petlja ako ikada naiđemo na sljedeću adresu trenutnog čvora koja je već sadržana u hash tablici. U suprotnom, nema petlje u povezanom popisu ako naiđemo na NULL (tj. dođemo do kraja povezanog popisa).
Bit će vrlo lako provesti ovu strategiju.
Dok prolazimo povezanim popisom, koristit ćemo unordered_hashmap i nastaviti mu dodavati čvorove.
Sada, kada naiđemo na čvor koji je već prikazan na karti, znat ćemo da smo stigli na početak petlje.
-
- Osim toga, zadržali smo dva pokazivača na svakom koraku, glavni čvor pokazujući na trenutni čvor i posljednjičvor pokazujući na prethodni čvor trenutnog čvora, tijekom ponavljanja.
- Kao naše glavni čvor sada pokazuje na početni čvor petlje i as posljednjičvor je pokazivao na čvor na koji je glava pokazivala (tj. odnosi se na posljednjičvor petlje), naš glavni čvor trenutno pokazuje na početni čvor petlje.
- Petlja će se prekinuti postavljanjem l astNode->sljedeći == NULL .
Čineći to, završni čvor petlje umjesto da upućuje na početni čvor petlje, počinje pokazivati na NULL.
Prosječna vremenska i prostorna složenost metode raspršivanja je O(n). Čitatelj bi uvijek trebao biti svjestan da će implementacija ugrađene Hashing DataStructure u programskom jeziku odrediti ukupnu vremensku složenost u slučaju kolizije u hashiranju.
Implementacija C++ programa za gornju metodu (HashSet):
#include
korištenje imenskog prostora std;
strukturni čvor {
int vrijednost;
strukturni čvor * Sljedeći;
} ;
Čvor * noviČvor ( int vrijednost )
{
Čvor * tempNode = novi čvor;
tempNode- > vrijednost = vrijednost;
tempNode- > sljedeći = NULL;
povratak tempNode;
}
// Prepoznajte i uklonite sve potencijalne petlje
// u povezani popis s ovom funkcijom.
void funkcijaHashMap ( Čvor * glavni čvor )
{
// Stvorena je unordered_map za implementaciju Hash mape
neuređena_mapa < Čvor * , int > hash_mapa;
// pokazivač na lastNode
Čvor * zadnjičvor = NULL;
dok ( glavni čvor ! = NULL ) {
// Ako čvor nedostaje na karti, dodajte ga.
ako ( hash_map.find ( glavni čvor ) == hash_map.end ( ) ) {
hash_mapa [ glavni čvor ] ++;
lastNode = glavni čvor;
glavni čvor = glavni čvor- > Sljedeći;
}
// Ako je ciklus prisutan, postaviti konačni čvor sljedeći pokazivač na NULL.
inače {
zadnjičvor->sljedeći = NULL;
pauza;
}
}
}
// Prikaz povezanog popisa
prazan prikaz (čvor * glavni čvor)
{
dok (headNode != NULL) {
cout << headNode->value << ' ';
glavniČvor = glavniČvor->sljedeći;
}
cout << endl;
}
/* Glavna funkcija*/
int main()
{
Čvor* glavniČvor = noviČvor(48);
glavniČvor->sljedeći = glavniČvor;
glavniČvor->sljedeći = noviČvor(18);
glavniČvor->sljedeći->sljedeći = noviČvor(13);
glavniČvor->sljedeći->sljedeći->sljedeći = noviČvor(2);
glavniČvor->sljedeći->sljedeći->sljedeći->sljedeći = noviČvor(8);
/* Stvorite petlju u linkedList */
headNode->next->next->next->next->next = headNode->next->next;
funkcijaHashMap(headNode);
printf('Povezani popis bez petlje \n');
prikaz(headNode);
povratak 0;
}
Izlaz:
Povezani popis bez petlje
48 18 13 2 8
Objašnjenje koda korak po korak navedeno je u nastavku:
-
- Bits/stdc++.h> datoteka zaglavlja, koja sadrži sve uobičajene C++ biblioteke, uključena je u kod.
- Konstruira se struktura nazvana 'Čvor' i ima dva člana: referencu na sljedeći čvor na popisu i cijeli broj nazvan 'vrijednost'.
- Uz vrijednost cijelog broja kao ulaz i pokazivač 'sljedeći' postavljen na NULL, funkcija 'newNode' stvara novi čvor s tom vrijednošću.
- Funkcija ' funkcijaHashMap' je definiran, koji kao ulaz uzima pokazivač na glavni čvor povezane liste.
- Unutar ' funkcijaHashMap ', stvara se unordered_map pod nazivom 'hash_map', koji se koristi za implementaciju strukture podataka hash mape.
- Pokazivač na posljednji čvor popisa je inicijaliziran na NULL.
- Koristi se while petlja za prolazak kroz povezanu listu, koja počinje od glavnog čvora i nastavlja se sve dok glavni čvor ne postane NULL.
- Pokazivač lastNode ažurira se na trenutni čvor unutar while petlje ako trenutni čvor (headNode) već nije prisutan u hash mapi.
- Ako je trenutačni čvor pronađen na karti, to znači da postoji petlja na povezanom popisu. Za uklanjanje petlje, sljedeći pokazivač na posljednjičvor postavljeno je na NULL a while petlja je prekinuta.
- Glavni čvor povezanog popisa koristi se kao ulaz za funkciju pod nazivom 'prikaz', koja ispisuje vrijednost svakog čvora na popisu od početka do kraja.
- u glavni funkcija, stvarajući petlju.
- Funkcija 'functionHashMap' se poziva s pokazivačem headNode kao ulazom, što uklanja petlju s popisa.
- Izmijenjeni popis prikazuje se pomoću funkcije 'prikaz'.
Pristup 2: Floydov ciklus
Floydov algoritam za otkrivanje ciklusa, često poznat kao algoritam kornjače i zeca, pruža temelj za ovu metodu lociranja ciklusa na povezanom popisu. 'Spori' pokazivač i 'brzi' pokazivač, koji prelaze popis različitim brzinama, dva su pokazivača koji se koriste u ovoj tehnici. Brzi pokazivač napreduje dva koraka, dok spori pokazivač napreduje jedan korak u svakoj iteraciji. Ciklus u povezanom popisu postoji ako se dvije točke ikada nađu licem u lice.
1. S glavnim čvorom povezane liste inicijaliziramo dva pokazivača koji se nazivaju brzi i spori.
2. Sada pokrećemo petlju za kretanje kroz povezani popis. Brzi pokazivač treba pomaknuti dva mjesta ispred sporog pokazivača u svakom koraku iteracije.
3. Neće biti petlje u povezanom popisu ako brzi pokazivač dođe do kraja popisa (fastPointer == NULL ili fastPointer->next == NULL). Ako ne, brzi i spori pokazivači će se na kraju susresti, što znači da povezani popis ima petlju.
Implementacija C++ programa za gornju metodu (Floydov ciklus):
#include
korištenje imenskog prostora std;
/* Čvor popisa veza */
strukturni čvor {
int podataka;
strukturni čvor * Sljedeći;
} ;
/* Funkcija za uklanjanje petlje. */
void deleteLoop ( strukturni čvor * , strukturni čvor * ) ;
/* Ovaj funkcija locira i uklanja petlje popisa. Popušta 1
ako bila je petlja u popis; drugo , vraća se 0 . */
int detectAndDeleteLoop ( strukturni čvor * popis )
{
strukturni čvor * slowPTR = popis, * fastPTR = popis;
// Ponovi za provjeru ako petlja je tu.
dok ( sporiPTR && brziPTR && brziPTR- > Sljedeći ) {
sporiPTR = sporiPTR- > Sljedeći;
brziPTR = brziPTR- > Sljedeći- > Sljedeći;
/* Ako se slowPTR i fastPTR sretnu u nekom trenutku zatim tamo
je petlja */
ako ( sporiPTR == brziPTR ) {
deleteLoop ( slowPTR, popis ) ;
/* Povratak 1 za označavanje da je otkrivena petlja. */
povratak 1 ;
}
}
/* Povratak 0 za označavanje da petlja nije otkrivena. */
povratak 0 ;
}
/* Funkcija za brisanje petlje s povezanog popisa.
loopNode pokazuje na jedan od čvorova petlje, a headNode pokazuje
do početnog čvora povezane liste */
void deleteLoop ( strukturni čvor * loopNode, struct Node * glavni čvor )
{
strukturni čvor * ptr1 = čvor petlje;
strukturni čvor * ptr2 = čvor petlje;
// Izbrojite koliko ima čvorova u petlja.
unsigned int k = 1 , i;
dok ( ptr1- > Sljedeći ! = ptr2 ) {
ptr1 = ptr1- > Sljedeći;
k++;
}
// Popravite jedan pokazivač na headNode
ptr1 = glavni čvor;
// I drugi pokazivač na k čvorova nakon headNode
ptr2 = glavni čvor;
za ( ja = 0 ; ja < k; i++ )
ptr2 = ptr2- > Sljedeći;
/* Kada se obje točke pomaknu istovremeno,
sudarit će se na petlji početni čvor. */
dok (ptr2 != ptr1) {
ptr1 = ptr1->sljedeći;
ptr2 = ptr2->sljedeći;
}
// Dobivanje čvora' s posljednji pokazivač.
dok ( ptr2- > Sljedeći ! = ptr1 )
ptr2 = ptr2- > Sljedeći;
/* Da biste zatvorili petlju, postaviti naknadni
čvor na petlju završni čvor. */
ptr2->sljedeći = NULL;
}
/* Funkcija za prikaz povezanog popisa */
void displayLinkedList(struct Node* node)
{
// prikaz povezanog popisa nakon brisanja petlje
dok (čvor != NULL) {
cout << node->data << ' ';
čvor = čvor->sljedeći;
}
}
struct Node* newNode(int ključ)
{
struct Node* temp = new Node();
temp->podaci = ključ;
temp->sljedeći = NULL;
povratna temp;
}
// Glavni kod
int main()
{
struct Node* headNode = newNode(48);
glavniČvor->sljedeći = noviČvor(18);
glavniČvor->sljedeći->sljedeći = noviČvor(13);
glavniČvor->sljedeći->sljedeći->sljedeći = noviČvor(2);
glavniČvor->sljedeći->sljedeći->sljedeći->sljedeći = noviČvor(8);
/* Stvori petlju */
headNode->next->next->next->next->next = headNode->next->next;
// prikaz petlje u povezanom popisu
//displayLinkedList(headNode);
detektiraj i izbriši petlju (glavni čvor);
cout << 'Povezani popis nakon bez petlje \n';
displayLinkedList(headNode);
povratak 0;
}
Izlaz:
Povezani popis bez petlje
48 18 13 2 8
Obrazloženje:
-
- Prvo su uključena relevantna zaglavlja, kao što su 'bits/stdc++.h' i 'std::cout'.
- Zatim se deklarira struktura 'Čvor', koja označava čvor na povezanom popisu. Sljedeći pokazivač koji vodi do sljedećeg čvora na popisu uključen je zajedno s poljem cjelobrojnih podataka u svakom čvoru.
- Zatim definira 'deleteLoop' i 'detectAndDeleteLoop', dvije funkcije. Petlja se uklanja s povezanog popisa pomoću prve metode, a petlja se otkriva na popisu pomoću druge funkcije, koja zatim poziva prvu proceduru za uklanjanje petlje.
- Novi povezani popis s pet čvorova stvara se u glavnoj funkciji, a petlja se uspostavlja postavljanjem sljedećeg pokazivača posljednjeg čvora na treći čvor.
- Zatim poziva metodu 'detectAndDeleteLoop' dok prosljeđuje glavni čvor povezanog popisa kao argument. Za prepoznavanje petlji ova funkcija koristi pristup 'Spori i brzi pokazivači'. Koristi dva pokazivača koji počinju na vrhu popisa, slowPTR i fastPTR. Dok brzi pokazivač pomiče dva čvora odjednom, spori pokazivač pomiče samo jedan po jedan čvor. Brzi pokazivač će u konačnici prestići spori pokazivač ako popis sadrži petlju, a dvije točke će se sudariti u istom čvoru.
- Funkcija poziva funkciju 'deleteLoop' ako pronađe petlju, dajući glavni čvor popisa i sjecište sporog i brzog pokazivača kao ulaze. Ova procedura uspostavlja dva pokazivača, ptr1 i ptr2, na glavni čvor liste i broji broj čvorova u petlji. Nakon toga, pomiče jedan pokazivač k čvorova, gdje je k ukupan broj čvorova u petlji. Zatim, dok se ne sretnu na početku petlje, pomiče obje točke jedan po jedan čvor. Petlja se tada prekida postavljanjem sljedećeg pokazivača čvora na kraju petlje na NULL.
- Nakon uklanjanja petlje, prikazuje povezani popis kao posljednji korak.
Pristup 3: Rekurzija
Rekurzija je tehnika za rješavanje problema njihovim dijeljenjem na manje, lakše podprobleme. Rekurzija se može koristiti za prelazak jednostruko povezanog popisa u slučaju da se pronađe petlja neprekidnim izvođenjem funkcije za sljedeći čvor na popisu dok se ne dosegne kraj popisa.
U jednostruko povezanom popisu, osnovno načelo korištenja rekurzije za pronalaženje petlje je započeti na početku popisa, označiti trenutni čvor kao posjećen u svakom koraku, a zatim prijeći na sljedeći čvor rekurzivnim pozivanjem funkcije za taj čvor. Metoda će iterirati preko cijelog povezanog popisa jer se poziva rekurzivno.
Popis sadrži petlju ako funkcija naiđe na čvor koji je prethodno bio označen kao posjećen; u ovom slučaju, funkcija može vratiti true. Metoda može vratiti false ako dođe do kraja popisa bez pokretanja posjećenog čvora, što znači da nema petlje.
Iako je ova tehnika za korištenje rekurzije za pronalaženje petlje u jednom povezanom popisu jednostavna za korištenje i razumijevanje, možda nije najučinkovitija u smislu vremenske i prostorne složenosti.
Implementacija C++ programa za gornju metodu (rekurzija):
#include
korištenje imenskog prostora std;
strukturni čvor {
int podataka;
Čvor * Sljedeći;
bool posjećen;
} ;
// Otkrivanje petlje povezanog popisa funkcija
bool detectLoopLinkedList ( Čvor * glavni čvor ) {
ako ( glavniČvor == NULL ) {
povratak lažno ; // Ako je vezani popis prazan, osnovni slučaj
}
// Postoji petlja ako trenutni čvor ima
// već posjećen.
ako ( glavni čvor- > posjetio ) {
povratak pravi ;
}
// Dodajte oznaku posjeta trenutnom čvoru.
glavni čvor- > posjetio = pravi ;
// Pozivanje šifre za sljedeći čvor više puta
povratak detektiratiLoopLinkedList ( glavni čvor- > Sljedeći ) ;
}
int glavni ( ) {
Čvor * headNode = novi čvor ( ) ;
Čvor * secondNode = novi čvor ( ) ;
Čvor * thirdNode = novi čvor ( ) ;
glavni čvor- > podaci = 1 ;
glavni čvor- > sljedeći = drugičvor;
glavni čvor- > posjetio = lažno ;
drugičvor- > podaci = 2 ;
drugičvor- > sljedeći = trećiČvor;
drugičvor- > posjetio = lažno ;
trećičvor- > podaci = 3 ;
trećičvor- > sljedeći = NULL; // Nema petlje
trećičvor- > posjetio = lažno ;
ako ( detektiratiLoopLinkedList ( glavni čvor ) ) {
cout << 'Otkrivena petlja na povezanom popisu' << endl;
} drugo {
cout << 'Nije otkrivena petlja na povezanom popisu' << endl;
}
// Stvaranje petlje
trećičvor- > sljedeći = drugičvor;
ako ( detektiratiLoopLinkedList ( glavni čvor ) ) {
cout << 'Otkrivena petlja na povezanom popisu' << endl;
} drugo {
cout << 'Nije otkrivena petlja na povezanom popisu' << endl;
}
povratak 0 ;
}
Izlaz:
Nije otkrivena petlja u povezani popis
Otkrivena petlja u povezani popis
Obrazloženje:
-
- Funkcija detektirajLoopLinkedList() u ovom programu prihvaća glavu povezane liste kao ulaz.
- Funkcija koristi rekurziju za ponavljanje preko povezanog popisa. Kao osnovni slučaj za rekurziju, ona počinje određivanjem je li trenutni čvor NULL. Ako je tako, metoda vraća false, što znači da petlja ne postoji.
- Vrijednost svojstva 'posjećeno' trenutnog čvora zatim se provjerava da se vidi je li već posjećen. Vraća vrijednost true ako je posjećena, sugerirajući da je pronađena petlja.
- Funkcija označava trenutni čvor kao posjećen ako je već posjećen promjenom svojstva 'posjećeno' u istinito.
- Vrijednost posjećene varijable zatim se provjerava da se vidi je li trenutni čvor već posjećen. Ako je već korištena, petlja mora postojati, a funkcija vraća true.
- Na kraju, funkcija poziva samu sebe sa sljedećim čvorom na popisu prosljeđivanjem glavniČvor->sljedeći kao argument. Rekurzivno , ovo se provodi sve dok se ne pronađe petlja ili dok se ne posjete svi čvorovi. Znači, funkcija postavlja posjećenu varijablu na true ako trenutni čvor nikada nije posjećen prije rekurzivnog poziva za sljedeći čvor na povezanom popisu.
- Kod gradi tri čvora i spaja ih kako bi proizveo povezani popis u glavna funkcija . Metoda detektirajLoopLinkedList() zatim se poziva na glavnom čvoru liste. Program proizvodi ' Petlja odbijena na povezanom popisu ” ako detektirajLoopLinkedList() vraća true; u suprotnom, izlazi ' Na povezanom popisu nije otkrivena petlja “.
- Kod zatim umeće petlju u povezani popis postavljanjem sljedećeg pokazivača posljednjeg čvora na drugi čvor. Zatim se, ovisno o ishodu funkcije, pokreće detektirajLoopLinkedList() ponovno i proizvodi ili ' Petlja odbijena na povezanom popisu ' ili ' Na povezanom popisu nije otkrivena petlja .”
Pristup 4: Korištenje snopa
Petlje u povezanom popisu mogu se pronaći pomoću hrpe i metode 'pretrage u dubinu' (DFS). Temeljni koncept je iterirati kroz povezani popis, gurajući svaki čvor na stog ako već nije posjećen. Petlja se prepoznaje ako se opet naiđe na čvor koji je već na stogu.
Evo kratkog opisa postupka:
-
- Napravite prazan stog i varijablu za bilježenje čvorova koji su posjećeni.
- Gurnite povezani popis na stog, počevši od vrha. Zabilježite da je glava posjećena.
- Gurnite sljedeći čvor na popisu na stog. Dodajte oznaku posjeta ovom čvoru.
- Dok prelazite popisom, gurnite svaki novi čvor na stog kako biste označili da je posjećen.
- Provjerite nalazi li se čvor koji je prethodno posjećen na vrhu stoga ako se na njega naiđe. Ako je tako, pronađena je petlja, a petlja je identificirana čvorovima u nizu.
- Izbacite čvorove sa stoga i nastavite obilaziti popis ako se ne pronađe petlja.
Implementacija C++ programa za gornju metodu (skup)
#include
#include
korištenje imenskog prostora std;
strukturni čvor {
int podataka;
Čvor * Sljedeći;
} ;
// Funkcija za otkrivanje petlje u povezani popis
bool detectLoopLinkedList ( Čvor * glavni čvor ) {
stog < Čvor *> stog;
Čvor * tempNode = glavni čvor;
dok ( tempNode ! = NULL ) {
// ako gornji element hrpe odgovara
// trenutni čvor i stog nije prazan
ako ( ! stog.prazan ( ) && stog.top ( ) == tempNode ) {
povratak pravi ;
}
slagati.gurati ( tempNode ) ;
tempNode = tempNode- > Sljedeći;
}
povratak lažno ;
}
int glavni ( ) {
Čvor * headNode = novi čvor ( ) ;
Čvor * secondNode = novi čvor ( ) ;
Čvor * thirdNode = novi čvor ( ) ;
glavni čvor- > podaci = 1 ;
glavni čvor- > sljedeći = drugičvor;
drugičvor- > podaci = 2 ;
drugičvor- > sljedeći = trećiČvor;
trećičvor- > podaci = 3 ;
trećičvor- > sljedeći = NULL; // Nema petlje
ako ( detektiratiLoopLinkedList ( glavni čvor ) ) {
cout << 'Otkrivena petlja na povezanom popisu' << endl;
} drugo {
cout << 'Nije otkrivena petlja na povezanom popisu' << endl;
}
// Stvaranje petlje
trećičvor- > sljedeći = drugičvor;
ako ( detektiratiLoopLinkedList ( glavni čvor ) ) {
cout << 'Otkrivena petlja na povezanom popisu' << endl;
} drugo {
cout << 'Nije otkrivena petlja na povezanom popisu' << endl;
}
Izlaz:
Nije otkrivena petlja u povezani popis
Otkrivena petlja u povezani popis
Obrazloženje:
Ovaj program koristi hrpu kako bi saznao ima li jednostruko povezana lista petlju.
- 1. Biblioteka ulazno/izlaznog toka i knjižnica stoga prisutne su u prvom redu.
2. Standardni imenski prostor uključen je u drugi redak, što nam omogućuje pristup funkcijama biblioteke ulazno/izlaznog toka bez potrebe da im se doda 'std::.'
3. Sljedeći redak definira strukturni čvor koji se sastoji od dva člana: cijeli broj koji se zove 'podaci' i pokazivač na drugi čvor koji se zove 'sljedeći'.
4. Glava povezane liste je ulaz za metodu detectLoopLinkedList(), koja je definirana u sljedećem retku. Funkcija proizvodi Booleovu vrijednost koja pokazuje je li pronađena petlja ili ne.
5. Hrpa pokazivača čvora pod nazivom 'stack' i pokazivač na čvor pod nazivom 'tempNode' koji je inicijaliziran s vrijednošću glavnog čvora stvoreni su unutar funkcije.
6. Zatim, sve dok tempNode nije nulti pokazivač, ulazimo u while petlju.
(a) Gornji element steka mora odgovarati trenutnom čvoru kako bismo utvrdili da nije prazan. Vraćamo true ako je to slučaj jer je pronađena petlja.
(b) Ako je gore spomenuti uvjet lažan, trenutni pokazivač čvora se gura na stog, a tempNode se postavlja na sljedeći čvor na povezanom popisu.
7. Vraćamo false nakon while petlje jer petlja nije opažena.
8. Gradimo tri objekta Node i inicijaliziramo ih u funkciji main(). Budući da u prvom primjeru nema petlje, pravilno smo postavili pokazivače 'sljedećeg' svakog čvora.
Zaključak:
Zaključno, najbolja metoda za otkrivanje petlji u povezanom popisu ovisi o konkretnom slučaju upotrebe i ograničenjima problema. Hash Table i Floydov algoritam za pronalaženje ciklusa učinkovite su metode i naširoko se koriste u praksi. Stog i rekurzija manje su učinkovite metode, ali su intuitivnije.