Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
 iakovlev.org 
 Languages
 С
 GNU С Library 
 Qt 
 STL 
 Threads 
 C++ 
 Samples 
 stanford.edu 
 ANSI C
 Libs
 LD
 Socket
 Pusher
 Pipes
 Encryption
 Plugin
 Inter-Process
 Errors
 Deep C Secrets
 C + UNIX
 Linked Lists / Trees
 Asm
 Perl
 Python
 Shell
 Erlang
 Go
 Rust
 Алгоритмы
NEWS
Последние статьи :
  Тренажёр 16.01   
  Эльбрус 05.12   
  Алгоритмы 12.04   
  Rust 07.11   
  Go 25.12   
  EXT4 10.11   
  FS benchmark 15.09   
  Сетунь 23.07   
  Trees 25.06   
  Apache 03.02   
 
TOP 20
 Linux Kernel 2.6...3653 
 Trees...490 
 Clickhouse...460 
 Go Web ...455 
 Ethreal 4...452 
 Максвелл 3...421 
 Ext4 FS...412 
 C++ Patterns 3...402 
 Rodriguez 6...397 
 William Gropp...390 
 Ethreal 1...385 
 Gary V.Vaughan-> Libtool...382 
 Secure Programming for Li...382 
 Steve Pate 1...381 
 Ethreal 3...371 
 Assembler...361 
 DevFS...359 
 Стивенс 9...353 
 Ulrich Drepper...349 
 Стивенс 10...324 
 
  01.01.2024 : 3621733 посещений 

iakovlev.org

История о том, как встретились 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