1 00:00:00,000 --> 00:00:03,381 >> [MUSIC CHƠI] 2 00:00:03,381 --> 00:00:04,604 3 00:00:04,604 --> 00:00:05,520 DOUG LLOYD: Tất cả các quyền. 4 00:00:05,520 --> 00:00:07,860 Vì vậy, nếu bạn chỉ cần hoàn thành mà video trên danh sách đơn lẻ liên kết xin lỗi 5 00:00:07,860 --> 00:00:09,568 Tôi rời bạn tắt trên bit của một cliffhanger. 6 00:00:09,568 --> 00:00:12,790 Nhưng tôi vui vì bạn đang ở đây để kết thúc những câu chuyện của danh sách liên kết kép. 7 00:00:12,790 --> 00:00:15,250 >> Vì vậy, nếu bạn nhớ lại từ video, chúng tôi nói chuyện 8 00:00:15,250 --> 00:00:18,500 khoảng cách đơn lẻ liên kết danh sách tham dự làm khả năng của chúng tôi 9 00:00:18,500 --> 00:00:22,090 để đối phó với thông tin mà số lượng các yếu tố 10 00:00:22,090 --> 00:00:24,442 hoặc số lượng các mục trong một danh sách có thể phát triển hoặc thu nhỏ. 11 00:00:24,442 --> 00:00:26,400 Bây giờ chúng ta có thể đối phó với một cái gì đó như thế, nơi 12 00:00:26,400 --> 00:00:28,310 chúng ta không thể đối phó với nó với mảng. 13 00:00:28,310 --> 00:00:30,560 >> Nhưng họ bị một giới hạn quan trọng mà 14 00:00:30,560 --> 00:00:33,790 được rằng với một đơn lẻ liên kết danh sách, chúng tôi chỉ bao giờ có thể di chuyển 15 00:00:33,790 --> 00:00:36,200 theo một hướng duy nhất thông qua danh sách. 16 00:00:36,200 --> 00:00:39,010 Và chỉ có tình hình thực tế nơi mà có thể trở thành một vấn đề 17 00:00:39,010 --> 00:00:41,250 là khi chúng tôi đã cố gắng để xóa một yếu tố duy nhất. 18 00:00:41,250 --> 00:00:46,000 Và chúng tôi thậm chí không thảo luận làm thế nào để làm điều đó trong một danh sách đơn lẻ liên kết trong giả. 19 00:00:46,000 --> 00:00:48,797 Đó chắc chắn là có thể làm được, nhưng nó có thể là một chút rắc rối. 20 00:00:48,797 --> 00:00:50,630 Vì vậy, nếu bạn thấy mình trong một tình huống mà 21 00:00:50,630 --> 00:00:53,175 bạn đang cố gắng để xóa yếu tố duy nhất từ ​​danh sách 22 00:00:53,175 --> 00:00:55,430 hoặc nó sẽ được yêu cầu rằng bạn sẽ bị xóa 23 00:00:55,430 --> 00:00:57,970 yếu tố duy nhất từ danh sách, bạn có thể muốn 24 00:00:57,970 --> 00:01:02,090 để xem xét sử dụng một kép liên kết danh sách thay vì một danh sách đơn lẻ liên kết. 25 00:01:02,090 --> 00:01:06,320 Bởi vì danh sách liên kết kép cho phép bạn để di chuyển cả chuyển tiếp và ngược 26 00:01:06,320 --> 00:01:09,340 thông qua danh sách thay vì chỉ về phía trước qua list-- 27 00:01:09,340 --> 00:01:13,950 chỉ bằng cách thêm một yếu tố thêm để định nghĩa cấu trúc của chúng tôi 28 00:01:13,950 --> 00:01:16,690 cho nút danh sách gấp đôi được liên kết. 29 00:01:16,690 --> 00:01:19,770 >> Một lần nữa, nếu bạn không đi đến được xóa yếu tố duy nhất 30 00:01:19,770 --> 00:01:24,810 từ list-- bởi vì chúng ta đang thêm một trường thêm cho cấu trúc của chúng tôi 31 00:01:24,810 --> 00:01:28,340 định nghĩa, các nút tự cho danh sách liên kết kép 32 00:01:28,340 --> 00:01:29,550 đang có được lớn hơn. 33 00:01:29,550 --> 00:01:31,600 Họ sẽ mất lên nhiều byte của bộ nhớ. 34 00:01:31,600 --> 00:01:34,160 Và do đó, nếu đây không phải là một cái gì bạn sẽ cần phải làm, 35 00:01:34,160 --> 00:01:36,300 bạn có thể quyết định nó không có giá trị thương mại giảm 36 00:01:36,300 --> 00:01:39,360 phải chi tiêu thêm byte bộ nhớ cần thiết 37 00:01:39,360 --> 00:01:43,940 cho một danh sách gấp đôi liên kết nếu bạn không sẽ được xóa yếu tố duy nhất. 38 00:01:43,940 --> 00:01:46,760 Nhưng chúng cũng mát cho những thứ khác quá. 39 00:01:46,760 --> 00:01:51,260 >> Vì vậy, như tôi đã nói, chúng ta chỉ cần có thêm một lĩnh vực duy nhất để cấu trúc của chúng tôi 40 00:01:51,260 --> 00:01:55,360 definition-- khái niệm này của một con trỏ trước. 41 00:01:55,360 --> 00:01:58,620 Vì vậy, với một danh sách đơn lẻ liên kết, chúng tôi có giá trị và con trỏ Tiếp theo, 42 00:01:58,620 --> 00:02:02,850 vì vậy danh sách gấp đôi được liên kết chỉ có một cách để di chuyển ngược trở lại là tốt. 43 00:02:02,850 --> 00:02:04,960 >> Bây giờ trong đơn lẻ liên kết danh sách video, chúng tôi nói chuyện 44 00:02:04,960 --> 00:02:07,210 về những năm của điều chính bạn cần 45 00:02:07,210 --> 00:02:09,449 có thể làm để làm việc với các danh sách liên kết. 46 00:02:09,449 --> 00:02:12,880 Và hầu hết trong số này, thực tế rằng đó là một danh sách gấp đôi liên kết 47 00:02:12,880 --> 00:02:14,130 là không thực sự là một bước nhảy lớn. 48 00:02:14,130 --> 00:02:17,936 Chúng ta vẫn có thể tìm kiếm thông qua bởi chỉ di chuyển về phía trước từ đầu đến cuối. 49 00:02:17,936 --> 00:02:20,810 Chúng tôi vẫn có thể tạo ra một nút ra khỏi không khí mỏng, khá nhiều theo cùng một cách. 50 00:02:20,810 --> 00:02:23,591 Chúng tôi có thể xóa danh sách khá nhiều cách giống nhau quá. 51 00:02:23,591 --> 00:02:25,340 Những điều duy nhất mà là tinh tế khác nhau, 52 00:02:25,340 --> 00:02:28,970 thực sự, đang chèn các nút mới vào danh sách, 53 00:02:28,970 --> 00:02:33,722 và cuối cùng chúng ta sẽ nói về việc xóa một yếu tố duy nhất trong danh sách là tốt. 54 00:02:33,722 --> 00:02:35,430 Một lần nữa, khá nhiều ba người kia, chúng tôi 55 00:02:35,430 --> 00:02:37,888 sẽ không nói về họ ngay bây giờ bởi vì họ chỉ 56 00:02:37,888 --> 00:02:43,920 chỉnh rất nhỏ trên các ý kiến ​​thảo luận trong danh sách video đơn lẻ liên kết. 57 00:02:43,920 --> 00:02:46,292 >> Vì vậy, hãy chèn một nút mới vào một danh sách gấp đôi được liên kết. 58 00:02:46,292 --> 00:02:48,750 Chúng tôi đã nói chuyện về việc này cho danh sách đơn lẻ liên kết là tốt, 59 00:02:48,750 --> 00:02:52,020 nhưng có một vài phụ bắt với danh sách liên kết kép. 60 00:02:52,020 --> 00:02:55,280 Chúng tôi [? đi qua?] vào đầu của liệt kê ở đây và một số giá trị tùy ý, 61 00:02:55,280 --> 00:02:58,600 và chúng tôi muốn có được người đứng đầu mới của danh sách ra khỏi chức năng này. 62 00:02:58,600 --> 00:03:01,414 Đó là lý do tại sao nó trả về một ngôi sao dllnode. 63 00:03:01,414 --> 00:03:02,330 Vì vậy, các bước là gì? 64 00:03:02,330 --> 00:03:04,496 Họ là, một lần nữa, rất tương tự vào các danh sách liên kết đơn lẻ 65 00:03:04,496 --> 00:03:05,670 với một Ngoài ra thêm. 66 00:03:05,670 --> 00:03:08,900 Chúng tôi muốn phân bổ không gian cho một mới nút và kiểm tra để chắc chắn rằng đó là hợp lệ. 67 00:03:08,900 --> 00:03:11,510 Chúng tôi muốn điền vào nút đó lên với bất cứ thông tin chúng tôi 68 00:03:11,510 --> 00:03:12,564 muốn đặt vào nó. 69 00:03:12,564 --> 00:03:15,480 Điều cuối cùng chúng ta cần phải do-- sự điều thêm chúng tôi cần phải làm, rather-- 70 00:03:15,480 --> 00:03:19,435 là để sửa chữa các con trỏ trước của người đứng đầu cũ của danh sách. 71 00:03:19,435 --> 00:03:21,310 Hãy nhớ rằng bởi vì danh sách gấp đôi được liên kết, 72 00:03:21,310 --> 00:03:23,110 chúng ta có thể di chuyển về phía trước và backwards-- mà 73 00:03:23,110 --> 00:03:27,080 có nghĩa là mỗi node thực sự chỉ để hai nút khác thay vì chỉ một. 74 00:03:27,080 --> 00:03:29,110 Và vì vậy chúng tôi cần phải sửa chữa người đứng đầu cũ của danh sách 75 00:03:29,110 --> 00:03:32,151 đến điểm phía sau để làm người đứng đầu mới của danh sách liên kết, đó là một cái gì đó 76 00:03:32,151 --> 00:03:33,990 chúng tôi đã không phải làm trước. 77 00:03:33,990 --> 00:03:37,420 Và như trước đây, chúng tôi chỉ trả lại một con trỏ để người đứng đầu mới của danh sách. 78 00:03:37,420 --> 00:03:38,220 >> Vì vậy, đây là một danh sách. 79 00:03:38,220 --> 00:03:40,144 Chúng tôi muốn chèn 12 vào danh sách này. 80 00:03:40,144 --> 00:03:42,060 Chú ý rằng các sơ đồ là hơi khác nhau. 81 00:03:42,060 --> 00:03:47,710 Mỗi nút chứa ba fields-- dữ liệu, và một con trỏ Tiếp màu đỏ, 82 00:03:47,710 --> 00:03:50,170 và một con trỏ trước màu xanh lam. 83 00:03:50,170 --> 00:03:54,059 Không có gì đến trước khi các nút 15, vì vậy con trỏ trước của nó là null. 84 00:03:54,059 --> 00:03:55,350 Đó là sự khởi đầu của danh sách. 85 00:03:55,350 --> 00:03:56,560 Có gì trước khi nó. 86 00:03:56,560 --> 00:04:03,350 Và không có gì xảy ra sau khi các nút 10, và do đó, nó là con trỏ Tiếp theo là null là tốt. 87 00:04:03,350 --> 00:04:05,616 >> Vì vậy, chúng ta hãy thêm 12 vào danh sách này. 88 00:04:05,616 --> 00:04:08,070 Chúng tôi cần [không nghe được] không gian cho các node. 89 00:04:08,070 --> 00:04:11,480 Chúng tôi đặt 12 bên trong của nó. 90 00:04:11,480 --> 00:04:14,840 Và sau đó một lần nữa, chúng ta cần phải thực sự cẩn thận không để phá vỡ dây chuyền. 91 00:04:14,840 --> 00:04:17,144 Chúng tôi muốn sắp xếp lại các con trỏ theo thứ tự đúng. 92 00:04:17,144 --> 00:04:19,519 Và đôi khi có thể mean-- như chúng ta sẽ thấy đặc biệt 93 00:04:19,519 --> 00:04:24,120 với delete-- rằng chúng tôi có một số con trỏ dư thừa, nhưng đó là OK. 94 00:04:24,120 --> 00:04:25,750 >> Vì vậy, những gì chúng tôi muốn làm đầu tiên? 95 00:04:25,750 --> 00:04:28,290 Tôi muốn giới thiệu điều bạn nên có lẽ 96 00:04:28,290 --> 00:04:35,350 làm là để điền vào các con trỏ của 12 nút trước khi chạm vào bất kỳ ai khác. 97 00:04:35,350 --> 00:04:38,640 Vì vậy, những gì được 12 sẽ trỏ đến tiếp theo? 98 00:04:38,640 --> 00:04:39,860 15. 99 00:04:39,860 --> 00:04:42,430 Cái gì đến trước 12? 100 00:04:42,430 --> 00:04:43,640 K có gì. 101 00:04:43,640 --> 00:04:46,280 Bây giờ chúng tôi đã đầy thông tin thêm trong 12 102 00:04:46,280 --> 00:04:49,320 vì vậy nó có trước, tiếp theo, và giá trị. 103 00:04:49,320 --> 00:04:53,505 >> Bây giờ chúng ta có thể có thêm 15-- này bước chúng tôi đã nói chuyện about-- chúng tôi 104 00:04:53,505 --> 00:04:56,590 có thể có 15 điểm trở lại đến 12. 105 00:04:56,590 --> 00:04:59,634 Và bây giờ chúng ta có thể di chuyển đầu của danh sách liên kết tới cũng là 12. 106 00:04:59,634 --> 00:05:02,550 Vì vậy, nó khá giống với những gì chúng tôi đã làm với danh sách đơn lẻ liên kết, 107 00:05:02,550 --> 00:05:06,940 trừ thêm bước kết nối các đầu cũ của danh sách 108 00:05:06,940 --> 00:05:09,810 sao để người đứng đầu mới của danh sách. 109 00:05:09,810 --> 00:05:12,170 >> Bây giờ chúng ta cuối cùng của xóa một nút từ một danh sách liên kết. 110 00:05:12,170 --> 00:05:14,350 Vì vậy, chúng ta hãy nói rằng chúng ta có một số chức năng khác 111 00:05:14,350 --> 00:05:18,080 là tìm kiếm một nút chúng ta muốn xóa và đã cho chúng ta một con trỏ đến một cách chính xác 112 00:05:18,080 --> 00:05:19,710 nút mà chúng ta muốn xóa. 113 00:05:19,710 --> 00:05:22,360 Chúng tôi thậm chí không need-- nói đầu vẫn tuyên bố trên toàn cầu. 114 00:05:22,360 --> 00:05:23,590 Chúng ta không cần đầu ở đây. 115 00:05:23,590 --> 00:05:26,830 Tất cả các chức năng này được thực hiện là chúng tôi đã tìm thấy một con trỏ đến một cách chính xác các nút chúng tôi 116 00:05:26,830 --> 00:05:28,090 muốn thoát khỏi. 117 00:05:28,090 --> 00:05:28,940 Hãy thoát khỏi nó. 118 00:05:28,940 --> 00:05:31,859 Nó dễ dàng hơn rất nhiều với danh sách gấp đôi được liên kết. 119 00:05:31,859 --> 00:05:33,650 First-- nó thực sự chỉ là một vài điều. 120 00:05:33,650 --> 00:05:38,760 Chúng tôi chỉ cần phải sửa chữa xung quanh con trỏ nút 'để họ bỏ qua 121 00:05:38,760 --> 00:05:40,240 các nút chúng ta muốn xóa. 122 00:05:40,240 --> 00:05:43,484 Và sau đó chúng ta có thể xóa nút đó. 123 00:05:43,484 --> 00:05:45,150 Vì vậy, một lần nữa, chúng ta chỉ cần đi qua đây. 124 00:05:45,150 --> 00:05:49,625 Chúng tôi rõ ràng đã quyết định rằng chúng ta muốn xóa các nút X. 125 00:05:49,625 --> 00:05:51,500 Và một lần nữa, những gì tôi làm here-- bởi way-- 126 00:05:51,500 --> 00:05:54,580 là một trường hợp tổng quát cho một nút đó là ở giữa. 127 00:05:54,580 --> 00:05:56,547 Có một vài hãy cẩn thận thêm rằng bạn 128 00:05:56,547 --> 00:05:59,380 cần phải xem xét khi bạn đang xóa đầu của danh sách 129 00:05:59,380 --> 00:06:01,040 hoặc kết thúc của danh sách. 130 00:06:01,040 --> 00:06:03,730 Có một vài đặc biệt trường hợp góc để đối phó với có. 131 00:06:03,730 --> 00:06:07,960 >> Vì vậy, công trình này để xóa bất kỳ nút ở giữa của một list-- đó 132 00:06:07,960 --> 00:06:11,550 có một con trỏ hợp pháp về phía trước và một con trỏ hợp pháp lạc hậu, 133 00:06:11,550 --> 00:06:14,460 hợp pháp Previous và Next trỏ. 134 00:06:14,460 --> 00:06:16,530 Một lần nữa, nếu bạn đang làm việc với kết thúc, bạn 135 00:06:16,530 --> 00:06:18,500 cần phải xử lý những người hơi khác nhau, 136 00:06:18,500 --> 00:06:19,570 và chúng tôi sẽ không nói về chuyện đó bây giờ. 137 00:06:19,570 --> 00:06:21,319 Nhưng bạn có thể có lẽ tìm ra những gì cần 138 00:06:21,319 --> 00:06:24,610 phải được thực hiện chỉ bằng cách xem video này. 139 00:06:24,610 --> 00:06:28,910 >> Vì vậy, chúng tôi đã cô lập X. X là node chúng tôi muốn xóa khỏi danh sách. 140 00:06:28,910 --> 00:06:30,140 Chúng ta làm gì? 141 00:06:30,140 --> 00:06:32,800 Đầu tiên, chúng ta cần phải sắp xếp lại các con trỏ bên ngoài. 142 00:06:32,800 --> 00:06:35,815 Chúng ta cần phải sắp xếp lại 9 tới để bỏ qua 13 143 00:06:35,815 --> 00:06:38,030 và điểm đến 10-- mà là những gì chúng ta vừa làm. 144 00:06:38,030 --> 00:06:41,180 Và chúng ta cũng cần phải sắp xếp lại 10 nhân trước 145 00:06:41,180 --> 00:06:44,610 để trỏ đến 9 thay vì trỏ đến 13. 146 00:06:44,610 --> 00:06:46,490 >> Vì vậy, một lần nữa, đây là sơ đồ để bắt đầu. 147 00:06:46,490 --> 00:06:47,730 Đây là dây chuyền của chúng tôi. 148 00:06:47,730 --> 00:06:51,027 Chúng tôi cần phải bỏ qua hơn 13, nhưng chúng ta cũng cần phải giữ gìn 149 00:06:51,027 --> 00:06:52,110 sự toàn vẹn của danh sách. 150 00:06:52,110 --> 00:06:54,680 Chúng tôi không muốn để mất bất kỳ thông tin trong hai hướng. 151 00:06:54,680 --> 00:06:59,620 Vì vậy, chúng ta cần phải sắp xếp lại các con trỏ một cách cẩn thận 152 00:06:59,620 --> 00:07:02,240 vì vậy chúng tôi không phá vỡ chuỗi xích. 153 00:07:02,240 --> 00:07:05,710 >> Vì vậy, chúng ta có thể nói rằng con trỏ Tiếp 9 trỏ đến cùng một nơi 154 00:07:05,710 --> 00:07:08,040 rằng mười ba của Tiếp theo con trỏ trỏ ngay bây giờ. 155 00:07:08,040 --> 00:07:10,331 Bởi vì chúng tôi cuối cùng sẽ muốn bỏ qua 13. 156 00:07:10,331 --> 00:07:13,750 Vì vậy, bất cứ nơi nào 13 điểm tiếp theo, bạn muốn chín chỉ có thay thế. 157 00:07:13,750 --> 00:07:15,200 Vì vậy, đó là điều đó. 158 00:07:15,200 --> 00:07:20,370 Và sau đó bất cứ nơi nào 13 điểm trở lại để, bất cứ điều gì đến trước 13, 159 00:07:20,370 --> 00:07:24,800 chúng tôi muốn 10 điểm cho rằng thay vì 13. 160 00:07:24,800 --> 00:07:29,290 Bây giờ để ý, nếu bạn làm theo các mũi tên, chúng ta có thể thả 13 161 00:07:29,290 --> 00:07:32,380 mà không thực sự mất thông tin. 162 00:07:32,380 --> 00:07:36,002 Chúng tôi đã giữ sự toàn vẹn của danh sách, di chuyển về phía trước và lạc hậu cả. 163 00:07:36,002 --> 00:07:38,210 Và sau đó chúng ta có thể chỉ là loại của làm sạch nó lên một chút 164 00:07:38,210 --> 00:07:40,930 bằng cách kéo danh sách với nhau. 165 00:07:40,930 --> 00:07:43,270 Vì vậy, chúng tôi sắp xếp lại các con trỏ ở hai bên. 166 00:07:43,270 --> 00:07:46,231 Và sau đó chúng ta giải thoát X nút có chứa 13, 167 00:07:46,231 --> 00:07:47,480 và chúng tôi đã không phá vỡ các chuỗi. 168 00:07:47,480 --> 00:07:50,980 Vì vậy, chúng tôi đã làm tốt. 169 00:07:50,980 --> 00:07:53,000 >> Cuối cùng lưu ý ở đây trên danh sách liên kết. 170 00:07:53,000 --> 00:07:55,990 Vì vậy, cả hai singly- và gấp đôi được liên kết danh sách, như chúng ta đã thấy, 171 00:07:55,990 --> 00:07:58,959 hỗ trợ chèn thực sự hiệu quả và xóa bỏ các yếu tố. 172 00:07:58,959 --> 00:08:00,750 Bạn có khá nhiều có thể làm nó trong thời gian liên tục. 173 00:08:00,750 --> 00:08:03,333 Chúng ta phải làm gì để xóa một yếu tố chỉ một giây trước đó? 174 00:08:03,333 --> 00:08:04,440 Chúng tôi di chuyển một con trỏ. 175 00:08:04,440 --> 00:08:05,920 Chúng tôi di chuyển con trỏ khác. 176 00:08:05,920 --> 00:08:07,915 Chúng tôi giải thoát X-- mất ba hoạt động. 177 00:08:07,915 --> 00:08:14,500 Nó luôn luôn có ba hoạt động để xóa node-- rằng để giải phóng một nút. 178 00:08:14,500 --> 00:08:15,280 >> Làm thế nào để chúng ta chèn? 179 00:08:15,280 --> 00:08:17,280 Vâng, chúng tôi chỉ luôn luôn tacking trên đầu 180 00:08:17,280 --> 00:08:19,400 nếu chúng ta đang chèn hiệu quả. 181 00:08:19,400 --> 00:08:21,964 Vì vậy, chúng ta cần phải rearrange-- tùy thuộc vào nếu nó 182 00:08:21,964 --> 00:08:24,380 một singly- hoặc gấp đôi được liên kết danh sách, chúng ta có thể cần phải làm ba 183 00:08:24,380 --> 00:08:26,824 hoặc bốn hoạt động tối đa. 184 00:08:26,824 --> 00:08:28,365 Nhưng một lần nữa, nó luôn luôn là ba hoặc bốn. 185 00:08:28,365 --> 00:08:30,531 Nó không quan trọng bao nhiêu yếu tố nằm trong danh sách của chúng tôi, 186 00:08:30,531 --> 00:08:33,549 nó luôn luôn ba hoặc bốn operations-- giống như xóa luôn 187 00:08:33,549 --> 00:08:35,320 ba hoặc bốn hoạt động. 188 00:08:35,320 --> 00:08:36,919 Đó là thời gian liên tục. 189 00:08:36,919 --> 00:08:38,169 Vì vậy, đó là thực sự tuyệt vời. 190 00:08:38,169 --> 00:08:40,620 >> Với mảng, chúng tôi đã làm một cái gì đó giống như sắp xếp chèn. 191 00:08:40,620 --> 00:08:44,739 Bạn có thể nhớ lại rằng chèn loại không phải là một thuật toán thời gian liên tục. 192 00:08:44,739 --> 00:08:46,030 Nó thực sự khá tốn kém. 193 00:08:46,030 --> 00:08:48,840 Vì vậy, đây là tốt hơn rất nhiều cho chèn. 194 00:08:48,840 --> 00:08:51,840 Tuy nhiên, như tôi đã đề cập trong đơn lẻ danh sách liên kết video, 195 00:08:51,840 --> 00:08:54,030 chúng tôi đã có một nhược điểm ở đây quá, phải không? 196 00:08:54,030 --> 00:08:57,580 Chúng tôi đã mất khả năng truy cập ngẫu nhiên các yếu tố. 197 00:08:57,580 --> 00:09:02,310 Chúng ta không thể nói, tôi muốn tố số bốn hoặc phần tử số 10 của một danh sách liên kết 198 00:09:02,310 --> 00:09:04,990 cùng một cách mà chúng ta có thể làm điều đó với một mảng 199 00:09:04,990 --> 00:09:08,630 hoặc chúng ta có thể chỉ trực tiếp chỉ số vào phần tử mảng của chúng tôi. 200 00:09:08,630 --> 00:09:10,930 >> Và do đó, cố gắng tìm một yếu tố trong một list-- liên kết 201 00:09:10,930 --> 00:09:15,880 nếu tìm kiếm là important-- bây giờ có thể mất thời gian tuyến tính. 202 00:09:15,880 --> 00:09:18,330 Khi danh sách được lâu hơn, nó có thể mất một bước bổ sung 203 00:09:18,330 --> 00:09:22,644 cho mỗi yếu tố duy nhất trong danh sách ở để tìm ra những gì chúng tôi đang tìm kiếm. 204 00:09:22,644 --> 00:09:23,560 Vì vậy, có thích thương mại. 205 00:09:23,560 --> 00:09:25,780 Có một chút của một chuyên nghiệp và con phần tử ở đây. 206 00:09:25,780 --> 00:09:29,110 >> Và danh sách gấp đôi được liên kết không phải là loại cuối cùng của sự kết hợp cấu trúc dữ liệu 207 00:09:29,110 --> 00:09:32,840 rằng chúng ta sẽ nói về, lấy tất cả những xây dựng cơ bản 208 00:09:32,840 --> 00:09:34,865 khối C là đặt lại với nhau. 209 00:09:34,865 --> 00:09:37,900 Bởi vì trong thực tế, chúng ta có thể thậm chí làm tốt hơn thế này 210 00:09:37,900 --> 00:09:41,970 để tạo ra một cấu trúc dữ liệu bạn có thể có thể tìm kiếm thông qua 211 00:09:41,970 --> 00:09:43,360 trong thời gian liên tục quá. 212 00:09:43,360 --> 00:09:46,080 Nhưng thêm vào đó trong một video khác. 213 00:09:46,080 --> 00:09:47,150 >> Tôi Doug Lloyd. 214 00:09:47,150 --> 00:09:49,050 Đây là CS50. 215 00:09:49,050 --> 00:09:50,877