[เล่นเพลง] 

DOUG LLOYD: ตกลงดังนั้นที่ จุดในหลักสูตรนี้ เราได้ครอบคลุมมากของพื้นฐานของซี เรารู้มากเกี่ยวกับตัวแปรอาร์เรย์ที่ ชี้ทุกสิ่งที่ดี ผู้ที่ได้รับการสร้างขึ้นจากการเรียงลำดับ เพื่อดูว่าเป็นปัจจัยพื้นฐานที่ แต่เราสามารถทำอะไรได้มากใช่มั้ย? เราสามารถรวมสิ่ง ร่วมกันในรูปแบบที่น่าสนใจ 

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

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

และตัวอย่างที่ดีที่สุดที่ผมมี สำหรับที่มีการจัดเรียงแทรก ถ้าคุณจำวิดีโอของเรา ในการจัดเรียงแทรก มีจำนวนมากของ ค่าใช้จ่ายในการมีส่วนร่วม ที่จะรับองค์ประกอบและเปลี่ยนพวกเขา ออกจากทางเพื่อให้พอดีกับบางสิ่งบางอย่าง เข้ากลางของอาเรย์ของคุณ อาร์เรย์ยังประสบจากที่อื่น ปัญหาที่เกิดขึ้นซึ่งเป็นความแข็ง เมื่อเราประกาศอาร์เรย์ เราได้รับการยิงหนึ่งที่มัน เราได้รับที่จะบอกว่าผมต้องการ นี้หลายองค์ประกอบ อาจจะ 100 ก็อาจจะ เป็น 1000 ก็อาจจะ เป็น x ที่ x คือตัวเลขที่ผู้ใช้ ให้เราที่พร้อมท์หรือคำสั่ง สาย 

แต่เราเท่านั้นที่ได้รับการยิงหนึ่งที่มันเรา ไม่ได้รับการพูดแล้วโอ้ที่จริงผม จำเป็น 101 หรือที่ผมต้องบวก x 20 สายเกินไปที่เราได้ประกาศไปแล้ว อาร์เรย์และถ้าเราต้องการที่จะได้รับ 101 x บวก 20 เราจะต้องประกาศ อาร์เรย์ที่แตกต่างกันอย่างสิ้นเชิง คัดลอกองค์ประกอบทั้งหมดของอาร์เรย์ มากกว่าและแล้วเรามีเพียงพอ และสิ่งที่ถ้าเราผิดอีกครั้งสิ่งที่ ถ้าเราต้องการจริง 102 หรือ x บวก 40 ที่เราต้องทำเช่นนี้อีกครั้ง ดังนั้นพวกเขาจะไม่ยืดหยุ่นมาก สำหรับการปรับขนาดข้อมูลของเรา แต่ถ้าเรารวมกันบางส่วน พื้นฐานที่เรามีอยู่แล้ว เรียนรู้เกี่ยวกับตัวชี้และโครงสร้าง โดยเฉพาะอย่างยิ่งแบบไดนามิกใช้หน่วยความจำ การจัดสรร malloc กับเรา สามารถนำชิ้นส่วนเหล่านี้ร่วมกัน เพื่อสร้างข้อมูลใหม่ structure-- เชื่อมโยงเดี่ยวรายการที่เราอาจจะ say-- ที่ช่วยให้เราเติบโตและ หดตัวคอลเลกชันของค่า และเราจะไม่ได้มีการสูญเสียพื้นที่ใด ๆ 

ดังนั้นอีกครั้งที่เราเรียกว่าความคิดนี้ ความคิดนี้เป็นรายการที่เชื่อมโยง โดยเฉพาะอย่างยิ่งในวิดีโอนี้เรา พูดคุยเกี่ยวกับรายการที่เชื่อมโยงโดยลำพัง แล้ววิดีโออื่นเราจะพูดคุย รายการเกี่ยวกับการเชื่อมโยงเป็นทวีคูณซึ่ง เป็นเพียงการเปลี่ยนแปลงในรูปแบบที่นี่ แต่รายการที่เชื่อมโยงโดยลำพัง ประกอบด้วยโหนด โหนดเพียงเป็น term-- นามธรรม มันเป็นเพียงแค่สิ่งที่ฉันโทร ที่ชนิดของ โครงสร้างโดยทั่วไปฉัน? เพียงแค่จะเรียกมันว่า node-- นี้ โหนดมีสองคนหรือสองช่อง แต่ก็มีข้อมูลปกติ จำนวนเต็มลอยตัวอักษร หรืออาจจะมีบางชนิดข้อมูลอื่น ๆ ที่คุณกำหนดด้วย def ประเภท และจะมีตัวชี้ไปยัง โหนดชนิดเดียวกันอีก 

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

อะไรพิเศษนี้ โครงสร้างโหนดมีลักษณะอย่างไร ดีถ้าคุณจำได้จากวิดีโอของเรา การกำหนดประเภทที่กำหนดเองที่มีความละเอียดชนิด เราสามารถกำหนด structure-- และ พิมพ์กำหนดโครงสร้างเช่นนี้ tyepdef struct sllist แล้วฉัน ใช้ค่าคำว่าที่นี่โดยพลการ เพื่อบ่งบอกชนิดของข้อมูลใด ๆ จริงๆ คุณสามารถส่งผ่านจำนวนเต็มหรือลอย คุณอาจจะมีสิ่งที่คุณต้องการ มันไม่ได้ จำกัด เพียงแค่ จำนวนเต็มหรืออะไรอย่างนั้น ดังนั้นค่าเป็นเพียงโดยพลการ ชนิดข้อมูลและจากนั้นตัวชี้ ไปยังโหนดชนิดเดียวกันอีก 

ขณะนี้มีการจับเล็ก ๆ น้อย ๆ ที่นี่มีการกำหนดโครงสร้าง เมื่อมันเป็นโครงสร้างที่อ้างอิงตัวเอง ฉันต้องมีชั่วคราว ชื่อโครงสร้างของฉัน ในตอนท้ายของฉันวันที่ เห็นได้ชัดว่าต้องการที่จะเรียกมันว่า โหนด sll ที่ใหม่ที่สุด ชื่อส่วนหนึ่งของการกำหนดประเภทของฉัน แต่ฉันไม่สามารถใช้โหนด sll ในช่วงกลางของเรื่องนี้ เหตุผลที่ผมยังไม่ได้ สร้างชนิดที่เรียกว่าโหนด sll จนกว่าฉันจะตีจุดสุดท้ายที่นี่ จนมาถึงจุดที่ฉันต้องมี วิธีการที่จะอ้างถึงชนิดข้อมูลนี้อีก 

และนี่คือตัวเอง ชนิดข้อมูลอ้างอิง มัน; s ข้อมูลชนิดหนึ่ง โครงสร้างที่มีข้อมูล และตัวชี้ไปยังอีก โครงสร้างของประเภทเดียวกัน ดังนั้นผมจึงจะต้องสามารถที่จะอ้างถึง ชนิดข้อมูลนี้อย่างน้อยชั่วคราว เพื่อให้มันเป็นชั่วคราว ชื่อของ struct sllist ช่วยให้ผมแล้วบอกว่าผมต้องการ ตัวชี้ไป sllist struct อื่น ดาว struct sllist แล้ว หลังจากที่ผมเสร็จสิ้นนิยาม ตอนนี้ผมสามารถเรียกประเภทนี้โหนด sll 

เพื่อที่ว่าทำไมคุณเห็นมี ชื่อชั่วคราวที่นี่ แต่ชื่อที่ถาวรที่นี่ บางครั้งคุณอาจจะเห็น คำจำกัดความของโครงสร้าง ยกตัวอย่างเช่นการที่ไม่ได้เป็น อ้างอิงตัวเองว่า ไม่ได้มีการระบุชื่อของที่นี่ มันก็จะบอกว่า typedef struct, เปิดวงเล็บปีกกาแล้วกำหนดมัน แต่ถ้าคุณ struct เป็นตัวเอง อ้างอิงว่าเป็นหนึ่งในนี้คือ คุณจำเป็นต้องระบุ ชื่อประเภทชั่วคราว แต่ในที่สุดตอนนี้ ที่เราได้กระทำเช่นนี้ เราก็สามารถอ้างถึง โหนดเหล่านี้หน่วยงานเหล่านี้ เป็นโหนด sll เพื่อวัตถุประสงค์ ส่วนที่เหลือของวิดีโอนี้ 

สิทธิทั้งหมดเพื่อให้เรารู้วิธีการ สร้างโหนดรายการที่เชื่อมโยง เรารู้วิธีการที่จะกำหนด โหนดรายการที่เชื่อมโยง ตอนนี้ถ้าเรากำลังจะเริ่มต้น ใช้พวกเขาในการเก็บรวบรวมข้อมูล มีคู่ของการดำเนินงานที่เรา ต้องเข้าใจและทำงานร่วมกับ เราจำเป็นต้องทราบวิธีการสร้าง รายการที่เชื่อมโยงออกจากอากาศบาง หากมีรายการที่ไม่มีอยู่แล้ว เราต้องการที่จะเริ่มต้นหนึ่ง ดังนั้นเราจึงจำเป็นที่จะสามารถ เพื่อสร้างรายการที่เชื่อมโยง เราต้องอาจค้นหา ผ่านรายการการเชื่อมโยง เพื่อหาองค์ประกอบที่เรากำลังมองหา เราจะต้องสามารถที่จะแทรก สิ่งใหม่ ๆ เข้ามาในรายการ เราต้องการให้รายการของเราจะสามารถที่จะเติบโต และในทำนองเดียวกันเราต้องการที่จะสามารถ ลบสิ่งที่ออกจากรายการของเรา เราต้องการให้รายการของเราที่จะสามารถที่จะหดตัวลง และในตอนท้ายของเรา โปรแกรมโดยเฉพาะอย่างยิ่ง ถ้าคุณจำได้ว่าเรา แบบไดนามิกจัดสรรหน่วยความจำ การสร้างรายชื่อเหล่านี้โดยทั่วไปแล้ว เราต้องการที่จะเป็นอิสระทั้งหมดของหน่วยความจำที่ เมื่อเรากำลังทำทำงานกับมัน และเพื่อให้เราจะต้องมีความสามารถที่จะลบ รายการที่เชื่อมโยงทั้งในถลาล้มเหลว ดังนั้นขอให้ผ่านไป บางส่วนของการดำเนินการเหล่านี้ และวิธีที่เราอาจเห็นภาพพวกเขา การพูดคุยในรหัส pseudocode เฉพาะ ดังนั้นเราจึงต้องการที่จะสร้าง เชื่อมโยงรายการดังนั้นบางทีเรา ต้องการกำหนดฟังก์ชั่น กับต้นแบบนี้ ดาวโหนด sll สร้างและฉันผ่าน หนึ่งในข้อโต้แย้งบางข้อมูลโดยพลการ พิมพ์อีกครั้งบางชนิดข้อมูลโดยพลการ แต่ฉัน returning-- ฟังก์ชั่นนี้ควร กลับมาหาเราตัวชี้ไปโดยลำพัง โหนดที่เชื่อมโยงกับรายการ อีกครั้งที่เรากำลังพยายามที่จะสร้าง รายการที่เชื่อมโยงออกมาจากอากาศบาง ดังนั้นผมจึงต้องชี้ไปยัง ว่ารายการเมื่อฉันทำ 

ดังนั้นสิ่งที่เป็นขั้นตอนที่เกี่ยวข้องที่นี่? ดีสิ่งแรกที่ฉัน จะทำคือแบบไดนามิก จัดสรรพื้นที่สำหรับโหนดใหม่ อีกครั้งที่เรากำลังสร้างมันออกมาจากบาง อากาศดังนั้นเราต้องไปยังพื้นที่ malloc สำหรับมัน และแน่นอนทันที หลังจากที่เรา malloc, เรามักจะตรวจสอบเพื่อให้แน่ใจว่าเรา pointer-- เราไม่ได้รับกลับ null เพราะถ้าหากเราพยายาม เคารพตัวชี้โมฆะ เรากำลังจะประสบ segfault และเราไม่ต้องการที่ 

จากนั้นเราก็ต้องการที่จะเติมในสนาม เราต้องการที่จะเริ่มต้นสนามค่า และเริ่มต้นสนามต่อไป แล้วเราต้องการ to-- ในที่สุดก็เป็น ต้นแบบ indicates-- ฟังก์ชั่นที่เราต้องการ ที่จะกลับตัวชี้ไปยังโหนด sll ดังนั้นสิ่งที่ทำให้มีลักษณะเหมือนสายตา? ดีแรกที่เรากำลังจะแบบไดนามิก จัดสรรพื้นที่สำหรับโหนด sll ใหม่ ดังนั้นเราจึง malloc-- ที่ การแสดงออก ของโหนดที่เราเพิ่งสร้างขึ้น และเราตรวจสอบเพื่อให้แน่ใจว่า มันไม่ได้ null-- ในกรณีนี้ ภาพจะไม่ได้ แสดงให้เห็นถึงว่ามันเป็นโมฆะ เราจะได้วิ่งออกมาจากหน่วยความจำ ดังนั้นเราจึงกำลังดีจะไปที่นั่น ดังนั้นตอนนี้เรากำลังจะก้าวซี เริ่มต้นเขตข้อมูลค่าโหนด ดีขึ้นอยู่กับฟังก์ชั่นนี้ เรียกฉันใช้ที่นี่ ดูเหมือนว่าฉันต้องการที่จะผ่านใน 6 ดังนั้นฉันจะ 6 ในด้านค่า ตอนนี้เริ่มต้นสนามต่อไป ดีสิ่งที่ฉันจะทำที่นั่น มีอะไรต่อไปขวา นี้เป็นสิ่งเดียวในรายการ ดังนั้นสิ่งที่เป็นสิ่งที่ถัดไปในรายการ? 

มันไม่ควรชี้ไปที่อะไรที่เหมาะสม มีอะไรอย่างอื่นมีดังนั้นสิ่งที่เป็น แนวคิดที่เรารู้ว่าเป็น nothing-- ชี้เพื่ออะไร? มันควรจะเป็นบางทีเราต้องการ ที่จะนำชี้โมฆะนั้น และฉันจะเป็นตัวแทนโมฆะ ชี้เป็นเพียงแค่กล่องสีแดง เราไม่สามารถไปเพิ่มเติมใด ๆ ในขณะที่เราจะเห็นเล็ก ๆ น้อย ๆ ในภายหลัง เราจะมีเครือข่ายในที่สุด การเชื่อมต่อของลูกศร โหนดเหล่านี้เข้าด้วยกัน แต่เมื่อคุณตี กล่องสีแดงที่เป็นโมฆะ เราไม่สามารถไปเพิ่มเติมใด ๆ ที่เป็นจุดสิ้นสุดของรายการ 

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

ตอนนี้ขอบอกว่าเราอยู่แล้ว มีโซ่ขนาดใหญ่ และเราต้องการที่จะหาบางสิ่งบางอย่างที่อยู่ในนั้น และเราต้องการฟังก์ชั่นที่จะ ที่จะกลับมาจริงหรือเท็จขึ้นอยู่ ว่าค่าที่มีอยู่ในรายการที่ ต้นแบบฟังก์ชั่นหรือ ประกาศสำหรับฟังก์ชั่นที่ อาจมีลักษณะเช่น this-- บูลพบและ แล้วเราต้องการที่จะผ่านในสองข้อโต้แย้ง 

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

และแล้วสิ่งที่สอง เรากำลังผ่านอีกครั้ง เป็นพล some-- สิ่งที่ชนิดของข้อมูลเรา มองหาที่มีอยู่ภายใน หวังว่าหนึ่งโหนดในรายการ ดังนั้นสิ่งที่เป็นขั้นตอนหรือไม่ ดีสิ่งแรกที่เราทำคือ เราสร้างตัวชี้ขวาง ชี้ไปที่หัวของรายการ ดีทำไมเราทำที่เรามีอยู่แล้ว มีตัวชี้ที่หัวรายการ ทำไมเราไม่เพียงแค่ย้ายที่หนึ่งรอบ? ดีเหมือนฉันเพียงแค่กล่าวว่า มันเป็นสิ่งสำคัญมากสำหรับเรา ที่มักจะติดตาม องค์ประกอบแรกในรายการ และเพื่อให้มันเป็นจริงดี เพื่อสร้างซ้ำนั้น และใช้ที่จะย้ายไปรอบ ๆ เพื่อให้เราไม่เคย ย้ายออกไปโดยไม่ได้ตั้งใจหรือเราเสมอ มีตัวชี้ที่จุดที่เป็นบางส่วน ขวาบนองค์ประกอบแรกของรายการ ดังนั้นมันจะดีกว่าที่จะสร้าง หนึ่งที่สองที่เราใช้ในการเคลื่อนย้าย 

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

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

ตอนนี้ที่นี่ยังสังเกตเห็นฉันไม่ได้ ต้อง malloc พื้นที่ใด ๆ สำหรับ Trav ผมไม่ได้พูด Trav เท่ากับ malloc บางสิ่งบางอย่างโหนดที่มีอยู่แล้ว พื้นที่ในหน่วยความจำที่มีอยู่แล้ว ดังนั้นสิ่งที่ฉันทำจริงคือ การสร้างตัวชี้ไปยังอีก ฉันไม่ได้ mallocing เพิ่มเติม พื้นที่ก็มีตอนนี้สองตัวชี้ ชี้ไปที่สิ่งเดียวกัน 

เพื่อให้เป็น 2 สิ่งที่ฉันกำลังมองหา? ดีไม่มีดังนั้นแทนที่จะฉัน จะย้ายไปที่หน้าหนึ่ง ดังนั้นโดยทั่วไปผมจะบอกว่า Trav เท่ากับ Trav ต่อไป 3 สิ่งที่ฉันกำลังมองหาไม่มี ดังนั้นผมจึงยังคงที่จะไป ผ่านจนในที่สุด ได้รับถึง 6 ซึ่งเป็นสิ่งที่ฉันกำลังมองหา สำหรับขึ้นอยู่กับการเรียกใช้ฟังก์ชัน ฉันมีที่ด้านบน มีและเพื่อให้ฉันทำ 

ตอนนี้สิ่งที่ถ้าองค์ประกอบฉัน มองหาไม่ได้ในรายการ มันยังจะทำงานอย่างไร ดีสังเกตเห็นว่ารายการ ที่นี่เป็นที่ที่แตกต่างกันอย่างละเอียด และนี่คือสิ่งที่อื่น ที่สำคัญกับรายการที่เชื่อมโยง คุณไม่ได้ที่จะรักษา พวกเขาในลำดับใด ๆ โดยเฉพาะอย่างยิ่ง คุณสามารถถ้าคุณต้องการ แต่ ที่คุณอาจจะสังเกตเห็นแล้ว ที่เราไม่ได้ติดตามความเคลื่อนไหวของ สิ่งที่องค์ประกอบจำนวนเราอยู่ที่ 

และนั่นคือการเรียงลำดับของการค้าหนึ่งที่เรา มีกับรายการที่เชื่อมโยงโองการอาร์เรย์ มันเป็นที่เราไม่ได้มี เข้าถึงโดยสุ่มอีกต่อไป เราก็ไม่สามารถพูดว่าฉันต้องการ ไปที่องค์ประกอบ 0, หรือองค์ประกอบที่ 6 ของอาเรย์ของฉัน ซึ่งผมสามารถทำในอาร์เรย์ ฉันไม่สามารถพูดฉันต้องการที่จะไป องค์ประกอบ 0 หรือองค์ประกอบที่ 6 หรือองค์ประกอบที่ 25 ของรายการที่เชื่อมโยงของฉัน มีดัชนีที่เกี่ยวข้องกับพวกเขา และดังนั้นจึงไม่ได้เรื่องจริงๆ ถ้าเรารักษารายการของเราในการสั่งซื้อ ถ้าคุณต้องการคุณ สามารถอย่างแน่นอน แต่มี เหตุผลที่ว่าทำไมพวกเขาจะต้องไม่มี ถูกเก็บรักษาไว้ในลำดับใด ดังนั้นอีกครั้งลองและ พบว่า 6 ในรายการนี​​้ ดีที่เราเริ่มต้นที่ เริ่มต้นเราจะไม่พบ 6 และจากนั้นเราคงไม่ได้หา 6 จนในที่สุดเราได้ที่นี่ ดังนั้นตอนนี้จุด Trav โหนด มี 8 หกและไม่ได้อยู่ในที่นั่น 

ดังนั้นขั้นตอนต่อไปจะเป็น ที่จะไปชี้ต่อไป เพื่อบอกว่า Trav เท่ากับ Trav ต่อไป ดี Trav ถัดไปที่ระบุโดย กล่องสีแดงนั้นเป็นโมฆะ ดังนั้นจึงมีไม่มีที่จะ ไปและเพื่อที่จุดนี้ เราสามารถสรุปได้ว่าเราได้มาถึง ในตอนท้ายของรายการที่เชื่อมโยง และ 6 ไม่ได้อยู่ในที่นั่น และมันจะถูกส่งกลับ ที่ผิดพลาดในกรณีนี้ 

ตกลงวิธีการที่เราจะใส่ใหม่ โหนดเข้าไปในรายการที่เชื่อมโยงหรือไม่ ดังนั้นเราจึงได้รับสามารถที่จะสร้าง รายการที่เชื่อมโยงจากที่ไหนเลย แต่เราอาจต้องการ สร้างห่วงโซ่และไม่ได้ สร้างพวงของรายการที่แตกต่างกัน เราต้องการที่จะมีรายการหนึ่งที่ มีพวงของโหนดในนั้น ไม่พวงของรายการที่มีโหนดเดียว ดังนั้นเราจึงไม่สามารถให้ใช้สร้าง ฟังก์ชั่นที่กำหนดไว้ก่อนหน้านี้ที่เราตอนนี้เรา ต้องการแทรกลงใน รายชื่อที่มีอยู่แล้ว 

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

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

มีเหตุผลที่ฉัน ต้องการที่จะทำเช่นนี้และมัน อาจจะมีมูลค่าการที่สอง เพื่อหยุดวิดีโอที่นี่ และคิดเกี่ยวกับเหตุผลที่ผมต้องการ แทรกที่จุดเริ่มต้นของการเชื่อมโยง รายการ อีกครั้งที่ผมกล่าวถึงก่อนหน้านี้ ว่ามันไม่ได้จริงๆ สำคัญว่าถ้าเรารักษามันไว้ในที่ใด ๆ การสั่งซื้อดังนั้นบางทีที่เบาะแส และคุณเห็นสิ่งที่จะเกิดขึ้นถ้าเรา อยาก to-- หรือจากเพียงสอง ที่ผ่านมาเมื่อเราได้ไป ผ่านการค้นหาคุณ จะได้เห็นสิ่งที่อาจ เกิดขึ้นถ้าเรากำลังพยายาม เพื่อแทรกในตอนท้ายของรายการ เพราะเราไม่ได้มี ตัวชี้ไปยังจุดสิ้นสุดของรายการ 

ดังนั้นเหตุผลที่ฉันต้องการ แทรกที่จุดเริ่มต้น เพราะผมสามารถทำมันได้ทันที ฉันมีตัวชี้ที่จุดเริ่มต้นและ เราจะเห็นในภาพในครั้งที่สอง แต่ถ้าผมต้องการที่จะใส่ในตอนท้าย ฉันจะต้องเริ่มต้นที่จุดเริ่มต้น สำรวจทุกทางไป สิ้นสุดแล้วตรึงไว้บน เพื่อที่ว่าจะหมายถึงว่า ใส่ในตอนท้ายของรายการ จะกลายเป็นของ n o การดำเนินงานจะกลับ การสนทนาของเราของ ความซับซ้อนของคอมพิวเตอร์ มันจะกลายเป็น o n ของการดำเนินการที่ เป็นรายการมีขนาดใหญ่และขนาดใหญ่ และขนาดใหญ่ก็จะกลายเป็นมากขึ้นและ ยากมากที่จะตรึงบางสิ่งบางอย่าง ในตอนท้าย แต่มันเป็นเรื่องง่ายเสมอจริงๆ ตะปูบางสิ่งบางอย่างที่จุดเริ่มต้น คุณเสมอที่จุดเริ่มต้น 

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

ดังนั้นนี่คือรายการของเราก็ประกอบด้วย สี่องค์ประกอบโหนดที่มี 15 ซึ่งชี้ไปโหนด มี 9 ซึ่ง ชี้ไปยังโหนดที่มี 13 ซึ่งชี้ไปยังโหนดที่มี 10 ซึ่งมีโมฆะ ชี้เป็นตัวชี้ต่อไป เพื่อให้เป็นจุดสิ้นสุดของรายการ ดังนั้นเราจึงต้องการที่จะใส่ โหนดใหม่ที่มีมูลค่า 12 ที่จุดเริ่มต้นของเรื่องนี้ รายการสิ่งที่เราจะทำอย่างไร ดีแรกที่เรา malloc พื้นที่สำหรับ โหนดและจากนั้นเราใส่ 12 ในการมี 

ดังนั้นตอนนี้เราได้มาถึง จุดตัดสินใจใช่มั้ย? เรามีคู่ของ ชี้ว่าการที่เราจะทำได้ ย้ายที่หนึ่งที่เราควรจะย้ายครั้งแรก? เราควรจะให้ชี้ไปที่ 12 หัวใหม่ของ list-- หรือขอโทษนะที่เราควรจะทำ 12 ชี้ไปที่หัวเก่ารายการหรือไม่ หรือเราควรจะพูดว่า รายการตอนนี้เริ่มต้นที่ 12 มีความแตกต่างคือ มีและเราจะดู สิ่งที่เกิดขึ้นกับทั้งสอง 

แต่นี้จะนำไปสู่ หัวข้อที่ดีสำหรับแถบด้านข้าง ซึ่งเป็นที่หนึ่งของ สิ่งที่ยากกับรายการที่เชื่อมโยง ที่จะจัดให้มีการชี้ ในลำดับที่ถูกต้อง ถ้าคุณย้ายสิ่งที่ออกคำสั่ง คุณสามารถท้ายตั้งใจ orphaning ส่วนที่เหลือของรายการ และนี่คือตัวอย่างของการที่ ดังนั้นขอไปกับความคิดที่ of-- ดีที่เราได้สร้างเพียง 12 เรารู้ว่า 12 เป็นไปได้ หัวใหม่ของรายการ และทำไมเราไม่เพียงแค่เลื่อน รายการตัวชี้ไปยังจุดที่มี 

ตกลงดังนั้นที่ดี ดังนั้นตอนนี้ที่ไม่ 12 จุดต่อไปหรือไม่ ฉันหมายความว่าสายตาเราสามารถมองเห็น ว่ามันจะชี้ไปที่ 15 เป็นมนุษย์จริงๆที่เห็นได้ชัดกับเรา คอมพิวเตอร์ไม่ทราบได้อย่างไร? เราไม่ได้มีอะไร ชี้ไปที่ 15 อีกต่อไปใช่มั้ย? 

เราได้สูญเสียความสามารถใด ๆ ที่จะอ้างถึง 15 เราไม่สามารถพูดเท่ากับลูกศรใหม่ต่อไป บางสิ่งบางอย่างไม่มีอะไรที่มี ในความเป็นจริงที่เราได้กำพร้า ส่วนที่เหลือของรายการ โดยการทำเช่นเราได้ ตั้งใจทำลายห่วงโซ่ และแน่นอนเราไม่ต้องการที่จะทำเช่นนั้น 

ดังนั้นขอให้กลับไปและพยายามที่นี้อีกครั้ง บางทีสิ่งที่ถูกต้องที่จะทำ คือการกำหนดตัวชี้ต่อไป 12 ที่ศีรษะเก่าของรายการแรก แล้วเราสามารถย้ายรายการมากกว่า และในความเป็นจริงที่เป็น ลำดับที่ถูกต้องที่เรา ต้องปฏิบัติตามเมื่อเรา การทำงานร่วมกับรายการที่เชื่อมโยงโดยลำพัง เรามักจะต้องการการเชื่อมต่อ องค์ประกอบใหม่ในรายการ ก่อนที่เราจะใช้ชนิดที่ ขั้นตอนที่สำคัญของการเปลี่ยนแปลง ที่หัวของรายการที่เชื่อมโยงเป็น อีกครั้งที่นั้นเป็นสิ่งพื้นฐาน เราไม่ต้องการที่จะสูญเสียการติดตามของมัน 

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

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

ถ้าเราได้มาถึงตัวชี้โมฆะเรา ต้องการที่จะหยุดมิฉะนั้นเพียงแค่ลบ ส่วนที่เหลือของรายการและจากนั้นฉันเป็นอิสระ ลบส่วนที่เหลือของรายการ แล้วฟรีโหนดปัจจุบัน ไม่ว่าสิ่งที่เสียงเหมือน สิ่งที่มีเทคนิคที่เราได้พูดคุย ก่อนหน้านี้ไม่เกี่ยวกับเสียงเช่นนั้น? ลบคนอื่นแล้ว กลับมาและลบฉัน 

นั่นคือการเรียกซ้ำที่เราได้ทำ ปัญหานิด ๆ หน่อย ๆ ที่มีขนาดเล็ก เรากำลังจะบอกว่าทุกคนลบ อื่นแล้วคุณสามารถลบฉัน และต่อไปลงที่ถนนโหนดที่ จะบอกว่าลบคนอื่น แต่ในที่สุดเราจะได้รับการ จุดที่รายการเป็นโมฆะ และเป็นกรณีฐานของเรา 

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

ดังนั้นเราจึง have-- และฉันยังดึง ขึ้นเฟรมสแต็คของเราภาพประกอบ จากวิดีโอของเราในกองโทร และหวังว่าทั้งหมดนี้ ร่วมกันจะแสดงให้คุณเห็นสิ่งที่เกิดขึ้น ดังนั้นนี่คือรหัส pseudocode ของเรา ถ้าเราไปถึงโมฆะ ตัวชี้หยุดมิฉะนั้น ลบส่วนที่เหลือของรายการ แล้วฟรีโหนดปัจจุบัน ดังนั้นตอนนี้ list-- ตัวชี้ว่าเรา ผ่านในจุดที่จะทำลายถึง 12 12 ไม่ได้เป็นตัวชี้โมฆะดังนั้นเรา จะลบส่วนที่เหลือของรายการ 

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

ดี 15 ไม่ได้เป็นตัวชี้โมฆะและ จึงจะพูดขวาทั้งหมด ดีลบส่วนที่เหลือของรายการ ส่วนที่เหลือของรายการเริ่มต้น ที่ 9, และอื่น ๆ เราจะเป็นเพียง รอจนกว่าคุณจะลบทั้งหมดที่ สิ่งนั้นกลับมาและลบฉัน ดี 9 จะบอกว่าดี ฉันไม่ได้เป็นตัวชี้โมฆะ เพื่อลบส่วนที่เหลือรายการจากที่นี่ และเพื่อพยายามทำลาย 13 13 บอกว่าผมไม่ได้เป็นตัวชี้โมฆะ สิ่งเดียวกันมันผ่านเจ้าชู้ 10 ไม่ได้เป็นตัวชี้โมฆะ 10 มีตัวชี้โมฆะ แต่ 10 ไม่ได้เป็นตัวเอง ตัวชี้ null ตอนนี้ และเพื่อให้มันผ่านเจ้าชู้มากเกินไป 

และตอนนี้จุดที่รายการมีก็ จริงๆจะชี้ไปที่ some-- ถ้าผมมีพื้นที่มากขึ้นในภาพ มันจะชี้ไปที่บางพื้นที่สุ่ม ที่เราไม่ทราบว่ามันคืออะไร มันเป็นตัวชี้โมฆะ แต่รายการ เป็นอักษรชุดนี้มันเป็นค่าโมฆะ มันชี้ว่าภายในกล่องสีแดง เรามาถึงตัวชี้โมฆะดังนั้น เราสามารถหยุดและเรากำลังทำ 

และเพื่อให้กรอบสีม่วง now-- ที่ ด้านบนของ stack-- ที่เฟรมที่ใช้งานอยู่ แต่มันทำ ถ้าเราได้มาถึงตัวชี้โมฆะหยุด เราไม่ได้ทำอะไรเรา ไม่สามารถปลดปล่อยตัวชี้โมฆะ เราไม่ได้ malloc ใด ๆ พื้นที่และเพื่อให้เราดำเนินการเสร็จแล้ว ดังนั้นกรอบการทำงานที่ ถูกทำลายและเรา resume-- เราเลือกที่เราทิ้ง ด้วยหน้าหนึ่งที่สูงที่สุดซึ่ง นี่คือกรอบสีน้ำเงินเข้มที่นี่ ดังนั้นเราจึงรับสิทธิที่เราออกมา เราลบส่วนที่เหลือของ รายการอยู่แล้วดังนั้นตอนนี้เรากำลัง จะเป็นอิสระโหนดปัจจุบัน ดังนั้นตอนนี้เราสามารถฟรีโหนดนี้และตอนนี้ เราได้มาถึงจุดสิ้นสุดของการทำงาน และเพื่อให้กรอบการทำงานที่ถูกทำลาย และเรารับที่แสงสีฟ้าหนึ่ง 

ดังนั้นฉัน says-- ได้แล้ว done-- ลบส่วนที่เหลือของรายการดังนั้น ฟรีโหนดปัจจุบัน และตอนนี้กรอบสีเหลือง กลับไปที่ด้านบนของสแต็ค และอื่น ๆ ตามที่คุณเห็นเราในขณะนี้ ทำลายรายการจากขวาไปซ้าย 

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

ดังนั้นที่ผมกล่าวว่ามี มีการดำเนินงานหลาย ที่เราจำเป็นต้องใช้ในการทำงาน ที่มีการเชื่อมโยงอย่างมีประสิทธิภาพรายการ และคุณอาจจะสังเกตเห็นผมมองข้ามอย่างใดอย่างหนึ่ง การลบองค์ประกอบหนึ่งจากการเชื่อมโยง รายการ เหตุผลที่ฉันไม่ว่า คือมันจริงชนิดของ เรื่องยุ่งยากที่จะคิดเกี่ยวกับวิธีที่จะลบ องค์ประกอบหนึ่งจากลำพัง รายการที่เชื่อมโยง เราจะต้องสามารถที่จะข้าม บางสิ่งบางอย่างในรายการที่ หมายถึงการที่เราจะไปเรา point-- ต้องการลบ node-- นี้ แต่เพื่อที่จะทำให้มันดังนั้นเรา จะไม่สูญเสียข้อมูลใด ๆ เราจำเป็นต้องเชื่อมต่อนี้ โหนดมากกว่าที่นี่ที่นี่ 

ดังนั้นผมอาจจะทำอย่างนั้นไม่ถูกต้อง จากมุมมองของภาพ ดังนั้นเราจึงอยู่ที่จุดเริ่มต้นของเรา รายการที่เรากำลังดำเนินการผ่าน เราต้องการที่จะลบโหนดนี้ ถ้าเราเพียงแค่ลบมัน เราได้ทำลายห่วงโซ่ โหนดนี้ที่นี่ หมายถึงทุกอย่างอื่น มันมีห่วงโซ่จากที่นี่ที่ออก 

ดังนั้นสิ่งที่เราต้องทำจริง หลังจากที่เราได้รับที่จะมาถึงจุดนี้ คือเราต้องย้อนกลับไปหนึ่งและ เชื่อมต่อโหนดนี้ผ่านไปยังโหนดนี้ เพื่อให้เราสามารถลบแล้ว หนึ่งที่อยู่ตรงกลาง แต่รายการที่เชื่อมโยงโดยลำพังไม่ได้ ให้เราวิธีที่จะไปข้างหลัง ดังนั้นเราจึงจำเป็นที่จะต้องให้อย่างใดอย่างหนึ่ง สองตัวชี้และย้ายไป การเรียงลำดับของขั้นตอนออกหนึ่งที่อยู่เบื้องหลัง อื่น ๆ ที่เราไปหรือได้รับไปยังจุด แล้วส่งผ่านตัวชี้อีก และในขณะที่คุณสามารถเห็นมัน จะได้รับยุ่งเล็ก ๆ น้อย ๆ โชคดีที่เรามี อีกวิธีหนึ่งที่จะแก้ปัญหานั้น เมื่อเราพูดคุยเกี่ยวกับรายการที่เชื่อมโยงเป็นทวีคูณ 

ฉันลอยด์ดั๊กนี้เป็น CS50