[เล่นเพลง] DOUG LLOYD: สิทธิทั้งหมด ดังนั้นถ้าคุณเพิ่งเสร็จสิ้นการว่า วิดีโอในรายการเดี่ยวที่เชื่อมโยงขอโทษ ผมออกจากคุณออกบน บิตของน่าตื่นเต้น แต่ฉันดีใจที่คุณอยู่ที่นี่ที่จะเสร็จสิ้น เรื่องราวของรายการที่เชื่อมโยงเป็นทวีคูณ 

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

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

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

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

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

ดังนั้นขอแทรกโหนดใหม่ เป็นรายการที่เชื่อมโยงเป็นทวีคูณ เราได้พูดคุยเกี่ยวกับการทำเช่นนี้ รายการเดี่ยวที่เชื่อมโยงเป็นอย่างดี แต่มีคู่ของพิเศษ จับกับรายการที่เชื่อมโยงเป็นทวีคูณ เรา [? ผ่าน?] ในหัวของ รายการที่นี่และบางค่าโดยพลการ และเราต้องการที่จะได้รับหัวใหม่ ของรายการจากฟังก์ชั่นนี้ นั่นเป็นเหตุผลที่มันส่งกลับ dllnode ดาว ดังนั้นสิ่งที่เป็นขั้นตอนหรือไม่ พวกเขาเป็นอีกครั้งที่คล้ายกันมาก รายการเดี่ยวที่เชื่อมโยง ด้วยการเพิ่มเสริม เราต้องการที่จะจัดสรรพื้นที่สำหรับใหม่ โหนดและตรวจสอบเพื่อให้แน่ใจว่ามันถูกต้อง เราต้องการที่จะเติมโหนดขึ้น มีข้อมูลอะไรก็ตามที่เรา ต้องการที่จะใส่ในนั้น สิ่งสุดท้ายที่เราต้อง do-- สิ่งที่พิเศษที่เราต้องทำ, rather-- คือการแก้ไขตัวชี้ก่อนหน้า ของหัวเก่าของรายการ โปรดจำไว้ว่าเพราะ รายชื่อของทวีคูณเชื่อมโยง เราสามารถก้าวไปข้างหน้า และ backwards-- ที่ หมายความว่าแต่ละโหนดชี้จริง สองโหนดอื่น ๆ แทนเพียงอย่างใดอย่างหนึ่ง และเพื่อให้เราต้องแก้ไข หัวหน้าเก่าของรายการ ที่จะชี้ให้ย้อนกลับไปที่หัวใหม่ของ รายการที่เชื่อมโยงซึ่งเป็นบางสิ่งบางอย่าง เราไม่ได้มีที่ต้องทำก่อน และในขณะที่ก่อนหน้านี้เราก็กลับมาเป็น ตัวชี้ไปยังหัวใหม่ของรายการ 

ดังนั้นนี่คือรายการ เราต้องการที่จะใส่ลงไปใน 12 รายชื่อนี้ได้ ขอให้สังเกตว่าแผนภาพ แตกต่างกันเล็กน้อย แต่ละโหนดมีสาม fields-- ข้อมูลและตัวชี้ต่อไปในสีแดง และตัวชี้ก่อนหน้าสีฟ้า ไม่มีอะไรมาก่อนโหนด 15 ดังนั้นตัวชี้ก่อนหน้ามันเป็นโมฆะ มันเป็นจุดเริ่มต้นของรายการ ไม่มีอะไรก่อนที่จะ และไม่มีอะไรมาหลังจากโหนด 10 และ ดังนั้นจึงเป็นตัวชี้ต่อไปเป็นโมฆะเช่นกัน 

ดังนั้นขอเพิ่ม 12 ในรายการนี​​้ เราจำเป็นต้อง [ไม่ได้ยิน] พื้นที่สำหรับโหนด เราใส่ 12 ภายในของมัน และหลังจากนั้นอีกเราต้องเป็นจริง ระมัดระวังไม่ให้ทำลายห่วงโซ่ เราต้องการที่จะจัดเรียง คำแนะนำในลำดับที่ถูกต้อง และบางครั้งที่อาจ mean-- ในขณะที่เราจะเห็นโดยเฉพาะอย่างยิ่ง delete-- กับที่เราทำมีบาง ตัวชี้ซ้ำซ้อน แต่ที่ตกลง 

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

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

ตอนนี้ขอลบในที่สุด โหนดจากรายการที่เชื่อมโยง ดังนั้นสมมติว่าเรามี บางฟังก์ชั่นอื่น ๆ ที่ คือการหาโหนดเราต้องการที่จะลบ และได้ให้เราชี้ไปว่า โหนดที่เราต้องการลบ เราไม่ได้พูด need-- หัวยังคงประกาศทั่วโลก เราไม่จำเป็นต้องหัวที่นี่ ทุกฟังก์ชั่นนี้จะทำก็คือเราได้ พบว่าตัวชี้ไปตรงที่เราโหนด ต้องการที่จะกำจัด ขอกำจัดมัน มันง่ายมากที่มี รายการที่เชื่อมโยงเป็นทวีคูณ First-- ก็จริง เพียงสองสิ่ง เราก็ต้องแก้ไขโดยรอบ ตัวชี้โหนด 'เพื่อให้พวกเขาข้าม โหนดที่เราต้องการลบ แล้วเราสามารถลบโหนดที่ ดังนั้นอีกครั้งเราก็จะผ่านที่นี่ เราได้ตัดสินใจที่เห็นได้ชัดว่า เราต้องการที่จะลบโหนดเอ็กซ์ และอีกครั้งสิ่งที่ฉัน ทำ here-- โดย way-- เป็นกรณีทั่วไปสำหรับ โหนดที่อยู่ตรงกลาง มีคู่ของมี caveats พิเศษที่คุณ ต้องพิจารณาเมื่อคุณลบ จุดเริ่มต้นของรายการ หรือส่วนท้ายสุดของรายการ มีคู่ของพิเศษเป็น กรณีมุมที่จะจัดการกับมี 

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

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

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

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

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

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

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

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

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

ฉันลอยด์ดั๊ก นี่คือ CS50