Двусвязный список (Doubly Linked List). Реализация на C#

Двусвязный список - динамическая структура данных, каждый из элементов которой содержит ссылку на предыдущего элемента и на следующего элемента.

Пример двусвязного списка:

• Также есть головной элемент First, который является ссылочной переменной и указывает на начало списка. First.Prev=null (ограничитель)
• Ссылочная переменная Last, указывает на конец списка. Last.Next=null (ограничитель)
• Ссылочная переменная Current, которая указывает на текущий элемент (выступает обычно в роли итератора списка, т.е. элемента с помощью которого мы можем перемещаться по списку)
• Беззнаковая переменная целого типа uint size, которая содержит информацию о количестве элементов в списке.

Раньше я упомянул ограничители, это специальные ссылки которые ссылаются на null. Их используют для того, чтобы обозначить конец или начало списка. То есть для того, чтобы остановить пользователя от доступа в другие участки памяти, не относящиеся к списку.

Я покажу только самые базовые операции вставки в конец и начало, проиллюстрирую и подробно опишу, что происходит. По просьбам в комментарии могу описать другой метод в списке.

Push_Front:

Цель: Вставить новый элемент в начало списка, сделав его первым, надо, чтобы, First ссылался на этот объект.

Синим отмечены ссылки, левая - Prev, правая - Next, серая - Data (наши данные), стрелки - на что они ссылаются.

В начальном состоянии Prev и Next ссылаются на null, First.Prev = null, First.Next ссылается на след объект и т.д.

1. Мы сделаем так, чтобы новый объект ссылался на First
2. Потом мы сделаем так, чтобы и First и newNode ссылались на новый объект.
3. Теперь просто новый объект ссылается на предыдущий первый.

Push_Back:

Цель, добавить новый элемент в конец, Last должен ссылаться на новый объект.

В начальном состоянии Last.Next=null.

1. Last.Next теперь ссылается на новый объект.
2. newNode.Prev ссылается на Last.
3. Last ссылается на новый объект.

Каждый объект описан классом Node (Узел)

• object _Data - наши данные, которые содержатся в узле.
• Node _Next - ссылка на следующий элемент.
• Node _Prev - ссылка на предыдущий элемент.
• Ну и свойства их описывающие, для доступа к ним.

public class Node {
        private object _Data;
        private Node _Next;
        private Node _Prev;
        public object Value
        {
            get { return _Data; }
            set { _Data = value; }
        }
        public Node(object Data)
        {
            this._Data = Data;
        }
        public Node Next
        {
            get { return this._Next; }
            set { this._Next = value; }
        }
        public Node Prev
        {
            get { return this._Prev; }
            set { this._Prev = value; }
        }
    }

UML диаграмма двусвязного списка:

Код двусвязного списка:

class Doubly_Linked_List
    {
        private Node First;
        private Node Current;
        private Node Last;
        private uint size;

        public Doubly_Linked_List()
        {
            size = 0;
            First = Current = Last = null;
        }

        public bool isEmpty //проверка на пустоту
        {
            get
            {
                return size == 0;
            }
        }

        public void Insert_Index(object newElement, uint index) //вставить по индекусу
        {
            if (index < 1 || index > size) //вброс ошибки, если неправильный индекс
            {
                throw new InvalidOperationException();
            }
            else if (index == 1) //если начало
            {
                Push_Front(newElement);
            }
            else if (index == size) //если конец
            {
                Push_Back(newElement);
            }
            else //иначе ищем элемент с таким индексом
            {
                uint count = 1;
                Current = First;
                while (Current != null && count != index)
                {
                    Current = Current.Next;
                    count++;
                }
                Node newNode = new Node(newElement); //создаем объект
                Current.Prev.Next = newNode; 
                newNode.Prev = Current.Prev;
                Current.Prev = newNode;
                newNode.Next = Current;
            }
        }

        public void Push_Front(object newElement)
        {
            Node newNode=new Node(newElement);

            if (First == null)
            {
                First = Last = newNode;
            }
            else
            {
                newNode.Next = First; 
                First = newNode; //First и newNode указывают на один и тот же объект
                newNode.Next.Prev = First;
            }
            Count++;
        }

        public Node Pop_Front()
        {
            if (First == null)
            {
                throw new InvalidOperationException();
            }
            else
            {
                Node temp = First;
                if (First.Next != null)
                {
                    First.Next.Prev = null;
                }
                First = First.Next;
                Count--;
                return temp;
            }
        }

        public void Push_Back(object newElement)
        {
            Node newNode = new Node(newElement);

            if (First == null)
            {
                First = Last = newNode;
            }
            else
            {
                Last.Next = newNode;
                newNode.Prev = Last;
                Last = newNode;
            }
            Count++;
        }

        public Node Pop_Back()
        {
            if (Last == null)
            {
                throw new InvalidOperationException();
            }
            else
            {
                Node temp = Last;
                if (Last.Prev != null)
                {
                    Last.Prev.Next = null;
                }
                Last = Last.Prev;
                Count--;
                return temp;
            }
        }

        public void ClearList() //полностью очистить список
        {
            while (!isEmpty)
            {
                Pop_Front();
            }
        }

        public uint Count //свойство для size
        {
            get { return size; }
            set { size = value; }
        }

        public void Display() //вывести в прямом порядке
        {
            if (First == null)
            {
                Console.WriteLine("Doubly Linked List is empty");
                return;
            }
            Current = First;
            uint count=1;
            while (Current != null)
            {
                Console.WriteLine("Element " + count.ToString()+" : " + Current.Value.ToString());
                count++;
                Current = Current.Next;
            }
        }

        public void ReverseDisplay() //вывести в обратном порядке
        {
            if (Last == null)
            {
                Console.WriteLine("Doubly Linked List is empty");
                return;
            }
            Current = Last;
            uint count = 1;
            while (Current != null)
            {
                Console.WriteLine("Element " + count.ToString() + " : " + Current.Value.ToString());
                count++;
                Current = Current.Prev;
            }
        }

        public void DeleteElement(uint index){ //удалить элемент по индексу
            if (index < 1 || index > size)
            {
                throw new InvalidOperationException();
            }
            else if (index == 1)
            {
                Pop_Front();
            }
            else if (index == size)
            {
                Pop_Back();
            }
            else
            {
                uint count = 1;
                Current = First;
                while (Current != null && count != index)
                {
                    Current = Current.Next;
                    count++;
                }
                Current.Prev.Next = Current.Next;
                Current.Next.Prev = Current.Prev;
            }
        }

        public Node FindNode(object Data) //найти Node и вернуть его
        {
            Current = First;
            while (Current != null)
            {
                Current = Current.Next;
            }
            return Current;
        }

        public uint GetIndex(object Data) //достать индекс по значению элемента
        {
            Current = First;
            uint index = 1;
            while (Current != null)
            {
                Current = Current.Next;
                index++;
            }
            return index;

        }

    }

Posted in: Алгоритмы, Структуры данных, C#