LinkedList. Davomi. DoubleLinkedList.

Bundan avvalgi maqolalarimizdan birida LinkedList ma’lumotlar strukturasiga
kirish qilgan edik. Undan keyin esa LinkedListning SingleLinkedList xususiy holatiga to’xtalganmiz. Bugun esa qimmatli vaqtingizni yana bir xususiy holat DoubleLinkedList uchun olaman(Albatta maqolani oxirigacha o’qisangiz).

SingleLinkedList bilan DoubleLinkedListning nima farqi bor?
Esingizda bo’lsa, LinkedList o’zida qandaydur qiymatni saqlagan sodda ma’lumotlar strukturasi «xalqa» yoki «node» larning zanjir va shu zanjir ustida bajarilishi mumkin bo’lgan amallar to’plami degan edik. SingleLinkedListning tashkil etuvchisi bo’lgan xalqada o’zidan keyingi xalqaga ko’rsatkich mavjudligini aytib o’tganmiz. Demak, DoubleLinkedListning SingleLinkedListdan farqi, tashkil etuvchi xalqada faqatgina o’zidan keyingi xalqaga emas, o’zidan oldingisiga ham ko’rsatkich mavjudligidadir. Quyidagi rasmda DoubleLinkedList uchun xalqa ifodalangan.

Ushbu kichik o’zgarish hisobiga amallarning tezligi sezilarli darajada oshadi. Yagona kamchiligi, qo’shimcha yo’llanma uchun joy olishidir.

Quyida esa ushbu rasmda berilgan nodening implementatsiyasini ko’rishingiz mumkin.

// DoubleLinkedList tashkil etuvchi node
        public class DoubleLinkedListNode
        {
            // bekorchi(bo'sh) konstruktor
            public DoubleLinkedListNode(){}
            // Node uchun qiymat 
            public DoubleLinkedListNode(T value)
            {
                Value = value;
            }
            //Nodening ichida yotgan gavhar
            public T Value { get; set; }
            //Ushbu nodening chap qo'shnisi
            public DoubleLinkedListNode Prev { get; set; }
            //Ushbu nodening o'ng qo'shnisi
            public DoubleLinkedListNode Next { get; set; }
            }

Keyingi rasmda DoubleLinkedListning mantiqiy ko’rinishi ifodalangan.

Ko’rib turganingizdak B dan turib A yoki C ga osongina bog’lanishimiz mumkin.

Yangi obyekt qo’shish.

LinkedListga to’rt xil usulda obyekt qo’shishimiz mumkin:

Listdan obyektni o’chirish. Bizning implementatsiya o’chirishning uch xil usulini o’z ichiga olgan:

Listdan obyektni topish. Berilgan qiymatga ko’ra listdan xalqani topish:

Ko’rib turganingizdek, amallarning ko’pchiligi O(1) murakkablikka ega. Faqatgina 2ta amalda O(n) vaqt talab qilinadi.

Endi e’tiboringizni DoubleLinkedListning implementatsiyaga qarataman.

        public class DoubleLinkedList
        {

        /// 

        public DoubleLinkedListNode Head
        {
            get;
            private set;
        }

        /// 

        /// Listdagi so'nggi node, List bo'sh bo'lgan holatda null ga teng.
        /// 
        public DoubleLinkedListNode Tail
        {
            get;
            private set;
        }

        /// 

        /// Listdagi nodelarning soni. List bo'sh bo'lsa 0 ga teng.
        /// 
        public int Count
        {
            get;
            private set;
        }
        /// 

        /// Listni nodelardan tozalaydi.
        /// 
        public void Clear()
        {
            Head = Tail = null;
            Count = 0;
        }

        /// 

        /// Listing boshiga yangi qiymat qo'shadi
        /// 
        /// Listning boshiga qo'shilishi lozim bo'lgan qiymat.
        public void AddFirst(T value)
        {
            AddFirst(new DoubleLinkedListNode(value));
        }

        /// 

        /// Listing boshiga yangi node qo'shadi.
        /// 
        /// Listning boshiga qo'shilishi lozim bo'lgan node.
        public void AddFirst(DoubleLinkedListNode node)
        {
            // Boshning qiymatini yo'qotib qo'ymaslik uchun saqlab turamiz.
            DoubleLinkedListNode temp = Head;

            //Boshni yangi nodega almashtiramiz.
            Head = node;

            //Eski boshni yangi boshning davomiga aylantiramiz.
            Head.Next = temp;
            Count++;

            if (Count == 1)
            {
                //Agar LinkedList bo'sh bo'lsa bosh va dum bitta xalqa.
                Tail = Head;
            }
            else
            {
                // eski boshning qiymat null edi, endi yangi boshga teng. 
                temp.Prev = Head;
            }
        }

        /// 

        /// Listing oxiriga yangi qiymat qo'shadi.
        /// 
        /// Listning boshiga qo'shilishi lozim bo'lgan qiymat.
        public void AddLast(T value)
        {
            AddLast(new DoubleLinkedListNode(value));
        }

        /// 

        /// Listing oxiriga yangi node qo'shadi.
        /// 
        /// Listning boshiga qo'shilishi lozim bo'lgan node.
        public void AddLast(DoubleLinkedListNode node)
        {
            if (Count == 0)
            {
                // list bo'sh bo'lganida, kiruvchi node listning boshiga aylanadi.
                Head = node;
            }
            else
            {
                // listning eski dumi, yangi dumning bitta oldingi nodega aylanadi.
                Tail.Next = node;
                node.Prev = Tail;
            }
            Count++;
            //listning yangi dumi kiruvchi nodega teng bo'ladi.
            Tail = node;
        }

        /// 

        /// Listning ixtiyoriy nodedan keyin yangi qiymat qo'shadi.
        /// 
        /// Undan keyin yangi qiymat qo'shilishi lozim bo'lgan node.
        /// Yangi qo'shilishi kerak bo'lsan qiymat.
        public void InsertBefore(DoubleLinkedListNode node, T value)
        {
            if (node != null)
            {
                DoubleLinkedListNode current = new DoubleLinkedListNode(value);

                //agar kiruvchi node Listing boshi bo'lsa AddFirst() ni chaqiramiz.
                if (node == Head)
                {
                    AddFirst(value);
                }
                else
                {
                    //kiruvchi node, listning o'rtasida joylashgan bo'lgan holat.
                    //yangi qiymatning keyingi xalqasi oldingi nodening keyingi xalqasiga teng bo'ladi.
                    current.Next = node.Next;
                    //yangi qiymat joylashgan nodedan oldingi xalqa, yangi yaratilgan xalqaga teng.
                    node.Next.Prev = current;
                    //yangi qiymat joylashgan nodening oldingi qiymati, nodega teng
                    current.Prev = node;
                    Count++;
                }
            }
        }

        /// 

        /// Listning ixtiyoriy nodedan oldin yangi qiymat qo'shadi.
        /// 
        /// Undan oldin yangi qiymat qo'shilishi lozim bo'lgan node.
        /// Yangi qo'shilishi kerak bo'lsan qiymat.
        public void InsertAfter(DoubleLinkedListNode node, T value)
        {
            if (node != null)
            {
                DoubleLinkedListNode current = new DoubleLinkedListNode(value);

                //agar kiruvchi node Listing dumi bo'lsa AddLast() ni chaqiramiz.
                if (node == Tail)
                {
                    AddLast(value);
                }
                else
                {
                    //Yangi yaratilgan nodedan keyingi xalqa, nodedan keyingi xalqaga teng.
                    current.Next = node.Next;
                    //Yangi yaratilgan nodedan keyingining oldingi xalqasi nodedan oldingi xalqaga teng.
                    node.Next.Prev = node.Prev;
                    //nodedan keyingi xalqa yangi nodega teng.
                    node.Next = current;
                    //yangi xalqaning oldingi xalqasi nodega teng.
                    current.Prev = node;
                    Count++;
                }

            }
        }

        /// 

        /// Listning boshidan xalqa o'chiradi.
        /// 
        public void RemoveFirst()
        {
            //Listi bo'sh bo'lsa xechnima qilinmaydi.
            if (Count != 0)
            {
                //zanjirda faqat bitta xalqa bo'lsa. Listni bo'shatamiz.
                if (Count == 1)
                {
                    Head = Tail = null;
                }
                else
                {
                    //listing yangi boshi, eski boshdan keyingi nodega teng.
                    Head = Head.Next;
                    Head.Prev = null;
                }

                Count--;
            }
        }

        /// 

        /// Listning oxiridan xalqa o'chiradi.
        /// 
        public void RemoveLast()
        {
            //Listi bo'sh bo'lsa xechnima qilinmaydi.
            if (Count != 0)
            {
                //zanjirda faqat bitta xalqa bo'lsa. Listni bo'shatamiz.
                if (Count == 1)
                {
                    Head = Tail = null;
                }
                else
                {
                    //Listning yangi dumi eski dumdan oldingi xalqaga teng.
                    Tail.Prev.Next = null;
                    Tail = Tail.Prev;
                }
                Count--;
            }
        }

        /// 

        /// Listning ichidagi qiymat joylashgan nodeni o'chiradi va bool qiymat qaytaradi.
        /// 
        /// O'chirilishi lozim bo'lgan nodeda yotgan qiymat.
        public bool Remove(T value)
        {
            DoubleLinkedListNode prev = null;
            DoubleLinkedListNode current = Head;

            //1. List bo'sh bo'lsa xech nima sodir bo'lmaydi.
            //2. Listda faqat bitta node bo'lsa.
            //3. Listda bittadan ko'p node  bo'lsa.
            //   1. O'chirilishi lozim bo'lgan listning boshida yotgan bo'lsa
            //   2. Qiymat listing o'rtasida yoki oxirida yotgan bo'lsa.
            while (current != null)
            {
                if (current.Value.Equals(value))
                {
                    // qiymat listning o'rtasi yoki oxiridami
                    if (prev != null)
                    {
                        //3.1 holat.
                        prev.Next = current.Next;

                        //listning oxirida joylashgan, dum o'zgaradi
                        if (current.Next == null)
                        {
                            Tail = prev;
                        }
                        else
                        {
                            current.Next.Prev = prev;
                        }
                        Count--;
                    }
                    else
                    {

                        // 2 yoki 3.1 holat uchun.
                        RemoveFirst();
                    }
                    return true;
                }
                prev = current;
                current = current.Next;
            }
            return false;
        }

        /// 

        /// Listning ichidagi qiymat joylashgan nodeni topib qaytaradi. Topolmasa null qaytadi.
        /// 
        /// Qidirilayotgan qiymat.
        public DoubleLinkedListNode Find(T value)
        {
            //Qidiruvning boshi.
            DoubleLinkedListNode current = Head;

            while (current != null)
            {
                 //topilsa qaytaradi.
                if (current.Value.Equals(value))
                    return current;
                current = current.Next;
            }
            //topolmadi.
            return null;
        }
    }

Manba:

Ulug’bek Normatov