Что такое двусвязный список

Двусвязный список — Основы алгоритмов и структур данных

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

Есть несколько задач, для которых односвязный список подходит не очень хорошо. В частности, он несимметричен — если вставка и удаление в начале списка выполняются за константное время

, то в конце — за линейное

. Если в списке будет тысяча элементов, вставка в начало может оказаться в тысячу раз быстрее, чем вставка в конец.

Другая задача, которую трудно решить с помощью односвязного списка — вставка перед заданным узлом. Предположим, у нас есть текст на русском языке, где каждый элемент — либо отдельное слово, либо знак препинания. В тексте могут быть ошибки: например, могут отсутствовать запятые и точки. Мы предполагаем, что если слово начинается с большой буквы, перед ним должна быть точка. Если в тексте есть союзы «но» и «а», перед ними должна стоять запятая.

Расссмотрим такой пример:

«Его» «пример» «другим» «наука» «но» «,» «боже» «мой» «,» «какая» «скука» «с» «больным» «сидеть» «и» «день» «и» «ночь» «,» «не» «отходя» «ни» «шагу» «прочь» «Какое» «низкое» «коварство» «полуживого» «забавлять» «ему» «подушки» «поправлять» «,» «печально» «подносить» «лекарство»

В этом тексте не хватает запятой перед словом «но» и точки перед словом «Какое». Попробуем решить эту задачу с помощью односвязного списка. Нам нужно:

• Поместить слова в односвязный список
• Найти слово «но»
• Попробовать вставить перед ним запятую

Здесь мы сталкиваемся с тем, что в узле нет ссылки на предыдущий элемент, только на следующий:

Односвязный список устроен так, что для вставки запятой между словами «наука» и «но» нужно модифицировать именно узел со словом «наука». Эти детали делают наш возможный алгоритм сложным и медленным.

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

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

В каждом узле двусвязного списка хранится две ссылки — на следующий и на предыдущий узел. Кроме того, в нем хранятся ссылки и на голову списка (первый элемент), и на его хвост (последний элемент):

Как и в случае с односвязным списком, нам приходится особым образом хранить ссылку на следующий узел для последнего узла. Там мы помещаем значение null — пустую ссылку, которая ни на что не указывает. На рисунке последний узел в списке — это D.

У первого узла не может быть предыдущего узла, поэтому и здесь мы записываем null вместо ссылки. На рисунке первый узел в списке — это A.

За счет изменения структуры, мы получаем две новые возможности:

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

Конечно, есть и минусы. Во-первых, сама структура и код становятся сложнее. Во-вторых, структура теперь занимает больше памяти, поскольку в каждом узле хранится две ссылки, а не одна.

Вставка узла в начало списка

Посмотрим, как выглядит вставка узла в начало списка:

class DoublyLinkedListNode  constructor(value, previous, next)  this.value = value; this.previous = previous; this.next = next; > > class DoublyLinkedList  head = null; tail = null; insertBegin(value)  if (this.head == null)  const node = new DoublyLinkedListNode(value, null, null); this.head = node; this.tail = node; > else  const node = new DoublyLinkedListNode(value, null, this.head); this.head.previous = node; this.head = node; > > >

class DoublyLinkedListNode: def __init__(self, value, previous, next): self.value = value self.previous = previous self.next = next class DoublyLinkedList: head = None tail = None def insert_begin(self, value): if self.head is None: node = DoublyLinkedListNode( value, None, None ) self.head = node self.tail = node else: node = DoublyLinkedListNode( value, None, self.head ) self.head.previous = node self.head = node

php class DoublyLinkedListNode  public function __construct($value, $previous, $next)  $this->value = $value; $this->previous = $previous; $this->next = $next; > > class DoublyLinkedList  public $head = null; public $tail = null; public function insertBegin($value)  if ($this->head == null)  $node = new DoublyLinkedListNode($value, null, null); $this->head = $node; $this->tail = $node; > else  $node = new DoublyLinkedListNode($value, null, $this->head); $this->head->previous = $node; $this->head = $node; > > >

class DoublyLinkedListNode  Object value; DoublyLinkedListNode previous; DoublyLinkedListNode next; DoublyLinkedListNode(Object value, DoublyLinkedListNode previous, DoublyLinkedListNode next)  this.value = value; this.previous = previous; this.next = next; > > class DoublyLinkedList  DoublyLinkedListNode head = null; DoublyLinkedListNode tail = null; public void insertBegin(Object value)  if (head == null)  var node = new DoublyLinkedListNode(value, null, null); head = node; tail = node; > else  var node = new DoublyLinkedListNode(value, null, head); head.previous = node; head = node; > > >

Разберем этот фрагмент кода подробнее.

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

Первый класс — DoublyLinkedListNode . Он описывает узел двусвязного списка и состоит из таких компонентов:

• Значения — value
• Ссылки на предыдущий узел — previous
• Ссылки на следующий узел — next

Второй класс — DoublyLinkedList . Он представляет список целиком, вместе с его операциями-алгоритмами. Там находятся:

• Ссылка на первый узел — head
• Ссылка на последний узел — tail
• Различные методы, например:

• insertBegin(value) — вставка в начало
• insertEnd(value) — вставка в конец
• removeBegin() — удаление из начала

Новый список пуст, поэтому поля head и tail содержат значение null :

После вставки первого узла head и tail содержат его адрес. При этом поля previous и next у этого узла никуда не указывают, потому что он одновременно является первым и последним в списке — другими словами, у него нет ни предыдущего, ни следующего узла:

Теперь посмотрим на фрагмент кода:

if (this.head == null)  const node = new DoublyLinkedListNode(value, null, null); this.head = node; this.tail = node; >

if self.head is None: node = DoublyLinkedListNode( value, None, None ) self.head = node self.tail = node

php if ($this->head == null)  $node = new DoublyLinkedListNode($value, null, null); $this->head = $node; $this->tail = $node; >

if (head == null)  var node = new DoublyLinkedListNode(value, null, null); head = node; tail = node; >

Условие this.head == null выполняется для пустого списка. Нам достаточно создать узел с пустыми ссылками на предыдущий и следующий узлы, а затем присвоить его адрес полям this.head и this.tail .

При вставке каждого следующего узла в начало, head всегда будет указывать на новый узел. Значение tail при этом не изменится, потому что хвост списка остается прежним. Поле next новой головы списка будет указывать на прежнюю голову, а в поле previous старой головы вместо null должен появиться адрес новой головы:

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

const node = new DoublyLinkedListNode(value, null, this.head);

node = DoublyLinkedListNode(value, None, self.head)

php $node = new DoublyLinkedListNode($value, null, $this->head);

var node = new DoublyLinkedListNode(value, null, head);

Создавая узел, мы сразу записываем в поле next текущее значение this.head — текущую голову. Поле previous текущей головы должно ссылать на новый узел, за это отвечает такая строка:

this.head.previous = node;

self.head.previous = node

php $this->head->previous = $node;

head.previous = node;

Наконец, новый узел становится новой головой списка:

this.head = node;

self.head = node

php $this->head= $node;

head = node;

Вставка узла в конец списка

Перейдем к вставке узла в конец списка:

insertEnd(value)  if (this.tail == null)  const node = new DoublyLinkedListNode(value, null, null); this.tail = node; this.head = node; > else  const node = new DoublyLinkedListNode(value, this.tail, null); this.tail.next= node; this.tail = node; > >

def insert_end(self, value): if self.tail is None: node = DoublyLinkedListNode(value, None, None) self.tail = node self.head = node else: node = DoublyLinkedListNode(value, self.tail, None) self.tail.next = node self.tail = node

php public function insertEnd($value)  if ($this->tail == null)  $node = new DoublyLinkedListNode($value, null, null); $this->tail = $node; $this->head = $node; > else  $node = new DoublyLinkedListNode($value, $this->tail, null); $this->tail->next= $node; $this->tail = $node; > >

class DoublyLinkedList  // . public void insertEnd(Object value)  if (tail == null)  var node = new DoublyLinkedListNode(value, null, null); tail = node; head = node; > else  var node = new DoublyLinkedListNode(value, tail, null); tail.next= node; tail = node; > > >

Такая вставка симметрична вставке в начало. Разница только в том, что здесь мы должны везде менять местами head и tail , а также previous и next .

Удаление узла

Перейдем к операциям удаления:

removeBegin()  if (this.head == null)  return undefined; > const result = this.head.value; if (this.head == this.tail)  this.head = null; this.tail = null; > else  this.head = this.head.next; this.head.previous = null; > return result; >

def remove_begin(self): if self.head is None: return None result = self.head.value if self.head == self.tail: self.head = None self.tail = None else: self.head = self.head.next self.head.previous = None return result

php public function removeBegin()  if ($this->head == null)  return null; > $result = $this->head->value; if ($this->head == $this->tail)  $this->head = null; $this->tail = null; > else  $this->head = $this->head->next; $this->head->previous = null; > return $result; >

class DoublyLinkedList  // . public Object removeBegin()  if (head == null)  return null; > var result = head.value; if (head == tail)  head = null; tail = null; > else  head = head.next; head.previous = null; > return result; > >

Метод удаления возвращает значение из удаленного узла. Если список пуст и удалять нечего, метод возвращает undefined . В остальных случаях мы сохраняем значение в переменную result :

if (this.head == null)  return undefined; > const result = this.head.value;

if self.head is None: return None result = self.head.value

php if ($this->head == null)  return null; > $result = $this->head->value;

if (head == null)  return null; > var result = head.value;

Если this.head == this.tail , значит, в списке находится один последний узел — он является одновременно и головой, и хвостом. Чтобы его удалить, достаточно обнулить head и tail :

if (this.head == this.tail)  this.head = null; this.tail = null; >

if self.head == self.tail: self.head = None self.tail = None

php if ($this->head == $this->tail)  $this->head = null; $this->tail = null; >

if (head == tail)  head = null; tail = null; >

А теперь посмотрим обратный пример — избавимся от первого узла в списке. Сначала записываем в head ссылку на второй узел, а потом обнуляем у нее поле previous :

this.head = this.head.next; this.head.previous = null;

self.head = self.head.next self.head.previous = None

php $this->head = $this->head->next; $this->head->previous = null;

head = head.next; head.previous = null;

Перебор значений в прямом порядке

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

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

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

Итератор — это объект, который одинаковым образом перебирает элементы коллекции, независимо от структуры данных. Скажем, мы можем написать функцию суммирования элементов любой коллекции и вызвать ее для списка:

const sum = (items) =>  let result = 0; for (item of items)  result = result + item; > return result; >; console.log(sum([1, 2, 3, 4])); // => 10

def sum(items): result = 0 for item in items: result = result + item return result print(sum([1, 2, 3, 4])) # => 10

php function sum($items)  $result = 0; foreach ($items as $item)  $result = $result + $item; > return $result; >; print_r(sum([1, 2, 3, 4])); // => 10

class App  public static int sum(IterableInteger> items)  var result = 0; for (var item: items)  result = result + (int) item; > return result; > > System.out.println(App.sum(List.of(1, 2, 3, 4))); // => 10

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

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

• От начала к концу
• От конца к началу

Поэтому двусвязный список должен иметь два итератора — прямой и обратный. Чтобы так сделать, можно возвращать итераторы из методов класса. Например, метод fore() может создавать и возвращать прямой итератор:

fore()  let iterator =  current: this.head >; iterator[Symbol.iterator] = function* ()  while (this.current != null)  yield this.current.value; this.current = this.current.next; > >; return iterator; >

def fore(self): current = self.head while current is not None: yield current.value current = current.next

php public functon fore()  $current = $this->head; while($current !== null)  yield $current->value $current = $current->next > >

Использовать итератор можно так:

let list = new DoublyLinkedList(); list.insertBegin(1); list.insertBegin(2); list.insertBegin(3); list.insertBegin(4); console.log(sum(list.fore())); // => 10

lst = DoublyLinkedList() lst.insert_begin(1) lst.insert_begin(2) lst.insert_begin(3) lst.insert_begin(4) print(sum(lst.fore()))

php $list = new DoublyLinkedList(); $list->insertBegin(1); $list->insertBegin(2); $list->insertBegin(3); $list->insertBegin(4); print_r(sum($list->fore())); // => 10

class DoubleLinkedList implements IterableObject>  // . @Override public IteratorObject> iterator()  return new DoubleLinkedListIterator(); > private class DoubleLinkedListIterator implements IteratorObject>  DoubleLinkedListNode current = head; @Override public Object next()  if (!this.hasNext())  throw new NoSuchElementException(); > var lastReturnedNode = current; current = current.next; return lastReturnedNode.value; > @Override public boolean hasNext()  return current != null; > > > var list = new DoubleLinkedList(); list.insertBegin(1); list.insertBegin(2); list.insertBegin(3); list.insertBegin(4); System.out.println(App.sum(list)); // => 10

В JavaScript используется синтаксис function* и yield , который упрощает работу с итераторами. В нашем примере порядок действий такой:

• Начинаем с первого узла, адрес которого хранится в поле head
• Пробегаем по всем узлам списка
• Передаем значения узлов в вызывающую функцию с помощью конструкции yield

Выводы

• Односвязный список подходит не для всех задач — вставка и удаление в конец списка гораздо медленнее, чем вставка и удаление в начало. Кроме того, в односвязном списке нельзя вставить узел перед другим узлом.
• Чтобы справиться с этими трудностями, программисты используют такую структуру данных, как двусвязный список.

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

• 130 курсов, 2000+ часов теории
• 1000 практических заданий в браузере
• 360 000 студентов

Наши выпускники работают в компаниях:

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

В информатике, cвя́зный спи́сок — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Виды связных списков

Линейный связный список

Односвязный список

В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента из данного невозможно.

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

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

XOR-связный список

Основная статья: XOR-связный список

Кольцевой связный список

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

Список с пропусками

Основная статья: Список с пропусками

Развёрнутый связный список

Основная статья: Развёрнутый связный список

Достоинства

• лёгкость добавления и удаления элементов
• размер ограничен только объёмом памяти компьютера и разрядностью указателей

Недостатки

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

См. также

Wikimedia Foundation . 2010 .

• Двуручник
• Двуспоровый шампиньон

Полезное

Смотреть что такое «Двусвязный список» в других словарях:

• Связный список — В информатике, связный список базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным… … Википедия
• Односвязный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия
• Связанный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия
• XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку,… … Википедия
• Развёрнутый связный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что … Википедия
• Xor-связанный список — XOR связный список структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться… … Википедия
• Структура данных — Бинарное дерево, простой пример ветвящейся связной структуры данных. Структура данных (англ. data structure) программная единица, позволяющая хран … Википедия
• Коллекция (программирование) — У этого термина существуют и другие значения, см. Коллекция. Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные исто … Википедия
• Коллекция данных — Коллекция в программировании программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям. Коллекция позволяет записывать в себя значения и извлекать их.… … Википедия
• Двусвязная очередь — (жарг. дэк, дек от англ. deque double ended queue; двухсторонняя очередь, двусвязный список, очередь с двумя концами) структура д … Википедия

• Обратная связь: Техподдержка, Реклама на сайте

• �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

• Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
• Искать во всех словарях
• Искать в переводах
• Искать в ИнтернетеИскать в этой же категории

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

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

Узел ДЛС можно представить в виде структуры:

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

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

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

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

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

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

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

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

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

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

Вот термины, необходnuимые для понимания концепции двусвязных (двунаправленных) списков:

• Ссылка. В каждой ссылке связного списка могут храниться данные, называемые элементом.
• Следующая ссылка. В каждой ссылке связного списка содержится ссылка на следующую ссылку (Next).
• Предыдущая ссылка. В каждой ссылке связного списка содержится ссылка на предыдущую ссылку (Prev).
• Связный список содержит ссылку (связку) на первую ссылку (First) и на последнюю ссылку (Last).

Представление двусвязного (двунаправленного) списка

Здесь надо учитывать следующие важные моменты:

• Двусвязный (двунаправленный) список содержит элемент ссылок — first (первой) и last (последней).
• Каждая ссылка имеет поле или поля данных и два поля ссылки — next (следующей) и prev (предыдущей).
• Каждая ссылка связана со следующей посредством своей ссылки next.
• Каждая ссылка связана с предыдущей посредством своей ссылки prev.
• Последняя ссылка содержит ссылку со значением null, обозначающую конец списка.

Базовые операции

Это основные операции, проводимые над списками:

• Вставка, то есть добавление элемента в начало списка.
• Удаление элемента из начала списка.
• Вставка последним, то есть добавление элемента в конец списка.
• Удаление последнего, то есть удаление элемента из конца списка.
• Вставка после, то есть добавление элемента после какого-то элемента списка.
• Удаление элемента из списка по заданному ключу.
• Отображение вперед полного списка в прямом порядке.
• Отображение назад полного списка в обратном порядке.

Вставка

В этом коде показана операция вставки в начало двусвязного (двунаправленного) списка:

Пример

//вставляем ссылку на первое место
void insertFirst(int key, int data)  //создаем ссылку 
struct node *link = (struct node*) malloc(sizeof(struct node)); 
link->key = key; 
link->data = data; 
 
if(isEmpty()) //делаем ее последней ссылкой 
last = link; 
> else //меняем первую предыдущую ссылку 
head->prev = link; 
> //указываем ей на прежнюю первую ссылку 
link->next = head; 
 
//указываем первой на новую первую ссылку 
head = link;
>

Удаление

В этом коде показана операция удаления в начале двусвязного (двунаправленного) списка:

Пример

//удаляем первый элемент
struct node* deleteFirst()  //сохраняем ссылку на первую ссылку 
struct node *tempLink = head; 
 
//если только одна ссылка 
if(head->next == NULL) last = NULL; 
> else head->next->prev = NULL; 
> 
 
head = head->next; 
 
//возвращаем удаленную ссылку 
return tempLink;
>

Вставка в конце операции

В этом коде показана операция вставки в последнее место двусвязного (двунаправленного) списка:

Пример

//вставляем ссылку в последнее место
void insertLast(int key, int data)  //создаем ссылку 
struct node *link = (struct node*) malloc(sizeof(struct node)); 
link->key = key; 
link->data = data; 
 
if(isEmpty()) //делаем ее последней ссылкой 
last = link; 
> else //делаем ссылку новой последней ссылкой 
last->next = link; 
 
//обозначаем прежний последний узел как предыдущий для новой ссылки 
link->prev = last; 
> //указываем последней на новый последний узел 
last = link;
>

Реализация на языке программирования C:

#include 
#include 
#include 
#include 

struct node int data; 
int key; 
 
struct node *next; 
struct node *prev;
>;

//Указатель показывает на начало списка
struct node *head = NULL;

//Указатель показывает на конец списка
struct node *last = NULL;

struct node *current = NULL;

//пуст ли список
bool isEmpty() return head == NULL;
>

int length() int length = 0; 
struct node *current; 
 
for(current = head; current != NULL; current = current->next) length++; 
> 
 
return length;
>

//показать список с первого элемента по последний
void displayForward()  
//начать с начала списка 
struct node *ptr = head; 
 
//выводить пока не конец списка 
printf("\n[ "); 
 
while(ptr != NULL) < 
printf("(%d,%d) ",ptr->key,ptr->data); 
ptr = ptr->next; 
> 
 
printf(" ]");
>

//показать список с последнего по первый элемент
void displayBackward()  
//начать с конца списка 
struct node *ptr = last; 
 
//выводить пока не начало списка 
printf("\n[ "); 
 
while(ptr != NULL) < 
 
//вывести данные 
printf("(%d,%d) ",ptr->key,ptr->data); 
 
//перейти к следующему элементу 
ptr = ptr ->prev; 
 
> 

>

//вставить элемент в начало списка
void insertFirst(int key, int data)  
//создать элемент 
struct node *link = (struct node*) malloc(sizeof(struct node)); 
link->key = key; 
link->data = data; 
 
if(isEmpty()) //поставить элемент в конец 
last = link; 
> else //update first prev link обновить у первого элемента ссылку на предыдущий элемент 
head->prev = link; 
>
 
//установить указатель на прошлый первый элемент 
link->next = head; 
 
//point first to new first link установить указатель списка первого элемента на новый первый элемент 
head = link;
>

//добавить элемент в конец списка
void insertLast(int key, int data)  
//создать указатель на элемент 
struct node *link = (struct node*) malloc(sizeof(struct node)); 
link->key = key; 
link->data = data; 
 
if(isEmpty()) //сделать последним элементом 
last = link; 
> else //сделать элемент новым последним элементом 
last->next = link; 
 
//установить указатель с нового элемента на прошлый последний элемент 
link->prev = last; 
>
 
//сделать элемент последним в списке 
last = link;
>

//удалить первый элемент
struct node* deleteFirst()  
//сохранить ссылку на первый элемент 
struct node *tempLink = head; 
 
//если один элемент 
if(head->next == NULL) last = NULL; 
> else head->next->prev = NULL; 
> 
 
head = head->next; 
//return the deleted link возвратить удаленный элемент 
return tempLink;
>

//удалить последний элемент 

struct node* deleteLast() //сохранить ссылку на последний элемент 
struct node *tempLink = last; 
 
//если один элемент 
if(head->next == NULL) head = NULL; 
> else last->prev->next = NULL; 
> 
 
last = last->prev; 
 
//возвратить удаленный элемент 
return tempLink;
>

//удалить элемент с заданным ключом
struct node* delete(int key)  
//начать с первого элемента 
struct node* current = head; 
struct node* previous = NULL; 
 
//если список пуст 
if(head == NULL) return NULL; 
>
 
//продвигаться по списку 
while(current->key != key) //если элемент последний 
 
if(current->next == NULL) return NULL; 
> else //сохранить указатель на текущий элемент 
previous = current; 
 
//перейти к следующему элементу 
current = current->next; 
> 
>
 
//если найдено совпадение, обновить ссылку 
if(current == head) //изменить указатель на первый элемент 
head = head->next; 
> else //установить у прошлого элемента ссылку на следующий от текущего 
current->prev->next = current->next; 
> 
 
if(current == last) //изменить указатель на последний элемент 
last = current->prev; 
> else current->next->prev = current->prev; 
> 
 
return current;
>

bool insertAfter(int key, int newKey, int data) //начать с первого элемента 
struct node *current = head; 
 
//если лист пуст 
if(head == NULL) return false; 
>
 
//продвигаться по списку 
while(current->key != key)  
//если это последний элемент 
if(current->next == NULL) return false; 
> else < 
//перейти к следующему 
current = current->next; 
> 
> 
 
//создать указатель на новый элемент 
struct node *newLink = (struct node*) malloc(sizeof(struct node)); 
newLink->key = newKey; 
newLink->data = data;
 
if(current == last) newLink->next = NULL; 
last = newLink; 
> else newLink->next = current->next; 
current->next->prev = newLink; 
> 
 
newLink->prev = current; 
current->next = newLink; 
return true; 
>

void main() insertFirst(1,10); 
insertFirst(2,20); 
insertFirst(3,30); 
insertFirst(4,1); 
insertFirst(5,40); 
insertFirst(6,56); 
 
printf("\nList (First to Last): "); 
displayForward(); 
 
printf("\n"); 
printf("\nList (Last to first): "); 
displayBackward();
 
printf("\nList , after deleting first record: "); 
deleteFirst(); 
displayForward();
 
printf("\nList , after deleting last record: "); 
deleteLast(); 
displayForward();
 
printf("\nList , insert after key(4) : "); 
insertAfter(4,7, 13); 
displayForward();
 
printf("\nList , after delete key(4) : "); 
delete(4); 
displayForward();
>

• Связный список в деталях
• Язык C: основы синтаксиса
• Структуры данных: основные понятия