linked list good taste

รายการที่เชื่อมโยงเทคนิคตัวชี้และรสชาติที่ดี

• การแนะนำ
• รหัส
  • เวอร์ชัน CS101
  • โซลูชันที่สง่างามยิ่งขึ้น
• มันทำงานอย่างไร?
  • การรวมตัวชี้หัว
  • การดูแลรักษา
• ไปไกลกว่า
  • การแทรกก่อนรายการที่มีอยู่
  • Refactor อย่างรวดเร็ว
  • การใช้ Insert_Before ()
• บทสรุป

การแนะนำ

ในการสัมภาษณ์ TED ปี 2559 (14:10) Linus Torvalds พูดถึงสิ่งที่เขาคิดว่า มีรสนิยมที่ดี ในการเขียนโค้ด ตัวอย่างเช่นเขานำเสนอการใช้งานการลบรายการสองรายการในรายการที่เชื่อมโยงกันโดยลำพัง (ทำซ้ำด้านล่าง) ในการลบรายการแรกออกจากรายการหนึ่งในการใช้งานต้องใช้กรณีพิเศษอีกรายการหนึ่งไม่ได้ Linus เห็นได้ชัดว่าชอบหลัง

ความคิดเห็นของเขาคือ:

[... ] ฉันไม่ต้องการให้คุณเข้าใจว่าทำไมมันถึงไม่มีคำสั่ง IF แต่ฉันต้องการให้คุณเข้าใจว่าบางครั้งคุณสามารถเห็นปัญหาในวิธีที่แตกต่างกันและเขียนใหม่เพื่อให้กรณีพิเศษหายไปและกลายเป็นกรณีปกติและนั่นเป็น รหัสที่ดี [... ] - L. Torvalds

รหัสตัวอย่างที่เขานำเสนอคือ pseudocode สไตล์ C และง่ายพอที่จะติดตาม อย่างไรก็ตามตามที่ Linus กล่าวไว้ในความคิดเห็นตัวอย่างตัวอย่างขาดความคิดและไม่เห็นได้ชัดว่าโซลูชันที่สง่างามมากขึ้นใช้งานได้จริง

สองส่วนถัดไปดูวิธีการทางเทคนิคโดยละเอียดและแสดงให้เห็นว่าวิธีการที่อยู่ทางอ้อมและวิธีการที่อยู่ทางอ้อมนั้นเรียบร้อยมาก ส่วนสุดท้ายขยายโซลูชันจากการลบรายการไปยังการแทรก

รหัส

โครงสร้างข้อมูลพื้นฐานสำหรับรายการจำนวนเต็มที่เชื่อมโยงกันโดยลำพังแสดงในรูปที่ 1

รูปที่ 1 : รายการที่เชื่อมโยงกันของจำนวนเต็ม

ตัวเลขถูกเลือกโดยพลการค่าจำนวนเต็มและลูกศรระบุตัวชี้ head เป็นตัวชี้ประเภท list_item * และแต่ละกล่องเป็นอินสแตนซ์ของ list_item struct แต่ละตัวมีตัวแปรสมาชิก (เรียกว่า next ในรหัส) ของประเภท list_item * ที่ชี้ไปที่รายการถัดไป

การใช้งาน C ของโครงสร้างข้อมูลคือ:

 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 ;

นอกจากนี้เรายังรวม API (น้อยที่สุด):

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

ด้วยสิ่งนั้นมาดูการใช้งานของ remove_cs101() และ remove_elegant() รหัสของตัวอย่างเหล่านี้เป็นจริงกับ pseudocode จากตัวอย่างของ Linus และรวบรวมและเรียกใช้

เวอร์ชัน CS101

รูปที่ 2 : แบบจำลองแนวคิดสำหรับโครงสร้างข้อมูลรายการในอัลกอริทึม 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 ;
}

วิธีการ CS101 มาตรฐานใช้ประโยชน์จากสองพอยน์เตอร์พอยน์เตอร์ cur และ prev ทำเครื่องหมายตำแหน่งการเดินทางในปัจจุบันและก่อนหน้าในรายการตามลำดับ cur เริ่มต้นที่ head รายการและก้าวหน้าจนกว่าจะพบเป้าหมาย prev เริ่มต้นที่ NULL และต่อมาได้รับการปรับปรุงด้วยค่าก่อนหน้าของ cur ทุกครั้งที่ cur ก้าวหน้า หลังจากพบเป้าหมายอัลกอริทึมจะทำการทดสอบหาก prev ไม่ใช่ NULL ถ้าใช่รายการไม่ได้อยู่ที่จุดเริ่มต้นของรายการและการลบประกอบด้วยการกำหนดเส้นทางใหม่รายการที่เชื่อมโยงรอบ cur หาก prev เป็น NULL cur จะชี้ไปที่องค์ประกอบแรกในรายการซึ่งในกรณีนี้การลบหมายถึงการย้ายหัวรายการไปข้างหน้า

โซลูชันที่สง่างามยิ่งขึ้น

รุ่นที่สง่างามมากขึ้นมีรหัสน้อยกว่าและไม่จำเป็นต้องมีสาขาแยกต่างหากเพื่อจัดการกับการลบองค์ประกอบแรกในรายการ

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

รหัสใช้ตัวชี้ทางอ้อม p ที่เก็บที่อยู่ของตัวชี้ไปยังรายการเริ่มต้นด้วยที่อยู่ของ head ในการทำซ้ำทุกครั้งตัวชี้นั้นจะมีความก้าวหน้าในการเก็บที่อยู่ของตัวชี้ไปยังรายการรายการถัดไปนั่นคือที่อยู่ขององค์ประกอบ next ใน list_item ปัจจุบัน เมื่อตัวชี้ไปยังรายการ *p เท่ากับ target เราออกจากลูปค้นหาและลบรายการออกจากรายการ

มันทำงานอย่างไร?

ความเข้าใจที่สำคัญคือการใช้ตัวชี้ทางอ้อม p มีประโยชน์สองประการเกี่ยวกับแนวคิด:

1. มันช่วยให้เราสามารถตีความรายการที่เชื่อมโยงในลักษณะที่ทำให้ตัวชี้ head เป็นส่วนหนึ่งของโครงสร้างข้อมูล สิ่งนี้ไม่จำเป็นต้องใช้กรณีพิเศษในการลบรายการแรก
2. นอกจากนี้ยังช่วยให้เราสามารถประเมินสภาพของการวนซ้ำ while โดยไม่ต้องปล่อยตัวชี้ที่ชี้ไปที่ target สิ่งนี้ช่วยให้เราสามารถปรับเปลี่ยนตัวชี้ที่ชี้ไปที่ target และหลีกหนีด้วยตัววนซ้ำเดี่ยวเมื่อเทียบกับ prev และ cur

ลองดูแต่ละจุดเหล่านี้กันเถอะ

การรวมตัวชี้ head

โมเดลมาตรฐานตีความรายการที่เชื่อมโยงเป็นลำดับของอินสแตนซ์ list_item จุดเริ่มต้นของลำดับสามารถเข้าถึงได้ผ่านตัวชี้ head สิ่งนี้นำไปสู่รูปแบบแนวคิดที่แสดงในรูปที่ 2 ด้านบน ตัวชี้ head ถือเป็นเพียงการจัดการเพื่อเข้าถึงจุดเริ่มต้นของรายการ prev และ cur เป็นพอยน์เตอร์ของประเภท list_item * และชี้ไปที่รายการหรือ NULL เสมอ

การใช้งานที่สง่างามใช้รูปแบบการกำหนดที่อยู่ทางอ้อมที่ให้มุมมองที่แตกต่างกันในโครงสร้างข้อมูล:

รูปที่ 3 : แบบจำลองแนวคิดสำหรับโครงสร้างข้อมูลรายการในวิธีการที่สง่างามยิ่งขึ้น

ที่นี่ p เป็นประเภท list_item ** และเก็บที่อยู่ของตัวชี้ไปยังรายการปัจจุบัน เมื่อเราเลื่อนตัวชี้เราจะส่งต่อไปยังที่อยู่ของตัวชี้ไปยังรายการถัดไป

ในรหัสสิ่งนี้แปลเป็น p = &(*p)->next หมายถึงเรา

1. (*p) : dereference ที่อยู่ไปยังตัวชี้ไปยังรายการปัจจุบัน
2. ->next : dereference ตัวชี้นั้นอีกครั้งและเลือกฟิลด์ที่เก็บที่อยู่ของรายการถัดไป
3. & : ใช้ที่อยู่ของฟิลด์ที่อยู่นั้น (เช่นรับตัวชี้ไปที่มัน)

สิ่งนี้สอดคล้องกับการตีความโครงสร้างข้อมูลที่รายการเป็นลำดับของพอยน์เตอร์ไปยัง list_item s (cf. รูปที่ 3)

การดูแลรักษา

ประโยชน์เพิ่มเติมของการตีความนั้นคือการสนับสนุนการแก้ไขตัวชี้ next ของรุ่นก่อนของรายการปัจจุบันตลอดการเดินทางทั้งหมด

ด้วย p ที่ถือที่อยู่ของตัวชี้ไปยังรายการการเปรียบเทียบในลูปการค้นหาจะกลายเป็น

 while ( * p != target )

ลูปการค้นหาจะออกหาก *p เท่ากับ target และเมื่อมันเป็นเช่นนั้นเรายังสามารถแก้ไข *p ได้เนื่องจากเราถือที่อยู่ p ดังนั้นแม้จะวนซ้ำวนซ้ำจนกว่าเราจะไปถึง target เรายังคงรักษาที่จับ (ที่อยู่ของฟิลด์ next หรือตัวชี้ head ) ที่สามารถใช้ในการปรับเปลี่ยนตัวชี้ที่ชี้ ไปยัง รายการโดยตรง

นี่คือเหตุผลที่เราสามารถปรับเปลี่ยนตัวชี้ขาเข้าไปยังรายการเพื่อชี้ไปที่ตำแหน่งอื่นโดยใช้ *p = target->next และทำไมเราไม่จำเป็นต้องมีพอยน์เตอร์ prev และ cur เพื่อสำรวจรายการสำหรับการลบรายการ

ไปไกลกว่า

ปรากฎว่าแนวคิดที่อยู่เบื้องหลัง remove_elegant() สามารถนำไปใช้เพื่อให้ได้การใช้งานโดยเฉพาะอย่างยิ่งของฟังก์ชั่นอื่นในรายการ API: insert_before() เช่นการแทรกรายการที่กำหนดก่อนอื่น

การแทรกก่อนรายการที่มีอยู่

ก่อนอื่นเรามาเพิ่มการประกาศต่อไปนี้ในรายการ API ใน list.h :

 void insert_before ( list * l , list_item * before , list_item * item );

ฟังก์ชั่นจะนำตัวชี้ไปยังรายการ l ซึ่งเป็นตัวชี้ before ไปยังรายการในรายการนั้นและตัวชี้ไปยัง item รายการใหม่ที่ฟังก์ชั่นจะแทรกก่อน before

Refactor อย่างรวดเร็ว

ก่อนที่เราจะเดินหน้าต่อไปเราจะปรับลูปค้นหาเป็นฟังก์ชั่นแยกต่างหาก

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

และใช้ฟังก์ชั่นนั้นใน remove_elegant() เช่นนั้น

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

การใช้ insert_before()

การใช้ find_indirect() มันตรงไปตรงมาที่จะใช้ 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 ;
}

ผลลัพธ์ที่สวยงามเป็นพิเศษคือการใช้งานมีความหมายที่สอดคล้องกันสำหรับกรณีขอบ: หาก before จะชี้ไปที่หัวรายการรายการใหม่จะถูกแทรกที่จุดเริ่มต้นของรายการหาก before เป็น NULL หรือไม่ถูกต้อง (เช่นรายการไม่มีอยู่ใน l ) รายการใหม่จะถูกผนวกเข้าด้วยกัน

บทสรุป

หลักฐานของโซลูชันที่สง่างามมากขึ้นสำหรับการลบรายการคือการเปลี่ยนแปลงที่เรียบง่ายเพียงครั้งเดียว: การใช้ตัวชี้ทางอ้อม list_item ** ตัวชี้เพื่อทำซ้ำผ่านพอยน์เตอร์ไปยังรายการรายการ ทุกอย่างอื่นไหลออกมาจากที่นั่น: ไม่จำเป็นต้องมีกรณีพิเศษหรือการแตกแขนงและตัววนซ้ำเดียวก็เพียงพอที่จะค้นหาและลบรายการเป้าหมาย นอกจากนี้ยังปรากฎว่าวิธีการเดียวกันนี้เป็นวิธีการแก้ปัญหาที่สง่างามสำหรับการแทรกรายการโดยทั่วไปและสำหรับการแทรก ก่อน รายการที่มีอยู่โดยเฉพาะ

ดังนั้นกลับไปที่ความคิดเห็นเริ่มต้นของ Linus: มันเป็นรสนิยมที่ดีหรือไม่? ยากที่จะพูด แต่แน่นอนว่ามันเป็นทางออกที่แตกต่างสร้างสรรค์และสง่างามมากสำหรับงาน CS ที่รู้จักกันดี