ბმული სიები

მასივს შუაში ჩასასმელად ელემენტების ნახევრის წანაცვლება სჭირდება. ბმული სია კი უბრალოდ ორ მიმთითებელს გადააბამს. სწორედ ამ სტრუქტურაზე დგას LRU ქეში, გაუქმების (undo) ისტორია და მეხსიერების გამომყოფის თავისუფალი ბლოკების სია.

დამწყები⏱ 8 წთ

←ეყრდნობა

1მასივები და დინამიური მასივებიბმული სია მასივის O(1) ინდექსაციას ცვლის ნებისმიერ ადგილას O(1) ჩასმაზე.

გზას უხსნის→

3რიგი (FIFO) და დეკირიგი შეიძლება იყოს ბმული სია თავისა და ბოლოს მიმთითებლებით.5ხეები: ცნებები, თვისებები, შემოვლებიხის წვერო იგივე ბმული სიის კვანძია, ერთის ნაცვლად რამდენიმე მიმთითებლით.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01მიმთითებლებით გადაბმული კვანძები

მასივი ერთი უწყვეტი ბლოკია, ამიტომ a[i]-ის მისამართი მარტივი არითმეტიკაა: base + i · size. სწორედ ამიტომაა ინდექსით წვდომა O(1).

ბმული სია ამ ბლოკზე უარს ამბობს. ყოველი ელემენტი საკუთარ კვანძში ცხოვრობს, რომელსაც ორი ველი აქვს: value და მომდევნო კვანძზე მიმთითებელი next. კვანძები მეხსიერებაში ნებისმიერ ადგილას შეიძლება იყოს. ჩვენ მხოლოდ პირველ კვანძზე მიმთითებელს ვინახავთ (head), ბოლო კვანძი კი null-ზე მიუთითებს.

ფასი წვდომაა: მე-5 ელემენტამდე მისასვლელად head-იდან უნდა დავიწყოთ და next ოთხჯერ გავიაროთ. მოკლე გზა არ არსებობს, ამიტომ წვდომა და ძებნა O(n) ღირს.

02ჩასმა და წაშლა გადაბმით

თუ p კვანძზე მიმთითებელი უკვე ხელთ გვაქვს, მის შემდეგ ახალი n კვანძის ჩასასმელად ორი მინიჭება კმარა:

n.next = p.next
p.next = n

არცერთი ელემენტი არ გადაადგილდება, ამიტომ ეს O(1)-ია სიის სიგრძის მიუხედავად. p-ის მომდევნო კვანძის წაშლა ერთი მინიჭებაა: p.next = p.next.next. სათავის წაშლა: head = head.next.

მინიჭებების რიგს მნიშვნელობა აქვს. თუ ჯერ p.next = n-ს დავწერთ, სიის დანარჩენ ნაწილზე ერთადერთი მიმთითებელი გადაიწერება და კუდი დაიკარგება. ეს ბმული სიის კლასიკური შეცდომაა. კოდის წერამდე ყუთები და ისრები ქაღალდზე დახატე.

ჯერ მწვანე კავშირი ყენდება, მერე ლურჯი; წითელი კავშირი ქრება.

03სახეობები და როდის გამოვიყენოთ

ორმხრივ ბმულ სიას prev მიმთითებელიც აქვს, ამიტომ ორივე მიმართულებით სიარული შეიძლება და კვანძის წაშლა O(1)-ში, თუ მხოლოდ ეს კვანძი გვაქვს. C++-ის std::list ორმხრივი ბმული სიაა. წრიულ სიაში ბოლო კვანძი ისევ სათავეს უერთდება.

პრაქტიკაში უმეტესად მასივი (vector) იგებს: ის კომპაქტურია, პროცესორის ქეშს კი უწყვეტი მეხსიერება უყვარს, ამიტომ O(n) წანაცვლებაც ხშირად უფრო სწრაფია, ვიდრე მიმთითებლებზე ხტუნვა. ბმული სია მაშინ აირჩიე, როცა კვანძებზე მიმთითებლებს ინახავ და მათ გარშემო ხშირად სვამ ან შლი: მაგალითად, LRU ქეში (ჰეშ-ცხრილი + ორმხრივი სია) ან სიების O(1)-ში შეერთება.

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

ფასი ერთი შეხედვით

i-ურ ელემენტზე წვდომაO(n)

ძებნაO(n)

ჩასმა / წაშლა ცნობილ კვანძთანO(1)

ჩასმა თავშიO(1)

დაიმახსოვრე

ბმული სია ყოველ ელემენტს კვანძში ინახავს, რომელიც შემდეგზე მიუთითებს, ამიტომ კვანძები უწყვეტად განლაგებული არ უნდა იყოს.
ჩასმა და წაშლა უკვე ხელთ არსებულ კვანძთან O(1)-ია, მაგრამ პოზიციამდე მისვლა ან ძებნა O(n)-ია.
ჩასმისას ჯერ ახალი კვანძი სიის დანარჩენ ნაწილს მიაბი და მხოლოდ მერე გადაამისამართე წინა კვანძი, თორემ კუდი დაიკარგება.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: დააკვირდი ჩასმას: ახალი კვანძი next მიმთითებელს მანამ იღებს, სანამ ძველი კვანძი გადამისამართდება. სცადე ისეთი მნიშვნელობის ძებნა, რომელიც სიაში არ არის.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

ცალმხრივი ბმული სია

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

ფსევდოკოდი

 1 node: { value, next } 2 traverse: follow next pointers  // O(n), no random access 3 insert after p: create node n 4   n.next = p.next; p.next = n   // order matters! 5 delete head: head = head.next   // O(1)

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

p კვანძის შემდეგ n კვანძის ჩასასმელად მინიჭებების რომელი რიგია სწორი?

№2

ბევრი შემთხვევითი k-სთვის k-ურ ელემენტზე სწრაფი წვდომა გჭირდება. რომელი სტრუქტურა?

№3

სიაა 12 → 5 → 8 → 23 და ასრულებ head = head.next. როგორი გახდა სია?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeReverse Linked List დამწყები↗LeetCodeMerge Two Sorted Lists დამწყები↗LeetCodeLinked List Cycle დამწყები↗LeetCodeRemove Nth Node From End of List საშუალო↗