daftar tertaut: Ini adalah linked list yang ingin kita balikkan.
Setelah daftar tertaut terbalik: Di bawah ini akan menjadi hasil setelah membalikkan daftar tertaut di atas.
Pada contoh diagram di atas, kita dapat melihat bahwa simpul kepala dan simpul ekor berubah posisinya ketika kita membalik daftar tertaut. Simpul kepala, yang sekarang menjadi simpul ekor, menunjuk ke simpul nol karena sekarang menjadi simpul ekor.
Langkah Algoritma
- Kami membuat metode utama dan mendeklarasikan beberapa variabel yang diperlukan.
- Kemudian, langkah kita selanjutnya adalah membuat metode yang dapat membuat linked list. Metode ini membantu kita membuat linked list.
- Langkah selanjutnya adalah membuat metode untuk membalik daftar tertaut. Dalam metode ini, kami melewatkan seluruh daftar tertaut, dan metode ini akan membalikkan daftar tertaut.
- Sekarang, kita memerlukan metode lain untuk menampilkan hasil kita setelah membaliknya.
- Kami akan menggabungkan semua metode di atas ke dalam metode utama kami.
Kami akan menjelaskan daftar tertaut terbalik menggunakan beberapa bentuk gambar agar lebih mudah dipahami. Jadi mari kita mulai dengan contohnya.
Di bawah ini adalah daftar tertaut yang ingin kami balikkan.
Langkah 1 . Node berwarna hijau adalah node kepala, yang menunjuk ke node pertama di startup.
Langkah 2. Pada langkah selanjutnya, kita akan melintasi seluruh daftar tertaut hingga kita tidak mendapatkan penunjuk nol di sebelah simpul tajuk. Untuk itu, kita akan memberikan nama sementara untuk node berikutnya, seperti yang ditunjukkan pada diagram di bawah ini.
Langkah 3. Karena kami memiliki simpul referensi baru bernama 'sementara,' yang dapat membantu kami melintasi seluruh daftar tertaut hingga kami tidak mendapatkan penunjuk nol, Jadi kami dapat menetapkan tautan berikutnya dari simpul header sebagai nol, yang tidak akan memengaruhi yang ditautkan daftar seperti yang ditunjukkan di bawah ini dalam diagram. Penunjuk nol di sebelah simpul saat ini disebut simpul sebelumnya.
Langkah 4. Sekarang, kami memindahkan simpul sementara ke simpul berikutnya dan simpul saat ini ke simpul sementara sebelumnya. Jadi sekarang kita telah pindah ke node berikutnya. Kami juga mengubah simpul sebelumnya dari nol menjadi hanya simpul sebelumnya dari simpul saat ini. Jadi sekarang simpul sementara akan mengurus semua traverse hingga penunjuk nol sehingga kita dapat mengatur tautan dari simpul saat ini ke simpul sebelumnya, dan sekarang menunjuk ke simpul sebelumnya, seperti yang ditunjukkan pada diagram di bawah ini.
Jadi kami mengikuti langkah yang sama dan, akhirnya, kami akan mendapatkan daftar tertaut terbalik.
Langkah 5 .
Langkah 6.
Langkah 7.
Langkah 8.
Langkah 9.
Langkah 10.
Langkah 11.
Langkah 12.
Langkah 13.
Langkah 14. Pada langkah ini, daftar tertaut kami terbalik.
Program C++ untuk membalik daftar tertaut
#termasukmenggunakan ruang nama std ;
// Metode untuk membuat node
struct simpul {
int nilai ;
simpul * nextNodePtr ;
} * nodeObject ;
ruang kosong buatLinkedList ( int n ) ;
ruang kosong ReverseLinkedList ( simpul ** nodeObject ) ;
ruang kosong menampilkan ( ) ;
int utama ( ) {
int n, nilai, barang ;
cout << 'Berapa banyak node yang ingin Anda buat =>:' ;
makan >> n ;
buatLinkedList ( n ) ;
cout << ' \n Informasi dalam daftar tertaut: \n ' ;
menampilkan ( ) ;
cout << ' \n Daftar tertaut setelah dibalik \n ' ;
ReverseLinkedList ( & nodeObject ) ;
menampilkan ( ) ;
kembali 0 ;
}
// Metode ini akan membuat linked list
ruang kosong buatLinkedList ( int n ) {
struct simpul * simpul depan, * tempNode ;
int nilai, saya ;
nodeObject = ( struct simpul * ) malloc ( ukuran dari ( struct simpul ) ) ;
jika ( nodeObject == BATAL )
cout << 'Tidak cukup untuk assing memori' ;
kalau tidak {
cout << 'Silakan masukkan info node 1 (hanya nomor): ' ;
makan >> nilai ;
nodeObject - > nilai = nilai ;
nodeObject - > nextNodePtr = BATAL ;
tempNode = nodeObject ;
untuk ( saya = dua ; saya <= n ; saya ++ ) {
frontNode = ( struct simpul * ) malloc ( ukuran dari ( struct simpul ) ) ;
// Ketika tidak ada simpul apapun dalam daftar tertaut
jika ( frontNode == BATAL ) {
cout << 'Memori tidak dapat dialokasikan' ;
merusak ;
}
kalau tidak {
cout << 'Silakan masukkan info node' << saya << ':' ;
makan >> nilai ;
frontNode - > nilai = nilai ;
frontNode - > nextNodePtr = BATAL ;
tempNode - > nextNodePtr = frontNode ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
ruang kosong ReverseLinkedList ( simpul ** nodeObject ) {
struct simpul * tempNode = BATAL ;
struct simpul * Node sebelumnya = BATAL ;
struct simpul * Node saat ini = ( * nodeObject ) ;
ketika ( Node saat ini ! = BATAL ) {
tempNode = Node saat ini - > nextNodePtr ;
Node saat ini - > nextNodePtr = Node sebelumnya ;
Node sebelumnya = Node saat ini ;
Node saat ini = tempNode ;
}
( * nodeObject ) = Node sebelumnya ;
}
ruang kosong menampilkan ( ) {
struct simpul * tempNode ;
jika ( nodeObject == BATAL ) {
cout << 'Daftar tertaut kosong' ;
}
kalau tidak {
tempNode = nodeObject ;
ketika ( tempNode ! = BATAL )
{
cout << tempNode - > nilai << ' \t ' ;
tempNode = tempNode - > nextNodePtr ;
}
}
cout << endl ;
}
Keluaran
Berapa banyak node yang ingin Anda buat =>: 6Silakan masukkan info node 1 (nomor saja): 101
Silakan masukkan info node 2: 95
Silakan masukkan info node 3: 61
Silakan masukkan info node 4: 19
Silakan masukkan info node 5: 12
Silakan masukkan info node 6: 11
Informasi dalam daftar tertaut:
101 95 61 19 12 11
Daftar tertaut setelah dibalik
11 12 19 61 95 101
Kesimpulan
Artikel LinuxHint ini telah meninjau cara membalik daftar tertaut di C++. Ada beberapa metode lain untuk membalik daftar tertaut, tetapi ini adalah metode yang sangat umum untuk membalikkan daftar tertaut. Terserah Anda untuk memutuskan bagaimana Anda ingin menyelesaikan masalah Anda, tetapi umumnya fungsi daftar tertaut terbalik harus berupa loop sederhana dengan pertukaran pointer.