Двунаправленные (двусвязные) списки

Удаление однонаправленного списка

Поиск элемента в однонаправленном списке

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

//поиск элемента в однонаправленном спискеbool Find_Item_Single_List(Single_List* Head, int DataItem){ Single_List *ptr; //вспомогательным указатель ptr = Head; while (ptr != NULL){//пока не конец списка if (DataItem == ptr->Data) return true; else ptr = ptr->Next; } return false;}

Операция удаления списка заключается в освобождении динамической памяти. Для данной операции организуется функция, в которой нужно переставлять указатель на следующий элемент списка до тех пор, пока указатель не станет, равен NULL, то есть не будет достигнут конец списка. Реализуем рекурсивную функцию.

/*освобождение памяти, выделенной под однонаправленный список*/void Delete_Single_List(Single_List* Head){ if (Head != NULL){ Delete_Single_List(Head->Next); delete Head; }}

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

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

Двунаправленный (двусвязный) список – это структура данных, состоящая из последовательности элементов, каждый из которых содержит информационную часть и два указателя на соседние элементы (рис. 29.4). При этом два соседних элемента должны содержать взаимные ссылки друг на друга.

В таком списке каждый элемент (кроме первого и последнего) связан с предыдущим и следующим за ним элементами. Каждый элемент двунаправленного списка имеет два поля с указателями: одно поле содержит ссылку на следующий элемент, другое поле – ссылку на предыдущий элемент и третье поле – информационное. Наличие ссылок на следующее звено и на предыдущее позволяет двигаться по списку от каждого звена в любом направлении: от звена к концу списка или от звена к началу списка, поэтому такой список называют двунаправленным.


Рис. 29.4. Двунаправленный список

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа {

информационное поле;

адресное поле 1;

адресное поле 2;

};

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

адресное поле 1 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка;

адресное поле 2 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес предыдущего элемента списка.

Например:

struct list {

type elem ;

list *next, *pred ;

}

list *headlist ;

где type – тип информационного поля элемента списка;

*next, *pred – указатели на следующий и предыдущий элементы этой структуры соответственно.

Переменная-указатель headlist задает список как единый программный объект, ее значение – указатель на первый (или заглавный) элемент списка.

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

Рассмотрим основные операции, осуществляемыми с двунаправленными списками, такие как:

  • создание списка;
  • печать (просмотр) списка;
  • вставка элемента в список;
  • удаление элемента из списка;
  • поиск элемента в списке;
  • проверка пустоты списка;
  • удаление списка.

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

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

struct Double_List {//структура данных

int Data; //информационное поле

Double_List *Next, //адресное поле

*Prior; //адресное поле

};

. . . . . . . . . .

Double_List *Head; //указатель на первый элемент списка

. . . . . . . . . .

Double_List *Current;

//указатель на текущий элемент списка (при необходимости)