სტრუკტურული მონაცემები. (სია - List)

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

სტრუკტურული მონაცემები იმდენად მნიშვნელოვანია, რომ რთულად დაიჯერებთ ალბათ, მაგრამ ის ჩვენ ყოველ-დღიურ ცხოვრებასაც აუმჯობესებს. აუმჯობესებს ცხოვრების დონეს, ხშირად სიცოცხლესაც არჩენს, ბევრმა ამ იდეით შეპყრობილმა ადამიანმა უზარმაზარი კომპანიებიც კი  შექმნეს. (მაგ: Google.com). ალბათ რთულად მისახვედრია სტრუკტურულ მონაცემს რა კავშირი აქვს ცხოვრების დონესთან ან მის გადარჩენასთან.

 წარმოიდგინეთ შემდეგი სიტუაციები.

·        შედიხართ თქვენ საყვარელ ვებ-გვერდზე,  შესვლის მომენტში სერვერი ძიებას იწყებს საკუთარ მონაცემთა ბაზაში რომ გადაამოწმოს არსებობს თუ არა მსგავსი მონაცემებით ადამიანი, თუ არსებობს უშვებს , თუ არა და რეგისტრაციას თავაზობს. ახლა წარმოიდგინეთ რო სერვერზე 4 მილიარდი ადამიანის ინფორმაცია ინახება. სწორი ალგორითმის და სტუკტურული მონაცემის შერჩევით ეს ყველაფეირ მოხდება 0 წამში, არა სწორი  სტრუკტურის და ალგორითმის შერჩევით სამსახურიდან გიშვებენ და 100 წლით უკან თუ გადავინაცვლებთ დროში, თქვენ საყვარელ ფსევდო ვერ გვერდზე დაახლოებით 10 საუკუნეში შეხვალთ, როცა სერვერი გადაამოწმებს 4 მილიარდ მოსახლეს დედამიწაზე.  დრო = ფულს,  „სტრუკტურული მონაცემები შემოსავლის წყაროა“

·        რეკავთ სასწრაფო დახმარების ნომერზე (112). როგორც კი ზარი შედის დაწესებულებაში, სასწრაფო დახმარების სერვერი ნომერს ადარებს მის მონაცემთა ბაზაში მყოფ ნომრებს რათა დაადგინოს პიროვნების სახელი, გვარი და მისამართი, ამით პოლიციის, სასწრაფო დახმარების და სახანძრო სამსახურის თანამშრომლებს ეძლევათ საშუალება მოახდინონ გამოძახებაზე დროული რეაგირება, შეიძლება ადამიანი ვინც რეკავს იმდენად ცუდათ არის, რომ ვერ ახერხებს მისამართის დასახელებას.  დაგვიანება ამ შემთხვევაში = გარდაცვალებას. „სტრუკტურული მონაცემები სიცოცხლეს არჩენენ “.

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

                             

მომდევნო ბლოგებში განვიხილავთ ყველაზე გამოყენებად სტრუკტურულ მონაცემებს, ისეთებს როგორიც არის List, LinkedList, ArrayList, Vector, Dictionary, Set, Map, Stack, HashTable,  Queue, Heaps, AA Trees and AVL Trees , RBD Trees, ტრევერსირების მაგალითებს Tree traversal Algorithms – BFS and DFS,  და სხვა მნიშვნელოვან დეტალს, რომელზე სტრუკტურა დგას. 

     როდესაც სტრუკტურულ მონაცემებზე ვსაუბრობთ, მნიშვნელოვანია ვიცოდეთ სხვაობა, სტრუკტურული მონაცემების ინტერფეის და მის იმპლემენტაციას შორის, როგორც წესი ინტერფეისი აღწერს თუ რას აკეთებს სტრუკტურა, მისი იმპლემენტაცია კი ამბობს როგორ აკეთებს ამას . ინტერფეისი ამ შემთხვევაში არის ADT (Abstract Data Type) ის ერთია თითქმის ყველა ენაში. ADT-ს მეშვეობით ჩვენ ვადგენთ ფუნქციების ერთობას, ტიპებს, რა ტიპით მუშაობს, რა ტიპს აბრუნებს დ ა.შ , მისი შიგთავსის მოდიფიკაციას კი კონკრეტული კლასი ან კლასები ახდენენ, შემოკლებით CDT(Concrete Data Type) მაგალითისთვის. List ინტერფეის გააჩნია get(), set(), add(), remove(), size() მეთოდები, რომელსაც გააჩნია ტიპები, პარამეტრები და Return Type, ნებისმიერი კლასი რომელიც მის იმპლემენტაციას მოახდენს, გადაწერს მეთოდებს დეფინრიებულს List-ში, კლას თუ ქვია Link ან Array სიასთან შერწყმის მერე გახდება LinkedList და ArrayList. ADT მოქმედების პრინციპი მარტივი და მოქნილია. თუ გაგიჭირდათ წარმოდგენა რა არის ADT , რეალური ცხოვრების მაგალითს მოვიყვან, წიგნი არის აბსტრაკტული ტიპის დატა, კულინარიის წიგნი, მათემატიკის წიგნი, ფიზიკის წიგნი კი არიან წიგნის კონკრეტული იმპლემენტაციები. 

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

როგორც ხედავთ საბაზისო ინტერფეისები არის SET, LIST, QUEUE, MAP, (Map ინტერფეისი არ არის კოლექციის იერარქიაში, ის ცალკე მდგონი სტრუკტურული მონაცემია) ყველაფერი რაც სტრუკტურულ მონაცემებში არსებობს იქმნება ამ 4 ინტერფეისისგან, აღქმადი დ გასაგები რომ იყოს დავყოფ ბლოგს 4 კატეგორიად და ყველა ინტერფეისის სტრუკტურას ცალ-ცალკე განვიხილავ.  განხილვაში მოექცევიან ძირითადი დ ყველაზე გამოყენებადი სტრუკტურები 4-ვე ინტერფეისიდან. (დეტალურად განხილვა ყველაფრის რაც სტრუკტურულ მონაცემებში არსებობს ფიზიკურად შეუძლებელია ბლოგის პირობებში და აუცილებელიც არ არის, თუ ამას კითხულობ დამწყები პროგრამისტი ხარ და ის ინფორმაცია რასაც ეს ბლოგი მოგცემს სავსებით საკმარისი იქნება რო წარმოდგენა შეგექმნას სტრუკტურაზე, ყველაზე ცუდ შემთხვევაში, ან ჯუნიორ დეველოპერად დაიწყო მუშაობა ყველაზე კარგ შემთხვევაში).

დიდი ნაწილი ჯავა კოლექციების ინახება java.util. ... ; პაკეტში, როგორც ესეთი თქვენ არ ხართ ვალდებული შექმნათ სტრუკტურები ნულიდან, რადგან ჯავას ბიბლიოთეკას ის უკვე შექმნილი მოყვება, თუმცა არის სიტუაციები როდესაც შექმნაც გიწევთ.

                                                     List        Map     Queue      Set

                  

                                                                              List

List ინტერფეისი: სუპერ ინტერფეისები Collection და Iterable.

სტრუკტურები რომლებიც შექმნილია List ინტერფეისისგან, ArrayList, LinkedList, Stack, Vector, AbstractList, AbstractSequqnetialList, AttributeList, RoleList, CopyOnWriteArrayList, RoleUnresolvedList, ბევრი ამათგან ახდენს იმპლიმენტირებას სხვა სუპერ ინტერფეისების და კლასების. ყველაზე გამოყენებადი სტრუკტურები არის ArrayList, LinkedList, Vector, Stack.

                                                                             LinkedList

  კომპიუტერულ მეცნიერებაში დაკავშირებული სიები არის წრფივი კოლექცია ელემენტების, რომლებიც ერთმანეთან დაკავშირებული არიან მიმთითებლებით(ცვლადებით) და ინახებიან კვანძებში(nodes).  ყველა კვანძი მეხსიერებაში ინახავს ინფორმაციას რომელიც დაკავშირებულია შემდეგ კვანძთან,  კვანძები ერთად წარმოადგენენ თანმიმდევრობას. მარტივი ენით რომ ავხსნათ , ყველა კვანძი ინახავს ინფორმაციას და რეფერენციულ  ცვლადს რომელიც მიგვითითებს შემდეგ ინფორმაციაზე მეხსირებაში.  ამ სახით ინფორმაციის შენახვა,  პროგრამისტებს საშუალებას აძლევს ეფეკტურად დაამატონ და წაშალონ მონაცემები მეხსიერებიდან. გაიხსენეთ მასივები, მასივი არის განსაზღვრული სიდიდის სტრუკტურული მონაცემი, მას ინფორმაციას ვერ დავამატებთ და  ვერ მოვაკლებთ, როგორც წესი, თუ დეფინრიებული გვაქ მასივი 10 ელემენტით, ის 10 ელემენტი იქნება მიუხედავად ყველაფრისა(გზები არსებობს თუ როგორ დავამატოთ და მოვაკლოთ მასივს ელემენტი) გამომდინარე აქედან, დაკავშირებული სიების პრინციპული უპირატესობა მასივთან არის ის, რომ მას ადვილად ვამატებთ და ვაკლებთ ელემენტს, მაგალითისთვის, თუ მასივში რამის შეცვლა გვინდა მთლიან მასივთან უნდა ვიმუშაოთ, ყველა ელემენტი უნდა დავამუშაოთ, მოვახდინოთ როტაციები და ა.შ. დაკავშირებულ სიებთან კი ამის აუცილებლობა არ არსებობს რადგან ის მეხსიერებაში ინახება არა თანმიმდევრულად. ნახეთ მაგალითი ფოტოზე.

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

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

უკეთ რო გავერკვეთ რა არის ელემენტი და რა არის მიმთითებელი, რომელსაც კვანძი ინახავს უნდა დაუბრუნდეთ მასივს, როგორც მაღლა ავღნიშნე, მასივი მეხსიერებაში ინახება თანმიმდევრულად. როდესაც კომპილატორი ხედავს რო იქმება მასივი, ის მეხსიერებაში ეძებს ზუსტად იმ სიდიდის ადგილს, რამდენიც დეფინირებული მასივის ალოკაციისთვის არის საჭირო, ახდენს მის რეზერვირებას ინიცირებული  ელემენტებისთვის, ან იმ ელემენტებისთვის რომელიც ჯერ არ არის ინცირებული, მაგრამ მომავალში მოხდება მისი ინიციალიზაცია. მაგალითად int[] a = {1,2,3} ამ შემთხვევაში ზუსტად იცის კომპილატორმა რო 3 ელემენტია მასივში და ახდენს 12 სლოტის გამოყოფას, int [] a = new int[100]; a[0] = 1; a[1] =2; a[2] = 3; ინიციალიზაცია მოხდა 12 სლოტის მაგრამ კომპილატორმა მასივისთვის გამოყო 400 სლოტი და დანარჩენი 388 სლოტი ცარიელია.  ამ ყველაფერში საინტერესო არის ის , თუ როგორ ხდება მეხსიერებაში თანმიმდევრულად განლაგებულ ელემენტებს შორის კავშირი, ანუ საიდან იცის [1] მასივმა რო მისი შემდეგი ელემენტი [2] მასივშია? დააკვირდით ფოტოს:

შემდეგ ელემენტზე მიმთითებელი მასივში არის თვითონ სლოტი, 8 ფოტოზე მოთავსებულია 101,102,103,104 სლოტებე, მისი მიმთიტებელი კი არის 101, რომელიც მიუთითებს 105 ნომერ სლოტზე სადაც შემდეგი ელემენტია მასივის შენახული, წარმოიდგინეთ კონტეინერი,

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

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

დააკვირდით როგორ არის მიმოფანტული ელემენტები მეხსიერებაში, 8,6,7 და 5 არის ელემენტი, რომლებიც იმყოფებიან გამოყოფილ სლოტებში, ყველა ელემენტის პირველი სლოტის ნომერი არის რეფერენცია შემდეგი ელემენტის, კონტეინერი რომელიც ინახავს არსებულ რეფერენციას, ელემენტს და შემდეგ რეფერენციას არის Node.

რეალურ პროგრამირებაში რა თქმა უნდა სლოტის ნაცვლად რეფერენციულ ცვლადს გამოიყენებთ. ნახეთ მაგალითი:

ფოტოზე ხედავთ Node-ის შექმნის მაგალითს, რომელიც მიიღებს ელემენტს და რეფერენციულ ცვლადს, ელემენტს შეინახავს Object და რეფერენციული ცვლადი(მიმთითებელი) შეინახავს დასახელებას რომელიც მიგვითითებს შემდეგ ელემენტზე მეხსიერებაში. უფრო გამარტივების მიზნით ვნახოთ ჯავა ბიბლიოთეკის მიერ შემოთავაზებული დაკავშირებული სიები. 

ჯავა ბიბლიოთეკის თანახმად სიას შეუძლია შეინახოს ნებისმიერი სახის ელემენტი, რადგან მუშაობს რეფერენციული ტიპის დატასთან, Object,  String, Integer, Double და ა.შ არ აგერიოთ პრიმიტიული ტიპის დატაში, int, double, short და ა.შ რეფერენციული ტიპის დატასთან მუშაობას განაპირობებს null-ის მიღების აუცილებლობა, მეხსიერებას ვერ გავანულებთ, მას ვა- null-ებთ. თუ მაგალითების ნახვის დროს წავაწყდით პრიმიტიული ტიპის დატას , მხოლოდ და მხოლოდ ინდექსის მოძებნის მიზნით.

არსებობს სამი სახის დაკავშირებული სია და ესენია:

Singly Linked List:

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

Doubly Linked List

სადაც ელემენტების ძიება ხდება ორმხრივად, ხშირად ბოლო ელემენტს პროგრამისტები tail -ს ეძახიან, პირველ ელემენტს კი head-ს.

Circular Linked List

მასში ბოლო ელემენტი მიუთითებს პირველ ემემენტზე. ან პირიქით.

შესაძლებელია Circular Linked List-ის გამოყენება Single Linked List-ან, ისევე როგორც Doubly Linked List-ან.

1 როგორ ხდება ელემენტის დამატება სიაში:

ახსნა განმარტებას არ საჭიროებს, საკმაოდ მარტივია.

2 შესაძლებელია ელემენტების სიის თავში ან ბოლოში დამატება:

კომპილირების შემდგომ:

3. შესაძლებელია ყველა ელემენტის სხვა სიაში გადატანა.

ამის შემდგომ შესაძლებელია პირველი სიის წაშლა, მეორე სია ინახავს ყველაფერს. კომპილირების შემდგომ:

4 შესაძლებელია პირველი, ბოლო და ნებისმიერი ელემენტის წაშლა სიიდან:

კომპილირების შემდგომ:

5 შესაძლებელია ელემენტის ნებისმიერ ინდექსზე ჩანაცვლება, ისევე როგორც შესაძლებელია მთლიანი სიის ნებისმიერ ინდექსზე ჩანაცვლება.

კომპილირების შემდგომ:

6 შესაძლებელია სიის შემოწმება, მისი სიდიდის გაგება, და მთლიანად წაშლა.

კომპილირების შემდგომ:

ყველა მეთოდს და ოპერაციას ვერ განვიხილავთ. რადგან სია ინფორმაცის იღებს 1 კლასის და 4 ინტერფეისისგან. დამატებით მეთოდებს, რომელიც მაგალითებში ვერ მოხვდნენ მიაგნებთ შემდეგ ბმულზე: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

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

მნიშვნელოვანი უპირატესობები სიის:

1.     შეუძლია მიიღოს კოპირებული ელემენტები.

2.     არ ხდება მისი სინქრონიზება

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

4.     ელემენტებთან მუშაობა ხდება სწრაფად, რადგან არ იყენებს ინდექსების სისტემას.

5.     ის შეიძლება გამოყენებულ იქნებს როგორც Stack ან/და Queue

6.     ის არის დინამიური თანმიმდევრობა ელემენტების

LinkedList Time Complexity: add()-O(1), Remove()- O(1) best case, O(n) worst case,   get()-O(N), Contains()- O(n). დეტალურ ყველა სტრუკტურის ალგორითმს მას შემდეგ ნახავთ რაც სათითაოდ გავივლით ინტერფეისებს და კლასებს. 

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

                                             Singly LinkedList From Scratch

სტრუკტურის დეფინირების და იმპლემენტაციის მაგალითი:

კვანძი რომელიც ინფორმაციის მატარებელი იქნება ჩავაბუდოთ კლასში:

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

და დავიწყოთ პირველი მეთოდის შექმნა, რომელიც დაამატებს ინფორმაციას სიას.

1.     Add() მეთოდი:

ეს მეთოდი ახდენს ელემენტის კვანძში დამატებას O(1) ალგორითმით, როგორც ხედავთ არ გვაქ ლუპები რომლებიც მთლიანად ახდენს კვანძის წაკითხვას და შემდგომ დამატებას, ანუ ინფორმაციის შეყვანა ხდება დინამიურად, რაც ძალიან სწრაფია, იმიტომ რომ ინფორმაციის დამატება არ არის დამოკიდებული არსებული ინფორმაციის სიდიდეზე.  პირველ ველზე მეთოდი უბრალოდ იღებს ღირებულებას, შემდეგ ველზე ვეუბნებით თუ სია ცარიელია მაშინ root ცვლადი უდრის  temp ცვლადს, თუ არ არის ცარიელი მაშინ temp ცვლადს ვეუბნებით რომ შემდეგ ცვლადად დასვას root ცვლადი და დაუბრუნდეს საწყისებს. თუ კვანძში შევიყვანთ 1 ის მოექცევა მეხსიერების ძირში, ზემოდან დაემატება 2,3,4,5 და ა.შ.

2.     Get(int index) მეთოდი:

ეს მოთოდი ისვრის გამონაკლის, თუ სია ცარიელია ან სია ნაკლებია ნულზე მაშინ IndexOutOfBoundsException, მეთოდი არ არის დახვეწილი იმიტომ რო ამ ეტაპზე size() მეთოდი არ არის ჯერ შექმნილი, გავითვალისწინე რომ 0-ზე ნაკლები არ უნდა იქნეს, თუმცა გასათვალისწინებელია ისიც რომ სიდიდეზე მეტი არ უნდა იქნეს ინდექსი. If ველზე ამის დამატება მარტივად შეიძლება როცა size() მეთოდს შევქმნით. მეთოდი არის O(N) ალგორითმის მატარებელი. რაგან არ ვიცით თუ რომელი ინდექსიდან მოგვიწევს ელემენტის დაბრუნება, გვიწევს მთლიანი კვაძის გადაკითხვა. 

getLast O(n) და getFirst O(1) მეთოდებს არ განვიხილავთ.  

3.     Set(int index, E value)

და ისევ size() მეთოდი არ არის შექმნილი. მოდით ამ მეთოდის იმპლემენტაცია თქვენ მოახდინეთ,  მინიშნება:  size() მეთოდის პირდაპირ დამატების შემთხვევაში მეთოდი სადაც ახდენთ მის იმპლემენტაციას გამონაკლის ისვრის. შეეცადეთ ამოხსნათ რატომ.  Set მეთოდი კი არის O(N) ალგორითმის მატარებელი.

4.     Size() მეთოდი:

ახსნა განმარტებას არ საჭიროებს, თვლის რამდენი კვანძი გვაქვს და გვიბრუნებს ოდენობას.  ფოტოზე ხედავთ თუ როგორ არ უნდა შექმნათ size მეთოდი, იმიტომ რო მისი შექმნის ბევრად უკეთესი გზაც არსებობს და ამას შემდეგ მაგალითებზე ნახავთ. ეს კონკრეტული მეთოდი კი O(n) ალგორითმის მატარებელია. უკეთესი ვარიანტი კონსტანტურ დროში მუშაობს. 

5.     Contains(E value)

თუ შეყვანილი ინფორმაცია უდრის კვანძში მყოფ იმფორმაციას მაშინ დააბრუნე true წინააღმდეგ შემთხვევაში დააბრუნე false. სამ ცვლადს რატომ ვიყებეთ არ მითქვია ჯერ, root არის ცვლადი რომელიც ყოველთვის მჭირდება კვანძის დასაწყისში,  temporary ცვლადი არის ცვლადი რომელიც მოძრაობს კვანძში ერთი მიმართულებით და previous ცვლადი არის ცვლადი რომელიც იღებს ღირებულებებს, წაკითხულს temporary ცვლადის მიერ. ეს საშუალებას მაძლევს წვდომა მექნეს წინამორბედ და უკან მდგარ ელემენტებზე.

6.     isEmpty() და clear() მეთოდები ყველაზე პატარა მეთოდებია სიაში. რუთ ელემენტის განულება არ შლის ყველა ელემენტს მეხსიერებაში, რომ წაშალოთ უნდა წაიკითხოთ მთლიანი ინფორმაცია და სათითაოდ გაანულოთ კვანძები. მაგრამ ვინაიდან სია მოძრაობს ერთი მიმართულებით, რუთ ცვლადის განულების შემთხვევაში სხვა კვანძებზე მიმთითებელს ვკარგავთ, მეხსიერებაში დარჩენილ კვანძებს კი GC წაშლის. 

თუ ცარიელია true,  წინააღმდეგ შემთხვევაში false

 და მეთოდი რომელიც ანულებს მთლიან სიას.

                                                                Doubly Linked List

წრფივი კოლექცია ელემენტების რომელსაც გააჩნია ორი მიმთითებელი (Head, Tail) კომპიუტერულ მეცნიერებაში ნაცნობია როგორც Doubly Linked List.  Singly Linked List-ან იმით განსხვავდება რომ ყველა კვანძს გააჩნია ორი მიმთითებელი, ერთი მიუთითებს წინ მდგარ ელემენტზე და მეორე მიუთითებს უკან მდგარ ელემენტზე. რო გაგაიდვილდეთ წარმოიდგინეთ ორი ცალი Singly Linked List რომლის გაერთიანებაც ხდება, ერთი სია მოძრაობს წინ და მეორე სია მოძრაობს უკან.  როგორც წესი სია ორი მიმთითებელით ძალიან სწრაფია,  ჯავას ბიბლიოთეკაში მყოფი დაკავშირებული სიები სწორედ ორი მიმთითებლით მუშაობს, თუმცა აქვს უარყოფითი მხარეც და ეს მეხსირების კონტროლს უკავშირდება, ამ ბლოგში აღნიშნულ პრობლემაზე არ ვიაუბრებთ.

სანამ მეთოდებს ვნახავდეთ ნახეთ ფოტო:

ეს არის ყველაზე მარტივი ვარიანტი ორმაგი დაკავშირებული სიის იმპლემენტაციის, არსებობს სხვა და სხვა გზები იმპლემენტაციის, მაგალითად ცარიელი კვანძს შექმნით რომელიც ღირებულების გარეშე იქნება, პირველ და ბოლო ელემენტს კი მისი მეშვეობით მიუთითებთ როგორ იმოქმედონ. ჟარგონულად მსგავს კვანძს პროგრამისტები dummy node-ს ეძახიან. ოფიციალურ ენაზე კი Sentinal Node ქვია.

dummy node-ის გამოყენებით იმპლემენტაცია უფრო მარტივდება. ხშირად მის გამოყენებას ნახავთ Circular Linked List-ის იმპლემენტაციის დროს, Singly და Doubly Linked List-ის გამოყენების დროს მის იმპლემენტაციას არსებითი დანიშნულება არ გააჩნია.  დადებითი მხარე: ა) ამცირებს კოდის მოცულობას. ბ) ზრდის ოპერაციების სისწრაფეს.  უარყოფითი მხარე: ა) ართულებს ოპერაციების წარმოებას კონკურენტული პროგრამირების დროს. 

1.     add()

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

2.     Get()

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

3.     Set()

სეთ მეთოდი გეთ მეთოდის შინაარსის არის, ამიტომ ახსნა განმარტება არ ჭირდება

4.     Size()

საიზ მეთოდის იმპლემენტაცია ამ ფორმით უფრო მართებულია. 

5.     Clear()

მეთოდი რომელიც შლის კვანძებს მეხსიერებიდან ფუნდამენტურად განსხვავდება იგივე მეთოდისგან ცალმხრივად დაკავშირებულ სიაში.  იმიტომ რო ორივე მხრიდან გვიწევს იმფორმაციის წაშლა. ცალმხრივად დაკავშირებულ სიაში საკმარისია დავწეროთ, რომ root = null და დავკარგავთ კავშირს ყველა ელემენტთან, უფრო სწორად ძირითად კვანძს წავშლით და დანარჩენ ელემენტებს GB წაშლის. მაგრამ ორმაგად დაკავშირებული სიის შემთხვევაში, თუ იგივე პრინციპით ვიხელმძღვანელებთ სიას წავშლით ერთი მიმართულებით, მეორე მიმართულებით ის იარსებებს მეხსიერებაში და კომპილირებასაც კი მოახდენს.  ამიტომ პირველი და ბოლო ელემენტის ღირებულებებს ვანიჭებს დროებით ცვლადებს, შემდგომ ვიჭყებთ მოძრაობას ორივე მხრიდან და სათითაოდ ვანულებთ ყველა კვანძს.  ამ მეთოდის იმპლემენტაცია უფრო დახვეწილი ფორმითაც შეიძლება მაგრამ ეს შევარციე საჩვენებლად, რადგან მარტივად აღქმადია.

6.     Compile methods()

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

ალბათ შეამჩნიეთ რო ორმხრივად  დაკავშირებული სია გაცილებით სწრაფია ცალმხრივად დაკავშირებულ სიაზე. სიის თავში და ბოლოში ელემენტების დამატება ხდება კონსტანტური სისწრაფით, წაშლაც ელემენტების ხდება კონსტანტური სისწრაფით, საუკეთესო ვარიანტში, O(n) ალგორითმით ყველაზე ცუდ შემთხვევაში, კონკრეტული ელემენტის სიიდან გამოტაან ხდება O(N/2) სისრაფით, ანუ იმის ნახევარი ჭირდება რაც ჩვეულებრივ სიას. ყველა მეთოდის იმპლემენტაციას ფიზიკურად ვერ გაჩვენებთ მთლიანდ პროეკტს ავტვირთავ GitHub.com-ზე რათა დამატებითი მეთოდების ნახვაც მოახერხოთ.

                                                           Circular Linked List

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

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

მეთოდები:

1.     Add()

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

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

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

 მოცემულ შემთხვაში სიის შემდეგი ელემენტი არის 2,3,4 და ა.შ, მაგრამ სათაო ელემენტის შემდეგი ელემენტი რომელი ელემენტი იქნება? თუ გავითვალისწინებთ იმას რომ სიამ ბოლო ელემენტი 8 შეიყავანა მაშინ სათაო ელემენტის შემდეგი ელემენტი გამოდის 8. 

2.     Get()

გეთ მეთოდში არაფერია განსხვავებული გარდა ერთი ველისა. სიაში ძიება უნდა დავიწყოთ სათაო ელემენტის შემდგი ელემენტიდან (ანუ ბოლო შეყვანილი ელემენტიდან).

3.     Set()

სეთ მეთოდში მნიშვნელოვანი ის არის რომ პირველ და ბოლო ელემენტზე გაგვაჩნია პირდაპირი წვდომა, იტერაციის გარეშე.

4.     Contains & size

Size მეთოდში ყველაფერი გასაგებია, contains მეთოდში, პირველ და ბოლო ელემენტს ვწვდებით და ვამოწმებთ იტერაციის გარეშე, getLastElement, getFirstElement მეთოდები ცალკე მაქ დეფინირებული და მათ იმპლემენტირებას ვახდენ სადაც მჭირდება. ბოლოში კი უბრალოდ ვეძებთ სასურველ ელემენტს.

5.     isEmpty & clear

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

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

                                                                      ArrayList

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

მისი გამოყენება მართებულია მაშინ როცა არ იცით თქვენი მასივი რა სიდიდის ინფორმაციას მიიღებს. მნიშვნელოვანი ინფორმაცია  მასიურ სია-ზე.

· ის არის სწრაფი რადგან ბაზირებულია ინდექსების სისტემაზე, ელემენტის დამატება, გამოტანა,  ჩანაცვლება და რამოდენიმე სხვა მნიშვნელოვანი ოპერაცია ხდება კონსტანტურ დროში. O(1).

·        ის არ არის სინქრონიზებული.

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

·        ის აკონტროლებს ელემენტების მეხსირებაში შესვლის პროცეს.

·        შეუძლია იქონიოს დუბლირებული ელემენტები.

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

1.     Add მეთოდები:

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

2.     Remove მეთოდები

ერთი აცილებს მითითებულ ინდექსზე ინფორმაციას, მეორე კონკრეტულ ობიეკტს.

3.     Set მეთოდი:

სვამს ელემენტს მითითებულ პოზიციაზე.

4.     Index მეთოდები

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

5.     Get მეთოდი

აბრუნებს ობიეკტს მითითებული ინდექსიდან.

       შემდეგ მაგალითზე ვნახავთ მასიური სიის შექმნას, ნულიდან. 

1.     კონსტრუკტორები:

კომსტრუკტორებამდე გვაქ რამოდენიმე ცვლადი. Size ცვლადი თვლის ელემენტების ოდენობას მასივში, DEFAULT_SIZE კონსტანტა არის ცვლადი რომელსაც ვიყენებთ მაშინ როცა ხდება სიის ინსტანცირება, ამ კონკრეტულ მაგალითზე როცა სიას შევქმნით მისი საწყისი სიდიდე იქნება 5, Object[] elements შეინახავლს ზოგადად ტიპიზირებულ ინფორმაციას, modificationCounter არის ცვლადი რომელიც ითვლის რამდენი მოდიფიკაცია მოხდა მასივში, ის მონიშნულია როგორც transient, ვინც არ იცით რას ნიშნავს transient მოკლედ ავხსნი. როდესაც ველის დეკლალირება ხდება ამ საკვანძო სიტყვის დახმარებით ის ველი არ ექცევა სერიალიზაციის ზეგავლენის ქვეშ, სერიალიზაციაზე მომავალში მოგვიწევს საუბარი, ახლა გაგება რომ გაგიადვილდეთ, სერიალიზაცია არის პროცესი როდესაც ობიეკტი ეშვება ინტერნეტში და მისი აღდგენა ხდება სადმე სხვაგან, ინტერნეტში ჩაშვების წინ ის იშლება ბაიტებად და სადმე სხვა კომპიუტერზე მსოფლიოს ნებისმიერ წერტილში ისევ ობიეკტად აღდგება. ამ პროცეს სერიალიზაცია და დესერიალიზაცია ქვია.  მეორე კონსტრუკტორი მომხმარებელს საშუალებას მიცემს იმ სიდიდის სია შექმნას რა სიდისაც სურს.

2.     Add() მეთოდი

ელემენტის მასივზე დამატება ხდება კონსტანტურ დროში, თუმცა თუ სიდიდე მივიდა საზღვრამდე მაშინ cheforsize მეთოდი მაოხდენს იტერაციას და სიდიდის გაზრდას, რაც O(n) ალგორითმის მატარებელია, მაშასადამე ელემენტის დამატებას აქვს ორივე ალგორითმი.

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

3.     Get მეთოდი:

ინფორმაციას აბრუნებს კონსტანტურ დროში. არ ჭირდება იტერაცია რადგან მასიური სია არის Index Based:

4.     Set მეთოდი:

ინფორმაციას ანაცვლებს მითითებულ ინდექზე კონსტანტურ დროში. მეთოდი აბრუნებს ჩანაცვლებულ ღირებულებას.

5.     Contains მეთოდი:

უწევს მთლიანი სიის წაკითხვა ამიტომ არის O(n) ალგორითმით.

6.     Size, isEmpty , Clear მეთოდები :

ახსნა განმარტებას არ საჭიროებს, უამრავჯერ გვაქ ნანახი.

              სხვაობა მასიურ სიასა და დაკავშირებულ სიას შორის

1.     ArrayList დინამიურად ინახავს მექხსირებაში ინფორმციას.

LinkedList იყენებს DoublyLinkedList ინფორმაციის შესანახად

2.     ArrayList კლასი არის List-ის ტიპის რადგან ახდენს მის იმპლემენტაციას.

LinkedList კლასი არის List და Queue ტიპის რადგან ახდენს მათ იმპლემენტაციას.  (Deque ინტერფეისის)

3. ელემენტებთან მანიპულაცია ArrayList-ში არის რთული, რადგან ბითების ჩაწევა გიწევს რო სხვა ელემენტები დაამატო, ან მოაშორო.

ელემენტებით  მანიპულაცია LinkedList-ში არის გაცილებით მარტივი რადგან არ გიწევს ბიტებთან შეხება. შესაბამისად უფრო მალე ახდენ სასურველი შედეგის მიღწევას.

4.     ArrayList კარგია ელემენტების შესანახად და ასაღებად.

LinkedList კარგია ელემენტებით მანიპულაციისთვის.

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

                                                               Vector

Vector გავს  ArrayList-ს, თუმცა თუ კორეკტულები ვიქნებით ArrayList გავს ვექტორს. ის გაცილებით ადრე გამოჩდა ჯავაში ვიდრე მასიური სია. თუ ზუსტად მახსოვს ჯავა 1.2-ის გამოსვლის დროს შეიქმნა. მსგავსად მასიური სიისა ისიც ბაზირებულია მასივზე. ამიტომ ელემენტების დამატება (დამატება როცა ადგილია ვეკტორში, წინაღმდეგ შემტხვევაში კლონირება, კოპირება და ხელოვნურად ადგილის გაზრდა რაც O(n) ალგორითმში ხდება) და გამოტანა ვეკტორიდან ხდება 0 დროში. 2 ძირითადი სხვაობა მასიურ სიასა და ვეკტორს შორის არის:

1.     ვეკტორში თითქმის ყველა მეთოდი სინქრონიზებულია, მასიურ სიაში არა.

2.   ვეკტორი ახდენს უამრავი საკუთარი მეთოდის დეფინირებას. მასიური სია არა.

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

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

2.   როდესაც არ არის სინქრონიზებული მაშინ შესვლა ოპერაციებში ხდება უპრობლემოდ და იმდენი ადამიანი იყენებს რამდენსაც უჩდება სურვილი.

3.  ბევრი კლასი არ არის სინქრონიზებული იმიტომ რო უბრალოდ მსგავს კლასებს არასდროს უწევთ ერთზე მეტ მომხმარებელზე გამკლავება.

4. სინქრონიზაციას აქვს თავისი მინუსებიც ის ტვირთავს პროეკტს და ოპერაციების შესრულება ხდება უფრო დიდ დროში.

5. თუ დავფიქრდებით ჯავაში ყველა არ-სინქრონიზებულ კლას აქვს სინქრონიზებული ვერსია. მაგალითისთვის: Vector-ArrayList, HashTable-HashMap, StringBuilder-StringBuffer და ა.შ

6.   Fail-fast & Fail-safe ვეკტორს აქვს უნარი იყოს  Fail-fast & Fail-safe რადგან იყენებს 2 იტერატორს. ერთია იტერატორი, და მეორე ენუმერაცია. რას ნიშნავს Fail-fast & Fail-safe:

Fail-fast- არის მომენტი როდესაც იტერატორი ნახავს რაიმე ცვლილებას სტრუკტურაში იტერაციის დროს, მაგალითად. გვაქ დეფინირებული იტერატორი java.util.*; პაკეტიდან, სტრუკტურაში გვაქ გარკვეული ინფორმაცია რომელსაც ვკითხულობ და პარალელურ რეჟიმში, სტრუკტურაში ხდება ცვლილებები, ემატება , აკლდება, იცვლება ელემენტები. ამ დროს იტერატორი წყვეტს მუშაობას და ისვრის ConcurrentModificationException-ს. ეს პროცესი გარკვეულ წილად ნოტიფიკაციაა რომელიც გვამცნობებს რო სტრუკტურა იცვლება.

იტერატორი ამ დროს სწრაფად და ეფეკტურად წყვეტს მუშაობას.

Fail-fast შესაძლებელია გამოწვეულ იქნეს როგორც სინქრონიზებულ ისე არ-სინქრონიზებულ სტრუკტურებში

Fail-safe - ენუმერაცია ან იტერატორი კონკურენტული პაკეტიდან  ან იტერატორი დეფინირებული თქვენს მიერ რომელიც აგებულია კოპირებულ ინფორმაციაზე არის fail-safe. ძირითადი სხვაობა Fail-fast იტერატორს შორის არის ის რომ Fail-safe იტერაციის დროს სისტემა მუშაობს კოპირებულ ინფორმაციასთან და არა ორიგინალთან. რაც გამორიცხავს ConcurrentModificationException გამონაკლისის სროლას. თუმცა ამ გამორიცხვასაც აქვს თავისი მინუსები. მთლიანი სტრუკტურის კოპირება და შემდგომ მისი წაკითხვა არ არის ეფეკტური მეხსირების კონტროლის თვალსაზრისით, Fail-safe იტერაცია არ იძლევა გარანტიას იმისა რომ ინფორმაცია რომელიც წავიკითხეთ ის ინფორმაციაა რომელიც სტრუკტურაში იმყოფება. რადგან იმფორმაცია კოპირებულია და კოპირებული მონაცემების წაკითხვის დროს შესაძლებელია მოდიფიკაცია მომხდარიყო სტრუკტურაში.  ორივეს მაგალითს ვნახავთ დაბლა.

დასკვნა: სინქრონიზაცია არის პრევენციული ზომა და ის ახდენს ამა თუ იმ ოპერაციის დაკეტვას მანამ სანამ მეთოდი გამოყენებაშია. როცა მეთოდი (ან ობიეკტი) განთავისუფლდება შემდეგ მას შემდეგი მომხმარებელი იყენებს.

 

დაუბრუნდეთ ვეკტორს, მას გააჩნია 4 კონსტრუკტორი, 1. არის სტანდარტული კონსტრუკტორი რომლის ინსტანცირების შემდგომაც ალოკაცია ხდება 10 სლოტის მეხსირებაში, მეორე კონსტრუკტორი, ახდენს იმ ზომის ალოკაციას მეხსირებაში, რამდენსაც მომხარებელი შეიყვანს, მესამე კონსტრუკტორი ახდენს 2 პარამეტრის მიღებას. პირველი პარამეტრი ახდენს ალოკაციას და მეორე პარამეტრი დეფინირებულ სიდიდეს ზრდის იმდენით რამდენის სურვილიც მომხმარებელს გააჩნია. მეოთხე კონსტრუკტორი იღებს კოლექციას ელემენტებისა რომელიც არის ვეკტორის Type Parameter-ის ტიპის.

მეთოდები. გარდა სტანდარტული მეთოდებისა რომლის იმპლემენტაციაც ხდება ზემდგომი კლასებისგან და ინტერფეისებისგან ვეკტორი ახდენს უამრავი საკუთარი მეთოდის დეფინირებას. თითქმის იგივე შინაარშით და განსხვავებული დასათაურებით. ვნახოთ მაგალითები:

1.     კონსტრუკტორები.

Default()

Initialized()

Initialized() + increment size;

სხვა სტრუკტურის გადაცემის დროს:

ყველაფერი კომპილირების შემდგომ:

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

                                                 Methods();

1.     Add()

Add მეთოდები არიან კოლექციიდან. AddElement მეთოდი არის ვეკტორის მეთოდი რომელიც ელემენტს ამატებს სიის ბოლოში.  insertElementAt მეთოდი ამატებს ელემენტს სპეციფიურ პოზიციაზე. Add  მეთოდში პირველს უთითებთ ინდექს და შემდგომ ელემენტს, insertElementAt მეთოდში პირველს უთითებთ ელემენტს და შემდეგ ინდექს.

2. copyInto(Object[]element) ვეკტორის მიერ დეფინირებული მეთოდი, რომელიც ახდენს კოპირებას სტრუკტურის, მასივში.  ArrayList-ში იგივე ოპერაციას ასრულებს toArray(), toArray(Object[]element) მეთოდები.

3.     first and Last Elements:

გამოაქ ეკრანზე პირველი და ბოლო ელემენტი, ArrayList-ს მსგავსი მეთოდები არ აქვს.

4.     Get & ElementAt:

5.     Remove methods;

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

6.     Fail-Fast & fail Safe

ენუმერაციის შემთხვევაში კომპილირება მაინც მოხდება, მიუხედავად იმისა რო სია უნდა შეიცვლალოს, მაგრამ იტერაციის დროს კომპილატორი ისვრის გამონაკლის:

ეს მაგალითი რო წარმოდგენა შეგექმნათ რა არის Fail fast & Fail safe. დეტალურად მას მოგვიანებით მოუბრუნდებით.

                           საკუთარი ვეკტორის შექმნა

1.     კონსტრუკტორები:

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

ვიწყებთ იქიდან რომ ვინახავთ არსებული მასივის სიდიდეს პირველ მეთოდში, შემდეგ ველზე (ველი რომელიც ჩარჩოებშია მოქცეული ასრულებს ყველაზე მნიშვნელოვან ოპერაციას ვეკტორში) ვქმნით ახალ სიდიდეს Ternary ოპერატორის დახმარებით, თუ გახსოვთ ტერნარი ოპერატორი შორთქათია if-else გამოხატულებუს. 20 ველი კოდი რომ არ მეწერა ყველაფერი მოვაქციე ერთ ველზე. სადაც ცვლადს ვანიჭებთ 2 ღირებულებას. ადამიანის ენაზე თუ ვთარგმნით ოპერაციას: ახალი სიდიდე უდრის, ძველ სიდიდეს + სიდიდე რომელიც უნდა გაიზარდოს თუ მეტია ნულზე, მაშინ სიდიდე რომელიც უნდა გაიზარდოს, წინააღმდეგ შემთხვევაში ძველი სიდიდე.  ანუ მომხმარებელმა თუ მაოხდინა სტანდარტული კონსტრუკტორის შექმნა მაშინ სიდიდეს რომელიც უნდა გაიზარდოს არ იქნება ნულზე მეტი, ის ნულს უდრის, შესაბამისად ახალი სიდიდე იქნება ძველ სიდიდეს + ძველი სიდიდე, მაგრამ თუ მომხმარებელმა მოახდინა სიდიდის დეფინირება და მისი გაზრდა ხელოვნურად, მაშინ შეყვანილი ციფრი იქნება ნულზე მეტი, და ყოველ ჯერზე სიდიდეს დაემატება გასაზრდელი სიდიდე. თუ გაგიჭირდათ არღქმა მომწერეთ იმეილზე და ჩვეულებრვი if-else გამოხატულებით ჩავანაცვლებ.

მეორე მეთოდში ვახდენთ ამ ყველაფრის კონტროლს, თუ შეყვანილ სიდიდეს - არსებული სიდიდე მეტია ნულზე მაშინ უნდა გავზარდოთ სიდიდე. მაგალითად მომხმარებელმა არ მოახდინა დეფინირება სიდიდის და მუშაობა დაიწყო 10 ელემენტით, როდესაც ის დაამატებს მე-11 ელემენტს მეთოდი გადაამოწმებს ამ ოპერაციას 11-10 > 0 true გადავა შემდეგ ველზე სადაც მეთოდი ხვდება რომელიც აკონტროლებს სიდიდის ზრდას, ძველი სიდიდე = 10, ახალი სიდიდე = 10 + 0>0? 0 :10 რის შემდგომაც სიდიდეს გახდება 20;  

2.     მეთოდები:

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

Get მეთოდებიც არაფრით განსხვავდება ერთმანეთისგან.

                        ძირითადი სხვაობები მასიურ სიასა და ვეკტორს შორის

1.  ArrayList არ არის სინქრონიზებული, და მისი სინქრონიზება შესაძლებელია კოლექციიდან,	1.     Vector არის სინქრონიზებული, მისი სინქრონიზების აუცილებლობა არ დგას
2.     ArrayList ზრდის სიდიდეს 50 %-ით ყოველ ჯერზე	2.        Vector აორმაგებს სიდიდეს ან ზრდის სიდიდეს იმდენით რამდენსაც მომხმარებელი მიუთითებს
3.     ArrayList იყენებს იტერატორს ელემენტების ასაკითხდ	3. Vector იყენებს იტერატორს დ ენუმერაციას ელემენტების წასაკითხდა.
4.     ArrayList არის გაცილებით სწრაფი რადგან არ არის სინქრონიზებული და უფრო ეფეკტური მეხსიერების კონსტროლის კუთხით,	4. Vector არის ნელი მასიურ სიასთან შედარებით რადგან ის ახდენს სინქრონიზებას მრავალ განშტოებიანი ოპერაციების შესრულების დროს, იყენებს დიდი მეხსიერებას
5.     ArrayList შეიქმნა კოლექციაში	5. Vector კოლექციამდე არსებობდა. მისი დამატება მოხდა კოლექციაზე მოგვიანებით.

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

რეალურ პრაკტიკაში ვეკტორის ადგილას ხდება მასიური სიის ან CopyOnWriteArrayList-ის გამოყენება.

                                                       Stack

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

მაგალითი:

ეს ხუთი მეთოდია stack-ში. Push -ამატებს ელემენტს მეხსიერებას, peek მეთოდი აბრუნებს ბოლო დამატებულ ელემენტს მეხსიერებიდან. Pop მეთოდი შლის ბოლო ელემენტს მეხსიერებიდან. Empty მეთოდი ამოწმებს ცარიელია თუ არა სია და search მეთოდი გვიბრუნებს ინდექსზე ელემენტს, LIFO პრინციპის გათვალისწინებით. ბოლო ელემემენტი რომელიც დაემატა მეხსირებას უნდა დაბრუნდეს პირველი. შესაბამისად პირველი ელემენტი ფოტოზე არის 4. სულ ეს არის. შემდეგ მაგალითზე ვცადოთ შევქმნათ საკუთარი Stack.

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

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

კომპილირების შემდგომ:

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

რა მოხდება თუ გასაუბრებაზე მოხვდებით და გამსაუბრებელი მოგცემთ დავალებას სადაც არ გაქვთ ვეკტორის გამოყენების უფლება, და არც ერთი კოლექციის, რომელიც ჯავას ბიბლიოთეკაში იმყოფება?

„როგორც წესი გასაუბრებაზე არაფრის გამოყენების უფელაბს არ გაძლევენ, ითხოვენ ამა თუ იმ ოპერაციის ნულიდან შექმნას რათა თქვენი ცოდნა საფუძვლიანად გადაამოწმონ.“

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

ვიყებთ ცვლადების დეფინირებით:

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

კონსტრუკტორი, რომლის ინსტანცირების შემდგომ მოხდება 10 ადგილის  ალოკაცია მეხსირებაში.  

მეთოდები რომლებიც გააკონტროლებენ სიდიდის ზრდას.

სიდიდე გაიზრდება ორჯერ, ყოველ ჯერზე როცა ადგილი მასივში შეივსება.

5 მეთოდი:

და მეთოდებ რომლებიც ეხმარება ფუნქციონირებაში ამ 5 მეთოდს.

დამატებითი მეთოდები ახსნა განმარტებას არ საჭიროებს. საკმაოდ პრიმიტიულად გამოიყურებიან.

რა მოხდება თუ იგივე იმპლემენტაციის განმეორება მოგვთხოვეს კვანძების დახმარებით? LinkedList-ის მსგავსად, არა მასივზე არამედ Node-ზე რომ იყოს აგებული სტექი?  

კვანძი:

მეთოდები:

Push მეთოდი ინფორმაციას ამატებს სთექს ნულ დროში, peek მეთოდს ინფორმაცია გამოაქვს სტექიდან ნულ დროში.

Pop და empty მეთოდებიც მუშაობენ ნულ დროში.

Search მეთოდი მუშაობს N დროში. არ გვაქ დამხმარე მეთოდები არ გვაქ კონსტრუკტორი. Default კონსტრუკტორს ვიყენებთ მხოლოდ. როგორც ხედავთ კვანძებზე ბაზირებული სთექი გაცილებით სწრაფია მასივზე ბაზირებულ სტექზე.

მასივზე ბაზირებული სთექი: push მეთოდი მუშაობს O(1), O(n) ალგორითმებით. Peek მეთოდი მუშაობს O(1), ალგორითმით, pop მეთოდი მუშაობს O(n) ალგორითმით. Search მეთოდი მუშაობს O(n) დროში.

კვანძე ბაზირებული სთექი : push მეთოდი მუშაობს O(1) ალგორითმით. Peek მეთოდი მუშაობს O(1), ალგორითმით, pop მეთოდი მუშაობს O(1) ალგორითმით. Search მეთოდი მუშაობს O(n) დროში.

ჯავაში არსებობს სთექის უფრო დახვეწილი იმპლემენტაცია. ინტერფეისი Deque, მისი სუპერ ინტერფეისებია, Collection, Queue, Iterable. ქვე ინტერფეისია, BlockingDeque და ქვე კლასებია  ArrayDeque, LinkedList, LinkedBlockingDeque, ConcurrentLinkedDeque.  მასზე Queue  იერარქიის განხილვის დროს ვისაუბრებთ.

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

შემდეგ ბმულზე ნახავთ ყველა კლასის სრულ ვერსიას GitHub-ზე. 

მე ამით დაგემშვიდობებით, შევხვდებით რიგზე საუბრის დროს. წარმატებები.