[მუსიკის დაკვრა] DOUG LLOYD: OK, ასე რომ, ამ ეტაპზე, რა თქმა უნდა, ჩვენ დაფარული ბევრი საფუძვლებს C. ჩვენ ვიცით, ბევრი ცვლადები, მასივები, პოინტერები, ყველა რომ კარგი პერსონალი. ისინი ყველა სახის აშენებული სანახავად, როგორც საფუძვლები, მაგრამ ჩვენ შეგვიძლია გავაკეთოთ მეტი, არა? ჩვენ შეგვიძლია დააკავშიროთ რამ ერთად საინტერესო გზები. ასე რომ, მოდით გავაკეთოთ, რომ, მოდით დავიწყოთ ფილიალი რა C გვაძლევს, და დაიწყოს, რათა შევქმნათ ჩვენი საკუთარი მონაცემები სტრუქტურების გამოყენებით ამ შენობაში ბლოკები ერთად, რომ რამე მართლაც ღირებული, სასარგებლო. ერთი გზა, ჩვენ შეგვიძლია ამის გაკეთება არის ვისაუბროთ კოლექცია. ასე რომ, ჯერჯერობით, ჩვენ გვქონდა ერთი სახის მონაცემები სტრუქტურა წარმოადგენს კოლექციები მოსწონს ღირებულებები, მსგავსი ღირებულებები. ეს იქნება მასივი. ჩვენ გვყავს კოლექციები რიცხვებით, ან კოლექციების გმირები და ასე შემდეგ. სტრუქტურებში ასევე დასალაგებლად მონაცემები სტრუქტურა ინფორმაციის შეგროვება, მაგრამ ეს არ არის შეგროვება ღირებულებები. ეს, როგორც წესი მიქსები სხვადასხვა მონაცემთა ტიპები ერთად შიგნით ერთი ყუთი. მაგრამ ეს არ არის თავად გამოიყენება ჯაჭვის ერთად ან აკავშირებს მსგავსი ნივთები, როგორიცაა მასივი. მასივები დიდი ელემენტის ეძებოთ, მაგრამ გავიხსენოთ ის, რომ ძალიან რთული ჩადეთ მასივი, თუ ჩვენ ჩასმა ზე ბოლომდე რომ მასივი. და საუკეთესო მაგალითად მე მაქვს რომ არის ჩანართი ჯიშია. თუ გავიხსენებთ ჩვენი ვიდეო on Insertion დალაგების, იყო ბევრი ხარჯზე ჩართული, რომელსაც შეარჩიო ელემენტები, და გადაიტანოს მათ იმ გზას, რათა შეწყობოდა რაღაც შუა თქვენი მასივი. კოლექტორები ასევე განიცდიან სხვა პრობლემა, რომელიც მოუქნელობის. როდესაც ვაცხადებთ მასივი, ჩვენ კიდევ ერთი ესროლეს. ჩვენ კიდევ უნდა ვთქვა, მე მინდა ეს ბევრი ელემენტები. შეიძლება 100, შესაძლოა, 1,000, შესაძლოა, იყოს x, სადაც x არის ნომერი, რომელიც მომხმარებელს მოგვცა საათზე სწრაფად და ბრძანებათა ონლაინ. მაგრამ ჩვენ მხოლოდ ერთი გასროლით ის, რომ ჩვენ არ მიიღოთ, მაშინ ამბობენ oh, რეალურად მე საჭიროა 101, ან მჭირდებოდა x + 20. ძალიან გვიან, ჩვენ უკვე გამოაცხადა მასივი, და თუ ჩვენ გვინდა, რომ 101 ან x + 20, ჩვენ უნდა განაცხადოს სრულიად განსხვავებული მასივი, დააკოპირეთ ყველა ელემენტების მასივი მეტი, ხოლო შემდეგ ჩვენ გვაქვს საკმარისი. და თუ ჩვენ ვცდებით კიდევ ერთხელ, რა თუ ჩვენ რეალურად უნდა 102, ან x + 40, ჩვენ უნდა გავაკეთოთ ეს კიდევ ერთხელ. ასე რომ, ისინი ძალიან მოუქნელი ამისთვის resizing ჩვენი მონაცემებით, მაგრამ თუ ჩვენ გავაერთიანებთ ერთად რამდენიმე საფუძვლებს, რომ ჩვენ უკვე შეიტყო მითითებას და სტრუქტურები, კერძოდ გამოყენებით დინამიური მეხსიერების განაწილების ერთად malloc, ჩვენ შეგიძლიათ განათავსოთ ამ ცალი ერთად რათა შეიქმნას ახალი მონაცემები სტრუქტურა ცალკე უკავშირდება სიაში ჩვენ შეიძლება ვთქვათ რომელიც საშუალებას გვაძლევს, რომ იზრდება და შემცირება კოლექცია ღირებულებები და ჩვენ არ გვაქვს რაიმე შეეწირა სივრცეში. ასე რომ კიდევ ერთხელ, ჩვენ მოვუწოდებთ ამ იდეას, ეს ცნება, უკავშირდება სიაში. კერძოდ, ეს ვიდეო ჩვენ ვსაუბრობთ ცალკე უკავშირდება სიაში, და შემდეგ კიდევ ერთი ვიდეო ვისაუბრებთ შესახებ ორმაგად უკავშირდება სიები, რომელიც მხოლოდ ვარიაცია აქ. მაგრამ ცალკე უკავშირდება სიაში შედგება კვანძების, კვანძების მხოლოდ იმიტომ, რომ აბსტრაქტული term-- ეს უბრალოდ რაღაც მე მოუწოდებენ რომ არის ერთგვარი სტრუქტურა, ძირითადად, მე? უბრალოდ აპირებს ეძახით კვანძის და ეს კვანძის აქვს ორი წევრი, ან ორი სფეროებში. მას აქვს მონაცემები, როგორც წესი, რიცხვი, ხასიათი float, ან შეიძლება იყოს ზოგიერთი სხვა მონაცემები ტიპი რომ თქვენ განსაზღვრული ტიპის Def. და იგი შეიცავს მომცეთ სხვა კვანძის იმავე ტიპის. ასე რომ, ჩვენ გვაქვს ორი რამ შიგნით ამ კვანძის, მონაცემები და მომცეთ სხვა კვანძის. და თუ თქვენ ვიზუალიზაციისთვის ამ, შეგიძლიათ ვიფიქროთ, რომ ეს მოსწონს ჯაჭვის კვანძების რომ დაკავშირებული ერთად. ჩვენ გვყავს პირველი კვანძის, შეიცავს მონაცემებს, და მომცეთ მეორე კვანძი, რომელიც შეიცავს მონაცემები და მომცეთ მესამე კვანძის. და ამიტომაც ჩვენ მას დაკავშირებული სიაში, ისინი დაკავშირებულია ერთად. რას ნიშნავს ეს სპეციალური კვანძის სტრუქტურა გამოიყურებოდეს? ისე, თუ გახსოვთ, ჩვენი ვიდეო განსაზღვრის საბაჟო ტიპის, ტიპის Def, ჩვენ შეგვიძლია განვსაზღვროთ სტრუქტურა და ტიპი განსაზღვრავს სტრუქტურა მოსწონს ეს. tyepdef struct sllist, და მაშინ მე გამოყენებით სიტყვა მნიშვნელობა აქ თვითნებურად მიუთითოს მონაცემები ტიპის ნამდვილად. თქვენ შეიძლება გაიაროს მთელი რიცხვი ან float, თქვენ შეიძლება ჰქონდეს, რაც გაგიხარდებათ. ის არ შემოიფარგლება მხოლოდ მთელი რიცხვები, ან რამე მსგავსი. ასე რომ მნიშვნელობა მხოლოდ თვითნებური მონაცემები ტიპის, და შემდეგ მაჩვენებელი სხვა კვანძის იმავე ტიპის. ახლა, იქ ცოტა დაჭერა აქ განსაზღვრის სტრუქტურა როდესაც ის თვითმმართველობის რეფერენტული სტრუქტურა. მაქვს აქვს დროებითი სახელი ჩემი სტრუქტურა. ბოლოს დღეს მე ნათლად გვინდა, რომ მას sll კვანძის, რომ საბოლოო ჯამში, ახალი ასახელებს ნაწილი ჩემი ტიპის განმარტება, მაგრამ მე ვერ გამოიყენებს sll კვანძის შუა ეს. მიზეზი ისაა, რომ მე არ ის ტიპის მოუწოდა კვლავ კვანძის სანამ მოხვდა საბოლოო წერტილი აქ. მანამდე, მე უნდა ჰქონდეს კიდევ ერთი გზა ეხება ამ მონაცემების ტიპის. და ეს არის თვითმმართველობის რეფერენტული მონაცემები ტიპის. ეს; s მონაცემთა ტიპის სტრუქტურა, რომელიც შეიცავს მონაცემებს, და მომცეთ სხვა სტრუქტურა იგივე ტიპის. ასე რომ, მე უნდა შეეძლოს მიმართოს მონაცემთა ამ ტიპის დროებით მაინც, ასე რომ, რაც მას დროებითი სახელი struct sllist საშუალებას აძლევს ჩემთვის, მაშინ ამბობენ მე მინდა მომცეთ კიდევ ერთი struct sllist, არის struct sllist ვარსკვლავი, და მაშინ მას შემდეგ, რაც მე დასრულდა განმარტება, მე ახლა ამ ტიპის sll კვანძი. ასე რომ, რატომ ხედავთ იქ დროებითი სახელი აქ, მაგრამ მუდმივი სახელი აქ. ზოგჯერ თქვენ შეიძლება ნახოთ განმარტებები სტრუქტურა, მაგალითად, რომ არ არის თვითმმართველობის რეფერენტული, რომელიც არ აქვს specifier სახელი აქ. ეს, უბრალოდ, ვამბობთ typedef struct, ღია Curly გაუწიოს და შემდეგ განსაზღვრავს მას. მაგრამ თუ თქვენ struct თვითმმართველობის რეფერენტული, როგორც ეს ერთი არის, თქვენ უნდა მიუთითოთ დროებითი ტიპის სახელი. მაგრამ, საბოლოო ჯამში, ახლა რომ ჩვენ გავაკეთეთ ეს, ჩვენ შეგვიძლია უბრალოდ ეხება ამ კვანძების, ამ ერთეულების, როგორც sll კვანძების მიზნებისათვის დანარჩენი ამ ვიდეო. ყველა უფლება, ჩვენ ვიცით, როგორ შექმნა უკავშირდება სია კვანძში. ჩვენ ვიცით, როგორ უნდა განისაზღვროს დაკავშირებული სიაში კვანძის. ახლა, თუ ჩვენ ვაპირებთ დავიწყოთ გამოყენებით მათ შეაგროვოს ინფორმაცია, არსებობს რამდენიმე ოპერაციის ჩვენ უნდა გვესმოდეს, და მუშაობა. ჩვენ უნდა ვიცოდეთ, თუ როგორ უნდა შექმნათ უკავშირდება სიაში გამოწოვილი. თუ არ არსებობს სია უკვე, ჩვენ გვინდა, რომ დაიწყოს ერთი. ასე რომ, ჩვენ უნდა შეეძლოს უნდა შეიქმნას უკავშირდება სია, ჩვენ უნდა ალბათ ძიება ბმულის სია მოვძებნოთ ელემენტი ჩვენ ვეძებთ. ჩვენ უნდა შეძლებს ჩადეთ ახალი რამ შევიდა სიაში, ჩვენ გვინდა, რომ ჩვენი სია შეძლებს იზრდება. და ანალოგიურად, ჩვენ გვინდა, რომ შეძლებს წაშლა რამ ჩვენი სიიდან, ჩვენ გვინდა, რომ ჩვენი სია შეძლებს შემცირება. და ბოლოს, ჩვენი პროგრამები, განსაკუთრებით თუ გავიხსენებთ, რომ ჩვენ დინამიურად გამოყოფის მეხსიერება უნდა ავაშენოთ ეს სიები, როგორც წესი, ჩვენ გვინდა გასათავისუფლებლად ყველა რომ მეხსიერება როდესაც ჩვენ გავაკეთეთ მუშაობა მას. ასე რომ, ჩვენ უნდა შეეძლოს წაშლა მთელი უკავშირდება სიაში ერთ ვერ swoop. მოდით გავლა ზოგიერთი ოპერაციების და როგორ შეიძლება ვიზუალურად მათ, საუბარი pseudocode კოდი კონკრეტულად. ასე რომ, ჩვენ გვინდა, რომ შეიქმნას უკავშირდება სია, იქნებ ჩვენ გვინდა განსაზღვრავს ფუნქცია ეს პროტოტიპი. sll კვანძის ვარსკვლავი, შექმნა, და მე გავლით ერთი არგუმენტი, ზოგიერთი თვითნებური მონაცემები ჩაწერეთ ერთხელ, ზოგიერთი თვითნებური მონაცემები ტიპის. მაგრამ მე returning-- ეს ფუნქცია უნდა დამიბრუნდება მაჩვენებელი, რომ ცალკე დაკავშირებული სიაში კვანძის. კიდევ ერთხელ, ჩვენ ვცდილობთ, რომ შევქმნათ უკავშირდება სიაში გამოწოვილი, ასე რომ მე უნდა მომცეთ რომ სიაში, როდესაც მე გაკეთდეს. ასე რომ, რა ნაბიჯები ჩართული აქ? ისე, პირველი, რაც მე აპირებს არის დინამიურად გამოყოს ფართი ახალი კვანძის. კიდევ ერთხელ, ჩვენ ქმნის გარეთ თხელი ჰაერის, ამიტომ ჩვენ უნდა malloc ფართი იგი. და რა თქმა უნდა, მაშინვე მას შემდეგ, რაც ჩვენ malloc, ჩვენ ყოველთვის შემოწმება, რათა დავრწმუნდეთ, რომ ჩვენი მაჩვენებელი ჩვენ არ დაუბრუნდება null. იმიტომ, რომ თუ ჩვენ ვცდილობთ და პარადიგმები, ტერმინოლოგიური null მაჩვენებელი, ჩვენ ვაპირებთ, რომ განიცდიან segfault და ჩვენ არ გვინდა, რომ. ამის შემდეგ ჩვენ გვინდა შეავსოთ სფეროში, ჩვენ გვინდა ინიციალიზაცია ღირებულება სფეროში და ინიციალიზაცია მომდევნო სფეროში. და შემდეგ ჩვენ გვინდა, რომელთა მიზანია, საბოლოო ჯამში, როგორც ფუნქციის პროტოტიპი indicates-- ჩვენ გვინდა დაბრუნების მომცეთ sll კვანძი. ასე რომ, რაც ამ ჰგავს ვიზუალურად? ისე, პირველი ჩვენ ვაპირებთ, რომ დინამიურად გამოყოს ფართი ახალი sll კვანძის, ასე რომ, ჩვენ malloc--, რომ ვიზუალური წარმომადგენლობა კვანძის ჩვენ შევქმენით. ჩვენ შეამოწმებს დარწმუნდით ეს არ null, ამ შემთხვევაში, სურათზე არ აქვს ნაჩვენები იყო თუ არა ეს null, ჩვენ არ ამოიწურა მეხსიერება, ასე რომ, ჩვენ კარგი წასასვლელად. ასე რომ, ახლა ჩვენ შესახებ გადადგას C, ინიციალიზაცია კვანძების მნიშვნელობა სფეროში. ისე, ამ ფუნქციის მოვუწოდებთ მე აქ გამოყენებით, ჰგავს მე მინდა გავლა, 6, ასე რომ, მე 6 ღირებულება სფეროში. ახლა, ინიციალიზაცია მომდევნო სფეროში. ისე, რა ვარ მე აპირებს ესაქმებათ, არაფერი არ არის შემდეგი, უფლება, ეს არის ერთადერთი, რაც ამ სიაში. რა არის შემდეგი რამ სიაში? ეს არ უნდა აღვნიშნო, რომ არაფერს, მარჯვნივ. იქ სხვა არაფერი არსებობს, ასე რომ, რა არის კონცეფცია ჩვენ ვიცით, რომ nothing-- მითითებას არაფერი? ეს უნდა იყოს იქნებ ჩვენ გვინდა დააყენოს null კურსორი იქ, და მე წარმოადგენს null მაჩვენებელი, როგორც მხოლოდ წითელი ყუთი, ჩვენ არ შეგვიძლია წავიდეთ რაიმე. როგორც ვნახავთ ცოტა მოგვიანებით, გვექნება საბოლოოდ ჯაჭვების ისრებით დამაკავშირებელი ამ კვანძების ერთად, მაგრამ როდესაც თქვენ მოხვდა წითელი ყუთი, რომ null, ჩვენ არ შეგვიძლია რაიმე, რომ ბოლოს სიაში. და ბოლოს, ჩვენ უბრალოდ გვინდა დააბრუნოს მომცეთ ამ კვანძის. ასე რომ, ჩვენ მოვუწოდებთ მას ახალი, და დაბრუნდება new ასე რომ, ეს შეიძლება იყოს გამოყენებული ყოველი ფუნქცია შექმნა. ასე რომ იქ წასვლა, ჩვენ შევქმენით ცალკე დაკავშირებული სიაში კვანძის გამოწოვილი, და ახლა ჩვენ გვაქვს სია შეგვიძლია ვიმუშაოთ. ახლა, ვთქვათ, უკვე აქვს დიდი ჯაჭვი, და ჩვენ გვინდა რაღაც მას. და ჩვენ გვინდა, ფუნქცია, რომ აპირებს დაბრუნდეს ჭეშმარიტი ან მცდარი, დამოკიდებულია თუ არა მნიშვნელობა არსებობს, რომ სიაში. ფუნქციის პროტოტიპი, ან დეკლარაციის ფუნქცია, შეიძლება გამოიყურებოდეს ამას bool იპოვოს და მაშინ ჩვენ გვინდა გავლა ორი არგუმენტები. პირველი არის მომცეთ პირველ ელემენტს უკავშირდება სიაში. ეს არის რეალურად რაღაც თქვენ ყოველთვის გვინდა, რომ შევინარჩუნოთ სიმღერა, და რეალურად შეიძლება იყოს ის, რომ თქვენ კი დააყენა გლობალური ცვლადი. მას შემდეგ, რაც თქვენ შექმნით სია, თქვენ ყოველთვის, ყოველთვის გვინდა, რომ შევინარჩუნოთ სიმღერა ძალიან პირველ ელემენტს სიაში. ამ გზით თქვენ შეგიძლიათ ეხება ყველა სხვა ელემენტების მიერ მხოლოდ შემდეგ ჯაჭვი, გარეშე შენარჩუნება პოინტერები უცვლელი თითოეული ელემენტს. თქვენ მხოლოდ უნდა შევინარჩუნოთ სიმღერა პირველი ერთ-ერთი, თუ ისინი ყველა მიჯაჭვული ერთად. და მერე მეორე, რაც ჩვენ გავლის ერთხელ არის თვითნებურად, რაღაც რასაც მონაცემები ტიპის ჩვენ ეძებს არსებობს შიგნით იმედია ერთ კვანძების სიაში. ასე რომ, რა არის ამისათვის საჭირო? ისე, პირველი, რასაც ვაკეთებთ არის ჩვენ ვქმნით განივი მაჩვენებელი მიუთითებს, რომ სიები ხელმძღვანელი. ისე, რატომ უნდა გავაკეთოთ, რომ, ჩვენ უკვე აქვს მაჩვენებელი სიები ხელმძღვანელი, რატომ არ გვაქვს უბრალოდ გადაადგილება, რომ ერთი გარშემო? ისე, როგორც მე უბრალოდ განაცხადა, ეს მართლაც მნიშვნელოვანია ჩვენთვის ყოველთვის შენარჩუნება სიმღერა პირველი ელემენტია სიაში. ასე რომ, ეს რეალურად უკეთესი უნდა შეიქმნას დუბლიკატი, რომ და გამოიყენოს, რომ გადაადგილება, ამიტომ ჩვენ არასდროს შემთხვევით გადაადგილება დაშორებით, ან ჩვენ ყოველთვის მომცეთ რაღაც მომენტში რომ არის უფლება პირველი ელემენტის სიაში. ასე რომ, უმჯობესია, რათა შეიქმნას მეორე, რომ ჩვენ ვიყენებთ გადაადგილება. მაშინ ჩვენ უბრალოდ შედარების თუ არა ღირებულება სფეროში, რომ კვანძის არის ის, რაც ჩვენ ვეძებთ, და თუ ეს არა, ჩვენ უბრალოდ გადაადგილება, რათა მომდევნო კვანძის. ჩვენ აკეთეთ, რომ მეტი და მეტი და მეტი, სანამ ჩვენ ან იპოვოს ელემენტი, ან ჩვენ მოხვდა null-- ჩვენ მიაღწია ბოლოს სია და ის იქ არ არის. ეს უნდა იმედია ბეჭედი ზარი თქვენ, როგორც მხოლოდ წრფივი ძებნა, ჩვენ უბრალოდ გამრავლების ეს საგნით უკავშირდება სია სტრუქტურა ნაცვლად გამოყენებით მასივი ამის გაკეთება. ასე რომ, აქ არის მაგალითი იმისა, საგნით უკავშირდება სიაში. ეს ერთი შედგება ხუთ კვანძების, და ჩვენ გვაქვს მომცეთ ხელმძღვანელი სია, რომელსაც სიაში. პირველი, რაც ჩვენ უნდა გავაკეთოთ არის ერთხელ, შექმნა, რომ გასვლის მაჩვენებელი. ასე რომ, ახლა ჩვენ გვაქვს ორი პოინტერები რომ წერტილი იგივე. ახლა, აქ, ასევე, მე არ უნდა malloc ნებისმიერი ფართი trav. მე არ ვამბობ, trav ტოლია malloc რაღაც, რომ კვანძის უკვე არსებობს, რომ სივრცეში მეხსიერებაში უკვე არსებობს. ასე რომ, ყველა მე რეალურად აკეთებს არის კიდევ ერთი მომცეთ იგი. მე არ mallocing დამატებითი სივრცე, უბრალოდ ახლა ორ მითითებას მიუთითებს, რომ იგივე. ასე რომ, 2, რასაც ვეძებ? ისე, არა, ასე ნაცვლად მე ვარ აპირებს გადავიდეს მომდევნო ერთი. ასე რომ, ძირითადად მე ვიტყოდი, trav ტოლია trav მომავალი. 3 რა ვეძებ, არ. ასე რომ, მე კვლავაც გაგრძელდება მეშვეობით, სანამ საბოლოოდ დან 6 რაც ვეძებ ამისთვის საფუძველზე ფუნქცია ზარი მაქვს ზედა არსებობს, და ამიტომ მე გაკეთდეს. ახლა, რა, თუ ელემენტს მე ეძებენ არ არის სიაში, არის ის კვლავ იმუშავებს? ისე, შეამჩნია, რომ სიაში აქ არის ნაზი განსხვავებული, და ეს არის კიდევ ერთი რამ, რომ მნიშვნელოვანი უკავშირდება სიები, თქვენ არ უნდა შეინარჩუნოს მათ კონკრეტული მიზნით. თქვენ შეგიძლიათ, თუ გნებავთ, მაგრამ თქვენ ალბათ უკვე შენიშნა რომ ჩვენ არ შენახვა სიმღერა რა რაოდენობის ელემენტს ჩვენ ვიმყოფებით. და ეს არის ერთგვარი ერთი სავაჭრო, რომ ჩვენ აქვს უკავშირდება სია ლექსები მასივები, არის ის, რომ ჩვენ არ გვაქვს წვდომის აღარ. ჩვენ ვერ ვიტყვით, მინდა წასვლა 0th ელემენტს, ან მე -6 ელემენტის ჩემი მასივი, რაც შემიძლია მასივი. მე ვერ ვიტყვი, მინდა წასვლა 0th ელემენტი, ან მე -6 ელემენტს, ან 25 ელემენტის ჩემი უკავშირდება სია, არ არსებობს ინდექსი მათთან ასოცირებული. ასე რომ, ეს ნამდვილად არ აქვს თუ ჩვენ ვიცავთ ჩვენს სიაში მიზნით. თუ გსურთ თქვენ რა თქმა უნდა შეიძლება, მაგრამ არსებობს არ არსებობს მიზეზი, თუ რატომ უნდა იყოს დაცული ნებისმიერი თანმიმდევრობით. ასე რომ კიდევ ერთხელ, მოდით, ვცადოთ და მოვძებნოთ 6 ამ სიაში. ისე, ჩვენ იწყება იწყება, ჩვენ ვერ 6, და მაშინ ჩვენ გავაგრძელებთ არ მოძიებაში 6, სანამ საბოლოოდ მისაღებად აქ. ასე რომ, ახლა trav რაოდენობა კვანძის შეიცავს 8, და ექვსი არ არსებობს. ასე რომ შემდეგი ნაბიჯი იქნება წასვლა მომდევნო მაჩვენებელი, ასე ვთქვათ, trav ტოლია trav მომავალი. ისე, trav შემდეგი, მიერ მითითებულ წითელი ყუთი იქ, null. ასე რომ, არსად წასვლა, და ამიტომ ამ ეტაპზე შეგვიძლია დავასკვნათ, რომ ჩვენ მიაღწია ბოლოს უკავშირდება სია, და 6 არ არსებობს. და ეს იქნება დაბრუნდა ცრუ ამ შემთხვევაში. OK, როგორ უნდა ჩაწეროთ ახალი კვანძის შევიდა უკავშირდება სიაში? ასე რომ, ჩვენ შევძელით შექმნა უკავშირდება სიაში აქედან არსად, მაგრამ ჩვენ, ალბათ, სურს ავაშენოთ ჯაჭვის და არა შექმნა bunch of მკაფიო სიები. ჩვენ გვინდა, რომ ერთ-ერთი სია, რომელიც აქვს რამოდენიმე კვანძების ის, არ არის bunch of სიები ერთი კვანძის. ასე რომ, ჩვენ არ შეგვიძლია უბრალოდ შეინახოს გამოყენებით შექმნა ფუნქცია ჩვენ განსაზღვრული ადრე, ახლა ჩვენ გსურთ ჩადეთ შევიდა სია, რომელიც უკვე არსებობს. ასე რომ, ამ შემთხვევაში, ჩვენ ვაპირებთ გაივლის ორ არგუმენტს, მომცეთ უფროსმა უკავშირდება სიაში, რომ ჩვენ გვინდა, რომ დაამატოთ. ისევ და ისევ, ამიტომ ეს ასე მნიშვნელოვანია, რომ ჩვენ ყოველთვის შენარჩუნება სიმღერა, იმიტომ, რომ ეს არის ერთადერთი გზა, ჩვენ ნამდვილად უნდა მიმართოს მთელი სია მხოლოდ მომცეთ პირველ ელემენტს. ასე რომ, ჩვენ გვინდა, რომ გაივლის მომცეთ, რომ პირველი ელემენტი, და რაც ღირებულების ჩვენ გსურთ დაამატოთ სიაში. და საბოლოოდ, ამ ფუნქციის დაბრუნებას აპირებს მომცეთ ახალი ხელმძღვანელი უკავშირდება სიაში. რა ნაბიჯები ჩართული აქ? ისე, ისევე, როგორც, შექმნა, ჩვენ უნდა დინამიურად გამოყოფს ფართი ახალი კვანძის და შემოწმება, რათა დარწმუნებული ვარ, ჩვენ არ ამოიწურა მეხსიერება, კიდევ ერთხელ, რადგან ჩვენ გამოყენებით malloc. ამის შემდეგ ჩვენ გვინდა მოეყვანა და ჩადეთ კვანძის, ასე რომ ნომერი, რასაც val არის, შევიდა კვანძი. ჩვენ გვინდა, რომ ჩასასმელად კვანძის დროს დასაწყისში უკავშირდება სიაში. არ არსებობს მიზეზი, რომ მე მინდა ამის გაკეთება, და ეს შეიძლება იყოს ღირს აღების მეორე პაუზის ვიდეო აქ, და იმაზე, თუ რატომ მე მინდა ჩადეთ დასაწყისში უკავშირდება სიაში. ისევ და ისევ, მე ზემოთ აღინიშნა, რომ ეს ნამდვილად არ აქვს მნიშვნელობა, თუ ჩვენ შევინარჩუნოთ ის ნებისმიერი იმისათვის, ასე რომ შესაძლოა, რომ ნახავ. და დაინახა, რა მოხდება, თუ ჩვენ მინდოდა, რომელთა მიზანია ან უბრალოდ მეორე წინ, როდესაც ჩვენ ვაპირებთ მეშვეობით საძიებო თქვენ ვერ ვხედავ, თუ რა შეიძლება მოხდება, თუ ჩვენ ვცდილობდით ჩადეთ ბოლოს სიაში. იმიტომ, რომ ჩვენ არ გვაქვს მომცეთ ბოლოს სიაში. ასე რომ, იმ მიზეზით, რომ მე მინდა, ჩადეთ დასაწყისში, იმიტომ, რომ მე შემიძლია ამის გაკეთება დაუყოვნებლივ. მე მომცეთ დასაწყისში და ჩვენ დავინახავთ, ეს ვიზუალური მეორე. მაგრამ თუ მინდა ჩადეთ ბოლოს, მე უნდა დაიწყოს დასაწყისში, traverse ყველა გზა ბოლოს და ბოლოს, და მაშინ დაყენება იგი. ასე რომ, ეს ნიშნავს იმას, რომ ჩასმა ბოლოს სია გახდება o ო ოპერაცია, ბრუნდება ჩვენი განხილვის გამოთვლითი სირთულის. ეს მინდა გახდეს o ო ოპერაცია, სადაც როგორც სიაში მიიღო დიდი და უფრო დიდი, და დიდი, ეს კიდე უფრო და უფრო რთული Tack რაღაც წლის ბოლოს. მაგრამ ეს ყოველთვის ძალიან ადვილი მადლობა რაღაც დასაწყისში, თქვენ ყოველთვის დასაწყისში. ჩვენ დავინახავთ, ვიზუალური ამ ერთხელ. და მერე კიდევ ჩვენ გავაკეთეთ, ერთხელ ჩვენ შეიყვანეს ახალი კვანძის, ჩვენ გვინდა დაბრუნდეს ჩვენი მომცეთ ახალი ხელმძღვანელი უკავშირდება სიაში, რომელიც მას შემდეგ, რაც ჩვენ ჩასმა ზე იწყება, რეალურად იყოს მომცეთ კვანძის ჩვენ შევქმენით. მოდით ვიზუალიზაციისთვის, იმიტომ, რომ მე ვფიქრობ, რომ დაეხმაროს. ასე რომ, აქ ჩვენს სიაში, იგი შედგება ოთხი ელემენტები, კვანძის შემცველი 15 რომელიც მიუთითებს კვანძის შეიცავს 9, რომელიც მიუთითებს კვანძის შემცველი 13 რომელიც მიუთითებს კვანძის შემცველი 10, რომელსაც აქვს null მაჩვენებელი, როგორც მისი მომავალი მაჩვენებელი ასე რომ, ბოლოს სიაში. ასე რომ, ჩვენ გვინდა ჩადეთ ახალი კვანძის ღირებულების 12 დასაწყისში ეს სიაში, რა ვქნათ? ისე, პირველი ჩვენ malloc ფართი კვანძის და შემდეგ ჩვენ დააყენა 12 იქ. ასე რომ, ახლა ჩვენ მიაღწია გადაწყვეტილება წერტილი, არა? ჩვენ გვაქვს რამდენიმე მითითებას, რომ ჩვენ შეგვიძლია გადაადგილება, რომელიც ერთი უნდა ჩვენ გადაადგილება პირველი? თუ ჩვენ 12 წერტილი ახალი ხელმძღვანელი list-- ან მაპატიეთ, უნდა მიიღოს 12 აღვნიშნო, რომ ძველმა უფროსმა სიაში? ან უნდა ითქვას, რომ სიაში ახლა იწყება 12. აქ არის განსხვავება იქ, და ჩვენ მოუთმენლად რა ხდება, როგორც მეორე. მაგრამ ეს იწვევს კარგი თემა sidebar, რაც არის, რომ ერთ-ერთი trickiest რამ უკავშირდება სიები არის მოწყობა პოინტერები სწორი მიზნით. თუ თქვენ გადატანა რამ მწყობრიდან, თქვენ შეგიძლიათ დასრულდება up შემთხვევით orphaning დანარჩენი სიაში. აქ არის მაგალითი, რომ. მოდით წავიდეთ ერთად იდეა of-- ასევე, ჩვენ უბრალოდ ის 12. ჩვენ ვიცით, 12 იქნება ახალი ხელმძღვანელი სიაში, და რატომ არ ვართ, უბრალოდ გადაადგილება სია მომცეთ აღვნიშნო. OK, ასე რომ კარგია. ასე რომ, ახლა სად 12 მომდევნო ეტაპზე? ვგულისხმობ, ვიზუალურად, ჩვენ ვხედავთ, რომ ეს იქნება აღვნიშნო, რომ 15, როგორც ადამიანებს ეს მართლაც ნათელია ჩვენთვის. როგორ კომპიუტერი ვიცი? ჩვენ არ გვაქვს, არაფერი მიუთითებს 15 აღარაა, არა? ჩვენ დავკარგეთ რაიმე უნარი ეხება 15. ჩვენ არ შეგვიძლია ვთქვათ, ახალი arrow შემდეგი ტოლობის რაღაც, იქ არაფერი არ არსებობს. ფაქტობრივად, ჩვენ ობოლი დანარჩენი სია ამით ჩვენ შემთხვევით გატეხილი ჯაჭვი. ჩვენ ნამდვილად არ გვინდა, რომ. მოდით დავუბრუნდეთ და ცდილობენ ამ ერთხელ. იქნებ სწორი საქციელი არის მითითებული 12 მომდევნო მაჩვენებელი ძველი ხელმძღვანელს სიაში პირველი, მაშინ ჩვენ შეგვიძლია გადაადგილება სია დასრულდა. და სინამდვილეში, ეს არის სწორი იმისათვის, რომ ჩვენ უნდა დაიცვას, როდესაც ჩვენ მუშაობის საგნით უკავშირდება სიაში. ჩვენ ყოველთვის გვინდა დაკავშირება ახალი ელემენტი შევიდა სიაში, სანამ ჩვენ, რომ სახის მნიშვნელოვანი ნაბიჯი შეცვლის სადაც ხელმძღვანელი უკავშირდება სია. კიდევ ერთხელ, რომ ასეთი ფუნდამენტური რამ, ჩვენ არ გვინდა, რომ დაკარგავს სიმღერა იგი. ამიტომ, ჩვენ გვინდა დავრწმუნდეთ, რომ ყველაფერი მიჯაჭვული ერთად, სანამ ჩვენ გადასვლა, რომ მაჩვენებელი. ასე რომ, ეს იქნება სწორი მიზნით, რომელიც დააკავშირებს 12 სიას, მაშინ ვთქვათ, რომ სია იწყება 12. თუ ჩვენ განაცხადა სია იწყება 12 და მაშინ სცადა დაკავშირება 12 სიას, ჩვენ უკვე ვნახეთ, რა ხდება. ჩვენ დასაკარგი სია შეცდომა. OK, ასე რომ კიდევ ერთი რამ უნდა ვისაუბროთ. რა მოხდება, თუ ჩვენ გვინდა, რომ თავი დაეღწია მთელი უკავშირდება სიაში ერთდროულად? კიდევ ერთხელ, ჩვენ mallocing ყველა ამ სივრცეში, და ამიტომ ჩვენ უნდა გავათავისუფლოთ, როდესაც ჩვენ გავაკეთეთ. ასე რომ, ახლა გვინდა წაშლა მთელი უკავშირდება სიაში. ისე, რა გვინდა გავაკეთოთ? თუ ჩვენ მიაღწია null მაჩვენებელი, ჩვენ გვინდა, რომ შეწყვიტოს, წინააღმდეგ შემთხვევაში, ვშლით დანარჩენი სიაში და შემდეგ გამათავისუფლონ. წაშალე დანარჩენი სიაში, და მერე გასათავისუფლებლად მიმდინარე კვანძში. რას გავს, რა ტექნიკა უნდა ჩვენ ვისაუბრეთ ადრე აკეთებს, რომ გავს? წაშალე ყველას სხვას, მაშინ დავბრუნდებით და წაშლა ჩემთვის. ეს არის ის, უკან, ჩვენ გააკეთა პრობლემა ცოტა პატარა, ჩვენ ვამბობთ, წაშლა ყველას სხვაგან, მაშინ თქვენ შეგიძლიათ წაშალოთ ჩემთვის. და შემდგომი ქვემოთ გზა, რომ კვანძის იტყვის, წაშლა ყველას სხვას. მაგრამ საბოლოოდ ჩვენ მისაღებად წერტილი, სადაც სიაში null, და ეს არის ჩვენი ბაზის შემთხვევაში. მოდით შევხედოთ ამ, და როგორ შეიძლება მუშაობა. ასე რომ, აქ ჩვენს სიაში, ის იგივე მიუთითეთ ჩვენ უბრალოდ ვსაუბრობთ, და იქ ნაბიჯები. არსებობს ბევრი ტექსტი აქ, მაგრამ იმედია ვიზუალიზაცია დაეხმარება. ასე რომ, ჩვენ ჰქონდეს და მე ასევე გამოყვანილია ჩვენი დასტის ფარგლებში ილუსტრაცია ჩვენი ვიდეო ზარის stacks, და იმედია ეს ყველაფერი ერთად გამოჩნდება, თუ რა ხდება. ასე რომ, აქ არის ჩვენი pseudocode კოდი. თუ ჩვენ მივაღწევთ null მაჩვენებელი, შეჩერება, წინააღმდეგ შემთხვევაში, წაშლა დანარჩენი სიაში, შემდეგ გასათავისუფლებლად მიმდინარე კვანძში. ასე რომ, ახლა, list-- მაჩვენებელი, რომ ჩვენ გავლის განადგურება რაოდენობა 12. 12 არ არის null მაჩვენებელი, ამიტომ ჩვენ ვაპირებ წაშლა დანარჩენი სიაში. რა არის წაშლის დანარჩენი ჩვენთვის ჩართული? ისე, ეს იმას ნიშნავს, მიღების დარეკეთ განადგურება და განაცხადა, რომ 15 დასაწყისში დანარჩენი სიაში ჩვენ გვინდა განადგურება. ასე რომ, დარეკეთ განადგურება 12 სახის ახდენენ. ეს გაყინული არ ელოდება დარეკეთ განადგურება 15, დაასრულოს თავისი სამუშაო. ისე, 15 არ არის null მაჩვენებელი, და ასე რომ, ის აპირებს ამბობენ, ყველა უფლება, ასევე, წაშლა დანარჩენი სიაში. დანარჩენი სია იწყება 9, და ამიტომ ჩვენ უბრალოდ დაველოდოთ თქვენ წაშლა ყველა, რომ პერსონალი, მაშინ დავბრუნდებით და წაშლა ჩემთვის. ისე 9 თქმას, ასევე, მე არ ვარ null მაჩვენებელი, ასე წაშლა დანარჩენი სიის აქ. ასე რომ ცდილობენ და განადგურება 13. 13 ამბობს, მე არ ვარ null მაჩვენებელი, იგივე, ის გადის მამალი. 10 არ არის null მაჩვენებელი, 10 შეიცავს null მაჩვენებელი, მაგრამ 10 არ არის თვითონ null მაჩვენებელი ახლა, და ასე რომ გადის მამალი ძალიან. და ახლა ჩამოვთვალოთ რაოდენობა არსებობს, ეს მართლაც აღვნიშნო, რომ, რაღაც თუ მქონდა მეტი სივრცე გამოსახულება, ეს აღვნიშნო, რომ გარკვეული შემთხვევითი სივრცეში რომ ჩვენ არ ვიცით, რა არის. ეს null მაჩვენებელი, თუმცა, სიაში ფაქტიურად არის მითითებული, რომ ეს ღირებულებები null. ეს მიუთითებს უფლება შიგნით რომ წითელი ყუთი. ჩვენ მიაღწია null მაჩვენებელი, ამიტომ ჩვენ ვერ შეაჩერებს, და ჩვენ გავაკეთეთ. ასე რომ, purple ჩარჩო, ახლა დროს ზევით დასტის, რომ აქტიური ჩარჩო, მაგრამ ეს კეთდება. თუ ჩვენ მიაღწია null მაჩვენებელი, შეწყვიტოს. ჩვენ არ არაფერი, ჩვენ ვერ გასათავისუფლებლად null მაჩვენებელი, ჩვენ არ malloc რაიმე სივრცეში, და ამიტომ ჩვენ გავაკეთეთ. ასე რომ ფუნქცია ფარგლებში განადგურებულია და ჩვენ resume-- ჩვენ შეარჩიო, სადაც დავტოვეთ off ერთად მომდევნო უმაღლესი ერთი, რომელიც ეს არის მუქი ლურჯი ჩარჩო აქ. ასე რომ, ჩვენ შეარჩიო უფლება, სადაც შეჩერდით. ჩვენ წაშლილია დანარჩენი სია უკვე, ასე რომ, ახლა ჩვენ ვაპირებ გასათავისუფლებლად მიმდინარე კვანძების. ასე რომ, ახლა ჩვენ შეგვიძლია გასათავისუფლებლად ამ კვანძის, და ახლა ჩვენ მიაღწია ბოლომდე ფუნქცია. და ისე, რომ ფუნქცია ფარგლებში განადგურებულია, და ჩვენ შეარჩიო ცისფერს. ასე რომ, ეს says-- მე უკვე done-- წაშლის დანარჩენი სიაში, ასე გასათავისუფლებლად მიმდინარე კვანძში. ახლა ყვითელი ჩარჩო უკან ზევით Stack. ასე რომ, როგორც ხედავთ, ჩვენ ახლა განადგურება სია მარჯვნიდან მარცხნივ. რა მოხდებოდა, თუმცა, თუ ჩვენ ისეთი რამ არასწორი გზა? ისევე, როგორც, როდესაც ჩვენ შევეცადეთ დაამატოთ ელემენტს. თუ ჩვენ არევა ჯაჭვი, თუ ჩვენ არ აკავშირებს პოინტერები სწორი მიზნით, თუ ჩვენ უბრალოდ გაათავისუფლა პირველ ელემენტს, თუ ჩვენ უბრალოდ გაათავისუფლა სიის თავში, ახლა ჩვენ სხვა გამოსავალი არ ეხება დანარჩენი სიაში. ასე რომ, ჩვენ არ გვაქვს ობოლი ყველაფერი, ჩვენ ექნებოდა რა არის მოუწოდა მეხსიერების გაჟონვის. თუ გავიხსენებთ ჩვენი ვიდეო დინამიური მეხსიერების გამოყოფის, ეს არ არის ძალიან კარგი რამ. ასე რომ, როგორც ვთქვი, არსებობს რამდენიმე ოპერაცია რომ ჩვენ უნდა გამოვიყენოთ მუშაობა დაკავშირებული სიაში ეფექტურად. თქვენ შეიძლება არ შეამჩნია, მე გამოტოვებული ერთი, წაშლის ერთ ელემენტს უკავშირდება სიაში. ამის მიზეზი მე რომ არის ის, ფაქტობრივად სახის სახიფათო ვიფიქროთ იმაზე, როგორ წაშლა ერთ ელემენტს საწყისი საგნით უკავშირდება სიაში. ჩვენ უნდა შეეძლოს გამოტოვოთ რაღაც სიაში, რომელიც ნიშნავს მივიღებთ point-- ჩვენ გსურთ წაშალოთ ეს კვანძის მაგრამ იმისათვის, რომ ეს ასე რომ, ჩვენ არ კარგავს ნებისმიერი ინფორმაცია, ჩვენ უნდა დაკავშირება კვანძის აქ, აქ. ასე რომ, მე ალბათ გააკეთა, რომ არასწორი საწყისი ვიზუალური პერსპექტივა. ასე რომ, ჩვენ დასაწყისში ჩვენი სია, ჩვენ გამომდინარე მეშვეობით, გვინდა წაშლა ამ კვანძში. თუ ჩვენ უბრალოდ წაშლა, ჩვენ გატეხილი ჯაჭვი. ეს კვანძი აქ ეხება ყველაფერი, ის შეიცავს ჯაჭვის აქ out. ასე რომ, ის, რაც ჩვენ უნდა გავაკეთოთ რეალურად შემდეგ მივიღებთ, რომ ამ ეტაპზე, არის, რომ ჩვენ უნდა უკან დახევას ერთი, და დაკავშირება ამ კვანძის მეტი ამ კვანძის, ასე რომ ჩვენ შეგვიძლია შემდეგ წაშლა ერთი შუა. მაგრამ საგნით უკავშირდება სიები არ მოგვაწოდოთ გზა მიდის უკან. ამიტომ, ჩვენ უნდა ან შენარჩუნება ორ მითითებას და გადაადგილება მათ ერთგვარი off ნაბიჯი, ერთი უკან სხვა, როგორც ჩვენ წავიდეთ და მისაღებად, და შემდეგ კიდევ ერთი მაჩვენებელი მეშვეობით. და როგორც ხედავთ, ეს შეიძლება კიდევ ცოტა რთული. საბედნიეროდ, ჩვენ გვაქვს სხვა გზა გაუმკლავდეთ, რომ, როდესაც ვსაუბრობთ ორმაგად დაკავშირებული სიები. მე Doug Lloyd, ეს არის CS50.