1
00:00:00,000 --> 00:00:03,381
>> [เล่นเพลง]

2
00:00:03,381 --> 00:00:04,604

3
00:00:04,604 --> 00:00:05,520
DOUG LLOYD: สิทธิทั้งหมด

4
00:00:05,520 --> 00:00:07,860
ดังนั้นถ้าคุณเพิ่งเสร็จสิ้นการว่า
วิดีโอในรายการเดี่ยวที่เชื่อมโยงขอโทษ

5
00:00:07,860 --> 00:00:09,568
ผมออกจากคุณออกบน
บิตของน่าตื่นเต้น

6
00:00:09,568 --> 00:00:12,790
แต่ฉันดีใจที่คุณอยู่ที่นี่ที่จะเสร็จสิ้น
เรื่องราวของรายการที่เชื่อมโยงเป็นทวีคูณ

7
00:00:12,790 --> 00:00:15,250
>> ดังนั้นถ้าคุณจำได้จาก
วิดีโอที่เราได้พูดคุย

8
00:00:15,250 --> 00:00:18,500
เกี่ยวกับวิธีการหลายอย่างที่เชื่อมโยง
เข้าร่วมทำรายการความสามารถของเรา

9
00:00:18,500 --> 00:00:22,090
ในการจัดการกับข้อมูล
ซึ่งมีจำนวนขององค์ประกอบ

10
00:00:22,090 --> 00:00:24,442
หรือจำนวนของรายการใน
รายการที่สามารถเจริญเติบโตหรือหด

11
00:00:24,442 --> 00:00:26,400
ตอนนี้เราสามารถจัดการกับ
สิ่งที่ต้องการที่

12
00:00:26,400 --> 00:00:28,310
เราไม่สามารถจัดการกับมันด้วยอาร์เรย์

13
00:00:28,310 --> 00:00:30,560
>> แต่พวกเขาต้องทนทุกข์ทรมานจากที่หนึ่ง
ข้อ จำกัด ที่สำคัญซึ่ง

14
00:00:30,560 --> 00:00:33,790
คือว่ามีหลายอย่างที่เชื่อมโยง
รายการเราสามารถเท่านั้นที่เคยย้าย

15
00:00:33,790 --> 00:00:36,200
ในทิศทางเดียวผ่านรายการ

16
00:00:36,200 --> 00:00:39,010
และมีเพียงสถานการณ์จริง
ที่ที่สามารถกลายเป็นปัญหา

17
00:00:39,010 --> 00:00:41,250
ก็คือตอนที่เรากำลังพยายามที่จะ
ลบองค์ประกอบหนึ่ง

18
00:00:41,250 --> 00:00:46,000
และเราไม่ได้หารือถึงวิธีการที่จะทำมัน
ในรายการเดี่ยวที่เชื่อมโยงใน pseudocode

19
00:00:46,000 --> 00:00:48,797
มันเป็นไปได้อย่างแน่นอน แต่
ก็สามารถเป็นบิตของการทะเลาะ

20
00:00:48,797 --> 00:00:50,630
ดังนั้นถ้าคุณพบว่าตัวเอง
ในสถานการณ์ที่

21
00:00:50,630 --> 00:00:53,175
คุณกำลังพยายามที่จะลบ
องค์ประกอบเดียวจากรายการ

22
00:00:53,175 --> 00:00:55,430
หรือว่ามันจะต้อง
ที่คุณจะลบ

23
00:00:55,430 --> 00:00:57,970
องค์ประกอบเดียวจาก
รายการคุณอาจต้องการ

24
00:00:57,970 --> 00:01:02,090
พิจารณาใช้เป็นทวีคูณเชื่อมโยง
รายการแทนโดยลำพังรายการที่เชื่อมโยง

25
00:01:02,090 --> 00:01:06,320
เพราะรายการที่เชื่อมโยงเป็นทวีคูณช่วยให้คุณ
ที่จะย้ายไปข้างหน้าทั้งในและข้างหลัง

26
00:01:06,320 --> 00:01:09,340
ผ่านรายการแทน
เพียงแค่ไปข้างหน้าผ่าน list--

27
00:01:09,340 --> 00:01:13,950
เพียงแค่เพิ่มองค์ประกอบเสริม
นิยามโครงสร้างของเรา

28
00:01:13,950 --> 00:01:16,690
สำหรับโหนดทวีคูณรายการที่เชื่อมโยง

29
00:01:16,690 --> 00:01:19,770
>> อีกครั้งถ้าคุณไม่ได้ไป
จะลบองค์ประกอบเดียว

30
00:01:19,770 --> 00:01:24,810
จาก list-- เพราะเรากำลังเพิ่ม
สนามพิเศษกับโครงสร้างของเรา

31
00:01:24,810 --> 00:01:28,340
นิยามโหนดตัวเอง
สำหรับรายการที่เชื่อมโยงเป็นทวีคูณ

32
00:01:28,340 --> 00:01:29,550
จะมีขนาดใหญ่

33
00:01:29,550 --> 00:01:31,600
พวกเขากำลังจะใช้
ขึ้นไบต์หน่วยความจำ

34
00:01:31,600 --> 00:01:34,160
และดังนั้นหากนี่ไม่ใช่สิ่งที่
คุณกำลังจะต้องทำ

35
00:01:34,160 --> 00:01:36,300
คุณอาจตัดสินใจมัน
ไม่คุ้มค่าการค้าปิด

36
00:01:36,300 --> 00:01:39,360
ที่จะมีการใช้จ่ายที่เพิ่มขึ้น
ไบต์ของหน่วยความจำที่จำเป็น

37
00:01:39,360 --> 00:01:43,940
สำหรับรายการที่เชื่อมโยงเป็นทวีคูณถ้าคุณไม่ได้
จะถูกลบองค์ประกอบเดียว

38
00:01:43,940 --> 00:01:46,760
แต่พวกเขายังเย็น
สำหรับสิ่งอื่น ๆ มากเกินไป

39
00:01:46,760 --> 00:01:51,260
>> ดังนั้นที่ผมกล่าวว่าเราก็ต้องเพิ่ม
หนึ่งในเขตข้อมูลเดียวกับโครงสร้างของเรา

40
00:01:51,260 --> 00:01:55,360
definition-- ความคิดนี้
ของตัวชี้ก่อนหน้า

41
00:01:55,360 --> 00:01:58,620
ดังนั้นกับรายการเดี่ยวที่เชื่อมโยงเรา
มีค่าและตัวชี้ถัดไป

42
00:01:58,620 --> 00:02:02,850
เพื่อให้รายการที่เชื่อมโยงเป็นทวีคูณก็มี
วิธีที่จะย้ายไปข้างหลังได้เป็นอย่างดี

43
00:02:02,850 --> 00:02:04,960
>> ตอนนี้ในการเชื่อมโยงโดยลำพัง
รายการวิดีโอที่เราได้พูดคุย

44
00:02:04,960 --> 00:02:07,210
เกี่ยวกับเหล่านี้ห้าของ
สิ่งสำคัญที่คุณจะต้อง

45
00:02:07,210 --> 00:02:09,449
สามารถที่จะทำในการทำงานกับรายการที่เชื่อมโยง

46
00:02:09,449 --> 00:02:12,880
และสำหรับส่วนมากของเหล่านี้ความจริงที่
ว่ามันเป็นรายการที่เชื่อมโยงเป็นทวีคูณ

47
00:02:12,880 --> 00:02:14,130
ไม่ได้จริงๆกระโดดใหญ่

48
00:02:14,130 --> 00:02:17,936
เรายังสามารถค้นหาผ่านโดยเพียงแค่
ก้าวไปข้างหน้าตั้งแต่ต้นจนจบ

49
00:02:17,936 --> 00:02:20,810
เรายังสามารถสร้างโหนดออกจาก
อากาศบางสวยมากเช่นเดียวกับ

50
00:02:20,810 --> 00:02:23,591
เราสามารถลบรายการสวย
ทางเดียวกันมากเกินไป

51
00:02:23,591 --> 00:02:25,340
สิ่งเดียวที่
จะแตกต่างกันอย่างละเอียด

52
00:02:25,340 --> 00:02:28,970
จริงๆจะใส่
โหนดใหม่เข้ามาในรายการ

53
00:02:28,970 --> 00:02:33,722
และในที่สุดเราก็จะพูดคุยเกี่ยวกับการลบ
องค์ประกอบหนึ่งจากรายการเช่นกัน

54
00:02:33,722 --> 00:02:35,430
อีกครั้งสวยมาก
อีกสามเรา

55
00:02:35,430 --> 00:02:37,888
จะไม่พูดคุยเกี่ยวกับพวกเขา
เพราะตอนนี้พวกเขากำลังเพียง

56
00:02:37,888 --> 00:02:43,920
ปรับแต่งน้อยมากในความคิดที่กล่าวถึง
ในวิดีโอรายการเดี่ยวที่เชื่อมโยง

57
00:02:43,920 --> 00:02:46,292
>> ดังนั้นขอแทรกโหนดใหม่
เป็นรายการที่เชื่อมโยงเป็นทวีคูณ

58
00:02:46,292 --> 00:02:48,750
เราได้พูดคุยเกี่ยวกับการทำเช่นนี้
รายการเดี่ยวที่เชื่อมโยงเป็นอย่างดี

59
00:02:48,750 --> 00:02:52,020
แต่มีคู่ของพิเศษ
จับกับรายการที่เชื่อมโยงเป็นทวีคูณ

60
00:02:52,020 --> 00:02:55,280
เรา [? ผ่าน?] ในหัวของ
รายการที่นี่และบางค่าโดยพลการ

61
00:02:55,280 --> 00:02:58,600
และเราต้องการที่จะได้รับหัวใหม่
ของรายการจากฟังก์ชั่นนี้

62
00:02:58,600 --> 00:03:01,414
นั่นเป็นเหตุผลที่มันส่งกลับ dllnode ดาว

63
00:03:01,414 --> 00:03:02,330
ดังนั้นสิ่งที่เป็นขั้นตอนหรือไม่

64
00:03:02,330 --> 00:03:04,496
พวกเขาเป็นอีกครั้งที่คล้ายกันมาก
รายการเดี่ยวที่เชื่อมโยง

65
00:03:04,496 --> 00:03:05,670
ด้วยการเพิ่มเสริม

66
00:03:05,670 --> 00:03:08,900
เราต้องการที่จะจัดสรรพื้นที่สำหรับใหม่
โหนดและตรวจสอบเพื่อให้แน่ใจว่ามันถูกต้อง

67
00:03:08,900 --> 00:03:11,510
เราต้องการที่จะเติมโหนดขึ้น
มีข้อมูลอะไรก็ตามที่เรา

68
00:03:11,510 --> 00:03:12,564
ต้องการที่จะใส่ในนั้น

69
00:03:12,564 --> 00:03:15,480
สิ่งสุดท้ายที่เราต้อง do--
สิ่งที่พิเศษที่เราต้องทำ, rather--

70
00:03:15,480 --> 00:03:19,435
คือการแก้ไขตัวชี้ก่อนหน้า
ของหัวเก่าของรายการ

71
00:03:19,435 --> 00:03:21,310
โปรดจำไว้ว่าเพราะ
รายชื่อของทวีคูณเชื่อมโยง

72
00:03:21,310 --> 00:03:23,110
เราสามารถก้าวไปข้างหน้า
และ backwards-- ที่

73
00:03:23,110 --> 00:03:27,080
หมายความว่าแต่ละโหนดชี้จริง
สองโหนดอื่น ๆ แทนเพียงอย่างใดอย่างหนึ่ง

74
00:03:27,080 --> 00:03:29,110
และเพื่อให้เราต้องแก้ไข
หัวหน้าเก่าของรายการ

75
00:03:29,110 --> 00:03:32,151
ที่จะชี้ให้ย้อนกลับไปที่หัวใหม่ของ
รายการที่เชื่อมโยงซึ่งเป็นบางสิ่งบางอย่าง

76
00:03:32,151 --> 00:03:33,990
เราไม่ได้มีที่ต้องทำก่อน

77
00:03:33,990 --> 00:03:37,420
และในขณะที่ก่อนหน้านี้เราก็กลับมาเป็น
ตัวชี้ไปยังหัวใหม่ของรายการ

78
00:03:37,420 --> 00:03:38,220
>> ดังนั้นนี่คือรายการ

79
00:03:38,220 --> 00:03:40,144
เราต้องการที่จะใส่ลงไปใน 12 รายชื่อนี้ได้

80
00:03:40,144 --> 00:03:42,060
ขอให้สังเกตว่าแผนภาพ
แตกต่างกันเล็กน้อย

81
00:03:42,060 --> 00:03:47,710
แต่ละโหนดมีสาม fields--
ข้อมูลและตัวชี้ต่อไปในสีแดง

82
00:03:47,710 --> 00:03:50,170
และตัวชี้ก่อนหน้าสีฟ้า

83
00:03:50,170 --> 00:03:54,059
ไม่มีอะไรมาก่อนโหนด 15
ดังนั้นตัวชี้ก่อนหน้ามันเป็นโมฆะ

84
00:03:54,059 --> 00:03:55,350
มันเป็นจุดเริ่มต้นของรายการ

85
00:03:55,350 --> 00:03:56,560
ไม่มีอะไรก่อนที่จะ

86
00:03:56,560 --> 00:04:03,350
และไม่มีอะไรมาหลังจากโหนด 10 และ
ดังนั้นจึงเป็นตัวชี้ต่อไปเป็นโมฆะเช่นกัน

87
00:04:03,350 --> 00:04:05,616
>> ดังนั้นขอเพิ่ม 12 ในรายการนี​​้

88
00:04:05,616 --> 00:04:08,070
เราจำเป็นต้อง [ไม่ได้ยิน] พื้นที่สำหรับโหนด

89
00:04:08,070 --> 00:04:11,480
เราใส่ 12 ภายในของมัน

90
00:04:11,480 --> 00:04:14,840
และหลังจากนั้นอีกเราต้องเป็นจริง
ระมัดระวังไม่ให้ทำลายห่วงโซ่

91
00:04:14,840 --> 00:04:17,144
เราต้องการที่จะจัดเรียง
คำแนะนำในลำดับที่ถูกต้อง

92
00:04:17,144 --> 00:04:19,519
และบางครั้งที่อาจ mean--
ในขณะที่เราจะเห็นโดยเฉพาะอย่างยิ่ง

93
00:04:19,519 --> 00:04:24,120
delete-- กับที่เราทำมีบาง
ตัวชี้ซ้ำซ้อน แต่ที่ตกลง

94
00:04:24,120 --> 00:04:25,750
>> ดังนั้นสิ่งที่เราต้องการจะทำครั้งแรก?

95
00:04:25,750 --> 00:04:28,290
ฉันอยากจะแนะนำ
สิ่งที่คุณควรอาจจะ

96
00:04:28,290 --> 00:04:35,350
ทำเพื่อเติมเต็มคำแนะนำของ 12
โหนดก่อนที่คุณจะสัมผัสคนอื่น

97
00:04:35,350 --> 00:04:38,640
ดังนั้นสิ่งที่ 12 จะชี้ไปที่ต่อไปหรือไม่

98
00:04:38,640 --> 00:04:39,860
15

99
00:04:39,860 --> 00:04:42,430
สิ่งที่มาก่อน 12?

100
00:04:42,430 --> 00:04:43,640
ไม่มีอะไร

101
00:04:43,640 --> 00:04:46,280
ตอนนี้เราได้เต็มไปด้วย
ข้อมูลเพิ่มเติมใน 12

102
00:04:46,280 --> 00:04:49,320
ดังนั้นจึงมีก่อนหน้าถัดไปและความคุ้มค่า

103
00:04:49,320 --> 00:04:53,505
>> ตอนนี้เราสามารถมี 15-- พิเศษนี้
ขั้นตอนที่เราได้พูดคุย about-- เรา

104
00:04:53,505 --> 00:04:56,590
สามารถมี 15 จุดกลับไปที่ 12

105
00:04:56,590 --> 00:04:59,634
และตอนนี้เราสามารถย้ายหัวของ
รายการที่เชื่อมโยงกับยัง 12

106
00:04:59,634 --> 00:05:02,550
ดังนั้นจึงเป็นที่สวยคล้ายกับสิ่งที่เรา
กำลังทำกับรายการเดี่ยวเชื่อมโยง

107
00:05:02,550 --> 00:05:06,940
ยกเว้นขั้นตอนพิเศษของ
การเชื่อมต่อหัวเก่าของรายการ

108
00:05:06,940 --> 00:05:09,810
กลับไปที่หัวใหม่ของรายการ

109
00:05:09,810 --> 00:05:12,170
>> ตอนนี้ขอลบในที่สุด
โหนดจากรายการที่เชื่อมโยง

110
00:05:12,170 --> 00:05:14,350
ดังนั้นสมมติว่าเรามี
บางฟังก์ชั่นอื่น ๆ ที่

111
00:05:14,350 --> 00:05:18,080
คือการหาโหนดเราต้องการที่จะลบ
และได้ให้เราชี้ไปว่า

112
00:05:18,080 --> 00:05:19,710
โหนดที่เราต้องการลบ

113
00:05:19,710 --> 00:05:22,360
เราไม่ได้พูด need--
หัวยังคงประกาศทั่วโลก

114
00:05:22,360 --> 00:05:23,590
เราไม่จำเป็นต้องหัวที่นี่

115
00:05:23,590 --> 00:05:26,830
ทุกฟังก์ชั่นนี้จะทำก็คือเราได้
พบว่าตัวชี้ไปตรงที่เราโหนด

116
00:05:26,830 --> 00:05:28,090
ต้องการที่จะกำจัด

117
00:05:28,090 --> 00:05:28,940
ขอกำจัดมัน

118
00:05:28,940 --> 00:05:31,859
มันง่ายมากที่มี
รายการที่เชื่อมโยงเป็นทวีคูณ

119
00:05:31,859 --> 00:05:33,650
First-- ก็จริง
เพียงสองสิ่ง

120
00:05:33,650 --> 00:05:38,760
เราก็ต้องแก้ไขโดยรอบ
ตัวชี้โหนด 'เพื่อให้พวกเขาข้าม

121
00:05:38,760 --> 00:05:40,240
โหนดที่เราต้องการลบ

122
00:05:40,240 --> 00:05:43,484
แล้วเราสามารถลบโหนดที่

123
00:05:43,484 --> 00:05:45,150
ดังนั้นอีกครั้งเราก็จะผ่านที่นี่

124
00:05:45,150 --> 00:05:49,625
เราได้ตัดสินใจที่เห็นได้ชัดว่า
เราต้องการที่จะลบโหนดเอ็กซ์

125
00:05:49,625 --> 00:05:51,500
และอีกครั้งสิ่งที่ฉัน
ทำ here-- โดย way--

126
00:05:51,500 --> 00:05:54,580
เป็นกรณีทั่วไปสำหรับ
โหนดที่อยู่ตรงกลาง

127
00:05:54,580 --> 00:05:56,547
มีคู่ของมี
caveats พิเศษที่คุณ

128
00:05:56,547 --> 00:05:59,380
ต้องพิจารณาเมื่อคุณลบ
จุดเริ่มต้นของรายการ

129
00:05:59,380 --> 00:06:01,040
หรือส่วนท้ายสุดของรายการ

130
00:06:01,040 --> 00:06:03,730
มีคู่ของพิเศษเป็น
กรณีมุมที่จะจัดการกับมี

131
00:06:03,730 --> 00:06:07,960
>> ดังนั้นงานนี้สำหรับการลบโหนดใด ๆ
ในช่วงกลางของหนึ่ง list-- ที่

132
00:06:07,960 --> 00:06:11,550
มีตัวชี้ไปข้างหน้าถูกต้องตามกฎหมาย
และตัวชี้ถูกต้องตามกฎหมายย้อนหลัง

133
00:06:11,550 --> 00:06:14,460
ถูกต้องตามกฎหมายชี้ก่อนหน้าและถัดไป

134
00:06:14,460 --> 00:06:16,530
อีกครั้งถ้าคุณกำลังทำงาน
มีปลายคุณ

135
00:06:16,530 --> 00:06:18,500
ต้องจัดการผู้
แตกต่างกันเล็กน้อย

136
00:06:18,500 --> 00:06:19,570
และเราไม่ได้ไป
พูดคุยเกี่ยวกับว่าตอนนี้

137
00:06:19,570 --> 00:06:21,319
แต่คุณอาจจะสามารถ
คิดออกสิ่งที่จำเป็น

138
00:06:21,319 --> 00:06:24,610
ที่จะทำเพียงแค่ดูวิดีโอนี้

139
00:06:24,610 --> 00:06:28,910
>> ดังนั้นเราจึงได้แยก X. X คือโหนด
เราต้องการที่จะลบออกจากรายการ

140
00:06:28,910 --> 00:06:30,140
พวกเราทำอะไร?

141
00:06:30,140 --> 00:06:32,800
อันดับแรกเราต้องจัดเรียง
ตัวชี้ออกไปข้างนอก

142
00:06:32,800 --> 00:06:35,815
เราจำเป็นต้องจัดเรียง
9 ต่อไปจะข้าม 13

143
00:06:35,815 --> 00:06:38,030
และชี้ไปที่ 10--
คือสิ่งที่เราได้ทำเพียงแค่

144
00:06:38,030 --> 00:06:41,180
และเรายังจำเป็นที่จะต้อง
จัดเรียง 10 ก่อนหน้า

145
00:06:41,180 --> 00:06:44,610
ให้ชี้ไปที่ 9 แทนการชี้ไปที่ 13

146
00:06:44,610 --> 00:06:46,490
>> ดังนั้นอีกครั้งนี้คือ
แผนภาพจะเริ่มต้นด้วย

147
00:06:46,490 --> 00:06:47,730
นี่เป็นห่วงโซ่ของเรา

148
00:06:47,730 --> 00:06:51,027
เราจำเป็นต้องข้าม 13
แต่เราจำเป็นต้องรักษายัง

149
00:06:51,027 --> 00:06:52,110
ความสมบูรณ์ของรายการ

150
00:06:52,110 --> 00:06:54,680
เราไม่ต้องการที่จะสูญเสียใด ๆ
ข้อมูลในทิศทางใดทิศทางหนึ่ง

151
00:06:54,680 --> 00:06:59,620
ดังนั้นเราจึงจำเป็นที่จะต้องจัดเรียง
คำแนะนำอย่างระมัดระวัง

152
00:06:59,620 --> 00:07:02,240
ดังนั้นเราจึงไม่ทำลายห่วงโซ่ที่ทั้งหมด

153
00:07:02,240 --> 00:07:05,710
>> ดังนั้นเราจึงสามารถพูดได้ 9 ตัวชี้ถัดไป
ชี้ไปที่สถานที่เดียวกัน

154
00:07:05,710 --> 00:07:08,040
ที่สิบสามถัดไป
ตัวชี้จุดในขณะนี้

155
00:07:08,040 --> 00:07:10,331
เพราะเราในที่สุด
จะต้องการที่จะข้าม 13

156
00:07:10,331 --> 00:07:13,750
เพื่อให้ทุก 13 คะแนนต่อไป
ต้องการที่จะชี้เก้ามีแทน

157
00:07:13,750 --> 00:07:15,200
ดังนั้นที่ว่า

158
00:07:15,200 --> 00:07:20,370
และแล้วทุกที่ที่ 13 คะแนนกลับ
กับสิ่งที่มาก่อน 13

159
00:07:20,370 --> 00:07:24,800
เราต้องการที่จะชี้ 10
ที่แทน 13

160
00:07:24,800 --> 00:07:29,290
สังเกตเห็นตอนนี้ถ้าคุณทำตาม
ลูกศรที่เราสามารถวาง 13

161
00:07:29,290 --> 00:07:32,380
โดยไม่ต้องสูญเสียข้อมูลใด ๆ

162
00:07:32,380 --> 00:07:36,002
เราได้เก็บความสมบูรณ์ของรายการ
การเคลื่อนย้ายทั้งข้างหน้าและถอยหลัง

163
00:07:36,002 --> 00:07:38,210
และจากนั้นเราสามารถจัดเรียงเพียง
การทำความสะอาดขึ้นนิด ๆ หน่อย ๆ

164
00:07:38,210 --> 00:07:40,930
โดยการดึงรายการด้วยกัน

165
00:07:40,930 --> 00:07:43,270
ดังนั้นเราจึงจัด
คำแนะนำเกี่ยวกับด้านใดด้านหนึ่ง

166
00:07:43,270 --> 00:07:46,231
แล้วเราเป็นอิสระเอ็กซ์
โหนดที่มี 13

167
00:07:46,231 --> 00:07:47,480
และเราไม่ได้ทำลายห่วงโซ่

168
00:07:47,480 --> 00:07:50,980
ดังนั้นเราจึงไม่ดี

169
00:07:50,980 --> 00:07:53,000
>> บันทึกสุดท้ายที่นี่ในรายการที่เชื่อมโยง

170
00:07:53,000 --> 00:07:55,990
ดังนั้นทั้งสอง singly- และทวีคูณเชื่อมโยง
รายการที่เราเคยเห็น

171
00:07:55,990 --> 00:07:58,959
การสนับสนุนที่มีประสิทธิภาพแทรกจริงๆ
และการลบขององค์ประกอบ

172
00:07:58,959 --> 00:08:00,750
คุณสวยมากสามารถทำ
ในเวลาที่คงที่

173
00:08:00,750 --> 00:08:03,333
สิ่งที่พวกเราต้องทำเพื่อลบ
เพียงองค์ประกอบที่สองที่ผ่านมาแล้ว?

174
00:08:03,333 --> 00:08:04,440
เราย้ายตัวชี้หนึ่ง

175
00:08:04,440 --> 00:08:05,920
เราย้ายตัวชี้อีก

176
00:08:05,920 --> 00:08:07,915
เราเป็นอิสระ X-- เอาสามการดำเนินงาน

177
00:08:07,915 --> 00:08:14,500
มันก็จะต้องใช้เวลาสามการดำเนินงานเพื่อ
ลบ node-- ที่จะเป็นอิสระโหนด

178
00:08:14,500 --> 00:08:15,280
>> เราจะใส่ได้อย่างไร

179
00:08:15,280 --> 00:08:17,280
ดีเราเพียงแค่เสมอ
ตรึงในการเริ่มต้น

180
00:08:17,280 --> 00:08:19,400
ถ้าเราใส่ได้อย่างมีประสิทธิภาพ

181
00:08:19,400 --> 00:08:21,964
ดังนั้นเราจึงจำเป็นที่จะ rearrange--
ขึ้นอยู่กับว่ามันเป็น

182
00:08:21,964 --> 00:08:24,380
singly- หรือทวีคูณเชื่อมโยง
รายการที่เราอาจจะต้องทำสาม

183
00:08:24,380 --> 00:08:26,824
หรือสี่การดำเนินงานสูงสุด

184
00:08:26,824 --> 00:08:28,365
แต่อีกครั้งก็มักจะสามหรือสี่

185
00:08:28,365 --> 00:08:30,531
มันไม่สำคัญว่าหลาย
องค์ประกอบในรายการของเรา

186
00:08:30,531 --> 00:08:33,549
ก็มักจะสามหรือสี่ operations--
เช่นเดียวกับการลบอยู่เสมอ

187
00:08:33,549 --> 00:08:35,320
สามหรือสี่การดำเนินงาน

188
00:08:35,320 --> 00:08:36,919
มันเป็นเวลาที่คงที่

189
00:08:36,919 --> 00:08:38,169
เพื่อให้เป็นที่ดีจริงๆ

190
00:08:38,169 --> 00:08:40,620
>> กับอาร์เรย์ที่เรากำลังทำ
บางสิ่งบางอย่างเช่นการจัดเรียงแทรก

191
00:08:40,620 --> 00:08:44,739
คุณอาจจะจำได้ว่าแทรก
การเรียงลำดับไม่ได้เป็นอัลกอริทึมเวลาคง

192
00:08:44,739 --> 00:08:46,030
เป็นจริงราคาแพงสวย

193
00:08:46,030 --> 00:08:48,840
ดังนั้นนี้เป็นจำนวนมากที่ดีกว่าสำหรับการใส่

194
00:08:48,840 --> 00:08:51,840
แต่ที่ผมกล่าวถึงใน
ลำพังเชื่อมโยงวิดีโอรายการ

195
00:08:51,840 --> 00:08:54,030
เรามีข้อเสียที่นี่ด้วยใช่มั้ย?

196
00:08:54,030 --> 00:08:57,580
เราได้สูญเสียความสามารถที่จะ
สุ่มเข้าถึงองค์ประกอบ

197
00:08:57,580 --> 00:09:02,310
เราไม่สามารถพูดฉันต้องการจำนวนองค์ประกอบที่สี่
หรือส่วนประกอบจำนวน 10 รายการที่เชื่อมโยง

198
00:09:02,310 --> 00:09:04,990
เช่นเดียวกับที่เราสามารถทำได้
ทำกับอาร์เรย์

199
00:09:04,990 --> 00:09:08,630
หรือเราสามารถเพียงดัชนีโดยตรง
เข้าองค์ประกอบอาร์เรย์ของเรา

200
00:09:08,630 --> 00:09:10,930
>> และเพื่อพยายามที่จะหา
องค์ประกอบในการเชื่อมโยง list--

201
00:09:10,930 --> 00:09:15,880
ถ้าการค้นหาเป็น important--
ตอนนี้อาจใช้เวลาในการเชิงเส้น

202
00:09:15,880 --> 00:09:18,330
เป็นรายการที่ได้รับอีกต่อไปมัน
อาจใช้เวลาอีกหนึ่งขั้นตอน

203
00:09:18,330 --> 00:09:22,644
สำหรับทุกองค์ประกอบเดียวในรายการใน
เพื่อหาสิ่งที่เรากำลังมองหา

204
00:09:22,644 --> 00:09:23,560
เพื่อให้มีการค้าที่ไม่ชอบ

205
00:09:23,560 --> 00:09:25,780
มีบิตของโปรที่เป็น
และองค์ประกอบนักโทษที่นี่

206
00:09:25,780 --> 00:09:29,110
>> และรายการทวีคูณเชื่อมโยงไม่ได้
ชนิดสุดท้ายของโครงสร้างข้อมูลรวมกัน

207
00:09:29,110 --> 00:09:32,840
ว่าเราจะพูดคุยเกี่ยวกับ
การทั้งหมดที่สร้างพื้นฐาน

208
00:09:32,840 --> 00:09:34,865
บล็อกของซีวางกัน

209
00:09:34,865 --> 00:09:37,900
เพราะในความเป็นจริงที่เราสามารถทำได้
แม้จะทำได้ดีกว่านี้

210
00:09:37,900 --> 00:09:41,970
ในการสร้างโครงสร้างข้อมูลที่
คุณอาจจะสามารถที่จะค้นหาผ่าน

211
00:09:41,970 --> 00:09:43,360
ในเวลาคงเกินไป

212
00:09:43,360 --> 00:09:46,080
แต่เพิ่มเติมว่าในวิดีโออื่น

213
00:09:46,080 --> 00:09:47,150
>> ฉันลอยด์ดั๊ก

214
00:09:47,150 --> 00:09:49,050
นี่คือ CS50

215
00:09:49,050 --> 00:09:50,877