Связанный список

Однонаправленный связанный список, узлы добавляются в конец списка

В данной своей статье я хотел бы рассмотреть такую интересную структуру данных, как связанный список или как его еще называют динамический список. Давайте сначала дадим определение. Связанный список - это динамическая структура данных, т.е. она непостоянная и в процессе своей работы может менять свои размеры в памяти компьютера как в сторону увеличения, так и в сторону уменьшения. Думаю, что с этим понятно. Продолжим... Связанный список - структура данных, состоящая из узлов, которые содержат в себе в классическом варианте два значения: первое - это какое-либо данное (этим данным может быть что угодно: обычная переменная, объект класса и так далее), а второе - это указатель на следующий узел в списке (не зря же список является связанным). Сразу оговорюсь, что структура данных эта не простая, но понять ее нужно - вы же претендуете на звание хорошего специалиста-программиста?! Я сам когда-то дни просиживал, чтобы разобраться с ней и написать программу реализующую ее. Еще один момент - почему данная структура данных имеет два названия: связанный список и динамический список. Объясняю... Связанный потому что все узлы списка связаны между собой с помощью указателей, а динамический потому что динамически во время выполнения программы можно расширять данную структуру путем добавления новых узлов в список. В отличие от массива будь то статического, либо динамического, динамический список можно увеличивать во время работы программы. В этом то и есть его очень большой плюс. А вот давайте теперь и рассмотрим все это на рисунке, который я постарался как можно удобнее зарисовать в Фотошопе, дабы было все очень понятно. Смотрим

Устройство связанного списка

Итак, на рисунке мы видим узлы, содержащие в себе два значения - данное и указатель. Указатель всегда указывает (содержит в себе адрес памяти, с которого начинается следующий узел) на следующий узел связанного списка. И самое важное - это то, что указатель последнего узла должен всегда выставляться в нуль (NULL или просто 0, хотя правильнее все же при работе с памятью указывать NULL). Этим он сообщает что является последним узлом связанного списка и что дальше указывать не на что. Если нужно будет добавить новый узел в динамический список, то это значение NULL заменяется на адрес нахождения в памяти нового узла (как это делается мы рассмотрим ниже), а сам же указатель нового узла опять выставляется в NULL. По ходу работы программы мы можем сколь угодно создавать таких узлов нашего связанного списка, единственное ограничение накладывает размер свободной оперативной памяти компьютера (ее конечно же должно хватать). Логически мы видим, что все узлы расположены как бы по порядку, хотя на самом деле в памяти компьютера они могут располагаться где угодно. И найти его не составит никакого труда, т.к. у нас есть в узле поле-указатель, указывающий на нужную ячейку памяти. Об особенности строения оперативной памяти компьютера мы будем говорить в главе моего учебника "Указатели". Здесь скажу лишь кратко, что оперативная (энергозависимая, быстродействующая) память компьютера состоит из множества ячеек размером в один байт (в этих ячейках хранятся наши данные), нумерация которых начинается с нуля и записана в шестнадцатеричном формате исчисления. Вот по этим шестнадцатеричным адресам связанный список и ориентируется.

Давайте теперь последовательно рассмотрим работу связанного списка. Итак, мы описали в своей программе структуру, представляющую собой узел динамического списка. Эта структура из двух полей - данное и указатель на структуру того же типа. Такие структуры еще называются самоссылающимися (или структуры с самоадресацией). Вот как это будет выглядеть

//стуктура, описывающая узел связанного списка
struct Node
{
    int data;
    Node *next;
};

А теперь нужно создать сам объект "связанный список", который и будет хранить эти самоссылающиеся узлы (Node - с англ. узел). Вот как мы это сделаем

//класс, описывающих объект "связанный список"
class List
{
private:
    Node *head; //"голова" связанного списка

public:
    List() //конструктор класса без параметров
    {
        head = NULL; //первого элемента пока нет
    }

    //метод, добавляющий новый узел в список
    void addNode(int d);
    //метод, выводящий связанный список на экран
    void printList();
};

Итак, если с первой структурой Node все понятно, то со структурой List, представляющей "связанный список" нам нужно сейчас разобраться. Мы выяснили, что динамический список состоит из узлов, значит класс List должен манипулировать этими узлами: создавать их, удалять, выводить на печать и так далее. Пока что остановимся только на таких моментах как создавать и выводить на печать, удаление оставим на потом. Как видите, в нашем классе List имеются два метода: addNode() - создает новый узел в динамическом списке, printList() - выводит содержание списка (всех узлов поочереди) на печать. Также у нас есть закрытое поле класса head типа Node - это так называемая "голова" связанного списка и судя из названия должна всегда указывать на начало списка в памяти компьютера, т.е. на его первый узел (этот момент мы не обсуждали выше, но он логически понятен - должен же быть указатель, указывающий просто на начало динамического списка и не содержащий никаких данных). Зная, где начинается связанный список, на него нам указывает "голова" head, и где заканчивается, об этом нам сообщает указатель последнего узла, выставленный в NULL, мы можем путешествовать по всему динамическому списку и произодить с них необходимые операции. Продолжаем рассматривать код... Изначально в конструкторе класса List переменной head выставляется значение в NULL, т.к. при создании объекта класса List связанный список еще пуст и узлов в нем нет, соответственно и указывать не на что. Складываем все вышеупомянутое и получаем рабочую программу, реализующую динамический список.

//Связанный список (динамический список)

#include <iostream>

using namespace std;

//стуктура, описывающая узел связанного списка
struct Node
{
    int data;
    Node *next;
};

//класс, описывающих объект "связанный список"
class List
{
private:
    Node *head; //"голова" связанного списка

public:
    List() //конструктор класса без параметров
    {
        head = NULL; //первого элемента пока нет
    }

    //метод, добавляющий новый узел в список
    void addNode(int d)
    {
        Node *nd = new Node; //динамически создаем новый узел

        nd->data = d;        //задаем узлу данные
        nd->next = NULL;     //новый узел в конце, поэтому NULL

        if(head == NULL)     //если создаем первый узел
            head = nd;
        else                 //если узел уже не первый
        {
            Node *current = head;

            //ищем в цикле предшествующий последнему узел
            while(current->next != NULL)
                current = current->next;

            //предшествующий указывает на последний
            current->next = nd;
        }
    }

    //метод, выводящий связанный список на экран
    void printList()
    {
        Node *current = head;

        while(current != NULL)
        {
            cout << current->data << endl;
            current = current->next;
        }
    }
};

int main()
{
    List myList;

    myList.addNode(5);
    myList.addNode(11);
    myList.addNode(27);
    myList.addNode(35);
    myList.addNode(50);

    myList.printList();

    return 0;
}

Результат работы программы будет выглядеть так

Результат работы программы, реализующей связанный список

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

//метод, добавляющий новый узел в список
void addNode(int d)
{
    Node *nd = new Node; //динамически создаем новый узел

    nd->data = d;        //задаем узлу данные
    nd->next = NULL;     //новый узел в конце, поэтому NULL

    if(head == NULL)     //если создаем первый узел
        head = nd;
    else                 //если узел уже не первый
    {
        Node *current = head;

        //ищем в цикле предшествующий последнему узел
        while(current->next != NULL)
            current = current->next;

        //предшествующий указывает на последний
        current->next = nd;
    }
}

Итак, первая строка кода

Node *nd = new Node;

динамически (new) создает новый объект типа Node, т.е. новый узел. Как вы знаете, после отработки данной строки, в указатель nd, при успешном создании объекта, записывается адрес созданного объекта в памяти (в неудачном случае будет записано NULL, т.е. объект не создан). Идем дальше...

nd->data = d;
nd->next = NULL;

В этих двух строках кода мы уже обращаемся к полям созданного узла и присваиваем им необходимые значения: задаем данное - это данное метод addNode() принимает в качестве аргумента, выставляем указатель в NULL, т.к. вновь созданный узел всегда у нас будет последним (в данном варианте программы узлы добавляются в конец связанного списка - классический вариант). Далее...

if(head == NULL)
    head = nd;
else
{
    ...
}

Следующая конструкция выбора служит для определения: создается первый узел в списке или он уже не первый. В случае, если создается только первый узел, то head будет в NULL и выполнится условие после if, т.е. head присвоится адрес первого узла в памяти. В последующих случаях, когда создаются 2, 3, 4, 5, ... узлы будет срабатывать блок после else. Его рассмотрим подробнее...

Node *current = head;

while(current->next != NULL)
    current = current->next;

current->next = nd;

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

Динамический список - добавление новых узлов

Осталось рассмотреть метод для вывода элементов динамического списка на экран

//метод, выводящий связанный список на экран
void printList()
{
    Node *current = head;

    while(current != NULL)
    {
        cout << current->data << endl;
        current = current->next;
    }
}

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

Однонаправленный связанный список, узлы добавляются в начало списка

Нами был рассмотрен классический вариант динамического списка, в котором новые узлы добавляются в конец, но есть еще вариант, когда узлы добаляются в начало, кстати, код такой программы немного меньше и проще. Его мы сейчас и рассмотрим.

//Динамический список
//Новые узлы добавляются в начало

#include <iostream>

using namespace std;

struct Node
{
    int data;
    Node *next;
};

class List
{
private:
    Node *head;

public:
    List()
    {
        head = NULL;
    }

    void addNode(int d)
    {
        Node *nd = new Node();

        nd->data = d;
        nd->next = head;
        head = nd;
    }

    void printList()
    {
        Node *current = head;

        while(current)
        {
            cout << current->data << endl;
            current = current->next;
        }
    }
};

int main()
{
    List ls;

    ls.addNode(134);
    ls.addNode(2387);
    ls.addNode(5);
    ls.addNode(74);
    ls.addNode(0);

    ls.printList();

    return 0;
}

Результат работы программы, реализующей динамический список

Рассмотрев код программы, видим, что изменился метод добавления нового узла в список. Теперь новый узел как бы вклинивается между "головой" списка и следующим после нее узлом. Соответственно, в результатах работы мы видим в какой последовательности выводятся значения, находящиеся в узлах. Если вам подходит такой вариант обратного вывода, то можете использовать этот код.

Двунаправленный связанный список

Когда-то я сам активно занимался изучением принципа работы связанного списка, затем пробовал написать программу - были ошибки и заблуждения, но после определенных трудов все же решение пришло - я написал программу, реализующую алгоритм работы динамического списка. Затем мне захотелось усовершенствовать данную программу и переделать однонаправленный динамический список в двунаправленный. Как это понять... В однонаправленном мы могли перемещаться только в одно направление и не могли вернуться назад, т.к. любой из следующих узлов не содержал в себе указателя на предыдущий. Также я добавил в программу возможность добавлять узлы как в начало списка, так и в конец, узлы теперь нумеруются, есть возможность удаления и поиска по ключу. Одним словом, привожу ниже код, ну а вы уже смотрите и разбирайтесь.

//Связанный список (динамический список)

#include <iostream>
using namespace std;

class Node        //один узел, представленный в виде структуры
{
friend class List;//объявляем класс Список дружественным, чтобы он имел доступ к закрытым полям
private:
    int key;       //номер узла в списке
    int data;      //данные, содержащиеся в узле
    Node *next;    //указатель на следующую структуру
    Node *last;    //указатель на предыдущую структуру

public:
    Node(int data, Node *next, Node *last)
    {
        this->data = data;
        this->next = next;
        this->last = last;
    }

    Node(int data)
    {
        this->data = data;
    }
};

class List        //класс, описывающий объект "список"
{
private:
    Node *head;   //голова списка (указатель на первый узел в списке)
    Node *temp;   //указатель на последний узел в списке

public:
    List() : head(NULL), temp(NULL) //в первом созданном объекта указатель равен нулю, т.к. следующего объекта еще нет и указывать не на что
    {
    }

    void addNodeEnd(int data)     //метод, добавляющий узел в конец списка
    {
        Node *nd = new Node(data, NULL, temp); //создаем новый узел, добавляем в него данные и делаем его последним, присваивая NULL
        temp = nd;

        if(head)
        {
            Node *current = head;  //указывает на начало списка, на первый узел; и используется в цикле для нахождения предыдущего узла
            while(current->next)   //прокручиваем в цикле наш список, пока не дойдем до последнего узла, остановившись на предыдущем
                current = current->next; //переходим на следующий узел

                current->next = nd;    //предыдущий указывает на следующий узел
        }
        else                       //если список был пуст и создается первый узел, то голова указывает на него
            head = nd;             //у головы бывает два состояния: она либо NULL, либо указывает на первый узел в списке

        numNode(); //нумеруем узлы списка
    }

    void addNodeBeginning(int data)   //метод, добавляющий узел в начало списка
    {
        Node *nd = new Node(data);

        if(head) //если уже есть узлы в списке
        {
            Node *tmp = head;
            head = nd;
            nd->next = tmp;
        }
        else    //если список пуст
        {
            head = nd;
            nd->next = NULL;
        }

        numNode();
    }

    void deleteNodeEnd() //удаление узла в конце списка
    {
        if(temp)
        {
            Node *current = temp;
            current = current->last;
            delete current->next;
            current->next = NULL;
        }
        else
            cout << "The list is empty!" << endl;
    }

    void deleteNodeBeginning() //удаление узла в начале списка
    {
        if(head)
        {
            Node *tmp = head;
            tmp = tmp->next;
            delete head;     //освобождаем память по этому адресу
            head = tmp;      //и задаем новое значение
        }
        else
            cout << "The list is empty!" << endl;

        numNode();
    }

    int find(int k) //поиск по ключу в списке
    {
        Node *counter = head;
        while(counter)
        {
            if(counter->key == k)
                return counter->data;

            counter = counter->next;
        }
    }

    void printListForward() const //выводим на печать наш список в прямом порядке
    {
        Node *current = head;
        while(current)             //пока не дойдем до последнего узла
        {
            cout << current->key << " - " << current->data << endl;   //выводим данные на экран
            current = current->next;         //переходим к следующему узлу
        }
    }

    void printListBack() const     //выводим на печать наш список в обратном порядке
    {
        Node *current = temp;
        while(current)
        {
            cout << current->key << " - " << current->data << endl;
            current = current->last;
        }
    }

    void numNode() //внутренняя функция-утилита, нумерует узлы списка
    {
        Node *counter = head;
        int i = 0;
        while(counter)
        {
            counter->key = ++i;
            counter = counter->next;
        }
    }
};

int main()
{
    List n; //создаем экземпляр класса List
    int key;

    n.addNodeEnd(21);  //вызываем метод addNode класса List (добавление узла)
    n.addNodeEnd(32);
    n.addNodeEnd(47);
    n.addNodeEnd(63);
    n.addNodeEnd(78);
    n.addNodeEnd(83);
    n.addNodeEnd(97);
    n.addNodeEnd(98);

    n.printListForward();
    cout << endl;
    n.printListBack();

    n.addNodeBeginning(17);
    n.addNodeBeginning(15);
    n.addNodeBeginning(10);
    n.addNodeBeginning(3);

    cout << endl;
    n.printListForward();

    n.deleteNodeEnd();
    cout << endl;
    n.printListForward();

    n.deleteNodeBeginning();
    cout << endl;
    n.printListForward();

    cout << "Enter a number of node: ";
    cin >> key;
    cout << "Data node " << key << " = " << n.find(key) << endl;
}