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

Сравнение массивов и связных списков

Массив Список
Выделение памяти осуществляется единовременно под весь массив до начала его использования Выделение памяти осуществляется по мере ввода новых элементов
При удалении/добавлении элемента требуется копирование всех последующих элементов для осуществления их сдвига Удаление/добавление элемента осуществляется переустановкой указателей, при этом сами данные не копируются
Для хранения элемента требуется объем памяти, необходимый только для хранения данных этого элемента Для хранения элемента требуется объем памяти, достаточный для хранения данных этого элемента и указателей (1 или 2) на другие элементы списка
Доступ к элементам может осуществляться в произвольном порядке Возможен только последовательный доступ к элементам

Структуры данных

Визуализация связей

Визуализация связей позволяет одним взглядом выявить наиболее “проблемные” точки. Акцент делается на визуализации актуальных связей по учредителям и руководителю


Также очень важно, что хорошо видны “группы влияния” и их пересечения

Исторические связи, связи по телефонам или адресам и другим признакам отходят на второй план.

Чтобы увидеть визуализацию связей, нужно перейти по одной из двух ссылок в разделе «Связи»:

Визуализация связей в блоке связанных организаций

Как устроен граф связей

Чтобы удобно визуализировать связи, применяются следующие визуальные блоки:

Овал – физическое лицо (руководитель, учредитель).

Прямоугольник – юридическое лицо или индивидуальный предприниматель.

Название компании черным цветом – ликвидированное юридическое лицо.

Непрерывная цветная линия – связь “учредитель”. Учредитель всегда располагается слева, учрежденное юрлицо – справа. Чем толще линия, тем больше доля в уставном капитале.

Тонкая серая штриховая линия – связь “руководитель”. Руководитель всегда располагается слева, а юрлицо – справа.

Тонкая серая прямая линия – любые другие отношения между юрлицами и физлицами (в том числе неактуальные исторические связи по руководителям или учредителям).

Визуализация связей

Группы влияния

Группы влияния можно увидеть за счет цветной раскраски плашек компаний.

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

Например, на графе представленном ниже, СКБ Контур как учредитель окрашен в фиолетовый цвет. Линии ведущие к учрежденным организациям также окрашены в фиолетовый цвет. Толщина линий разная, в зависимости от доли СКБ Контур: к “Сертум-Про” и “Контур Рисерч” самые толстые линии, что визуализирует 100% долю; к “Офис-Сервис” и “Уралфининвест” линии тоньше, т.к. доля всего 51%; ещё тоньше линия к “Инновационным системам управления”, где доля СКБ 34%. Организации в которых доля учредителя 100% (“Сертум-Про” и “Контур Рисерч”) окрашены так же как учредитель – в фиолетовый цвет.

Визуализация групп влияния

Способы исследования графа

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


Управление графом связей

Чтобы увидеть компании подчиненного уровня – необходимо нажать на цифру (указывает количество вершин графа на следующем уровне). Чтобы удалить компанию из графа – нужно нажать крестик. Чтобы свернуть все подчиненные связи – нажать “минус” .

При большом количестве связей и, соответственно, большом количестве контрагентов на графе, картинку можно увеличить прокрутив колёсико мыши “от себя”. Чтобы охватить весь куст связей одним взглядом нужно прокрутить колёсико мыши в другую сторону – изображение уменьшится.

Фильтрация и сортировка

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

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

Например, если мы хотим увидеть компании, которые закончили прошлый финансовый год с прибылью – достаточно щелкнуть мышью соответствующий фильтр в правой части экрана, где показана общая статистика по связанным компаниям:

Фильтры

Подобным образом можно отфильтровать компании по любому признаку, и как бы “осмотреть” граф связей с разных сторон.

Визуализация пользовательских списков

Если у пользователя есть список компаний, то можно визуализировать связи в нем. Для этого нужно войти в “Управление списками”, выбрать список и воспользоваться ссылкой “Визуализировать список”:

Визуализация пользовательских списков

Ограничения в применении

Визуализация работает только в следующих браузерах:

  • Internet Explorer версии 10 и выше;
  • Браузеры Chrome, Firefox или Yandex-браузер последних версий.

Пример анализа группы сомнительных организаций

Нередко вместо классической процедуры ликвидации фирмы прибегают к “альтернативной” в форме смены руководителя и учредителей или реорганизации в форме присоединения к фирме-однодневке. Для поиска таких фактов удобно анализировать массовые параметры группы.

На приведенном ниже примере в группе потенциально связанных организаций много таких, которые находятся в процессе реорганизации, ликвидации либо уже ликвидированы. При достаточно большой валовой выручке (344 млн.руб.) прибыль составила всего лишь 463 тыс.руб. (0,13% выручки) – маловероятно, что реальные предприятия будут работать с такой низкой рентабельностью.

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

Группа связанных организаций зарегистрированных на физ.лицо

Интересно наблюдать за подобными фирмами в динамике, т.е. фиксировать изменения в группе с течением времени. Приведенная выше группа, несколькими месяцами ранее – в январе 2015 года, выглядела так:


Группа сомнительных связанных организаций, январь 2015 г.

Как видите, за это время было присоединено к группе ещё 47 фирм (примерно по 6 в месяц), при этом недействующих фирм стало больше на 58 штук!

Но, благодаря Контур.Фокусу, спрятать свои темные делишки в прошлом становится очень сложно!

Сортировка односвязного списка

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

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

Node tmp;
*c = NULL;
if (a == NULL) {
	*c = b;
	return;
}
if (b == NULL) {
	*c = a;
	return;
}

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

if (a->value < b->value) {
	*c = a;
	a = a->next;
} else {
	*c = b;
	b = b->next;
}

Теперь сохраним указатель c, так как в дальнейшем он будет использоваться для прохода по списку

tmp.next = *c;

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

while (a && b) {
	if (a->value < b->value) {
		(*c)->next = a;
		a = a->next;
	} else {
		(*c)->next = b;
		b = b->next;
	}
	(*c) = (*c)->next;
}

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

if (a) {
	while (a) {
		(*c)->next = a;
		(*c) = (*c)->next;
		a = a->next;
	}
}
if (b) {
	while (b) {
		(*c)->next = b;
		(*c) = (*c)->next;
		b = b->next;
	}
}

Теперь указатель c хранит адрес последнего узла, а нам нужна ссылка на голову. Она как раз хранится во второй переменной tmp

*c = tmp.next;

Весь алгоритм

void merge(Node *a, Node *b, Node **c) {
	Node tmp;
	*c = NULL;
	if (a == NULL) {
		*c = b;
		return;
	}
	if (b == NULL) {
		*c = a;
		return;
	}
	if (a->value < b->value) {
		*c = a;
		a = a->next;
	} else {
		*c = b;
		b = b->next;
	}
	tmp.next = *c;
	while (a && b) {
		if (a->value < b->value) {
			(*c)->next = a;
			a = a->next;
		} else {
			(*c)->next = b;
			b = b->next;
		}
		(*c) = (*c)->next;
	}
	if (a) {
		while (a) {
			(*c)->next = a;
			(*c) = (*c)->next;
			a = a->next;
		}
	}
	if (b) {
		while (b) {
			(*c)->next = b;
			(*c) = (*c)->next;
			b = b->next;
		}
	}
	*c = tmp.next;
}

Ещё одна важная функция – нахождение середины списка. Для этих целей будем использовать два указателя. Один из них — fast – за одну итерацию будет два раза изменять значение и продвигаться по списку вперёд. Второй – slow, всего один раз. Таким образом, если список чётный, то slow окажется ровно посредине списка, а если список нечётный, то второй подсписок будет на один элемент длиннее.

void split(Node *src, Node **low, Node **high) {
	Node *fast = NULL;
	Node *slow = NULL;

	if (src == NULL || src->next == NULL) {
		(*low) = src;
		(*high) = NULL;
		return;
	}

	slow = src;
	fast = src->next;

	while (fast != NULL) {
		fast = fast->next;
		if (fast != NULL) {
			fast = fast->next;
			slow = slow->next;
		}
	}

	(*low) = src;
	(*high) = slow->next;
	slow->next = NULL;
}

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

Теперь у нас есть функция, которая позволяет разделить список на две части и функция слияния отсортированных списков. С их помощью реализуем функцию сортировки слиянием.

Сортировка слиянием для односвязного списка

Функция рекурсивно вызывает сама себя, передавая части списка. Если в функцию пришёл список длинной менее двух элементов, то рекурсия прекращается. Идёт обратная сборка списка. Сначала из двух списков, каждый из которых хранит один элемент, создаётся отсортированный список, далее из таких списков собирается новый отсортированный список, пока все элементы не будут включены.

void mergeSort(Node **head) {
	Node *low  = NULL;
	Node *high = NULL;
	if ((*head == NULL) || ((*head)->next == NULL)) {
		return;
	}
	split(*head, &low, &high);
	mergeSort(&low);
	mergeSort(&high);
	merge(low, high, head);
}

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

Q&A

Всё ещё не понятно? – пиши вопросы на ящик

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

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

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

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

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051

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

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

Поиск длины хвоста в списке с циклом[править]

Так как для поиска хвоста мы должны знать, что цикл существует, воспользуемся предыдущей функцией и при выходе из неё запомним «момент встречи» зайца и черепахи. Назовем её .

Наивные реализацииправить

Реализация за править

Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от вперёд указатель. Если он окажется в текущем элементе, прежде чем посетит снова, то точку окончания (начала) хвоста нашли.

Реализация за править

Реализацию, приведенную выше можно улучшить. Для этого воспользуемся бинарным поиском. Сначала проверим голову списка, потом сделаем шага вперёд, потом , потом и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции — на левой границе, где мы в хвосте, и на правой — в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за .

Эффективная реализацияправить

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

 int getTail(Node head, Node pointMeeting):
   firstElement = head.next
   secondElement = pointMeeting.next
   lengthTail = 1
   while firstElement != secondElement
     firstElement = firstElement.next
     secondElement = secondElement.next
     lengthTail = lenghtTail + 1
   return lengthTail

Доказательство корректности алгоритмаправить

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

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

, но так как

Пусть

Известно, что

откуда

Подставив полученные значения, получим: , откуда следует, что если запустить указатели с одной скоростью из и , то они встретятся через шагов в точке . К этому времени вышедший из пройдёт ровно шагов и остановится в , вышедший из накрутит по циклу шагов и пройдёт ещё шагов. Поскольку , то они встретятся как раз в точке .

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

Последнее обновление: 02.09.2016

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

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

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

public class DoublyNode<T>
{
    public DoublyNode(T data)
    {
        Data = data;
    }
    public T Data { get; set; }
    public DoublyNode<T> Previous { get; set; }
    public DoublyNode<T> Next { get; set; }
}

Далее определим сам класс списка:

using System.Collections.Generic;
using System.Collections;

namespace SimpleAlgorithmsApp
{
    public class DoublyLinkedList<T> : IEnumerable<T>  // двусвязный список
    {
        DoublyNode<T> head; // головной/первый элемент
        DoublyNode<T> tail; // последний/хвостовой элемент
        int count;  // количество элементов в списке

        // добавление элемента
        public void Add(T data)
        {
            DoublyNode<T> node = new DoublyNode<T>(data);

            if (head == null)
                head = node;
            else
            {
                tail.Next = node;
                node.Previous = tail;
            }
            tail = node;
            count++;
        }
        public void AddFirst(T data)
        {
            DoublyNode<T> node = new DoublyNode<T>(data);
            DoublyNode<T> temp = head;
            node.Next = temp;
            head = node;
            if (count == 0)
                tail = head;
            else
                temp.Previous = node;
            count++;
        }
		// удаление
        public bool Remove(T data)
        {
            DoublyNode<T> current = head;

            // поиск удаляемого узла
            while (current != null)
            {
                if (current.Data.Equals(data))
                {
                    break;
                }
                current = current.Next;
            }
            if(current!=null)
            {
                // если узел не последний
                if(current.Next!=null)
                {
                    current.Next.Previous = current.Previous;
                }
                else
                {
                    // если последний, переустанавливаем tail
                    tail = current.Previous;
                }

                // если узел не первый
                if(current.Previous!=null)
                {
                    current.Previous.Next = current.Next;
                }
                else
                {
                    // если первый, переустанавливаем head
                    head = current.Next;
                }
                count--;
                return true;
            }
            return false;
        }

        public int Count { get { return count; } }
        public bool IsEmpty { get { return count == 0; } }

        public void Clear()
        {
            head = null;
            tail = null;
            count = 0;
        }

        public bool Contains(T data)
        {
            DoublyNode<T> current = head;
            while (current != null)
            {
                if (current.Data.Equals(data))
                    return true;
                current = current.Next;
            }
            return false;
        }
        
        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable)this).GetEnumerator();
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            DoublyNode<T> current = head;
            while (current != null)
            {
                yield return current.Data;
                current = current.Next;
            }
        }

        public IEnumerable<T> BackEnumerator()
        {
            DoublyNode<T> current = tail;
            while (current != null)
            {
                yield return current.Data;
                current = current.Previous;
            }
        }
    }
}

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

В методе добавления , если в списке уже есть элементы, то у добавляемого узла свойство указывает на узел, который до этого хранился в переменной tail:

if (head == null)
    head = node;
else
{
    tail.Next = node;
    node.Previous = tail;
}
tail = node;

Аналогично в методе добавлении в начало списка для головного элемента свойство Previous начинает указывать на новый элемент, а новый элемент, таким образом, становиться первым элементом в списке.

При удалении вначале необходимо найти удаляемый элемент. Затем в общем случае надо переустановить две ссылки:

current.Next.Previous = current.Previous;
current.Previous.Next = current.Next;

Если удаляются первый и последний элемент, соответственно надо переустановить переменные head и tail.

И также в отличие от односвязной реализации здесь добавлен метод для перебора элементов с конца.

Применение списка:

DoublyLinkedList<string> linkedList = new DoublyLinkedList<string>();
// добавление элементов
linkedList.Add("Bob");
linkedList.Add("Bill");
linkedList.Add("Tom");
linkedList.AddFirst("Kate");
foreach (var item in linkedList)
{
    Console.WriteLine(item);
}
// удаление
linkedList.Remove("Bill");

// перебор с последнего элемента
foreach (var t in linkedList.BackEnumerator())
{
    Console.WriteLine(t);
}

НазадВперед

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

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

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

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

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

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

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950


struct list * swap(struct list *lst1, struct list *lst2, struct list *head){  // Возвращает новый корень списка  struct list *prev1, *prev2, *next1, *next2;  prev1 = head;  prev2 = head;  if (prev1 == lst1)    prev1 = NULL;  else    while (prev1->ptr != lst1) // поиск узла предшествующего lst1      prev1 = prev1->ptr;  if (prev2 == lst2)    prev2 = NULL;  else    while (prev2->ptr != lst2) // поиск узла предшествующего lst2      prev2 = prev2->ptr;  next1 = lst1->ptr;  // узел следующий за lst1  next2 = lst2->ptr;  // узел следующий за lst2  if (lst2 == next1)  {                       // обмениваются соседние узлы    lst2->ptr = lst1;    lst1->ptr = next2;    if (lst1 != head)      prev1->ptr = lst2;  }  else    if (lst1 == next2)    {      // обмениваются соседние узлы      lst1->ptr = lst2;      lst2->ptr = next1;      if (lst2 != head)        prev2->ptr = lst2;    }    else    {      // обмениваются отстоящие узлы      if (lst1 != head)        prev1->ptr = lst2;      lst2->ptr = next1;      if (lst2 != head)        prev2->ptr = lst1;      lst1->ptr = next2;    }  if (lst1 == head)    return(lst2);  if (lst2 == head)    return(lst1);  return(head);}

Структуры данных

Взаимообмен узлов списка

Здесь тоже необходимо рассмотреть две ситуации:

  • меняются соседние узлы При этом узлы могут быть переданы в любом порядке относительно корня списка. Для упрощения реализации функции поменяем узлы так, чтобы node1 стоял перед node2
  • меняются отстоящие узлы

1234567891011121314151617181920212223242526272829303132333435

void List::Swap(Node* node1, Node* node2){  if (node1 == NULL || node2 == NULL) return; // не допускаем обмен с несуществующим узлом  if (node1 == node2) return; // если один узел указан дважды, менять ничего не надо  if (node2->ptr == node1) // если node2 находится перед node1, меняем их местами  {    Node *p = node1;    node1 = node2;    node2 = p;  }  Node *prev1 = Prev(node1);  Node *prev2 = Prev(node2);  Node *next1 = Next(node1);  Node *next2 = Next(node2);  if (next1 == node2) // обмен соседних узлов  {    if (prev1 != NULL)      prev1->ptr = node2;    else      head = node2;    node2->ptr = node1;    node1->ptr = next2;    return;  }  if (prev1 != NULL)  // обмен отстоящих узлов    prev1->ptr = node2;  else    head = node2;  if (prev2 != NULL)    prev2->ptr = node1;  else    head = node1;  node2->ptr = next1;  node1->ptr = next2;}

Сортировка вставками

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

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

void insertBeforeElement(DblLinkedList *list, Node* elm, void *value) {
	Node *ins = NULL;
	if (elm == NULL) {
		exit(6);
	}
	
	if (!elm->prev) {
		pushFront(list, value);
		return;
	}
	ins = (Node*) malloc(sizeof(Node));
	ins->value = value;
	ins->prev = elm->prev;
	elm->prev->next = ins;
	ins->next = elm;
	elm->prev = ins;

	list->size++;
}

Теперь непосредственно сортировка

void insertionSort(DblLinkedList **list, int (*cmp)(void*, void*)) {
	DblLinkedList *out = createDblLinkedList();
	Node *sorted = NULL;
	Node *unsorted = NULL;
	
	pushFront(out, popFront(*list));

	unsorted = (*list)->head;
	while (unsorted) {
		sorted = out->head;		
		while (sorted && !cmp(unsorted->value, sorted->value)) {
			sorted = sorted->next;
		}
		if (sorted) {
			insertBeforeElement(out, sorted, unsorted->value);
		} else {
			pushBack(out, unsorted->value);
		}
		unsorted = unsorted->next;
	}

	free(*list);
	*list = out;
}

Видно, что в конце в переданном списке не остаётся элементов, так как мы их выталкиваем, так что старый список мы подменяем на вновь созданный.

Сложность алгоритма – O(n2), мы имеем одни проход по неотсортированному списку сложностью порядка n, для каждого элемента проходим по отсортированному.

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

Тепер сравним сложности различных операций для односвязного и двусвязного списка. Однонаправленный связный список

Сложность операций для односвязного списка.
pushFront popFront pushBack popBack insert delete get size
O(1) O(1) O(1) O(n) O(n) O(n) O(n) O(1)

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

Сложность операций для двусвязного списка.
pushFront popFront pushBack popBack insert delete get size
O(1) O(1) O(1) O(1) O(n) O(n) O(n) O(1)

Q&A

Всё ещё не понятно? – пиши вопросы на ящик

Пример

В качестве примера использования ОЛС рассмотрим следующую задачу.

  • Создать список из 10 элементов.
  • Удалить все элементы, равные нулю.
  • Поменять местами первый и последний элементы.

1234567891011121314151617181920212223242526272829303132333435

int main(){  system(«chcp 1251»);  system(«cls»);  List list;  list.Print();  // Создаем список, помещаем элементы в начало  for (int i = 0; i < 10; i++)   {    int z;    cout << «>> «;    cin >> z;    list.Add(z);  }  list.Print();  cout << «Последний элемент: » << list.getValue(list.getLast()) << endl;  // Удаляем элементы, равные 0  Node *p = list.getFirst();  do {    if (list.getValue(p) == 0)      p = list.Delete(p);    else      p = list.Next(p);  } while (p != NULL);  list.Print();  cout << «В списке » << list.getCount() << » элементов» << endl;  list.Swap(list.getFirst(), list.getLast());  list.Print();  list.Clear();  list.Print();  cout << «В списке » << list.getCount() << » элементов» << endl;  cin.get(); cin.get();  return 0;}

123456789101112131415161718192021222324252627282930313233

int main(){  system(«chcp 1251»);  system(«cls»);  List list;  list.Print();  Node *s = list.getLast();  for (int i = 0; i < 10; i++) {    int z;    cout << «>> «;    cin >> z;    s = list.Add(z, s);  }  list.Print();  cout << «Последний элемент: » << list.getValue(list.getLast()) << endl;  // Удаляем элементы, равные 0  Node *p = list.getFirst();  do {    if (list.getValue(p) == 0)      p = list.Delete(p);    else      p = list.Next(p);  } while (p != NULL);  list.Print();  cout << «В списке » << list.getCount() << » элементов» << endl;  list.Swap(list.getFirst(), list.getLast());  list.Print();  list.Clear();  list.Print();  cout << «В списке » << list.getCount() << » элементов» << endl;  cin.get(); cin.get();  return 0;}

Скачать полный код программыСтруктуры данных

Структура данных Список

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

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

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

Двусвязный список — элемент имеет указатели и на потомка, и на родителя.

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

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

Замкнутый список

На базе простого однонаправленного списка могут быть построены такие структуры данных, как очередь (queue) и стек (stack).

Очередь есть ничто иное, как список, операции чтения и добавления элементов в котором подвержены определенным правилам. При этом, при чтении элемента, он удаляется из очереди. Все операции проводятся по принципу «Первый пришел, первый вышел» (FIFO — first in, first out). Таким образом, для чтения в очереди доступна только голова, в то время как добавление проводится только в хвост.

Стек во многом похож на очередь, с той лишь разницей, что извлечение и добавление элементов в нем происходит по правилу «Последний пришел, первый вышел» (LIFO — last in, first out). Добавление и извлечение элементов проводится от головы. По принципу похоже на работу обоймы огнестрельного оружия.

Двусвязный список на языке C++

Рассмотрим пример реализации простейшего двусвязного списка. Этот и последующие примеры кода будут приведены на языке c++. В примере реализованы операции добавления нового элемента в список и вывод элементов на форму.

Элемент списка
Список

С этим читают