Привет всем) Это - моя первая статья на vr-online, и что там vr, это - вообще моя первая статья =). Поэтому очень не ругайте, если что-то не так. Статья, как видно из заголовка, будет о динамических списках.Попробую вам объяснить, что такое динамические списки и показать простейшие примеры работы с ними. Для понимания всего, что будет ниже нужны начальные знания по С++. Вы должны уметь работать со структурами, указателями, циклами. Ну, что ж, вводная часть закончилась. Перейдем к основной.

Связные списки - структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. Существует несколько видов списков, вот некоторые из них: односвязный однонаправленный, односвязный кольцевой двусвязный однонаправленный, двусвязный кольцевой.

Односвязный однонаправленный список.

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

Давайте подумаем, какие функции могут нам понадобиться для работы со списком. Наверное, это - организация самого списка, вывод списка, сортировка списка, вставка нового элемента в отсортированный список. Так что сначала надо организовать сам узел, из совокупности которых будет формироваться список.

struct list
{
int item; //полезная информация узла списка
list *next;//ссылка на следующий элемент списка.
};

Теперь нам нужно создать переменную start типа list, которая будет указывать на первый элемент
списка.

list *start = new list; //выделяем память для первого элемента
start->next = NULL; // на данный момент первый элемент одновременно является и последним том next ссылается на NULL

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

list *p_list = start;
for (int i=0; i<20; i+=2)
{
list *tmp = new list; //Выделяем память для
tmp->item = i; // здесь все понятно
tmp->next = NULL; //мы вставляем узел в конец списка и поэтому next = NULL
p_list->next = tmp; //теперь p_list-> next указывает на созданный узел
p_list = p_list->next;// Передвигаем указатель на последний элемент.
}

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

Давайте выведем в консоль созданный список. Для этого напишем отдельную функцию:

void show (list *start)//параметр - указатель на начало списка.
{
list *p_list; //рабочий указатель
p_list = start->next;//в начале он ссылается на второй узел списка.
while (p_list != NULL)
{
cout << p_list->item << endl;//Выводим данные
p_list = p_list->next;//передвигаем указатель на один узел.
}
}

Здесь вроде все ясно становится из комментариев) Теперь напишем функцию, которая будет вставлять элемент в отсортированный список. В этой функции есть два нюанса: надо проверять, нужно вставить элемент в начало списка или в конец. void insert (list *start, int el)//указатель на начало списка, число которое нужно вставить в список. { list *p_list;//рабочий указатель. p_list = start->next;//в начале он ссылается на второй узел списка. while (p_list->next != NULL) { if (p_list == start->next && p_list->item >el) //эта проверка нужна для того, чтоб проверить не надо ли вставить елемент в начало списка. { list *temp = new list; //временная переменная, в которую будем записывать узел, на который ссылается p_list *temp = *p_list;//запоминаем *p_list в *tmp. Здесь мы запоминаем не адрес, а именно значение p_list->item = el;//теперь в item записываем елемент который нужно было вставить в список. p_list->next = temp;//и в next записываем адрес tmp break; } if (p_list->item <= el && p_list->next->item >= el) //Если элемент надо вставить не на начало и не в конец списка. {

list *tmp = new list;//Выделяем память для нового узла
tmp->item = el;
tmp->next = p_list->next;
p_list->next = tmp; //Вставляем узел после узла, на который указывает p_list
break;
}
p_list = p_list->next; //передвигаем указатель на следующий элемент.
if (p_list->next == NULL && el>=p_list->item) //Проверяем не нужно вставить узел в конец списка.
{
list *tmp = new list;
tmp->item = el;
tmp->next = NULL; //Так как вставляем узел в конец списка то его элемент next должен ссылаться на NULL
p_list->next = tmp;//вставляем узел в список.
break;
}

}
}

Попробуйте нарисовать схему вставки элемента в список. Это будет ваше домашнее задание)
Теперь напишем функцию, которая будет сортировать список. Будем использовать один из простейших алгоритмов сортировки - сортировка пузырьком.

void sort(list *start) //параметр - указатель на начало списка.
{
list *p_list; // указатель для внешнего цыкла for
list *pp_list; // для внутреннего
for (p_list = start->next; p_list != NULL; p_list = p_list->next) //пробегаемся по всех узлах списка
for (pp_list = start->next; pp_list->next != NULL; pp_list = pp_list->next) //а здесь только до узла, next которого указывает на NULL
//обычный обмен значениями
if (pp_list->item > pp_list->next->item)
{
int tmp;
tmp = pp_list->item; //
pp_list->item = pp_list->next->item;
pp_list->next->item = tmp;
}

}

И последняя функция - удаление элемента из списка:

void dell(list *start, int el) //указатель на начало списка, и значение которое мы будем искать в списке, если найдем значит нужно удалить.
{
list *p_list = start->next; //рабочий указатель, который будем использовать для пробега по списку.
list *prev = start; //указатель, который всегда будет указывать на элемент предыдущий до p_list.
while (p_list != NULL) //пробегаемся по всему списку
{
//проверка - нужно ли удаление
if (p_list->item == el)
{
// временней узел, в который будем записывать значение того узла который нужно удалить.
list *tmp = new list;
*tmp = *p_list;
//теперь нужно сделать так, чтоб элемент next предыдущего узла указывал на узел, который идет после p_list,то есть на p_list->next
prev->next = p_list->next;
delete tmp;
}
prev = p_list; // перемещаем указатель prev на один элемент
p_list = p_list->next; //так же перемещаем next.
}
}

Вот как это примерно выглядит:

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

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

На этом все) если кого-то заинтересовала эта тема, то позже будет продолжение) опишу работу с односвязным кольцевым списком, двусвязным, двусвязным кольцевыми.
Возможны грамматические ошибки) русский не является моим родным языком) готов выслушать все замечания).

Исходник: