Связный список
Содержание:
Тестирование производительности
Для тестирования производительности связных списков использовался список, состоящий из 2000 элементов, при этом значение элемента могло быть от 0 до 100, и элементы вставлялись в отсортированном порядке.
В ходе тестирования было выяснено, что реализация одного и того же алгоритма для вставки элементов в отсортированный связный список ведет себя по-разному в зависимости от языка и размера списка. Производительность Python-реализации начинает снижаться, когда в списке накапливается более 2-х тысяч элементов. Анализ результатов теста показывает, что основные потери процессорного времени происходят во время итерации.
Исходный код тестов на языках Си и Python можно найти в архиве performance_benchmark.zip, прикрепленном к статье. Реализация на языке Си работает гораздо быстрее, и ее производительность начинает снижаться, когда размер списка становится значительно больше 2-х тысяч элементов. Версию на языке Python не спасает даже оптимизация кода за счет сокращения вызовов функции SortedInser, так как из-за динамического создания объектов в Python, начиная с определенного момента, возникают проблемы при итерации.
Удаление элемента из односвязного списка
При удалении узла из односвязного списка усекается его головной элемент. Если в списке еще остаются узлы, то новым головным элементом становится узел, следующий за головным элементом, иначе остается :
|
1 |
template<typenameT> voidList<T>remove(){ if(m_head){// Если список не пуст: // Сохраняем указатель на второй узел, который станет новым головным элементом Node*newHead=m_head->m_next; // Освобождаем память, выделенную для удаляемого головного элемента delete m_head; // Назначаем новый головной элемент m_head=newHead; }// Иначе могли бы возбудить исключение } |
Список является динамической структурой. При добавлении новых узлов выделяется память из кучи, которую нужно освободить, чтобы не создавать утечек памяти. Имея функцию удаления элементов, реализовать деструктор односвязного списка совсем не сложно:
|
1 |
template<typenameT> List<T>~List(){ while(m_head){ remove(); } } |
Недостатки
Недостатки связных списков вытекают из их главного свойства — последовательного доступа к данным:
- сложность прямого доступа к элементу, а именно определения физического адреса по его индексу (порядковому номеру) в списке
- на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны)
- некоторые операции со списками медленнее, чем с массивами, так как к произвольному элементу списка можно обратиться, только пройдя все предшествующие ему элементы
- соседние элементы списка могут быть распределены в памяти нелокально, что снизит эффективность кэширования данных в процессоре
- над связными списками, по сравнению с массивами, гораздо труднее (хоть и возможно) производить параллельные векторные операции, такие, как вычисление суммы: накладные расходы на перебор элементов снижают эффективность распараллеливания
Вставка элемента в отсортированный список
В листинге 18 представлена функция для вставки элемента в отсортированный список. Как обычно, сначала выполняется проверка, что список не пустой, а затем итерация в поисках ближайшего элемента, значение которого меньше, чем у добавляемого.
Листинг 18. Си — вставка элемента в отсортированный список
void SortedInsert(struct node** headRef, struct node* newNode)
{
if (*headRef == NULL || (*headRef)->data >= newNode->data)
{
newNode->next = *headRef;
*headRef = newNode;
}
else
{
struct node* current = *headRef;
while (current->next!=NULL && current->next->data < newNode->data)
{
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
В реализации на языке Python выполняется проверка списка на пустоту, а затем выполняется итерация с помощью двух временных переменных, как и в листинге 18.
Листинг 19. Python – вставка элемента в отсортированный список
def SortedInsert(self,x):
if (self.first == None):
self.first = Node(x,self.last)
return
if self.first.value > x:
self.first = Node(x,self.first)
return
old = curr = self.first
while curr != None:
if curr.value > x:
curr = Node(x,curr)
old.next = curr
return
old = curr
curr = curr.next
curr = Node(x,None)
old.next = curr
Массивы и связные списки
Связные списки используются, когда требуется структура данных, размер которой заранее неизвестен. В такие списки можно добавлять и удалять элементы уже после создания самого списка. Однако такой список требует дополнительных усилий для поддержания целостности при динамических операциях, так как при удалении элемента из списка обрывается связь между элементами, находящимися до и после него, и эти элементы необходимо снова связать между собой.
Списки широко используются в реальных проектах — операционных системах, базах данных, но для работы с ними требуется знать, как устроена арифметика указателей. В листинге 1 представлен массив из 100 элементов и инициализируются его первые 3 значения.
Листинг 1. Инициализация массива
int my_array; my_array=1; my_array=20; my_array=100;
Физически все 100 элементов располагаются в памяти последовательно, и индекс элемента — это смещение в блоке памяти от его начала, поэтому извлечение элемента по индексу выполняется крайне быстро. Это и есть адресная арифметика, но так как память для стандартного массива выделяется на этапе компиляции, то и модифицировать его впоследствии уже нельзя.
Для выделения памяти для связного списка используется иной механизм, когда память выделяется динамически, во время работы программы. Данный тип памяти называется «куча» (heap) и добавляемые элементы физически могут располагаться в такой куче без всякого упорядочивания.
Кольцевой двусвязный список
Последнее обновление: 25.10.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;
using System.Collections.Generic;
namespace SimpleAlgorithmsApp
{
public class CircularDoublyLinkedList<T> : IEnumerable<T> // кольцевой двусвязный список
{
DoublyNode<T> head; // головной/первый элемент
int count; // количество элементов в списке
// добавление элемента
public void Add(T data)
{
DoublyNode<T> node = new DoublyNode<T>(data);
if (head == null)
{
head = node;
head.Next = node;
head.Previous = node;
}
else
{
node.Previous = head.Previous;
node.Next = head;
head.Previous.Next = node;
head.Previous = node;
}
count++;
}
// удаление элемента
public bool Remove(T data)
{
DoublyNode<T> current = head;
DoublyNode<T> removedItem = null;
if (count == 0) return false;
// поиск удаляемого узла
do
{
if (current.Data.Equals(data))
{
removedItem = current;
break;
}
current = current.Next;
}
while (current!=head);
if (removedItem != null)
{
// если удаляется единственный элемент списка
if (count==1)
head = null;
else
{
// если удаляется первый элемент
if(removedItem==head)
{
head = head.Next;
}
removedItem.Previous.Next = removedItem.Next;
removedItem.Next.Previous = removedItem.Previous;
}
count--;
return true;
}
return false;
}
public int Count { get { return count; } }
public bool IsEmpty { get { return count == 0; } }
public void Clear()
{
head = null;
count = 0;
}
public bool Contains(T data)
{
DoublyNode<T> current = head;
if (current == null) return false;
do
{
if (current.Data.Equals(data))
return true;
current = current.Next;
}
while (current != head);
return false;
}
IEnumerator IEnumerable.GetEnumerator()
{
return ((IEnumerable)this).GetEnumerator();
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
DoublyNode<T> current = head;
do
{
if (current != null)
{
yield return current.Data;
current = current.Next;
}
}
while (current != head);
}
}
}
Суть добавления состоит в том, что мы переустанавливаем предыдущий элемент по отношению к head:
public void Add(T data)
{
DoublyNode<T> node = new DoublyNode<T>(data);
if (head == null)
{
head = node;
head.Next = node;
head.Previous = node;
}
else
{
node.Previous = head.Previous;
node.Next = head;
head.Previous.Next = node;
head.Previous = node;
}
count++;
}
Частным случаем здесь будет являться ситуация, когда список пуст. Тогда устанавливается головной элемент head.
При удалении переустанавливаем указатели у предыдущего и следующего элементов, по отношению к удаляемому:
public bool Remove(T data)
{
DoublyNode<T> current = head;
DoublyNode<T> removedItem = null;
if (count == 0) return false;
// поиск удаляемого узла
do
{
if (current.Data.Equals(data))
{
removedItem = current;
break;
}
current = current.Next;
}
while (current!=head);
if (removedItem != null)
{
// если удаляется единственный элемент списка
if (count==1)
head = null;
else
{
// если удаляется первый элемент
if(removedItem==head)
{
head = head.Next;
}
removedItem.Previous.Next = removedItem.Next;
removedItem.Next.Previous = removedItem.Previous;
}
count--;
return true;
}
return false;
}
Применение класса:
CircularDoublyLinkedList<string> circularList = new CircularDoublyLinkedList<string>();
circularList.Add("Tom");
circularList.Add("Bob");
circularList.Add("Alice");
circularList.Add("Sam");
foreach (var item in circularList)
{
Console.WriteLine(item);
}
circularList.Remove("Bob");
Console.WriteLine("\n После удаления: \n");
foreach (var item in circularList)
{
Console.WriteLine(item);
}
Консольный вывод:
Tom Bob Alice Sam После удаления: Tom Alice Sam
Назад
Недостатки
Недостатки связных списков вытекают из их главного свойства — последовательного доступа к данным:
- сложность прямого доступа к элементу, а именно определения физического адреса по его индексу (порядковому номеру) в списке
- на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны)
- некоторые операции со списками медленнее, чем с массивами, так как к произвольному элементу списка можно обратиться, только пройдя все предшествующие ему элементы
- соседние элементы списка могут быть распределены в памяти нелокально, что снизит эффективность кэширования данных в процессоре
- над связными списками, по сравнению с массивами, гораздо труднее (хоть и возможно) производить параллельные векторные операции, такие, как вычисление суммы: накладные расходы на перебор элементов снижают эффективность распараллеливания
Файл «List_Two.h»
/****************************************/
/* Двусвязный список */
/****************************************/
#ifndef _LIST_TWO_H_
#define _LIST_TWO_H_
/*Описание исключительных ситуаций*/
const int listTwoOk = 0; // Все впорядке
const int listTwoEmpty = 1; // Список пуст
const int listTwoNoMem = 2; // Недостаточно памяти
const int listTwoEnd = 3; // Указатель в конце
const int listTwoBegin = 4; // Указатель в начале
/**********************************/
/*Переменная ошибок*/
extern int listTwoError;
/*Базовый тип списка*/
typedef int listTwoBaseType;
/*Структура элемента списка*/
struct elementTwo {
listTwoBaseType data; // Данные
elementTwo *predLink; // Указатель на предыдущий элемент
elementTwo *nextLink; // Указатель на следующий элемент
};
/*Дескриптор списка*/
typedef struct {
elementTwo *Start; // Указатель на левый фиктивный элемент
elementTwo *End; // Указатель на правый фиктивный элемент
elementTwo *ptr; // Рабочий указатель
} ListTwo;
/*Функции работы со списком*/
void initListTwo(ListTwo *L); // Инициализация списка
void predPut(ListTwo *L, listTwoBaseType E); // Включение до рабочего указателя
void postPut(ListTwo *L, listTwoBaseType E); // Включение после рабочего указателя
void predGet(ListTwo *L, listTwoBaseType *E); // Исключение до рабочего указателя
void postGet(ListTwo *L, listTwoBaseType *E); // Исключение после рабочего указателя
void movePtrListTwoLeft(ListTwo *L); // Сдвиг рабочего указателя назад
void movePtrListTwoRight(ListTwo *L); // Сдвиг рабочего указателя вперед
void beginPtrListTwo(ListTwo *L); // Установить рабочий указатель в начало
void endPtrListTwo(ListTwo *L); // Установить рабочий указатель в конец
void doneListTwo(ListTwo *L); // Удаление списка
int isEmptyListTwo(ListTwo *L); // Предикат: пуст ли список
/***************************/
#endif
Пример
В качестве примера использования ОЛС рассмотрим следующую задачу.
- Создать список из 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;}
Скачать полный код программыСтруктуры данных
