[მუსიკის დაკვრა] DOUG LLOYD ყველა უფლება. ასე რომ, თუ თქვენ უბრალოდ დასრულდა, რომ ვიდეო საგნით დაკავშირებული სიები ბოდიში დავტოვე თქვენ ფასდაკლებას ცოტა cliffhanger. მაგრამ მოხარული ვარ, რომ თქვენ აქ დასრულდება ამბავი ორმაგად დაკავშირებული სიები. 

ასე რომ, თუ გახსოვთ, რომ ვიდეო, ჩვენ ვისაუბრეთ იმაზე, თუ როგორ საგნით დაკავშირებული სიები ამის დასასწრებად ჩვენი უნარი გაუმკლავდეთ ინფორმაცია სადაც რაოდენობის ელემენტები ან რაოდენობის ნივთები სია შეგიძლიათ იზრდება ან მცირდება. ახლა ჩვენ შეგვიძლია გავუმკლავდეთ ასე რომ, სადაც ჩვენ ვერ გაუმკლავდეთ მას მასივები. 

მაგრამ ისინი არ განიცდიან ერთი კრიტიკული შეზღუდვა, რომელიც ის არის, რომ ერთად საგნით დაკავშირებული სია, ჩვენ შეგვიძლია მხოლოდ ოდესმე გადასვლის ერთი მიმართულებით მეშვეობით სიაში. და ერთადერთი რეალური სიტუაცია სადაც ეს შეიძლება გახდეს პრობლემა იყო, როცა ჩვენ ცდილობს წაშლა ერთ ელემენტს. და ჩვენ კი არ განიხილავენ, თუ როგორ უნდა გავაკეთოთ ეს ერთი საგნით დაკავშირებული სიაში pseudocode. რა თქმა უნდა, შესაძლებელია, მაგრამ ეს შეიძლება იყოს ცოტა hassle. ასე რომ, თუ თქვენ აღმოჩნდეთ ამ სიტუაციაში, როდესაც თქვენ ცდილობთ წაშლა ერთ ელემენტების სია ან ის იქნება საჭირო რომ თქვენ უნდა წაშლის ერთ ელემენტები სია, დაგვჭირდება განიხილოს გამოყენებით ორმაგად დაკავშირებული მიუთითეთ ნაცვლად საგნით დაკავშირებული სიაში. იმის გამო, რომ ორმაგად დაკავშირებული სიები საშუალებას გაძლევთ გადაადგილება ორივე ფორვარდები და უკან მეშვეობით სიაში ნაცვლად მხოლოდ ნაბიჯია მეშვეობით list-- უბრალოდ შეავსოთ ერთი დამატებითი ელემენტი ჩვენი სტრუქტურა განმარტება რომ ორმაგად დაკავშირებული სიაში კვანძის. 

კიდევ ერთხელ, თუ არ ვაპირებთ უნდა წაშლის ერთი ელემენტები საწყისი list-- იმიტომ, რომ ჩვენ ვამატებთ დამატებითი სფეროში ჩვენი სტრუქტურა განმარტება, კვანძების თავს ამისთვის ორმაგად დაკავშირებული სიები ვაპირებთ, რომ იყოს უფრო დიდი. ისინი აპირებს up მეტი ბაიტი მეხსიერება. ასე რომ, თუ ეს არ არის რაღაც თქვენ აპირებთ უნდა გავაკეთოთ, თქვენ შეიძლება გადაწყვიტოს, რომ ეს არ ღირს ვაჭრობის უნდა დახარჯოს ზედმეტი ბაიტი მეხსიერება საჭირო ამისთვის ორმაგად უკავშირდება სიაში, თუ თქვენ არ იქნება წაშლის ერთი ელემენტებს. მაგრამ ისინი ასევე cool სხვა რამ, ძალიან. 

ასე რომ, როგორც ვთქვი, ჩვენ უბრალოდ უნდა დაამატოთ ერთი სფეროში ჩვენი სტრუქტურა definition-- ეს ცნება წინა მაჩვენებელი. ამრიგად საგნით დაკავშირებული სიაში, ჩვენ აქვს მნიშვნელობა და შემდეგი მაჩვენებელი, ასე რომ ორმაგად უკავშირდება სიაში მხოლოდ აქვს გზა გადავა უკან ასევე. 

ახლა საგნით დაკავშირებული სიაში ვიდეო, ჩვენ ვისაუბრეთ შესახებ ეს არის ხუთ მთავარი რამ, რომ თქვენ უნდა იყოს შეუძლია გააკეთოს მუშაობა დაკავშირებული სიები. და ყველაზე მეტად ამ, ის ფაქტი, ის, რომ ორმაგად უკავშირდება სიაში ნამდვილად არ არის დიდი ნახტომი. ჩვენ ჯერ კიდევ შეგვიძლია ძებნის მეშვეობით მხოლოდ წინსვლის დაწყების დასრულდება. ჩვენ მაინც შევქმნათ კვანძის გარეთ თხელი საჰაერო, საკმაოდ ბევრი იგივე გზა. ჩვენ შეგვიძლია წაშლა სიები საკმაოდ ზუსტად იგივე გზა ძალიან. ერთადერთი რამ, უეცრად სხვადასხვა, მართლაც, ჩასმა ახალი კვანძების შევიდა სიაში, და ჩვენ საბოლოოდ ვისაუბროთ წაშლის ერთ ელემენტს სიიდან ისევე. ერთხელ, საკმაოდ ბევრი სხვა სამი, ჩვენ არ ვაპირებ ვისაუბრო მათ ახლა, რადგან ისინი მხოლოდ ძალიან უმნიშვნელო შესწორებები იდეები განიხილეს ამ საგნით დაკავშირებული სიაში ვიდეო. 

ასე რომ, მოდით ჩადეთ ახალი კვანძის შევიდა ორმაგად უკავშირდება სიაში. ჩვენ ვისაუბრეთ ამით საგნით დაკავშირებული სიები, აგრეთვე, მაგრამ არსებობს რამდენიმე დამატებითი იჭერს ერთად ორმაგად დაკავშირებული სიები. ჩვენ [? ჩაბარების?] და ხელმძღვანელი ჩამოთვლა აქ და ზოგიერთი თვითნებური ღირებულება, და ჩვენ გვინდა ახალი ხელმძღვანელი სიაში out ამ ფუნქციას. სწორედ ამიტომ, ის დააბრუნებს dllnode ვარსკვლავი. ასე რომ, რა არის ამისათვის საჭირო? ისინი, კიდევ ერთხელ, ძალიან ჰგავს რომ საგნით დაკავშირებული სიები ერთი ზედმეტი გარდა. ჩვენ გვინდა, რომ გამოყოფს ფართი ახალი კვანძის და გამშვები დარწმუნდით, რომ იგი მოქმედებს. ჩვენ გვინდა, რომ შეავსოთ, რომ კვანძის up რასაც ინფორმაციას ჩვენ გვინდა, რომ დააყენა იგი. ბოლო რაც ჩვენ უნდა გავაკეთოთ დამატებითი რამ, რაც ჩვენ უნდა გავაკეთოთ, rather-- არის დაფიქსირება წინა მაჩვენებელი ძველი ხელმძღვანელს სიაში. გახსოვდეთ, რომ იმის გამო, რომ საქართველოს ორმაგად დაკავშირებული სიები, ჩვენ შეგვიძლია წინსვლა და backwards-- რომელიც იმას ნიშნავს, რომ თითოეული კვანძის რეალურად მიუთითებს ორი სხვა კვანძების ნაცვლად მხოლოდ ერთი. ასე რომ, ჩვენ უნდა დააფიქსიროს ძველი ხელმძღვანელი სია უნდა აღვნიშნო, უკან ახალი ხელმძღვანელი უკავშირდება სია, რომელიც იყო რაღაც ჩვენ არ უნდა გავაკეთოთ, სანამ. და როგორც ადრე, ჩვენ უბრალოდ დააბრუნოს მომცეთ ახალი ხელმძღვანელი სიაში. 

ასე რომ, აქ არის სია. გვინდა ჩადეთ 12 შევიდა ამ სიაში. გაითვალისწინეთ, რომ სქემა ოდნავ განსხვავებული. თითოეული კვანძის შეიცავს სამი სფეროებში მონაცემები და მომავალი მაჩვენებელი წითელი, და წინა მაჩვენებელი ლურჯი ფერით. არაფერი მოდის ადრე 15 კვანძის, ასე რომ მისი წინა მაჩვენებელი არის null. ეს არის დასაწყისში სიაში. არაფერია, სანამ. და არაფერი უძღოდა 10 კვანძის და ასე რომ, ეს არის შემდეგი მაჩვენებელი არის null ისევე. 

მოდით დავამატოთ 12 ამ სიაში. ჩვენ უნდა [INAUDIBLE] ფართი კვანძი. ჩვენ ბოლო 12 შიგნით მას. და მერე ისევ, ჩვენ უნდა ნამდვილად ფრთხილად არ დაარღვიოს ჯაჭვი. ჩვენ გვინდა, უნდა rearrange პოინტერები სწორი მიზნით. და ზოგჯერ, რომ შესაძლოა mean-- როგორც ვნახავთ, განსაკუთრებით ერთად delete--, რომ ჩვენ გვაქვს გარკვეული გადაჭარბებული მითითებას, მაგრამ ეს OK. 

ასე რომ, რა გვინდა გავაკეთოთ პირველ რიგში? მე რეკომენდაციას რამ, რაც უნდა ალბათ ამის შევსება მითითებას 12 კვანძის სანამ შეეხოთ ვინმეს. ასე რომ, რა არის 12 აპირებს აღვნიშნო, რომ მომავალი? 15. რა მოდის ადრე 12? არაფერი. ახლა ჩვენ შევსებული დამატებითი ინფორმაცია 12 ასე რომ, მას წინა, შემდეგი, და მნიშვნელობა. 

ახლა ჩვენ შეგვიძლია აქვს 15-- დამატებითი ნაბიჯი ჩვენ ვსაუბრობთ ჩვენ შეიძლება ჰქონდეს 15 წერტილი უკან 12. და ახლა ჩვენ შეგვიძლია გადაადგილება ხელმძღვანელი უკავშირდება სიაში ასევე 12. ასე რომ საკმაოდ მსგავსია, რაც ჩვენ აკეთებდნენ ერთად საგნით დაკავშირებული სიები, გარდა ზედმეტი ნაბიჯი დამაკავშირებელი ძველი ხელმძღვანელი სია თავში ახალი ხელმძღვანელი სიაში. 

ახლა მოდით საბოლოოდ წაშლა კვანძის ეხლა უკავშირდება სიაში. ასე ვთქვათ ჩვენ ზოგიერთი სხვა ფუნქცია, რომელიც მოძიებაში კვანძის გვინდა წაშლა და მოგვცა მაჩვენებელი ზუსტად კვანძის, რომ ჩვენ გვინდა წაშლა. ჩვენ კი არ need-- ამბობენ, უფროსი გლობალურად კვლავ განაცხადა. ჩვენ არ გვჭირდება ხელმძღვანელი აქ. ყველა ეს ფუნქცია აკეთებს, რომ ჩვენ ი მაჩვენებელი ზუსტად კვანძის ჩვენ გსურთ, თავი დაეღწია. მოდით დავაღწიოთ მას. ეს არის ბევრი ადვილია ორმაგად დაკავშირებული სიები. , პირველი ის, ფაქტობრივად, მხოლოდ რამდენიმე რამ. ჩვენ უბრალოდ უნდა დააფიქსიროს მიმდებარე კვანძების "მითითებას, რომ მათ გამოტოვოთ კვანძის გვინდა წაშლა. და მაშინ ჩვენ შეგვიძლია წაშლა რომ კვანძის. ასე რომ, კიდევ ერთხელ, ჩვენ უბრალოდ გადის აქ. ჩვენ, როგორც ჩანს, გადაწყვიტა, რომ ჩვენ გვინდა წაშლა კვანძის X. ისევ და ისევ, რაც მე აკეთებს აქ, რომ way-- არის ზოგადი საქმე კვანძი, რომელიც არის შუა. არსებობს რამდენიმე დამატებითი აპირებს, რომ თქვენ უნდა განიხილოს, როდესაც თქვენ წაშლის თავიდანვე სია ან ბოლომდე სიაში. არსებობს რამდენიმე სპეციალური კუთხეში შემთხვევაში გაუმკლავდეთ არსებობს. 

ასე რომ, ეს მუშაობს წაშლის ნებისმიერი კვანძის ამ შუა list-- ერთი, რომ აქვს ლეგიტიმური მაჩვენებელი წინ და ლეგიტიმური მაჩვენებელი უკან, ლეგიტიმური წინა და შემდეგი მაჩვენებელი. კიდევ ერთხელ, თუ თქვენ სამუშაო მთავრდება, თქვენ უნდა გაუმკლავდეს იმ ოდნავ განსხვავებულად, და ჩვენ არ ვაპირებთ გაიგო, რომ ახლა. მაგრამ თქვენ ალბათ შეუძლია გაერკვნენ, თუ რა სჭირდება უნდა გაკეთდეს მხოლოდ თვალს ამ ვიდეო. 

ასე რომ, ჩვენ იზოლირებული X. X კვანძის გვინდა წაშლა სიიდან. რას ვაკეთებთ? პირველ რიგში, ჩვენ უნდა rearrange გარე მითითებას. ჩვენ უნდა rearrange 9 შემდეგი გამოტოვოთ 13 და წერტილი 10-- რომელიც არის ის, რაც ჩვენ უბრალოდ გაკეთდეს. ჩვენ ასევე უნდა rearrange 10-ის წინა უნდა აღვნიშნო, რომ 9 ნაცვლად მიუთითებს 13. 

ასე რომ კიდევ ერთხელ, ეს იყო სქემა უნდა დაიწყოს. ეს იყო ჩვენი ჯაჭვი. ჩვენ უნდა გამოტოვოთ 13 მაგრამ ჩვენ უნდა ასევე შეინარჩუნოს მთლიანობის სიაში. ჩვენ არ გვინდა, რომ დაკარგავს ნებისმიერი ინფორმაცია ორივე მიმართულებით. ასე რომ, ჩვენ უნდა rearrange პოინტერები ყურადღებით ასე რომ, ჩვენ არ დაარღვიოს ჯაჭვი ყველა. 

ასე რომ, ჩვენ შეგვიძლია ვთქვათ, 9 მომდევნო მაჩვენებელი მიუთითებს, რომ ერთი და იგივე ადგილზე რომ ცამეტი ს შემდეგი მაჩვენებელი მიუთითებს ახლავე. იმის გამო, რომ ჩვენ საბოლოოდ აპირებს გსურთ გამოტოვოთ 13. ასე რომ, სადაც 13 ქულა შემდეგი, თქვენ მინდა ცხრა აღვნიშნო ნაცვლად. ასე რომ, რომ. და მაშინ, სადაც 13 ქულა უკან რომ, რასაც მოდის ადრე 13 ჩვენ გვინდა 10 აღვნიშნო რომ ნაცვლად 13. ახლა შეამჩნია, თუ თქვენ დაიცვას ისრები, ჩვენ ვერ ჩამოაგდეს 13 გარეშე რეალურად დაკარგვის ნებისმიერი ინფორმაცია. ჩვენ ინახება მთლიანობის სია, მოძრავი ორივე წინ და უკან. და მაშინ ჩვენ შეგვიძლია მხოლოდ ერთგვარი საქართველოს გაწმენდა ეს ცოტა უბიძგებენ სია ერთად. ასე რომ, ჩვენ გადალაგება მითითებას ორივე მხარეს. და მაშინ ჩვენ გათავისუფლდა X The კვანძი, რომელიც შეიცავს 13 და ჩვენ არ დაარღვიოს ჯაჭვი. ასე რომ, ჩვენ გავაკეთეთ კარგი. 

შენიშვნა აქ დაკავშირებული სიები. ასე რომ, ორივე singly- და ორმაგად დაკავშირებული სიები, როგორც ჩვენ ვნახეთ, მხარდაჭერა ნამდვილად ეფექტური ჩასმა და წაშლა ელემენტები. თქვენ შეგიძლიათ საკმაოდ ბევრი ეს მუდმივი დროს. რა გააკეთა, ჩვენ უნდა გავაკეთოთ წაშლა ელემენტს მხოლოდ მეორე წინ? გადავედით ერთი მაჩვენებელი. გადავედით ერთი მაჩვენებელი. ჩვენ გათავისუფლდა რომ X სამი ოპერაციებში. იგი ყოველთვის იღებს სამ ოპერაციების წაშლა, რომ კვანძის გასათავისუფლებლად კვანძის. 

როგორ უნდა ჩადოთ? ასევე, ჩვენ უბრალოდ ყოველთვის tacking დასაწყისში თუ ჩვენ ჩასმა ეფექტურად. ამიტომ, ჩვენ უნდა rearrange-- დამოკიდებულია თუ ის singly- და ორმაგად დაკავშირებული სია, ჩვენ შეიძლება უნდა გავაკეთოთ სამი ან ოთხი ოპერაციების მაქს. მაგრამ ერთხელ, ის ყოველთვის სამი ან ოთხი. არ აქვს მნიშვნელობა, რამდენი ელემენტები ჩვენს სიაში, ის ყოველთვის სამი ან ოთხი ოპერაციები ისევე წაშლა ყოველთვის სამი ან ოთხი ოპერაციებში. ეს მუდმივი დრო. ასე რომ, ნამდვილად დიდი. 

მასივები, ვაკეთებდით რაღაც ჩასაგდები დალაგების. თქვენ, ალბათ, გახსოვთ, რომ ჩასმა ერთგვარი არ არის მუდმივი დრო ალგორითმი. ეს, ფაქტობრივად, საკმაოდ ძვირი. ასე რომ, ეს არის უკეთესი ჩასმა. მაგრამ, როგორც აღვნიშნე, საგნით დაკავშირებული სიაში ვიდეო, ჩვენ მივიღეთ downside აქ ძალიან, არა? ჩვენ დავკარგეთ უნარი შემთხვევით წვდომის ელემენტებს. ჩვენ არ შეგვიძლია ვთქვათ, მინდა ელემენტის ნომერი ოთხი ან ელემენტის ნომერი 10 უკავშირდება სიაში ანალოგიურად, რომ ჩვენ შეგვიძლია გავაკეთოთ, რომ მასივი ან ჩვენ შეგვიძლია მხოლოდ პირდაპირ ინდექსი ჩვენს მასივი ის ელემენტს. 

ასე რომ, ცდილობს იპოვოს ელემენტს უკავშირდება list-- თუ ჩხრეკის important-- შეიძლება ახლა მიიღოს წრფივი დროს. როგორც სიაში იღებს აღარ, შეიძლება მიიღოს დამატებით ერთი ნაბიჯი თითოეული ელემენტის სიაში იმისათვის, რომ იპოვოს ის, რაც ჩვენ ვეძებთ. ასე რომ, სავაჭრო ღ. არსებობს ცოტა პრო და con ელემენტი აქ. 

და ორმაგად დაკავშირებული სიები არ არიან ბოლო სახის მონაცემები სტრუქტურა კომბინაცია რომ ჩვენ ვსაუბრობთ, მიმდინარე ყველა ძირითადი შენობა ბლოკების C აყენებს ერთად. იმის გამო, რომ ის ფაქტი, რომ ჩვენ შეგვიძლია კიდევ უკეთესია, ვიდრე ეს შექმნათ მონაცემთა სტრუქტურა, რომელიც თქვენ შეძლებთ მოძებნოთ მეშვეობით მუდმივი დროს ძალიან. მაგრამ უფრო, რომ სხვა ვიდეო. 

მე Doug Lloyd. ეს არის CS50.