НАЗАД

C#. Часть 1.

Связные списки (построение спсика без использования стандартных классов)

Настоящая статья рассматривает типы связных списков и какие типы списков бывают.
В процессе рассмотрения списков будет приведен программные код на языке C#, который продемонстрирует работу связных списков. Связные списки тема настолько же простая, насколько сложная, особенно для новичков. В теории вроде кажется все просто, но когда пытаешься организовать связный список в реальной программе начинаются трудности с реализацией (а собственно с чего начать?!).
Начнем с понятия связный список. По сути связный список – это массив данных, который не имеет начального определения размера массива. Подобные списки идеально подходят для создания структур данных, размер которых неизвестен. Связный список состоит из элементов списка, которые имеют ссылки, в зависимости от типа списка, на следующий и/или предыдущий элемент. В этом по сути и есть основное отличие от массива. При добавлении или удаления элементов из списка, происходит изменение ссылок в элементах. В случае добавления происходит изменение ссылок для доступа к новому элементу, в случае удаления, ссылки из предыдущего объекта ведут к следующему. По сути, элемент даже может остаться существовать со всеми входящими в него данными, но в списке он находится не будет и доступа к нему из механизма работы со списком также не будет.
Один из недостатков связного списка, связан с поиском элемента по списку. Поиск элемента по списку выполняется перебором последовательно каждого элемента.
Связные списки можно разделить на следующие основные типы:

На рисунке ниже (рисунок 1) приведена схема линейного однонаправленного списка. Здесь каждый элемент имеет ссылку на следующий элемент. Проход по списку возможен только в одном направлении.

Рисунок 1.

При операциях добавления и удаления элементов происходит изменение ссылок в элементе. На рисунке ниже (рисунок 2) показан процесс добавления элемента.

Рисунок 2.

На рисунке 3 приведена схема кольцевого однонаправленного списка, а рисунок 4 демонстрирует добавления элемента в с список. Кольцевой однонаправленный список отличается от линейного однонаправленного тем, что имеет ссылку в последнем элементе на первый элемент списка.

Рисунок 3

Рисунок 4

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

Рисунок 5

На рисунке 6 показано добавление нового элемента в двусвязный список.

Рисунок 6

На рисунке 7 приведен циклический двунаправленный список. На рисунке 8 показано добавление нового элемента в двусвязный циклический список.

Рисунок 7

Рисунок 4

Практика создания связного списка на C#.

По сути здесь вся теория заканчивается и начинается практика.
Все программы работающие со связными списками создадим с помощью C# и Visual Studio.
Рассмотрим создание связного списка самостоятельно, без использования специальных классов. В следующей статье рассмотрим создание связанного списка с помощью средств Visual Studio, класса LinkedList().

Самостоятельное создание связного списка.

Сначала рассмотрим создание связного списка самостоятельно.
Все связные списки будут циклические, не циклические списки лишь частный случай циклических.
Для этого необходимо создать пять классов:

Основное описание и код для примера к каждой программы ниже.
Все данные хранятся в объектах класса DataClass.cs. Всего в классе три поля, которые содержат данные.
Код класса ниже:

public class DataClass
{
    private string number_account;
    private string value_account;
    private string FIO_account;
    public string NumberAccount
    {
        get { return number_account; }
        set { this.number_account = value; }
    }
    public string ValueAccount
    {
        get { return value_account; }
        set { this.value_account = value; }
    }
    public string FIOAccount
    {
        get { return FIO_account; }
        set { this.FIO_account = value; }
    }
    public DataClass(string number_account, string value_account, string FIO_account)
    {
        this.number_account = number_account;
        this.value_account = value_account;
        this.FIO_account = FIO_account;
    }
}

Элемент односвязного списка создается в классе NodeSingle.
Данный класс содержит два поля: поле dataclass, содержащие объект класса DataClass; поле next, содержащий объект NodeSingle, который является следующим объектом по списку.

class NodeSingle
{
    private DataClass dataclass;
    private NodeSingle next;
    public DataClass Dataclass
    {
        get { return dataclass; }
        set { this.dataclass = value; }
    }
    public NodeSingle Next
    {
        get { return next; }
        set { this.next = value; }
    }
}

Непосредственно односвязный список создается как объект класса SingleList.
Данный класс содержит методы для работы со связным списком, а именно вставку данных в список (Метод Insert). Метод SizeList является служебным методом и выполняет подсчет элементов связного списка.

class SingleList
{
    private NodeSingle first;
    private NodeSingle service;
    private NodeSingle current;
    private NodeSingle postcurrent;
    private NodeSingle last;
    private int count, serv;
    private int countfind;
    public int Count
    {
        get { return count; }
        set { this.count = value; }
    }
    public int CountFind
    {
        get { return countfind; }
        set { this.countfind = value; }
    }
    public SingleList()
    {
        count = 0;
        serv=0;
        countfind = 0;
    }
    public void Insert(DataClass ds, int index)
    {
        Size_List(index);
        if (index == 0)
        {
            first = new NodeSingle();
            current = new NodeSingle();
            last = new NodeSingle();
            first.Dataclass = ds;
            first.Next = first;
            current = last = first;
        }
        if (index > 0)
        {
            if (index == Count)
            {
                current = first;
                service= new NodeSingle();
                while (current.Next != first)
                {
                    service = current.Next;
                    current = service;
                }
                postcurrent = new NodeSingle();
                postcurrent.Dataclass = ds;
                postcurrent.Next = first;
                last = postcurrent;
                current.Next = last;
            }
            if (index < Count)
            {
                current = first;
                service = new NodeSingle();
                for (int i = 0; i < index-1; i++)
                {
                    service = current.Next;
                    current = service;
                }
                postcurrent = new NodeSingle();
                postcurrent.Dataclass = ds;
                postcurrent.Next = current.Next;
                current.Next = postcurrent;
            }
        }
        Count++;
    }
    public void Size_List(int index)
    {
        current=first;
        serv = 0;
        if (index != 0)
        {
            while (current.Next != first)
            {
                postcurrent = current.Next;
                current = postcurrent;
                serv++;
            }
        }
    }
}

Код двусвязного списка в качестве блока хранения данных использует тот же класс, что и односвязный список (DataClass). Этот класс приведен выше.
Элемент двусвязного списка создается в классе NodeTwo. Класс содержит три поля: поле dataclass, содержащий объект класса DataClass; поле next, содержащий объект класса NodeTwo, который является следующим по списку, поле previous, содержащий объект класса NodeTwo, который предшествуют текущему по списку.

class NodeTwo
{
    private DataClass dataclass;
    private NodeTwo previous;
    private NodeTwo next;
    public DataClass Dataclass
    {
        get { return dataclass; }
        set { this.dataclass = value; }
    }
    public NodeTwo Previous
    {
        get { return previous; }
        set { this.previous = value; }
    }
    public NodeTwo Next
    {
        get { return next; }
        set { this.next = value; }
    }
}

Непосредственно сам двусвязный список создается в классе TwoList. Список является циклическим. Данный класс содержит все те же методы, что и класс создающий односвязный список.

class TwoList
{
    private NodeTwo first;
    private NodeTwo service;
    private NodeTwo current;
    private NodeTwo postcurrent;
    private NodeTwo last;
    private int count, serv;
    private int countfind;
    public int Count
    {
        get { return count; }
        set { this.count = value; }
    }
    public int CountFind
    {
        get { return countfind; }
        set { this.countfind = value; }
    }
    public TwoList()
    {
        count = 0;
        serv=0;
        countfind = 0;
    }
    public void Insert(DataClass ds, int index)
    {
        Size_List(index);
        if (index == 0)
        {
            first = new NodeTwo
            current = new NodeTwo();
            last = new NodeTwo();
            first.Dataclass = ds;
            first.Next = first;
            first.Previous = first;
            current = last = first;
        }
        if (index > 0)
        {
            if (index == Count)
            {
                current = first;
                service = new NodeTwo();
                while (current.Next != first)
                {
                    service = current.Next;
                    current = service;
                }
                postcurrent = new NodeTwo();
                postcurrent.Dataclass = ds;
                postcurrent.Next = first;
                postcurrent.Previous = current;
                last = postcurrent;
                current.Next = last;
            }
        if (index < Count)
        {
            current = first;
            service = new NodeTwo();
            for (int i = 0; i < index - 1; i++)
            {
                service = current.Next;
                current = service;
            }
            postcurrent = new NodeTwo();
            postcurrent.Dataclass = ds;
            postcurrent.Next = current.Next;
            postcurrent.Previous = current;
            current.Next = postcurrent;
            }
        }
        Count++;
    }
    public void Size_List(int index)
    {
        current = first;
        serv = 0;
        if (index != 0)
        {
            while (current.Next != first)
            {
                postcurrent = current.Next;
                current = postcurrent;
                serv++;
            }
        }
    }
}

Программа создана для проверки работы со связным списком. Данную программу можно скачать по ссылке ниже. Исходный код в архиве расположен по ссылке ниже. Прошу обратить внимание, что пользовательский интерфейс не создавался специально для «промышленной» версии программы (только для демонстрации работы со связными списками), поэтому в нем отсутствуют какие-либо проверки на ввод и обработки исключительных ситуаций. Все поля ввода строковые, за исключением поля индекса. Индекс необходимо вводить целым числом.
В программе присутствует только метод по добавлению элемента связного списка. Каких-либо других методов обработки данных нет.
При работе с программой необходимо учесть, что индекс начинается с номера 0. Проверки на ввод значения индекса больше, чем элементов в массиве не производится. При вводе значении для элементов связного списка необходимо указывать значение индекса ( иначе программа закроется с ошибкой).
В данной программе не реализован механизм вставки элемента по нулевому индексу. Нет соответствующего кода в методе Insert. Это вы можете реализовать самостоятельно.
При работе с программой, вы сначала создаете список нажатием кнопки «Create list», затем добавляем элемент нажатием по кнопке «Add record».

Исходный код LinkedListOneTwo(code) в архиве 7z

Исполняемый код LinkedListOneTwo(exe) в архиве 7z



Николай Ткаченко, 2015 г.