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

Структуры данных / Двусвязный линейный список

 

Каждый узел двунаправленного (двусвязного) линейного списка (ДЛС) содержит два поля указателей — на следующий и на предыдущий узлы. Указатель на предыдущий узел корня списка содержит нулевое значение. Указатель на следующий узел последнего узла также содержит нулевое значение.
Двусвязный линейный список
Узел ДЛС можно представить в виде структуры:

 
 
 
 
 
 
struct list
{
  int field; // поле данных
  struct list *next; // указатель на следующий элемент
  struct list *prev; // указатель на предыдущий элемент
};


Основные действия, производимые над узлами ДЛС:

  • Инициализация списка
  • Добавление узла в список
  • Удаление узла из списка
  • Удаление корня списка
  • Вывод элементов списка
  • Вывод элементов списка в обратном порядке
  • Взаимообмен двух узлов списка

 

Инициализация ДЛС

Инициализация списка предназначена для создания корневого узла списка, у которого поля указателей на следующий и предыдущий узлы содержат нулевое значение.
Инициализация двусвязного линейного списка

1
2
3
4
5
6
7
8
9
10
struct list * init(int a)  // а- значение первого узла
{
  struct list *lst;
  // выделение памяти под корень списка
  lst = (struct list*)malloc(sizeof(struct list));
  lst->field = a;
  lst->next = NULL// указатель на следующий узел
  lst->prev = NULL// указатель на предыдущий узел
  return(lst);
}


 

Добавление узла в ДЛС

Функция добавления узла в список принимает два аргумента:

  • Указатель на узел, после которого происходит добавление
  • Данные для добавляемого узла.

Процедуру добавления узла можно отобразить следующей схемой:
Добавление узла двусвязного линейного списка

Добавление узла в ДЛС включает в себя следующие этапы:

  • создание узла добавляемого элемента и заполнение его поля данных;
  • переустановка указателя «следующий» узла, предшествующего добавляемому, на добавляемый узел;
  • переустановка указателя «предыдущий» узла, следующего за добавляемым, на добавляемый узел;
  • установка указателя «следующий» добавляемого узла на следующий узел (тот, на который указывал предшествующий узел);
  • установка указателя «предыдущий» добавляемого узла на узел, предшествующий добавляемому (узел, переданный в функцию).

Таким образом, функция добавления узла в ДЛС имеет вид:

1
2
3
4
5
6
7
8
9
10
11
12
13
struct list * addelem(list *lst, int number)
{
  struct list *temp, *p;
  temp = (struct list*)malloc(sizeof(list));
  p = lst->next; // сохранение указателя на следующий узел
  lst->next = temp; // предыдущий узел указывает на создаваемый
  temp->field = number; // сохранение поля данных добавляемого узла
  temp->next = p; // созданный узел указывает на следующий узел
  temp->prev = lst; // созданный узел указывает на предыдущий узел
  if (p != NULL)
    p->prev = temp;
  return(temp);
}

Возвращаемым значением функции является адрес добавленного узла.

 

Удаление узла ДЛС

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

Функция возвращает указатель на узел, следующий за удаляемым.

Удаление узла может быть представлено следующей схемой:
Удаление узла двусвязного линейного списка

Удаление узла ДЛС включает в себя следующие этапы:

  • установка указателя «следующий» предыдущего узла на узел, следующий за удаляемым;
  • установка указателя «предыдущий» следующего узла на узел, предшествующий удаляемому;
  • освобождение памяти удаляемого узла.

1
2
3
4
5
6
7
8
9
10
11
12
struct list * deletelem(list *lst)
{
  struct list *prev, *next;
  prev = lst->prev; // узел, предшествующий lst
  next = lst->next; // узел, следующий за lst
  if (prev != NULL)
    prev->next = lst->next; // переставляем указатель
  if (next != NULL)
    next->prev = lst->prev; // переставляем указатель
  free(lst); // освобождаем память удаляемого элемента
  return(prev);
}


 

Удаление корня ДЛС

Функция удаления корня ДЛС в качестве аргумента получает указатель на текущий корень списка. Возвращаемым значением будет новый корень списка — тот узел, на который указывает удаляемый корень.

1
2
3
4
5
6
7
8
struct list * deletehead(list *root)
{
  struct list *temp;
  temp = root->next;
  temp->prev = NULL;
  free(root);   // освобождение памяти текущего корня
  return(temp); // новый корень списка
}


 

Вывод элементов ДЛС

Функция вывода элементов ДЛС аналогична функции для ОЛС.
В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

1
2
3
4
5
6
7
8
9
void listprint(list *lst)
{
  struct list *p;
  p = lst;
  do {
    printf("%d ", p->field); // вывод значения элемента p
    p = p->next; // переход к следующему узлу
  } while (p != NULL); // условие окончания обхода
}


Для ДЛС также можно вызвать функцию вывода элементов списка в обратном порядке.

 

Вывод элементов ДЛС в обратном порядке

Функция вывода элементов ДЛС в обратном порядке принимает в качестве аргумента указатель на корень списка. Функция перемещает указатель на последний узел списка и осуществляет последовательный обход всех узлов с выводом их значений в обратном порядке.

1
2
3
4
5
6
7
8
9
10
11
void listprintr(list *lst)
{
  struct list *p;
  p = lst;
  while (p->next != NULL)
    p = p->next;  // переход к концу списка
  do {
    printf("%d ", p->field); // вывод значения элемента p
    p = p->prev; // переход к предыдущему узлу
  } while (p != NULL); // условие окончания обхода
}


 

Взаимообмен узлов ДЛС

В качестве аргументов функция взаимообмена узлов ДЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого узла списка.

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

  • заменяемые узлы являются соседями;
  • заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один узел.

При замене соседних узлов переустановка указателей выглядит следующим образом:
Замена соседних узлов двусвязного линейного списка
При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:
Замена узлов двусвязного линейного списка

Функция взаимообмена узлов списка выглядит следующим образом:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct list * swap(struct list *lst1, struct list *lst2, struct list *head)
{
  // Возвращает новый корень списка
  struct list *prev1, *prev2, *next1, *next2;
  prev1 = lst1->prev;  // узел предшествующий lst1
  prev2 = lst2->prev;  // узел предшествующий lst2
  next1 = lst1->next; // узел следующий за lst1
  next2 = lst2->next; // узел следующий за lst2
  if (lst2 == next1)  // обмениваются соседние узлы
  {
    lst2->next = lst1;
    lst2->prev = prev1;
    lst1->next = next2;
    lst1->prev = lst2;
    if(next2 != NULL)
      next2->prev = lst1;
    if (lst1 != head)
      prev1->next = lst2;
  }
  else if (lst1 == next2)  // обмениваются соседние узлы
  {
    lst1->next = lst2;
    lst1->prev = prev2;
    lst2->next = next1;
    lst2->prev = lst1;
    if(next1 != NULL)
      next1->prev = lst2;
    if (lst2 != head)
      prev2->next = lst1;
  }
  else  // обмениваются отстоящие узлы
  {
    if (lst1 != head)  // указатель prev можно установить только для элемента,
      prev1->next = lst2; // не являющегося корневым
    lst2->next = next1;
    if (lst2 != head)
      prev2->next = lst1;
    lst1->next = next2;
    lst2->prev = prev1;
    if (next2 != NULL// указатель next можно установить только для элемента,
      next2->prev = lst1; // не являющегося последним
    lst1->prev = prev2;
    if (next1 != NULL)
      next1->prev = lst2;
  }
  if (lst1 == head)
    return(lst2);
  if (lst2 == head)
    return(lst1);
  return(head);
}


Код примера использования приведенных функций


Назад: Структуры данных

Комментариев к записи: 25

  • Арнольд
    Здравствуйте! Прежде всего, спасибо вам за вашу работу, очень полезный ресурс, к которому уже не раз обращался. Интересует, как в поле данных узла списка сделать поле ввода char[], чтобы был строковый ввод. Например, для реализации программ типа Телефонная книга или Менеджер билетов. То есть имеющих несколько полей ввода, как символьного, так и цифрового. Встречал много реализаций подобных программ, но ни одна из них не устраивает, нужно сделать свой нормальный шаблон. Когда добавляю поля типа char[], программа либо их игнорирует, либо уходит в бесконечный цикл

    • Елена Вставская
      Вместо int field будет char* field. Ввод рекомендую делать во вспомогательную строку, а затем копировать. И не забыть выделить память перед тем, как копировать данные.

  • Елена, здравствуйте, я написал свой двусвязный список(он немного отличается от вашего). Но я не могу написать функцию свап, я еще в процессе понимания как работают списки( так не пойму даже какие мне аргументы впихнуть в функцию). Вот я наткнулся на ваш сайт и я немного в ступоре уже от этой строчки
    1
    struct list * swap(struct list *lst1, struct list *lst2, struct list *head) 
    Вот для чего вы добавили аргумент голова, не могу представить как это выглядит в main, вот что туда ложить?. Вы бы не могли,пожалуйста, написать функцию свап для моей структуры списка с комментариями где обмениваются узлы...Я так понял у вас свап только соседних узлов? а как быть если я захочу к примеру свапнуть только голову и хвост? Вот моя структура:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    typedef unsigned int uint;
    struct Node
    {
      uint count;
      string data;
      Node* next;
      Node* prev;
    }; 

    struct List
    {
        Node *head = NULL;
        Node *tail = NULL;
    };

    • Елена Вставская
      Любой список имеет свой корень, который и передается в качестве третьего аргумента в функцию swap. Он нужен для корректной замены элементов если один из них является корнем (в этом случае у списка будет новый корень, который и вернёт функция). Функция предусматривает обмен как соседних, так и отстоящих элементов.

      • " который и передается в качестве третьего аргумента в функцию swap." Почему? Можно ведь сравнивать по индексам или такой вариант будет менее оптимальным?

        • Елена Вставская
          В том-то и дело, что в списке нет индексов, и доступ к элементам только последовательный, перемещаясь по указателям, начиная с корня списка.

  • Я правильно понимаю, что функция deletelem не проверяет, что мы пытаемся удалить первый или последний элемент списка? Мне кажется, что попытка удалить такие элементы нарушит связи в списке.

    • Елена Вставская
      Строчки 6-9 функции deletelem() проверяют первый и последний элементы.

  • Александр
    Елена, процедура "обмена" тут представляет только учебный интерес. В реальной программе проще обменять данные. Если данные реально большие и/или сложной конфигурации то в объявлении структуры необходимо int field (и прочие данные) заменить на void *data, которая будет ссылаться на реальные данные. Структура списка получается универсальной, можно быстро сделать сортировку с передачей функции сравнения, обмен данными не зависит от структуры - просто переставляются два указателя.

  • Здравствуйте. Подскажите как реализовать быструю сортировку ДЛС? И возможно ли это?

    • Елена Вставская
      Да, возможно. Как - отвечу когда со временем посвободнее будет



      • Дмитрий
        lst2->prev это узел левее узла 2 и на рисунке он двумя указателями связан с узлом 1. Значит lst2->prev = lst1;?

        • Елена Вставская
          Мы говорим о самой нижней стрелке на рисунке для отстоящих узлов

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

  • Не работает обмен, если меняется последний элемент и предпоследний.

    • Елена Вставская
      Спасибо за замечание. Исправила функцию swap() в тексте статьи. Теперь должно работать.

  • здравствуйте Елена. как преобразовать ДЦС в два циклических списка? первый из которых содержит первую половину, а вторая вторую половину. Пожалуйста можно с примерами

    • Елена Вставская
      Нужно найти соединение, по которому список делится на два. Взять точку соединения начала и конца. Начало соединить с "левой" серединой - получится первый список. "правую" середину соединить с концом - получится второй список.

  • Владислав
    Не могли бы вы дать полностью код, одну целую программу, если быть точнее?

  • У меня не работает обмен, при попытке обменять последний элемент с первым.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *