История о том, как встретились 2 программиста, и зашел у них разговор про связные списки
Эта статья является комментарием к Nick Parlante.
Написана она в полу-шутливой манере, в форме диалога.
$1 РАЗГОВОР О ТОМ, ЧТО ТАКОЕ СВЯЗНЫЕ СПИСКИ И КАК ОНИ УСТРОЕНЫ
Встретились значит однажды 2 друга - Олег, студент - первокурсник, и Артем - программист, и зашел у них
следующий разговор:
О: Слушай, мне нужна структура данных, которая позволяет организовать хранение информации,
обычный массив не подходит, нужно что-то другое.
А: Чем тебе массив не угодил ?
О: Да преподаватель сказал, что структура хранения должна в принципе отличаться от массива.
В частности, нельзя обращаться к данным по индексу.
А: Ну тогда связные списки тебе в руки.
О: А что это такое - связные списки ?
А: Ну вот смотри: представь себе строго упорядоченную очередь, каждый в такой очереди совершенно
точно знает, кто стоит впереди него, но ничего не знает о том, кто стоит позади него - такую очередь
называют односвязным списком.
О: Бывают другие очереди ?
А: Бывают - это когда ты знаешь не только того, кто стоит впереди тебя, но и кто позади -
это 2-связный список.
О: В чем принципиальное отличие такого списка от того же массива ?
А: Обычный массив отличается тем, что у каждого на груди есть
табличка с порядковым номером, и всегда можно скомандовать: 5-й номер - выйти из строя!
Когда 5-й номер выходит, выясняется например, что это Иванов.
О: А как в твоем связном списке найти Иванова ?
А: Нужно сделать перекличку с самого начала. Эта перекличка идет строго по порядку очереди до тех пор,
пока не будет найден искомый.
О: Понятно. Т.е. получается, что массив - фиксированная структура, т.е. всегда известен его размер?
А: Да, размер массива фиксирован. А вот размер связного списка ничем не ограничен - в любой момент
в нее может быть добавлен новый элемент, т.е. это "резиновая" структура данных.
О: Если мне нужна структура данных, размер которой заранее неизвестен, получается, что подходит
как раз список. А если мне нужно изменять размер структуры данных как в сторону увеличения,
так и в сторону уменьшения ?
А: Ну с массивом у тебя этот номер вообще не пройдет - нельзя ни уменьшать его размер, ни увеличивать.
Размер стандартного массива, что называется, забивается гвоздями. А вот со списком можно делать и то,
и другое - можно добавлять в него элементы, можно удалять элементы.
О: Ну это круто - список воистину очень гибкая структура.
А: Гибкая-то она гибкая, только вот поаккуратней с ней надо быть.
О: В каком смысле ?
А: Когда например удаляешь элемент из списка, ты обрываешь связи с элементами, которые могут стоять
как спереди, так и позади тебя. Нужно эти два элемента привязать друг к другу.
О: А, я знаю - нужно переназначить указатели.
А: Вот-вот, допустим, ты покидаешь очередь, и указатель предыдущего элемента, который указывал
на тебя, нужно перекинуть на следующего.
О: И что в этом сложного ?
А: Да ничего, просто надо помнить, что это переназначение указателя необходимо выполнять всегда.
Потому что если ты этого не сделаешь хотя бы раз, можешь попрощаться со списком.
О: В каком смысле ?
А: Произойдет частичная потеря данных, причем необратимая.
О: Ну в этом же нет ничего сложного - переназначить указатель, только и всего.
А: Конечно . Вообще, для изучения списков есть несколько веских причин. Они широко
используются в реальных проектах - я не имею ввиду студенческие лабораторные работы, я имею ввиду
операционные системы, базы данных, огромное количество приложений, да куда ни ткни - везде списки.
Те, кто используют списки, хорошо владеют арифметикой указателей.
О: Хорошо. Я морально созрел. Давай показывай на пальцах, как они работают.
А: Вот смотри: обьявим массив в 100 элеметов и проинициализируем первые 3 элемента:
int my_array[100];
my_array[0]=1;
my_array[1]=20;
my_array[2]=100;
Физически в памяти все 100 элементов располагаются подряд, и индекс элемента есть фактически смещение
в этом блоке памяти от начала, поэтому взятие элемента по индексу - это очень быстро. поскольку
это адресная арифметика.
О: Мне это как раз и не нужно
А: Да, я помню. Память для массива выделяется на этапе компиляции, и сделать с ним уже ничего нельзя.
$2 ПРО УКАЗАТЕЛИ
О: Что нужно знать для того, чтобы использовать указатели?
А: Первое: указатель может указывать как на конкретный обьект, так и ни на что не указывать.
О: В смысле ?
А: В последнем случае указатель может быть установлен в NULL.
Далее - указатель может быть РАЗИМЕНОВАН, то бишь можно всегда поменять обьект, на который он указывает
О: Т.е. указатель жестко ни к чему не привязывается ?
А: Да. Далее - указатель может быть ПЛОХИМ.
О: Дай угадаю - это когда создали указатель и ни к чему не привязали ?
А: Точно. А потом где-то взяли и попытались разименовать - и опаньки, программа накрывается.
О: Почему ?
А: Попытка использовать непроинициализированный обьект. Кстати, когда в java создается указатель,
он по умолчанию всегда устанавливается в NULL.
О: Называется подстраховались.
А: Далее - указатель может быть НАЗНАЧЕН. Например, если есть два указателя - a и b,
то между ними возможна операция назначения:
a = b
После чего 2 указателя указывают на одну и ту же область памяти - которая как называется ?
О: Я знаю - это расшаренная память.
А: Да - но не от слова "шарить", а от "shared".
О: Про указатели я понял - для работы с ними нужна аккуратность и ряд правил, иначе возможны проблемы.
У меня вопрос про то, где и как выделяется память, когда в список добавляется новый элемент.
А: Память под это дело выделяется, как принято говорить, в куче - "heap" по английски.
Это такая область памяти, которая может быть использована программой на протяжении всей ее жизни.
Для выделения памяти мы будем использовать функцию malloc()
О: Я знаю, что она делает - она выделяет блок памяти.
А: Либо ничего не выделяет, если не хватает места - в этом случае она может вернуть NULL.
Этот блок памяти, который был откушен у системы, может быть вернут назад с помощью функции free().
О: Таким образом, получается, что элементы списка могут быть раскиданы по куче как попало ?
А: Да, так оно и происходит, в отличие от массива, который представляет из себя один непрерывный
кусок памяти.
$3 ЧТО ТАКОЕ НОДА
Теперь пришло время ввести новое понятие - НОДА. Это такая область памяти, в которой хранится
ячейка связного списка. Нода состоит из 2-х полей - в первом хранятся данные.
О: А во втором - указатель на следующую ноду ?
А: Точно. Существует специальный отдельный головной - "head" - указатель, который указывает на первую ноду.
Он не принадлежит списку, это просто отдельная локальная переменная.
О: А куда указывает последняя нода ?
А: В никуда - точнее, она указывает на NULL.
О: Голова может быть пустой ? В смысле - головной указатель может указывать на NULL ?
А: Может - пустой список в таком случае получается.
О: Немного непривычный подход. После массивов переход к спискам словно открывает глаза на то,
что происходит с обьектами на уровне физической памяти, как-то все начинает вставать на свои места.
А: Это и неудивительно. Стандартные массивы - это суррогаты реальных обьектов, которые используются
на практике. Массивы искажают реальную картину и не дают полного представления о том, что же
происходит на самом деле. Протри глаза и войди в мир реальных программ.
О: И реальных пацанов ?
А: Нет, это немного из другой оперы. Теперь пришло время изобразить нашу ноду :
struct node
{
int data;
struct node* next;
};
Мы используем классический си-шный вариант и в качестве типа ноды используем структуру.
О: Как-то непривычно видеть внутри структуры указатель на другую структуру.
А: Это всего лишь обьявление, и не более того. Пока мы не создали ничего, мы можем обьявлять
все что угодно.
О: Что разрешено, то не запрещено ?
А: Точно. Это указатель того же типа, что и сама нода. Он указывает на другую ноду.
Головной указатель имеет точно такой же тип.
О: Непривычно то, что указатель может иметь произвольный тип - в данном случае это тип структуры.
А: Все правильно - указатель может иметь какой угодно произвольный тип.
О: Вот это меня и смущает.
А: Привыкай. После обьявления теперь давай создадим три пустых нодовых указателя:
struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;
О: Которые указывают на одну и ту же область памяти ?
А: Ничего подобного. Они все указывают на разные области памяти, в которых хранятся NULL.
Теперь создадим 3 ноды:
head = malloc(sizeof(struct node));
second = malloc(sizeof(struct node));
third = malloc(sizeof(struct node));
О: А, это мы раз-именование указателя сделали. Зачем нужен оператор sizeof ?
А: Он автоматически вычисляет размер ноды и передает его в байтах функции malloc.
Теперь проинициализируем каждую ноду:
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
О: А что это за стрелки такие ?
А: Когда ты создаешь указатель на структуру, то для того, чтобы в дальнейшем через указатель
обращаться к элементам структуры, используется оператор ->. Это очень удобно, что позволяет
создавать произвольное количество полей внутри структуры.
$4 КАК УЗНАТЬ ДЛИНУ СВЯЗНОГО СПИСКА
О: Когда мы говорили о масииве, то было сказано, что размер массива известен с самого начала.
Как можно узнать размер списка ?
А: Нужно организовать проход по списку и посчитать в нем количество элементов.
Вот пример функции, подсчитывающей число нод:
int Length(struct node* head)
{
struct node* current = head;
int count = 0;
while (current != NULL)
{
count++;
current = current->next;
}
return count;
}
О: Сразу возник вопрос: зачем в этой функции создается дополнительный указатель - почему нельзя
вместо него воспользоваться параметром функции head ?
А: Хороший вопрос. Можно не создавать локальную копию current и использовать параметр функции head,
при этом она будет работать точно так же. Тут current создается скорее для наглядности.
Здесь мы вводим понятие итерации связного списка - я имею ввиду строку
current = current->next;
Прошу обратить внимание на эту операцию - при этой операции со списком ничего не происходит,
но происходит с указателем - указателю НАЗНАЧАЕТСЯ новое значение, помнишь - мы говорили про операцию
с указателями
a = b
Сразу вопрос: что произойдет, если мы вызовем эту функцию для пустого списка ?
О: У пустого списка вершина равна NULL - значит - мы пролетаем мимо цикла while.
А: Точно - функция вернет ноль.
$5 ДОБАВЛЯЕМ НОДУ В НАЧАЛО СПИСКА
А: Сейчас мы напишем функцию, которая добавляет новый элемент в вершину списка, а не в конец,
и назовем ее стандарным образом - Push(). И сделаем это намеренно неправильно.
Угадай с трех раз, где ошибка :
void WrongPush(struct node* head, int data)
{
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->next = head;
head = newNode;
}
О: Так: создаем в функции локальный обьект ноды, заполняем поле данными, далее становимся
в голову списка, и последний штрих - присваиваем указатель на вершину списка на вновь созданную.
Вроде все правильно.
А: Все да не все. Последняя строчка в этой функции не работает.
О: Почему? Мы же переназначаем указатель на вершину списка на вновь созданную ноду.
А: Все правильно. И после того как выходим из функции, тут же стираем этот указатель.
Ты забыл о том, что head - это локальный указатель, который погибает после возвращения функции.
Пришло время поговорить про ссылочные параметры. Вообще говоря, параметры, передаваемые в функцию,
после возвращения из функции обычно не меняются, поскольку передаются по значению.
А вот если возникает необходимость его изменить, параметр передают по ссылке - точнее сказать,
передают не сам параметр, а указатель на него.
О: Ну дак первый параметр и так же был указателем.
А: Дело в том, что по умолчанию, указатель на голову уже сам по себе является указателем.
В данном случае речь идет о том, что нам нужно создать указатель на указатель
О: Масло масляное.
А: Привыкай к двойным указателям, но не привыкай к двойным стандартам.
Двойные указатели - это привычный атрибут в классическом си. Правильный вариант функции Push
выглядит вот так:
void Push(struct node** headRef, int data)
{
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->next = *headRef;
*headRef = newNode;
}
О: С не-привычки крышу сносит. Одного указателя почему-то мало. Ну ладно.
А: Теперь показываю, как можно использовать функцию Push:
struct node* head = NULL; //
Push(&head, 1);
Push(&head, 2);
Push(&head, 3);
О: Что это за лямбда & ?
А: Это указание компилятору, что параметр передается по ссылке, т.е. все изменения, которые могут
быть сделаны с эти параметром внутри вызываемой функции, останутся актуальными и после выхода из функции.
При использовании параметров по ссылке нужно придерживаться 3-х правил:
1. В определении функции для указателей нужно использовать двойной указатель **
2. При вызове функции перед ссылочным параметром нужно поставить лямбду &
3. В самой функции к ссылочному параметру обращаться через указатель *
О: Да, теперь я понял, зачем нужен указатель перед headRef в теле самой функции.
А: Когда я привел в качестве примера функцию Length, в ней использовался цикл while.
Но никто не запрещает вместо while использовать другой оператор цикла, более популярный - for.
Аналогично цикл прописывается вот так:
for (current = head; current != NULL; current = current->next) {
О: while как-то более понятен
А: На вкус и цвет товарищей нет, это в принципе без разницы.
Кстати, вариант с Push в качестве добавления один из самых простых и быстрых.
О: Но элементы добавляются в обратном порядке.
А: Это плата за простоту.
$6 ДОБАВЛЯЕМ НОДУ В КОНЕЦ СПИСКА
А: Теперь рассмотрим пример с добавлением ноды в конец списка.
struct node* AppendNode(struct node** headRef, int num)
{
struct node* current = *headRef;
struct node* newNode;
newNode = malloc(sizeof(struct node));
newNode->data = num;
newNode->next = NULL;
// если список пуст
if (current == NULL) {
*headRef = newNode;
}
else {
// иначе
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
}
О: Я понял - нужно пройтись по всему списку, как мы это делали в Length, дойти до последней
ноды и у нее назначить указатель next. Семечки. Все просто.
А: Теперь предлагаю поиграться с этим примером. Давай заменим строку
*headRef = newNode;
на вызов функции Push
О: Что делает эта строка ? Мы определили, что список пуст, и в его голову помещаем только что
созданную ноду. Просто берем предыдущий пример:
Push(&headRef, num);
А: Ошибочка вышла. Первый параметр взят неправильно.
О: Мы же должны передать ссылку ?
А: headRef уже является ссылкой, и поэтому правильно будет так:
Push(headRef, num);
О: Понял.
А: Предлагаю заменить еще одну строку в последнем примере на вызов Push - речь идет о строке
current->next = newNode;
О: Аналогично:
Push(&(current->next), num);
А: А это уже лучше - ты растешь на глазах. Все правильно - первый параметр функции Push
является ссылочным аргументом, и ты этого не забыл.
О: А то.
$7 КОПИРУЕМ СПИСОК
А: Напишем функцию, которая делает копию для уже существующего списка.
В ней ты можешь увидеть целых 3 указателя. Первый - current - указывает на вершину оригинального списка.
Второй - newList - указывает на вершину копии, третий - tail - на последнюю ноду копии.
struct node* CopyList(struct node* head)
{
struct node* current = head;
struct node* newList = NULL;
struct node* tail = NULL;
while (current != NULL)
{
if (newList == NULL) // создаем первую ноду списка
{
newList = malloc(sizeof(struct node));
newList->data = current->data;
newList->next = NULL;
tail = newList;
}
else
{
tail->next = malloc(sizeof(struct node));
tail = tail->next;
tail->data = current->data;
tail->next = NULL;
}
current = current->next;
}
return(newList);
}
О: Понятно. Делаем проход по нодам оригинального списка и для каждой ноды делаем копию.
А: Предлагаю сделать модернизацию этого кода с использованием Push
О: Я знаю - три строки
newList = malloc(sizeof(struct node));
newList->data = current->data;
newList->next = NULL;
меняем на одну
Push(&newList, current->data);
три других строки
tail->next = malloc(sizeof(struct node));
tail = tail->next;
tail->data = current->data;
меняем на
Push(&(tail->next), current->data);
Вроде все просто, но все равно как-то все непривычно это. Спроси у меня об этом завтра -
и я наделаю кучу ошибок.
А: Ну дак это только первые 5 лет тяжело - потом привыкаешь.
А на закуску я предлагаю рекурсивный вариант копирования списка:
struct node* CopyList(struct node* head)
{
struct node* current = head;
if (head == NULL) return NULL;
else
{
struct node* newList = malloc(sizeof(struct node));
newList->data = current->data;
newList->next = CopyList(current->next);
return(newList);
}
}
И: ОК.
А: Теперь обьединим весь рассмотренный код как единое целое, как одну программу :
#include < stdio.h>
#include < stdlib.h>
struct node
{
int data;
struct node * next;
};
int num = 0 ;
int Length(struct node *head)
{
struct node * current = head;
int count=0;
while(current !=NULL)
{
printf("%d\n",current->data);
count++;
current=current->next;
if(current==head) break;
}
printf("=========\n");
}
void Push (struct node ** head , int data)
{
struct node * new = malloc(sizeof(struct node));
new->data=data;
new->next=*head;
*head=new;
}
struct node* CopyList(struct node* head)
{
struct node* current = head;
if (head == NULL) return NULL;
else
{
struct node* newList = malloc(sizeof(struct node));
newList->data = current->data;
newList->next = CopyList(current->next);
return(newList);
}
}
int main()
{
struct node * List = NULL;
Push(&List,1);
Push(&List,2);
Push(&List,3);
Push(&List,4);
Push(&List,5);
Push(&List,6);
int len = Length(List);
struct node * List2 = NULL;
List2 = CopyList(List);
len = Length(List2);
return 0;
}
|
olga | Огромное спасибо! В доступной форме рассказано самое главное про списки и указатели. Но для "особо одарённых"
вроде меня хотелось бы видеть побольше комментариев.
Ещё раз спасибо. 2014-04-25 17:07:31 | Андрей | Реально очень доступно рассказано! Автор - молодец!!!
Долго не мог понять тему "связные списки". После прочтения - понял!
Спасибо огромное!
С уважением,
Андрей
2014-05-19 22:49:55 | |
|