Node akhir dari linked list yang memiliki loop akan merujuk ke node lain dalam list yang sama daripada NULL. Jika ada node dalam linked list yang dapat diakses berulang kali dengan mengikuti pointer berikutnya, list dikatakan memiliki siklus.
Biasanya, node terakhir dari Daftar Tertaut mengacu pada referensi NULL untuk menunjukkan kesimpulan daftar. Namun, dalam daftar tertaut dengan loop, simpul akhir dari daftar merujuk ke simpul awal, simpul internal, atau simpul itu sendiri. Oleh karena itu, dalam keadaan seperti itu, kita harus mengidentifikasi dan menghentikan loop dengan menyetel referensi node berikutnya ke NULL. Bagian deteksi loop dalam daftar tertaut dijelaskan dalam artikel ini.
Di C++, ada banyak cara untuk menemukan loop dalam linked list:
Pendekatan berbasis tabel hash : Pendekatan ini menyimpan alamat node yang dikunjungi dalam tabel hash. Sebuah loop dalam daftar tertaut ada jika sebuah node sudah ada di tabel hash saat dikunjungi lagi.
Pendekatan siklus Floyd : Algoritme 'kura-kura dan kelinci', umumnya dikenal sebagai algoritme pencarian siklus Floyd: Teknik ini menggunakan dua penunjuk, satu bergerak lebih lambat dari yang lain dan yang lainnya bergerak lebih cepat. Penunjuk yang lebih cepat pada akhirnya akan mengambil alih penunjuk yang lebih lambat jika ada perulangan dalam daftar tertaut, mengungkapkan keberadaan perulangan tersebut.
Metode rekursif : Metode ini melewati daftar tertaut dengan memanggil dirinya berulang kali. Daftar tertaut berisi loop jika node saat ini telah dikunjungi sebelumnya.
Pendekatan berbasis tumpukan : Pendekatan ini menyimpan alamat node yang dikunjungi dalam tumpukan. Sebuah loop dalam daftar tertaut hadir jika sebuah node sudah ada di tumpukan saat dikunjungi lagi.
Mari kita jelaskan setiap pendekatan secara rinci untuk memahami konsepnya.
Pendekatan 1: Pendekatan HashSet
Memanfaatkan hashing adalah metode yang paling mudah. Di sini, kita menelusuri daftar satu per satu sambil menyimpan tabel hash dengan alamat node. Oleh karena itu, sebuah perulangan akan terjadi jika kita pernah melewati alamat berikutnya dari node saat ini yang sudah terdapat dalam tabel hash. Jika tidak, tidak ada perulangan dalam Daftar Tertaut jika kita menemukan NULL (yaitu, mencapai akhir Daftar Tertaut).
Akan sangat mudah untuk menerapkan strategi ini.
Saat melintasi daftar tertaut, kami akan menggunakan unordered_hashmap dan terus menambahkan node ke dalamnya.
Sekarang, begitu kita menemukan node yang sudah ditampilkan di peta, kita akan tahu bahwa kita telah tiba di awal loop.
-
- Selain itu, kami menyimpan dua petunjuk di setiap langkah, headNode menunjuk ke node saat ini dan lastNode menunjuk ke node sebelumnya dari node saat ini, sementara iterasi.
- Sebagai milik kita headNode sekarang menunjuk ke node awal dari loop dan as lastNode menunjuk ke simpul yang ditunjuk oleh kepala (yaitu, mengacu pada lastNode dari loop), kami headNode saat ini menunjuk ke node awal dari loop.
- Loop akan diputus dengan menyetel l astNode->berikutnya == NULL .
Dengan melakukan ini, simpul loop akhir alih-alih merujuk ke simpul awal loop, mulai menunjuk ke NULL.
Kompleksitas ruang dan waktu rata-rata metode hashing adalah O(n). Pembaca harus selalu menyadari bahwa penerapan Struktur Data Hashing bawaan dalam bahasa pemrograman akan menentukan kompleksitas waktu total jika terjadi tabrakan dalam hashing.
Implementasi program C++ untuk metode di atas (HashSet):
#sertakan
menggunakan namespace std;
struct Node {
nilai int;
struct Node * Berikutnya;
} ;
Node * newNode ( nilai int )
{
Node * tempNode = Node baru;
tempNode- > nilai = nilai;
tempNode- > selanjutnya = NULL;
kembali tempNode;
}
// Identifikasi dan hilangkan potensi loop
// di dalam daftar tertaut dengan fungsi ini.
batal functionHashMap ( Node * headNode )
{
// Membuat unordered_map untuk mengimplementasikan peta Hash
unordered_map < Node * , int > hash_map;
// pointer ke lastNode
Node * lastNode = NULL;
ketika ( headNode ! = NULL ) {
// Jika sebuah node hilang dari peta, tambahkan.
jika ( hash_map.find ( headNode ) == hash_map.akhir ( ) ) {
hash_map [ headNode ] ++;
simpulterakhir = simpulkepala;
headNode = headNode- > Berikutnya;
}
// Jika ada siklus, mengatur simpul terakhir pointer berikutnya ke NULL.
kalau tidak {
lastNode->next = NULL;
merusak;
}
}
}
// Tampilkan daftar tertaut
tampilan kosong (Node* headNode)
{
while (headNode != NULL) {
cout << headNode->nilai << ' ';
headNode = headNode->next;
}
cout<
/* Fungsi utama*/
int utama()
{
Node* headNode = newNode(48);
headNode->next = headNode;
headNode->next = newNode(18);
headNode->next->next = newNode(13);
headNode->next->next->next = newNode(2);
headNode->next->next->next->next = newNode(8);
/* Membuat loop di linkedList */
headNode->next->next->next->next->next = headNode->next->next;
functionHashMap(headNode);
printf('Daftar Tertaut tanpa loop \n');
tampilan(headNode);
kembali 0;
}
Keluaran:
Daftar Tertaut tanpa loop
48 18 13 2 8
Penjelasan langkah demi langkah kode disediakan di bawah ini:
-
- File header bits/stdc++.h>, yang berisi semua pustaka umum C++, disertakan dalam kode.
- Struktur yang disebut 'Node' dibangun, dan memiliki dua anggota: referensi ke node berikutnya dalam daftar dan bilangan bulat yang disebut 'nilai'.
- Dengan nilai integer sebagai inputnya dan pointer “next” diatur ke NULL, fungsi “newNode” membuat node baru dengan nilai tersebut.
- Fungsi ' functionHashMap’ didefinisikan, yang mengambil pointer ke simpul kepala dari daftar tertaut sebagai input.
- Di dalam ' functionHashMap ' fungsi, unordered_map bernama 'hash_map' dibuat, yang digunakan untuk mengimplementasikan struktur data peta hash.
- Pointer ke simpul terakhir dari daftar diinisialisasi ke NULL.
- Sebuah while loop digunakan untuk melintasi daftar tertaut, yang dimulai dari simpul kepala dan berlanjut hingga simpul kepala adalah NULL.
- Pointer lastNode diperbarui ke node saat ini di dalam while loop jika node saat ini (headNode) belum ada di peta hash.
- Jika node saat ini ditemukan di peta, itu berarti ada loop di daftar tertaut. Untuk menghapus loop, pointer berikutnya dari lastNode diatur ke BATAL dan while loop rusak.
- Node kepala daftar tertaut digunakan sebagai input untuk fungsi yang disebut 'tampilan', yang menampilkan nilai setiap node dalam daftar dari awal hingga akhir.
- Dalam utama fungsi, membuat loop.
- Fungsi 'functionHashMap' dipanggil dengan pointer headNode sebagai input, yang menghapus loop dari daftar.
- Daftar yang dimodifikasi ditampilkan menggunakan fungsi 'tampilan'.
Pendekatan 2: Siklus Floyd
Algoritme deteksi siklus Floyd, sering dikenal sebagai algoritme kura-kura dan kelinci, menyediakan dasar untuk metode menemukan siklus ini dalam daftar tertaut. Penunjuk 'lambat' dan penunjuk 'cepat', yang melintasi daftar dengan berbagai kecepatan, adalah dua penunjuk yang digunakan dalam teknik ini. Penunjuk cepat memajukan dua langkah sedangkan penunjuk lambat memajukan satu langkah setiap iterasi. Sebuah siklus dalam daftar tertaut ada jika dua titik pernah bertatap muka.
1. Dengan node kepala daftar tertaut, kami menginisialisasi dua penunjuk yang disebut cepat dan lambat.
2. Sekarang kita menjalankan loop untuk menelusuri daftar tertaut. Penunjuk cepat harus dipindahkan dua lokasi di depan penunjuk lambat pada setiap langkah iterasi.
3. Tidak akan ada loop pada linked list jika fast pointer mencapai akhir list (fastPointer == NULL atau fastPointer->next == NULL). Jika tidak, pointer cepat dan lambat pada akhirnya akan bertemu, yang berarti linked list memiliki loop.
Implementasi program C++ untuk metode di atas (Siklus Floyd):
#sertakan
menggunakan namespace std;
/* Node daftar tautan */
struct Node {
int data;
struct Node * Berikutnya;
} ;
/* Berfungsi untuk menghapus lingkaran. */
batal deleteLoop ( struct Node * , struktur Node * ) ;
/* Ini fungsi menempatkan dan menghilangkan loop daftar. Itu menghasilkan 1
jika ada lingkaran di dalam Daftar; kalau tidak , itu kembali 0 . */
int detectAndDeleteLoop ( struct Node * daftar )
{
struct Node * slowPTR = daftar, * fastPTR = daftar;
// Ulangi untuk memeriksa jika loopnya ada.
ketika ( PTR lambat && fastPTR && fastPTR- > Berikutnya ) {
slowPTR = slowPTR- > Berikutnya;
fastPTR = fastPTR- > Berikutnya- > Berikutnya;
/* Jika slowPTR dan fastPTR bertemu di beberapa titik Kemudian di sana
adalah lingkaran */
jika ( slowPTR == fastPTR ) {
deleteLoop ( slowPTR, daftar ) ;
/* Kembali 1 untuk menunjukkan bahwa loop telah ditemukan. */
kembali 1 ;
}
}
/* Kembali 0 untuk menunjukkan bahwa tidak ada loop yang ditemukan. */
kembali 0 ;
}
/* Berfungsi untuk menghapus loop dari linked list.
loopNode menunjuk ke salah satu loop node dan headNode menunjuk
ke simpul awal dari linked list */
batal deleteLoop ( struct Node * loopNode, struct Node * headNode )
{
struct Node * ptr1 = loopNode;
struct Node * ptr2 = loopNode;
// Hitung berapa banyak node di dalam putaran.
unsigned int k = 1 , Saya;
ketika ( ptr1- > Berikutnya ! = ptr2 ) {
ptr1 = ptr1- > Berikutnya;
k++;
}
// Perbaiki satu pointer ke headNode
ptr1 = simpul kepala;
// Dan pointer lainnya ke k node setelah headNode
ptr2 = simpul kepala;
untuk ( saya = 0 ; Saya < k; saya++ )
ptr2 = ptr2- > Berikutnya;
/* Ketika kedua titik dipindahkan secara bersamaan,
mereka akan bertabrakan di loop simpul awal. */
sementara (ptr2 != ptr1) {
ptr1 = ptr1->berikutnya;
ptr2 = ptr2->berikutnya;
}
// Dapatkan simpulnya' S terakhir penunjuk.
ketika ( ptr2- > Berikutnya ! = ptr1 )
ptr2 = ptr2- > Berikutnya;
/* Untuk menutup loop, mengatur berikutnya
simpul ke loop node terminasi. */
ptr2->berikutnya = NULL;
}
/* Fungsi untuk menampilkan linked list */
batal displayLinkedList(node struct Node*)
{
// tampilkan linked list setelah menghapus loop
while (simpul != NULL) {
cout << simpul-> data << ' ';
simpul = simpul->berikutnya;
}
}
struct Node* newNode(int key)
{
struct Node* temp = Node baru();
temp->data = kunci;
temp->berikutnya = NULL;
suhu kembali;
}
// Kode Utama
int utama()
{
struct Node* headNode = newNode(48);
headNode->next = newNode(18);
headNode->next->next = newNode(13);
headNode->next->next->next = newNode(2);
headNode->next->next->next->next = newNode(8);
/* Membuat lingkaran */
headNode->next->next->next->next->next = headNode->next->next;
// tampilkan loop di daftar tertaut
//displayLinkedList(headNode);
detectAndDeleteLoop(headNode);
cout << 'Daftar Tertaut setelah tidak ada loop \n';
displayLinkedList(headNode);
kembali 0;
}
Keluaran:
Daftar Tertaut setelah tidak ada pengulangan
48 18 13 2 8
Penjelasan:
-
- Header yang relevan, seperti “bits/stdc++.h” dan “std::cout,” disertakan terlebih dahulu.
- Struktur 'Node', yang merupakan singkatan dari node dalam daftar tertaut, kemudian dideklarasikan. Pointer berikutnya yang mengarah ke node berikut dalam daftar disertakan bersama dengan bidang data bilangan bulat di setiap node.
- Kemudian, ia mendefinisikan 'deleteLoop' dan 'detectAndDeleteLoop,' dua fungsi. Sebuah loop dihapus dari daftar tertaut menggunakan metode pertama, dan sebuah loop terdeteksi dalam daftar menggunakan fungsi kedua, yang kemudian memanggil prosedur pertama untuk menghapus loop.
- Daftar tertaut baru dengan lima node dibuat di fungsi utama, dan sebuah loop dibuat dengan menyetel pointer berikutnya dari node terakhir ke node ketiga.
- Itu kemudian membuat panggilan ke metode 'detectAndDeleteLoop' sambil meneruskan node kepala daftar tertaut sebagai argumen. Untuk mengidentifikasi loop, fungsi ini menggunakan pendekatan “Petunjuk Lambat dan Cepat”. Ini mempekerjakan dua petunjuk yang dimulai di bagian atas daftar, slowPTR dan fastPTR. Sementara penunjuk cepat menggerakkan dua node sekaligus, penunjuk lambat hanya memindahkan satu node pada satu waktu. Penunjuk cepat pada akhirnya akan mengambil alih penunjuk lambat jika daftar berisi satu lingkaran, dan dua titik akan bertabrakan pada simpul yang sama.
- Fungsi ini memanggil fungsi 'deleteLoop' jika menemukan sebuah loop, memasok simpul utama daftar dan perpotongan pointer lambat dan cepat sebagai input. Prosedur ini menetapkan dua pointer, ptr1 dan ptr2, ke node utama daftar dan menghitung jumlah node dalam loop. Setelah itu, ia memajukan satu node k node, di mana k adalah jumlah total node dalam loop. Kemudian, sampai mereka bertemu di awal loop, itu memajukan kedua titik satu node pada satu waktu. Loop tersebut kemudian diputus dengan menyetel pointer berikutnya dari node di akhir loop ke NULL.
- Setelah menghapus loop, daftar tertaut akan ditampilkan sebagai langkah terakhir.
Pendekatan 3: Rekursi
Rekursi adalah teknik untuk memecahkan masalah dengan mempartisinya menjadi submasalah yang lebih kecil dan lebih mudah. Rekursi dapat digunakan untuk melintasi daftar tertaut tunggal jika sebuah loop ditemukan dengan terus menjalankan fungsi untuk node berikutnya dalam daftar hingga akhir daftar tercapai.
Dalam daftar tertaut tunggal, prinsip dasar di balik penggunaan rekursi untuk menemukan loop adalah mulai dari bagian atas daftar, tandai simpul saat ini sebagai dikunjungi pada setiap langkah, lalu lanjutkan ke simpul berikutnya dengan secara rekursif memanggil fungsi untuk simpul itu. Metode ini akan mengulangi daftar tertaut lengkap karena disebut secara rekursif.
Daftar tersebut berisi sebuah loop jika sebuah node yang sebelumnya telah ditandai sebagai telah dikunjungi ditemukan oleh fungsi tersebut; dalam hal ini, fungsi dapat mengembalikan nilai true. Metode ini dapat mengembalikan false jika mencapai akhir daftar tanpa berjalan melintasi node yang dikunjungi, yang menunjukkan bahwa tidak ada loop.
Meskipun teknik untuk memanfaatkan rekursi untuk menemukan loop dalam satu daftar tertaut ini mudah digunakan dan dipahami, ini mungkin bukan yang paling efektif dalam hal kompleksitas ruang dan waktu.
Implementasi program C++ untuk metode di atas (Rekursi):
#termasuk
menggunakan namespace std;
struct Node {
int data;
Node * Berikutnya;
bool dikunjungi;
} ;
// Deteksi loop daftar tertaut fungsi
bool detectLoopLinkedList ( Node * headNode ) {
jika ( kepalaNode == NULL ) {
kembali PALSU ; // Jika daftar tertaut kosong, daftar dasar kasus
}
// Ada lingkaran jika node saat ini memiliki
// sudah dikunjungi.
jika ( kepalaNode- > dikunjungi ) {
kembali BENAR ;
}
// Tambahkan tanda kunjungan ke node saat ini.
kepalaNode- > dikunjungi = BENAR ;
// Memanggil kode untuk simpul berikutnya berulang kali
kembali detectLoopLinkedList ( kepalaNode- > Berikutnya ) ;
}
int utama ( ) {
Node * headNode = Node baru ( ) ;
Node * secondNode = Node baru ( ) ;
Node * thirdNode = Node baru ( ) ;
kepalaNode- > data = 1 ;
kepalaNode- > selanjutnya = simpul kedua;
kepalaNode- > dikunjungi = PALSU ;
Node kedua- > data = 2 ;
Node kedua- > selanjutnya = Node ketiga;
Node kedua- > dikunjungi = PALSU ;
Node ketiga- > data = 3 ;
Node ketiga- > selanjutnya = NULL; // Tidak ada putaran
Node ketiga- > dikunjungi = PALSU ;
jika ( detectLoopLinkedList ( headNode ) ) {
cout << 'Loop terdeteksi di daftar tertaut' << akhir;
} kalau tidak {
cout << 'Tidak ada loop yang terdeteksi dalam daftar tertaut' << akhir;
}
// Membuat lingkaran
Node ketiga- > selanjutnya = simpul kedua;
jika ( detectLoopLinkedList ( headNode ) ) {
cout << 'Loop terdeteksi di daftar tertaut' << akhir;
} kalau tidak {
cout << 'Tidak ada loop yang terdeteksi dalam daftar tertaut' << akhir;
}
kembali 0 ;
}
Keluaran:
Tidak ada putaran yang terdeteksi di dalam daftar tertaut
Lingkaran terdeteksi di dalam daftar tertaut
Penjelasan:
-
- Fungsi detectLoopLinkedList() dalam program ini menerima kepala daftar tertaut sebagai masukan.
- Rekursi digunakan oleh fungsi untuk beralih di seluruh daftar tertaut. Sebagai kasus dasar untuk rekursi, dimulai dengan menentukan apakah simpul saat ini adalah NULL. Jika demikian, metode mengembalikan false, yang menunjukkan bahwa tidak ada loop.
- Nilai dari properti “visited” node saat ini kemudian diperiksa untuk melihat apakah sebelumnya telah dikunjungi. Mengembalikan true jika telah dikunjungi, menunjukkan bahwa sebuah loop telah ditemukan.
- Fungsi menandai node saat ini sebagai telah dikunjungi jika telah dikunjungi dengan mengubah properti “visited” menjadi true.
- Nilai dari variabel yang dikunjungi kemudian diperiksa untuk melihat apakah node saat ini telah dikunjungi sebelumnya. Jika sudah pernah digunakan sebelumnya, sebuah loop harus ada, dan fungsi mengembalikan nilai true.
- Terakhir, fungsi memanggil dirinya sendiri dengan node berikutnya dalam daftar dengan meneruskan headNode->berikutnya sebagai argumen. Secara rekursif , ini dilakukan hingga loop ditemukan atau semua node telah dikunjungi. Artinya, fungsi menyetel variabel yang dikunjungi ke true jika node saat ini belum pernah dikunjungi sebelumnya secara rekursif memanggil dirinya sendiri untuk node berikut dalam daftar tertaut.
- Kode membangun tiga node dan menggabungkannya untuk menghasilkan daftar tertaut di fungsi utama . Metode detectLoopLinkedList() kemudian dipanggil pada node kepala daftar. Program menghasilkan “ Pengurangan pengulangan dalam daftar tertaut ' jika detectLoopLinkedList() mengembalikan benar; yang lain, itu menghasilkan ' Tidak ada loop yang terdeteksi dalam daftar tertaut “.
- Kode kemudian menyisipkan sebuah loop ke dalam daftar tertaut dengan menyetel pointer berikutnya dari node terakhir ke node kedua. Kemudian, tergantung pada hasil dari fungsi, itu berjalan detectLoopLinkedList() lagi dan menghasilkan ' Pengurangan pengulangan dalam daftar tertaut ' atau ' Tidak ada loop yang terdeteksi dalam daftar tertaut .”
Pendekatan 4: Menggunakan Stack
Loop dalam linked list dapat ditemukan menggunakan stack dan metode “depth-first search” (DFS). Konsep dasarnya adalah mengulang melalui daftar tertaut, mendorong setiap node ke tumpukan jika belum dikunjungi. Sebuah loop dikenali jika node yang sudah ada di stack ditemui lagi.
Berikut adalah penjelasan singkat tentang prosedur tersebut:
-
- Buat tumpukan kosong dan variabel untuk merekam node yang telah dikunjungi.
- Dorong daftar tertaut ke tumpukan, mulai dari atas. Catat bahwa kepala telah dikunjungi.
- Dorong simpul berikutnya dalam daftar ke tumpukan. Tambahkan tanda kunjungan ke node ini.
- Saat Anda melintasi daftar, dorong setiap node baru ke tumpukan untuk menunjukkan bahwa itu telah dikunjungi.
- Periksa untuk melihat apakah simpul yang sebelumnya telah dikunjungi berada di puncak tumpukan jika ditemukan. Jika demikian, sebuah loop telah ditemukan, dan loop tersebut diidentifikasi oleh node-node dalam stack.
- Keluarkan node dari tumpukan dan terus telusuri daftar jika tidak ada loop yang ditemukan.
Implementasi program C++ untuk metode di atas (Stack)
#termasuk
#termasuk
menggunakan namespace std;
struct Node {
int data;
Node * Berikutnya;
} ;
// Berfungsi untuk mendeteksi loop di dalam daftar tertaut
bool detectLoopLinkedList ( Node * headNode ) {
tumpukan < Node *> tumpukan;
Node * tempNode = kepalaNode;
ketika ( tempNode ! = NULL ) {
// jika elemen teratas tumpukan cocok
// simpul saat ini dan tumpukan tidak kosong
jika ( ! tumpukan.kosong ( ) && stack.top ( ) == tempNode ) {
kembali BENAR ;
}
stack.push ( tempNode ) ;
tempNode = tempNode- > Berikutnya;
}
kembali PALSU ;
}
int utama ( ) {
Node * headNode = Node baru ( ) ;
Node * secondNode = Node baru ( ) ;
Node * thirdNode = Node baru ( ) ;
kepalaNode- > data = 1 ;
kepalaNode- > selanjutnya = simpul kedua;
Node kedua- > data = 2 ;
Node kedua- > selanjutnya = Node ketiga;
Node ketiga- > data = 3 ;
Node ketiga- > selanjutnya = NULL; // Tidak ada putaran
jika ( detectLoopLinkedList ( headNode ) ) {
cout << 'Loop terdeteksi di daftar tertaut' << akhir;
} kalau tidak {
cout << 'Tidak ada loop yang terdeteksi dalam daftar tertaut' << akhir;
}
// Membuat lingkaran
Node ketiga- > selanjutnya = simpul kedua;
jika ( detectLoopLinkedList ( headNode ) ) {
cout << 'Loop terdeteksi di daftar tertaut' << akhir;
} kalau tidak {
cout << 'Tidak ada loop yang terdeteksi dalam daftar tertaut' << akhir;
}
Keluaran:
Tidak ada putaran yang terdeteksi di dalam daftar tertaut
Lingkaran terdeteksi di dalam daftar tertaut
Penjelasan:
Program ini menggunakan stack untuk mengetahui apakah single linked list memiliki loop.
- 1. Pustaka aliran input/output dan pustaka tumpukan keduanya ada di baris pertama.
2. Ruang nama standar disertakan di baris kedua, memungkinkan kita untuk mengakses fungsi pustaka aliran input/output tanpa harus mengawalinya dengan 'std::.'
3. Baris berikut mendefinisikan struct Node, yang terdiri dari dua anggota: integer yang disebut 'data' dan penunjuk ke Node lain yang disebut 'next'.
4. Kepala linked list adalah masukan untuk metode detectLoopLinkedList(), yang didefinisikan pada baris berikutnya. Fungsi menghasilkan nilai boolean yang menunjukkan apakah loop ditemukan atau tidak.
5. Tumpukan pointer Node yang disebut 'stack' dan pointer ke Node bernama 'tempNode' yang diinisialisasi dengan nilai headNode keduanya dibuat di dalam fungsi.
6. Kemudian, selama tempNode bukan pointer null, kita masukkan while loop.
(a) Elemen paling atas dari tumpukan harus cocok dengan node saat ini agar kita dapat menentukan bahwa node tersebut tidak kosong. Kami mengembalikan true jika ini masalahnya karena sebuah loop telah ditemukan.
(b) Jika kondisi yang disebutkan di atas salah, penunjuk simpul saat ini didorong ke tumpukan, dan tempNode disetel ke simpul berikut dalam daftar tertaut.
7. Kami mengembalikan false setelah perulangan while karena tidak ada perulangan yang teramati.
8. Kami membuat tiga objek Node dan menginisialisasinya dalam fungsi main() . Karena tidak ada perulangan pada contoh pertama, kita atur pointer “berikutnya” dari setiap Node dengan benar.
Kesimpulan:
Kesimpulannya, metode terbaik untuk mendeteksi loop dalam linked list bergantung pada kasus penggunaan spesifik dan batasan masalahnya. Algoritme pencarian siklus Hash Table dan Floyd adalah metode yang efisien dan banyak digunakan dalam praktik. Stack dan rekursi adalah metode yang kurang efisien tetapi lebih intuitif.