Как поменять местами узлы в односвязном списке

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как и в случае с односвязным списком, нам приходится особым образом хранить ссылку на следующий узел для последнего узла. Там мы помещаем значение 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 студентов

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

Поменять местами в односвязном списке

Здравствуйте! По условию задачи необходимо поменять первый и второй элемент, третий и четвертый и т.д.У меня получилось поменять только два первых элемента(head и head.next).Далее возникли проблемы, хотя делала по тому же принципу что и первые два. Как я понимаю нужно делать через while пока список не будет null.А вот как делать, это вопрос конечно. Помогите пожалуйста!

1 2 3 4

Node s = head.next; head.next = s.next; s.next = head; head = s;

Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Как в односвязном списке поменять соседние элементы
Я писал самостоятельную реализацию односвязного списка и для сортировки мне необходимо поменять два.

Рекурсия: максимальный элемент в односвязном списке
Хэй Народ, я начинающий, помогите плиз. Изучаю односвязные списки, задача состоит в том, что.

В односвязном списке поменять местами 3 и последний элемент
Есть у кого пример как в односвязном списке поменять местами 3 и последний элемент ?

В односвязном списке поменять местами крайние элементы
что есть у меня: #include <iostream> #define N 6 using namespace std; struct Node < int d;.

485 / 333 / 132
Регистрация: 14.06.2016
Сообщений: 650

Лучший ответ

Сообщение было отмечено Alexandra1234A как решение

Решение

1 2 3 4 5 6 7 8 9 10

public Node transform(Node first)

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Поменять местами первый и пятый элементы в односвязном списке
Этот код на 2й и предпоследний элемент. Нужно поменять местами первый и пятый, Что заменить? где-то.

Стек: В односвязном списке поменять местами крайние элементы.
В односвязном списке поменять местами крайние элементы — C++ Builder.

Как в односвязном списке поменять местами один элемент и следующий за ним?
Напр., что есть: 0 1 2 3 4 5 6 7 должно быть: 0 1 2 3 4 6 5 7

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

Найти в односвязном списке минимальный и максимальный элементы и поменять их местами с помощью указателей
Нужно найти в односвязном списке минимальный и максимальный элемент и поменять их местами с помощью.

Поменять местами первый и последний узел в односвязном циклическом списке с указателем на хвост
Здравствуйте! Нужно написать процедуру, которая меняет местами первый и последний узел в.

Поменять местами два элемента односвязного списка

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

struct SingleList < int Data; SingleList *Next; >;

Отслеживать
user252108
задан 28 мая 2017 в 11:48
user252108 user252108
13 4 4 бронзовых знака

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Пусть два следующих не NULL.

// ptr -> a -> b -> c SingleList *a = ptr->Next; SingleList *b = a->Next; ptr->Next = b; // a -> b -> c // ^ // ptr | a->Next = b->Next; // a -> c // ^ // ptr -> b | b->Next = a; // ptr -> b -> a -> c

Добавьте необходимую логику в случае если имеется NULL значение и проверку на NULL перед обращением к Next.

Односвязный список. Поменять местами элементы

Привет. Есть односвязный список. Например: 5 элементов, поменять местами 2 и 3
Как поменять местами элементы p1 и p2.
Что я сделал?
нашел позиции этих p1 и p2 через циклы.
Как поменять? Я думаю, что нужно поменять указатели, как конкретно их поменять?
Что на что должно указывать? Напишите кодом, пожалуйста.

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

void list::change(int first,int last) { nodes *p1 = new nodes; nodes *p2 = new nodes; nodes *tmp_pos = new nodes; p1 = begin; p2 = begin; tmp_pos = begin; for(int i = 1; i  first; i++) { p2 = p2->next; } for(int i = 1; i  last; i++) { p1 = p1->next; } p2->data.vivod(); printf("\n"); p1->data.vivod(); printf("\n"); tmp_pos->next = p1->next; p1->next = p2->next; p2->next = tmp_pos->next; delete tmp_pos; }

мой нерабочий вариант

Добавлено через 2 минуты
Нерабочий почему? потому что запуска такой функции и вывода на экран список не выводится, вернее выводится через *опу!