История о том, как встретились 2 программиста, и зашел у них разговор про связные списки

$1 РАЗГОВОР О ТОМ, ЧТО ТАКОЕ СВЯЗНЫЕ СПИСКИ И КАК ОНИ УСТРОЕНЫ

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

А: Чем тебе массив не угодил ?

О: Да преподаватель сказал, что структура хранения должна в принципе отличаться от массива. В частности, нельзя обращаться к данным по индексу.

А: Ну тогда связные списки тебе в руки.

О: А что это такое - связные списки ?

А: Ну вот смотри: представь себе строго упорядоченную очередь, каждый в такой очереди совершенно точно знает, кто стоит впереди него, но ничего не знает о том, кто стоит позади него - такую очередь называют односвязным списком.

О: Бывают другие очереди ?

А: Бывают - это когда ты знаешь не только того, кто стоит впереди тебя, но и кто позади - это 2-связный список.

О: В чем принципиальное отличие такого списка от того же массива ?

А: Обычный массив отличается тем, что у каждого на груди есть табличка с порядковым номером, и всегда можно скомандовать: 5-й номер - выйти из строя! Когда 5-й номер выходит, выясняется например, что это Иванов.

О: А как в твоем связном списке найти Иванова ?

А: Нужно сделать перекличку с самого начала. Эта перекличка идет строго по порядку очереди до тех пор, пока не будет найден искомый.

О: Понятно. Т.е. получается, что массив - фиксированная структура, т.е. всегда известен его размер?

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

О: Если мне нужна структура данных, размер которой заранее неизвестен, получается, что подходит как раз список. А если мне нужно изменять размер структуры данных как в сторону увеличения, так и в сторону уменьшения ?

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

О: Ну это круто - список воистину очень гибкая структура.

А: Гибкая-то она гибкая, только вот поаккуратней с ней надо быть.

О: В каком смысле ?

А: Когда например удаляешь элемент из списка, ты обрываешь связи с элементами, которые могут стоять как спереди, так и позади тебя. Нужно эти два элемента привязать друг к другу.

О: А, я знаю - нужно переназначить указатели.

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

О: И что в этом сложного ?

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

О: В каком смысле ?

А: Произойдет частичная потеря данных, причем необратимая.

О: Ну в этом же нет ничего сложного - переназначить указатель, только и всего.

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

О: Хорошо. Я морально созрел. Давай показывай на пальцах, как они работают.

А: Вот смотри: обьявим массив в 100 элеметов и проинициализируем первые 3 элемента:

 
 	int my_array[100];
 	my_array[0]=1;
 	my_array[1]=20;
 	my_array[2]=100;
 

О: Мне это как раз и не нужно

А: Да, я помню. Память для массива выделяется на этапе компиляции, и сделать с ним уже ничего нельзя.

$2 ПРО УКАЗАТЕЛИ

А: Первое: указатель может указывать как на конкретный обьект, так и ни на что не указывать.

О: В смысле ?

А: В последнем случае указатель может быть установлен в NULL. Далее - указатель может быть РАЗИМЕНОВАН, то бишь можно всегда поменять обьект, на который он указывает

О: Т.е. указатель жестко ни к чему не привязывается ?

А: Да. Далее - указатель может быть ПЛОХИМ.

О: Дай угадаю - это когда создали указатель и ни к чему не привязали ?

А: Точно. А потом где-то взяли и попытались разименовать - и опаньки, программа накрывается.

О: Почему ?

А: Попытка использовать непроинициализированный обьект. Кстати, когда в java создается указатель, он по умолчанию всегда устанавливается в NULL.

О: Называется подстраховались.

А: Далее - указатель может быть НАЗНАЧЕН. Например, если есть два указателя - a и b, то между ними возможна операция назначения:

a = b

После чего 2 указателя указывают на одну и ту же область памяти - которая как называется ?

О: Я знаю - это расшаренная память.

А: Да - но не от слова "шарить", а от "shared".

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

А: Память под это дело выделяется, как принято говорить, в куче - "heap" по английски. Это такая область памяти, которая может быть использована программой на протяжении всей ее жизни. Для выделения памяти мы будем использовать функцию malloc()

О: Я знаю, что она делает - она выделяет блок памяти.

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

О: Таким образом, получается, что элементы списка могут быть раскиданы по куче как попало ?

А: Да, так оно и происходит, в отличие от массива, который представляет из себя один непрерывный кусок памяти.

$3 ЧТО ТАКОЕ НОДА

О: А во втором - указатель на следующую ноду ?

А: Точно. Существует специальный отдельный головной - "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));
 

А: Он автоматически вычисляет размер ноды и передает его в байтах функции 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;
 	}
 

А: Хороший вопрос. Можно не создавать локальную копию current и использовать параметр функции head, при этом она будет работать точно так же. Тут current создается скорее для наглядности. Здесь мы вводим понятие итерации связного списка - я имею ввиду строку

current = current->next;

Прошу обратить внимание на эту операцию - при этой операции со списком ничего не происходит, но происходит с указателем - указателю НАЗНАЧАЕТСЯ новое значение, помнишь - мы говорили про операцию с указателями

a = b

Сразу вопрос: что произойдет, если мы вызовем эту функцию для пустого списка ?

О: У пустого списка вершина равна NULL - значит - мы пролетаем мимо цикла while.

А: Точно - функция вернет ноль.

$5 ДОБАВЛЯЕМ НОДУ В НАЧАЛО СПИСКА

 
 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;
    }
 }
 

А: Теперь предлагаю поиграться с этим примером. Давай заменим строку

*headRef = newNode;

на вызов функции Push

О: Что делает эта строка ? Мы определили, что список пуст, и в его голову помещаем только что созданную ноду. Просто берем предыдущий пример:

Push(&headRef, num);

А: Ошибочка вышла. Первый параметр взят неправильно.

О: Мы же должны передать ссылку ?

А: headRef уже является ссылкой, и поэтому правильно будет так:

Push(headRef, num);

О: Понял.

А: Предлагаю заменить еще одну строку в последнем примере на вызов Push - речь идет о строке

current->next = newNode;

О: Аналогично:

Push(&(current->next), num);

А: А это уже лучше - ты растешь на глазах. Все правильно - первый параметр функции Push является ссылочным аргументом, и ты этого не забыл.

О: А то.

$7 КОПИРУЕМ СПИСОК

 
 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