linked list good taste
1.0.0
Dalam wawancara TED 2016 (14:10) Linus Torvalds berbicara tentang apa yang ia anggap selera yang baik dalam pengkodean. Sebagai contoh, ia menyajikan dua implementasi penghapusan item dalam daftar yang terhubung secara tunggal (direproduksi di bawah). Untuk menghapus item pertama dari daftar, salah satu implementasi memerlukan kasus khusus, yang lain tidak. Linus, jelas, lebih suka yang terakhir.
Komentarnya adalah:
[...] Saya tidak ingin Anda mengerti mengapa itu tidak memiliki pernyataan IF. Tetapi saya ingin Anda memahami bahwa kadang -kadang Anda dapat melihat masalah dengan cara yang berbeda dan menulis ulang sehingga kasus khusus hilang dan menjadi kasus normal, dan itu kode yang bagus . [...] - L. Torvalds
Cuplikan kode yang dia sajikan adalah pseudocode gaya-C dan cukup sederhana untuk diikuti. Namun, seperti yang disebutkan oleh Linus dalam komentar, cuplikan tidak memiliki penjelasan konseptual dan tidak segera terbukti bagaimana solusi yang lebih elegan sebenarnya bekerja.
Dua bagian berikutnya melihat pendekatan teknis secara rinci dan menunjukkan bagaimana dan mengapa pendekatan pengalamatan tidak langsung sangat rapi. Bagian terakhir memperluas solusi dari penghapusan item ke penyisipan.
Struktur data dasar untuk daftar bilangan bulat yang terhubung secara tunggal ditunjukkan pada Gambar 1.
Gambar 1 : Daftar bilangan bulat yang terhubung secara tunggal.
Angka -angka dipilih secara sewenang -wenang dan panah yang dipilih secara sewenang -wenang menunjukkan petunjuk. head adalah penunjuk tipe list_item * dan masing -masing kotak adalah instance dari struct list_item , masing -masing dengan variabel anggota (disebut next dalam kode) tipe list_item * yang menunjuk ke item berikutnya.
Implementasi C dari struktur data adalah:
struct list_item {
int value ;
struct list_item * next ;
};
typedef struct list_item list_item ;
struct list {
struct list_item * head ;
};
typedef struct list list ;Kami juga menyertakan API (minimal):
/* The textbook version */
void remove_cs101 ( list * l , list_item * target );
/* A more elegant solution */
void remove_elegant ( list * l , list_item * target ); Dengan itu di tempat, mari kita lihat implementasi remove_cs101() dan remove_elegant() . Kode contoh -contoh ini berlaku untuk pseudocode dari contoh Linus dan juga menyusun dan berjalan.
Gambar 2 : Model konseptual untuk struktur data daftar dalam algoritma CS101.
void remove_cs101 ( list * l , list_item * target )
{
list_item * cur = l -> head , * prev = NULL ;
while ( cur != target ) {
prev = cur ;
cur = cur -> next ;
}
if ( prev )
prev -> next = cur -> next ;
else
l -> head = cur -> next ;
} Pendekatan CS101 standar memanfaatkan dua pointer traversal cur dan prev , masing -masing menandai posisi traversal saat ini dan sebelumnya dalam daftar. cur dimulai pada head kepala daftar, dan maju sampai target ditemukan. prev dimulai pada NULL dan kemudian diperbarui dengan nilai cur sebelumnya setiap kali cur maju. Setelah target ditemukan, tes algoritma jika prev non- NULL . Jika ya, item tidak ada di awal daftar dan penghapusan terdiri dari rute ulang daftar tertaut di sekitar cur . Jika prev NULL , cur menunjuk ke elemen pertama dalam daftar, dalam hal ini, penghapusan berarti memindahkan daftar ke depan.
Versi yang lebih elegan memiliki lebih sedikit kode dan tidak memerlukan cabang terpisah untuk menangani penghapusan elemen pertama dalam daftar.
void remove_elegant ( list * l , list_item * target )
{
list_item * * p = & l -> head ;
while ( * p != target )
p = & ( * p ) -> next ;
* p = target -> next ;
} Kode ini menggunakan p pointer tidak langsung yang memegang alamat pointer ke item daftar, dimulai dengan alamat head . Dalam setiap iterasi, pointer itu maju untuk menahan alamat pointer ke item daftar berikutnya, yaitu alamat elemen next dalam list_item saat ini. Ketika pointer ke daftar item *p sama dengan target , kami keluar dari loop pencarian dan menghapus item dari daftar.
Wawasan utama adalah bahwa menggunakan Pointer p tidak langsung memiliki dua manfaat konseptual:
head menjadi bagian integral dari struktur data. Ini menghilangkan kebutuhan untuk kasus khusus untuk menghapus item pertama.while tanpa harus melepaskan pointer yang menunjuk ke target . Ini memungkinkan kami untuk memodifikasi pointer yang menunjuk ke target dan untuk lolos dengan satu iterator yang bertentangan dengan prev dan cur .Mari kita lihat masing -masing poin ini.
head Model standar menafsirkan daftar yang ditautkan sebagai urutan contoh list_item . Awal urutan dapat diakses melalui penunjuk head . Ini mengarah pada model konseptual yang diilustrasikan pada Gambar 2 di atas. Pointer head hanya dianggap sebagai pegangan untuk mengakses awal daftar. prev dan cur adalah pointer tipe list_item * dan selalu menunjuk ke item atau NULL .
Implementasi elegan menggunakan skema pengalamatan tidak langsung yang menghasilkan pandangan berbeda pada struktur data:
Gambar 3 : Model konseptual untuk struktur data daftar dalam pendekatan yang lebih elegan.
Di sini, p adalah tipe list_item ** dan memegang alamat pointer ke item daftar saat ini. Saat kami memajukan pointer, kami meneruskan ke alamat pointer ke item daftar berikutnya.
Dalam kode, ini diterjemahkan menjadi p = &(*p)->next , artinya kami
(*p) : Dereferensi alamat ke pointer ke item daftar saat ini->next : Dereferensi yang Pointer Lagi dan Pilih Bidang Yang Menahan Alamat Item Daftar Berikutnya& : Ambil alamat bidang alamat itu (yaitu mendapatkan pointer untuk itu) Ini sesuai dengan interpretasi struktur data di mana daftar tersebut merupakan urutan pointer ke list_item S (lih. Gambar 3).
Manfaat tambahan dari interpretasi khusus itu adalah bahwa ia mendukung pengeditan pointer next dari pendahulu item saat ini di seluruh traversal.
Dengan p memegang alamat pointer ke item daftar, perbandingan dalam loop pencarian menjadi
while ( * p != target ) Loop pencarian akan keluar jika *p sama dengan target , dan begitu itu terjadi, kami masih dapat memodifikasi *p karena kami memegang alamatnya p . Dengan demikian, meskipun mengulangi loop sampai kami mencapai target , kami masih mempertahankan pegangan (alamat bidang next atau pointer head ) yang dapat digunakan untuk secara langsung memodifikasi pointer yang menunjuk ke item.
Ini adalah alasan mengapa kita dapat memodifikasi pointer yang masuk ke item untuk menunjuk ke lokasi yang berbeda menggunakan *p = target->next dan mengapa kita tidak memerlukan pointer prev dan cur untuk melintasi daftar untuk penghapusan item.
Ternyata ide di balik remove_elegant() dapat diterapkan untuk menghasilkan implementasi yang sangat ringkas dari fungsi lain dalam daftar API: insert_before() , yaitu memasukkan item yang diberikan sebelum yang lain.
Pertama, mari kita tambahkan deklarasi berikut ke daftar API di list.h :
void insert_before ( list * l , list_item * before , list_item * item ); Fungsi akan mengambil pointer ke daftar l , pointer before ke item dalam daftar itu dan pointer ke item daftar item baru yang akan dimasukkan fungsi sebelumnya before .
Sebelum kami melanjutkan, kami refactor loop pencarian ke fungsi terpisah
static inline list_item * * find_indirect ( list * l , list_item * target )
{
list_item * * p = & l -> head ;
while ( * p != target )
p = & ( * p ) -> next ;
return p ;
} dan gunakan fungsi itu di remove_elegant() seperti itu
void remove_elegant ( list * l , list_item * target )
{
list_item * * p = find_indirect ( l , target );
* p = target -> next ;
}insert_before() Menggunakan find_indirect() , mudah untuk mengimplementasikan insert_before() :
void insert_before ( list * l , list_item * before , list_item * item )
{
list_item * * p = find_indirect ( l , before );
* p = item ;
item -> next = before ;
} Hasil yang sangat indah adalah bahwa implementasinya memiliki semantik yang konsisten untuk kasus tepi: jika before menunjuk ke kepala daftar, item baru akan dimasukkan pada awal daftar, jika before NULL atau tidak valid (yaitu item tidak ada di l ), item baru akan ditambahkan pada akhirnya.
Premis dari solusi yang lebih elegan untuk penghapusan item adalah perubahan tunggal yang sederhana: menggunakan pointer tidak langsung list_item ** untuk mengulangi pointer ke item daftar. Segala sesuatu yang mengalir dari sana: tidak perlu untuk kasus khusus atau percabangan dan satu iterator cukup untuk menemukan dan menghapus item target. Ternyata pendekatan yang sama memberikan solusi elegan untuk penyisipan item secara umum dan untuk dimasukkan sebelum item yang ada pada khususnya.
Jadi, kembali ke komentar awal Linus: apakah rasanya enak? Sulit dikatakan, tetapi tentu saja solusi yang berbeda, kreatif, dan sangat elegan untuk tugas CS yang terkenal.
