>> [MUSIC CHƠI]
DOUG LLOYD: Tất cả các quyền.
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
Tôi rời bạn tắt trên bit của một cliffhanger.
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.
>> Vì vậy, nếu bạn nhớ lại từ video, chúng tôi nói chuyện
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
để đối phó với thông tin mà số lượng các yếu tố
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ỏ.
Bây giờ chúng ta có thể đối phó với một cái gì đó như thế, nơi
chúng ta không thể đối phó với nó với mảng.
>> Nhưng họ bị một giới hạn quan trọng mà
đượ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
theo một hướng duy nhất thông qua danh sách.
Và chỉ có tình hình thực tế nơi mà có thể trở thành một vấn đề
là khi chúng tôi đã cố gắng để xóa một yếu tố duy nhất.
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ả.
Đó chắc chắn là có thể làm được, nhưng nó có thể là một chút rắc rối.
Vì vậy, nếu bạn thấy mình trong một tình huống mà
bạn đang cố gắng để xóa yếu tố duy nhất từ ​​danh sách
hoặc nó sẽ được yêu cầu rằng bạn sẽ bị xóa
yếu tố duy nhất từ danh sách, bạn có thể muốn
để 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.
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
thông qua danh sách thay vì chỉ về phía trước qua list--
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
cho nút danh sách gấp đôi được liên kết.
>> Một lần nữa, nếu bạn không đi đến được xóa yếu tố duy nhất
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
định nghĩa, các nút tự cho danh sách liên kết kép
đang có được lớn hơn.
Họ sẽ mất lên nhiều byte của bộ nhớ.
Và do đó, nếu đây không phải là một cái gì bạn sẽ cần phải làm,
bạn có thể quyết định nó không có giá trị thương mại giảm
phải chi tiêu thêm byte bộ nhớ cần thiết
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.
Nhưng chúng cũng mát cho những thứ khác quá.
>> 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
definition-- khái niệm này của một con trỏ trước.
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,
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.
>> Bây giờ trong đơn lẻ liên kết danh sách video, chúng tôi nói chuyện
về những năm của điều chính bạn cần
có thể làm để làm việc với các danh sách liên kết.
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
là không thực sự là một bước nhảy lớn.
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.
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.
Chúng tôi có thể xóa danh sách khá nhiều cách giống nhau quá.
Những điều duy nhất mà là tinh tế khác nhau,
thực sự, đang chèn các nút mới vào danh sách,
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.
Một lần nữa, khá nhiều ba người kia, chúng tôi
sẽ không nói về họ ngay bây giờ bởi vì họ chỉ
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.
>> 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.
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,
nhưng có một vài phụ bắt với danh sách liên kết kép.
Chúng tôi [? đi qua?] vào đầu của liệt kê ở đây và một số giá trị tùy ý,
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.
Đó là lý do tại sao nó trả về một ngôi sao dllnode.
Vì vậy, các bước là gì?
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ẻ
với một Ngoài ra thêm.
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ệ.
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
muốn đặt vào nó.
Đ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--
là để sửa chữa các con trỏ trước của người đứng đầu cũ của danh sách.
Hãy nhớ rằng bởi vì danh sách gấp đôi được liên kết,
chúng ta có thể di chuyển về phía trước và backwards-- mà
có nghĩa là mỗi node thực sự chỉ để hai nút khác thay vì chỉ một.
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
đế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ì đó
chúng tôi đã không phải làm trước.
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.
>> Vì vậy, đây là một danh sách.
Chúng tôi muốn chèn 12 vào danh sách này.
Chú ý rằng các sơ đồ là hơi khác nhau.
Mỗi nút chứa ba fields-- dữ liệu, và một con trỏ Tiếp màu đỏ,
và một con trỏ trước màu xanh lam.
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.
Đó là sự khởi đầu của danh sách.
Có gì trước khi nó.
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.
>> Vì vậy, chúng ta hãy thêm 12 vào danh sách này.
Chúng tôi cần [không nghe được] không gian cho các node.
Chúng tôi đặt 12 bên trong của nó.
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.
Chúng tôi muốn sắp xếp lại các con trỏ theo thứ tự đúng.
Và đôi khi có thể mean-- như chúng ta sẽ thấy đặc biệt
với delete-- rằng chúng tôi có một số con trỏ dư thừa, nhưng đó là OK.
>> Vì vậy, những gì chúng tôi muốn làm đầu tiên?
Tôi muốn giới thiệu điều bạn nên có lẽ
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.
Vì vậy, những gì được 12 sẽ trỏ đến tiếp theo?
15.
Cái gì đến trước 12?
K có gì.
Bây giờ chúng tôi đã đầy thông tin thêm trong 12
vì vậy nó có trước, tiếp theo, và giá trị.
>> 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
có thể có 15 điểm trở lại đến 12.
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.
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,
trừ thêm bước kết nối các đầu cũ của danh sách
sao để người đứng đầu mới của danh sách.
>> 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.
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
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
nút mà chúng ta muốn xóa.
Chúng tôi thậm chí không need-- nói đầu vẫn tuyên bố trên toàn cầu.
Chúng ta không cần đầu ở đây.
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
muốn thoát khỏi.
Hãy thoát khỏi nó.
Nó dễ dàng hơn rất nhiều với danh sách gấp đôi được liên kết.
First-- nó thực sự chỉ là một vài điều.
Chúng tôi chỉ cần phải sửa chữa xung quanh con trỏ nút 'để họ bỏ qua
các nút chúng ta muốn xóa.
Và sau đó chúng ta có thể xóa nút đó.
Vì vậy, một lần nữa, chúng ta chỉ cần đi qua đây.
Chúng tôi rõ ràng đã quyết định rằng chúng ta muốn xóa các nút X.
Và một lần nữa, những gì tôi làm here-- bởi way--
là một trường hợp tổng quát cho một nút đó là ở giữa.
Có một vài hãy cẩn thận thêm rằng bạn
cần phải xem xét khi bạn đang xóa đầu của danh sách
hoặc kết thúc của danh sách.
Có một vài đặc biệt trường hợp góc để đối phó với có.
>> Vì vậy, công trình này để xóa bất kỳ nút ở giữa của một list-- đó
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,
hợp pháp Previous và Next trỏ.
Một lần nữa, nếu bạn đang làm việc với kết thúc, bạn
cần phải xử lý những người hơi khác nhau,
và chúng tôi sẽ không nói về chuyện đó bây giờ.
Nhưng bạn có thể có lẽ tìm ra những gì cần
phải được thực hiện chỉ bằng cách xem video này.
>> 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.
Chúng ta làm gì?
Đầu tiên, chúng ta cần phải sắp xếp lại các con trỏ bên ngoài.
Chúng ta cần phải sắp xếp lại 9 tới để bỏ qua 13
và điểm đến 10-- mà là những gì chúng ta vừa làm.
Và chúng ta cũng cần phải sắp xếp lại 10 nhân trước
để trỏ đến 9 thay vì trỏ đến 13.
>> Vì vậy, một lần nữa, đây là sơ đồ để bắt đầu.
Đây là dây chuyền của chúng tôi.
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
sự toàn vẹn của danh sách.
Chúng tôi không muốn để mất bất kỳ thông tin trong hai hướng.
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
vì vậy chúng tôi không phá vỡ chuỗi xích.
>> 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
rằng mười ba của Tiếp theo con trỏ trỏ ngay bây giờ.
Bởi vì chúng tôi cuối cùng sẽ muốn bỏ qua 13.
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ế.
Vì vậy, đó là điều đó.
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,
chúng tôi muốn 10 điểm cho rằng thay vì 13.
Bây giờ để ý, nếu bạn làm theo các mũi tên, chúng ta có thể thả 13
mà không thực sự mất thông tin.
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ả.
Và sau đó chúng ta có thể chỉ là loại của làm sạch nó lên một chút
bằng cách kéo danh sách với nhau.
Vì vậy, chúng tôi sắp xếp lại các con trỏ ở hai bên.
Và sau đó chúng ta giải thoát X nút có chứa 13,
và chúng tôi đã không phá vỡ các chuỗi.
Vì vậy, chúng tôi đã làm tốt.
>> Cuối cùng lưu ý ở đây trên danh sách liên kết.
Vì vậy, cả hai singly- và gấp đôi được liên kết danh sách, như chúng ta đã thấy,
hỗ trợ chèn thực sự hiệu quả và xóa bỏ các yếu tố.
Bạn có khá nhiều có thể làm nó trong thời gian liên tục.
Chúng ta phải làm gì để xóa một yếu tố chỉ một giây trước đó?
Chúng tôi di chuyển một con trỏ.
Chúng tôi di chuyển con trỏ khác.
Chúng tôi giải thoát X-- mất ba hoạt động.
Nó luôn luôn có ba hoạt động để xóa node-- rằng để giải phóng một nút.
>> Làm thế nào để chúng ta chèn?
Vâng, chúng tôi chỉ luôn luôn tacking trên đầu
nếu chúng ta đang chèn hiệu quả.
Vì vậy, chúng ta cần phải rearrange-- tùy thuộc vào nếu nó
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
hoặc bốn hoạt động tối đa.
Nhưng một lần nữa, nó luôn luôn là ba hoặc bốn.
Nó không quan trọng bao nhiêu yếu tố nằm trong danh sách của chúng tôi,
nó luôn luôn ba hoặc bốn operations-- giống như xóa luôn
ba hoặc bốn hoạt động.
Đó là thời gian liên tục.
Vì vậy, đó là thực sự tuyệt vời.
>> Với mảng, chúng tôi đã làm một cái gì đó giống như sắp xếp chèn.
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.
Nó thực sự khá tốn kém.
Vì vậy, đây là tốt hơn rất nhiều cho chèn.
Tuy nhiên, như tôi đã đề cập trong đơn lẻ danh sách liên kết video,
chúng tôi đã có một nhược điểm ở đây quá, phải không?
Chúng tôi đã mất khả năng truy cập ngẫu nhiên các yếu tố.
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
cùng một cách mà chúng ta có thể làm điều đó với một mảng
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.
>> Và do đó, cố gắng tìm một yếu tố trong một list-- liên kết
nếu tìm kiếm là important-- bây giờ có thể mất thời gian tuyến tính.
Khi danh sách được lâu hơn, nó có thể mất một bước bổ sung
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.
Vì vậy, có thích thương mại.
Có một chút của một chuyên nghiệp và con phần tử ở đây.
>> 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
rằng chúng ta sẽ nói về, lấy tất cả những xây dựng cơ bản
khối C là đặt lại với nhau.
Bởi vì trong thực tế, chúng ta có thể thậm chí làm tốt hơn thế này
để 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
trong thời gian liên tục quá.
Nhưng thêm vào đó trong một video khác.
>> Tôi Doug Lloyd.
Đây là CS50.