Dalam wawancara TED 2016 (14:10), Linus Torvalds berbicara tentang gaya pengkodean yang baik . Sebagai contoh, dia memberikan dua opsi untuk menghapus elemen dari daftar tertaut tunggal (lihat di bawah). Opsi pertama memiliki kasus khusus, sedangkan opsi lainnya tidak. Linus lebih memilih yang terakhir.



Komentarnya:

[...] Tidak perlu dipikirkan kenapa tidak ada pernyataan if di sini. Penting untuk melihat masalah dari perspektif yang berbeda dan menulis ulang sehingga kasus khusus menghilang dan menjadi kasus biasa, dan itu kode yang bagus . - L. Torvalds

Linus menunjukkan pseudocode gaya-C yang cukup sederhana sebagai contoh. Namun tidak memberikan penjelasan konseptual. Oleh karena itu, tidak segera jelas bagaimana penunjuk tidak langsung bekerja.



Mari kita lihat lebih dekat solusi ini dan kelebihannya. Sebagai bonus, tidak hanya penghapusan yang ditampilkan, tetapi juga penyisipan elemen melalui pengalamatan tidak langsung.

Kode

Struktur data dasar untuk daftar bilangan bulat yang terhubung tunggal ditunjukkan pada Gambar. 1.





Gambar. 1. Daftar bilangan bulat yang tertaut tunggal



Bilangan adalah nilai bilangan bulat yang dipilih secara acak, dan panah sesuai dengan penunjuk: head



 - ini adalah penunjuk tipe IntListItem*



, semua blok adalah contoh struktur IntListItem



, masing-masing dengan variabelnya sendiri ( next



dalam kode) dari jenisnya IntListItem*



, yang menunjuk ke elemen berikutnya.



Implementasi struktur data di C:

struct IntListItem {
    int value;
    struct IntListItem* next;
};
typedef struct IntListItem IntListItem;

struct IntList {
    IntListItem* head;
};
typedef struct IntList IntList;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Juga API (minimal):

/* The textbook version */
void remove_cs101(IntList* l, IntListItem* target);
/* A more elegant solution */
void remove_elegant(IntList* l, IntListItem* target);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Sekarang mari kita lihat implementasi remove_cs101()



dan remove_elegant()



. Kode contoh tidak bertentangan dengan pseudocode dari contoh Linus, tetapi mengkompilasi dan menjalankan.

Versi dasar

Angka: 2. Model konseptual dari struktur data daftar dalam algoritma dasar

void remove_cs101(IntList *l, IntListItem *target)
{
    IntListItem *cur = l->head, *prev = NULL;
    while (cur != target) {
        prev = cur;
        cur = cur->next;
    }
    if (prev) {
        prev->next = cur->next;
    } else {
        l->head = cur->next;
    }
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Dalam pendekatan standar, ada dua penunjuk traversal cur



dan prev



, yang masing-masing menandai posisi traversal saat ini dan sebelumnya dalam daftar. cur



dimulai di bagian atas daftar head



dan bergerak maju hingga target ditemukan. Pada gilirannya, ini prev



dimulai dengan NULL



dan kemudian diperbarui ke nilai sebelumnya cur



setiap kali bergerak maju. Ketika target ditemukan, algoritme memeriksa apakah itu bukan prev



nol. Jika demikian, ini cur



menunjuk ke item pertama dalam daftar, dalam hal ini menghapus berarti menggerakkan kepala daftar ke depan.

Solusi yang lebih elegan

Versi yang lebih elegan memiliki lebih sedikit kode dan tidak memerlukan cabang terpisah untuk menghapus item pertama dalam daftar.

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) != target) {
        p = &(*p)->next;
    }
    *p = target->next;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Kode menggunakan penunjuk tidak langsung p



yang berisi alamat penunjuk ke item daftar, dimulai dari alamat head



. Di setiap iterasi, penunjuk ini diperluas untuk menyertakan alamat penunjuk ke item berikutnya dalam daftar, yaitu alamat item next



di item saat ini IntListItem



. Ketika penunjuk ke item daftar (*p)



sama target



, kami keluar dari loop pencarian dan menghapus item dari daftar.

Bagaimana itu bekerja?

Pointer tidak langsung memiliki p



dua keunggulan konseptual:

1. Memungkinkan Anda menafsirkan daftar tertaut sedemikian rupa sehingga penunjuk head
   
   
   
   menjadi bagian integral dari struktur data. Ini menghilangkan kebutuhan akan kasing khusus untuk menghapus item pertama.
   
   
2. Ini juga memungkinkan Anda untuk mengevaluasi status pengulangan while
   
   
   
   tanpa harus melepaskan penunjuk yang menunjuk target
   
   
   
   . Ini memungkinkan Anda untuk mengubah penunjuk ke target
   
   
   
   dan berkeliling dengan satu iterator, tidak seperti prev
   
   
   
   dan cur
   
   
   
   .

Mari kita lihat setiap item secara bergantian.

Integrasi penunjuk kepala

Model Standar menafsirkan daftar tertaut sebagai urutan contoh IntListItem



. Awal urutan dapat diperoleh dengan menggunakan penunjuk head



. Ini mengarah ke model konseptual yang ditunjukkan pada Gambar. 2. Penunjuk head



hanya diperlakukan sebagai pegangan untuk mengakses awal daftar. prev



dan cur



merupakan penunjuk tipe IntListItem*



dan selalu mengarah ke atau NULL



.



Implementasi elegan menggunakan skema pengalamatan tidak langsung, yang memberikan tampilan berbeda dari struktur data:





Gbr. 3. Model konseptual dari struktur data daftar dalam solusi yang lebih elegan



Di sini p



mewakili tipeIntListItem**



dan berisi alamat penunjuk ke item daftar saat ini. Saat penunjuk bergerak maju, alamatnya berubah ke elemen berikutnya.



Dalam kode, terlihat seperti ini p = &(*p)->next



:

1. (*p)
   
   
   
   : dereferensi alamat penunjuk ke item daftar saat ini.
   
   
2. ->next
   
   
   
   : dereferensi penunjuk ini lagi dan pilih bidang dengan alamat elemen berikutnya.
   
   
3. &
   
   
   
   : ambil alamat bidang ini (yaitu, dapatkan penunjuk ke sana).

Hal ini sejalan dengan interpretasi suatu struktur data, dimana list merupakan urutan pointer ke elemen IntListItem



(Gambar 3).

Sentuhan akhir

Keuntungan tambahan dari interpretasi khusus ini adalah memungkinkan penunjuk diedit next



untuk elemen pendahulu saat ini di seluruh traversal .



Jika p



berisi alamat penunjuk ke elemen daftar, perbandingan di loop pencarian menjadi:

while ((*p) != target) {
    ...
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Siklus pencarian akan berakhir jika (*p)



sama target



, dan segera setelah ini terjadi, kita masih bisa berubah (*p)



, karena kita menahan alamatnya p



. Jadi, meskipun loop berulang sampai akhir, sebuah deskriptor (alamat bidang next



atau pointer head



) disimpan yang dapat digunakan untuk mengubah pointer ke elemen secara langsung.



Itulah mengapa kita dapat mengubah masukan ke penunjuk elemen untuk menunjuk ke lokasi yang berbeda, menggunakan *p = target->next



, dan karena itu kita tidak perlu melewati penunjuk prev



dan cur



untuk menghapus item tersebut.

Aplikasi baru

Ternyata ide yang sama dapat diterapkan pada implementasi yang sangat singkat dari fungsi lain dalam daftar tertaut:, insert_before()



yaitu, menyisipkan elemen ini sebelum yang lain.

Penyisipan sebelum elemen yang ada

Pertama, mari tambahkan deklarasi berikut ke list.h



:

void insert_before(IntList *l, IntListItem *before, IntListItem *item);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Fungsi ini akan membawa penunjuk ke daftar l, penunjuk sebelum elemen dalam daftar ini, dan penunjuk ke elemen daftar baru yang akan disisipkan oleh fungsi sebelumnya.

Refaktor cepat

Sebelum melanjutkan, mari kita buat loop pencarian sebagai fungsi terpisah:

static inline IntListItem **find_indirect(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) && (*p) != target) {
        p = &(*p)->next;
    }
    return p;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

dan gunakan di remove_elegant()



:

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = find_indirect(l, target);
    *p = target->next;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Insert_before () implementasi

Menggunakannya find_indirect()



mudah untuk diterapkan insert_before()



:

void insert_before(IntList *l, IntListItem *before, IntListItem *item)
{
    IntListItem **p = find_indirect(l, before);
    *p = item;
    item->next = before;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Yang paling menyenangkan adalah semantik padat untuk kasus tepi: jika before



menunjuk ke kepala daftar, elemen baru akan disisipkan di awal, jika before



nol atau tidak valid (yaitu, tidak ada di l



), elemen baru akan ditambahkan di akhir.

Kesimpulan

Prasyarat untuk solusi yang lebih elegan untuk menghapus elemen adalah satu perubahan sederhana: penunjuk tidak langsung IntListItem**



untuk mengulang penunjuk ke elemen daftar. Segala sesuatu yang lain mengikuti dari sana: tidak perlu kasus atau cabang khusus. Satu iterator cukup untuk menemukan dan menghapus elemen target. Dan ternyata pendekatan yang sama memberikan solusi elegan untuk penyisipan secara umum dan penyisipan di depan elemen yang ada pada khususnya.



Jadi, kembali ke ucapan awal Linus, apakah ini indikator selera yang baik? Sulit untuk dikatakan. Tapi jelas ada solusi yang kreatif dan sangat elegan untuk masalah yang terkenal.