Моя реализация двусвязного списка

Немного лирики

Примерно полгода назад мне было дано задание реализовать двусвязный список на языке С++. В тот момент мои познания в языке были сугубо скромные. Разумеется, я начал искать решение своей проблемы в интернете, но все найденные варианты меня не устроили либо из-за своей простоты, либо излишней запутанности объяснений. Поэтому я решил, что как только сделаю что-то более достойное, то тут же попытаюсь написать об этом статью. И вот этот момент настал.

Немного теории

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

Класс LinkedList

Класс LinkedList будет реализовывать наш двусвязный список. Пожалуй, удобно сделать его шаблонным, чтобы в нем можно было хранить любой тип данных. Ниже представлено объявление класса.

template<typename Item> class LinkedList {  private:  	// Структура, которая реализует узел списка 	struct Node												 	{ 		Item item;	// Содержимое узла 		Node* prev;	// Указатель на предыдущий узел 		Node* next;	// Указатель на следующий узел 	};  	Node* first;	// Указатель на первый узел списка 	Node* last;	// Указатель на последний узел списка 	int size;		// Размер списка  	// Перечисление, используемое в приватном методе ниже 	enum { 		up = 0, 		down = 1, 		};  	// Метод, исключающий дублирование кода при поиске элементов внутри класса 	Node& findElement(int pos, int count = up) const;  	 public:  	// Конструктор по умолчанию 	LinkedList(); 	// Конструктор с созданием одного узла 	LinkedList(Item); 	// Конструктор копирования (глубокое копирование) 	LinkedList(const LinkedList&);  	// Деструктор 	~LinkedList();	  	// Добавление узла в конец списка 	LinkedList& Add(const Item&);			 	// Добавление узла на указанную позицию 	LinkedList& Add(const Item&, int pos);	  	// Размещение указанного количества элементов массива в конец списка 	LinkedList& Add(const Item[], int number);	 	// То же, что и выше, только с указанием позиции размещения 	LinkedList& Add(const Item[], int number, int pos);  	// Добавление узлов из другого списка 	LinkedList& Add(const LinkedList<Item>&); 	// То же, только с добавлением на указанную позицию 	LinkedList& Add(const LinkedList<Item>&, int pos);  // Удаление узлов, начиная с узла, который указан в pos  // (по умолчанию удаляется один узел) 	LinkedList& Delete(int pos, int range = 1);             	// Удаление узла в конце списка 	LinkedList& Delete();						  // Перегрузка операции [], используется при использование  	Item operator[](int i) const; 	// То же, только используется в изменяемом списке 	Item& operator[](int i);	  	// Перегрузка оператора сложения 	LinkedList operator+(const LinkedList<Item>&) const; 	// Перегрузка операции равно (глубокое копирование) 	const LinkedList& operator=(const LinkedList<Item>&);  	// Метод, возвращающий размер списка 	int Size();					 };

Приватная часть класса

Начнем с того, что объявим внутри класса структуру, представляющую собой узел списка. Ее объявление в приватной части класса позволит обеспечить инкапсуляцию. Затем надо объявить поля, являющиеся указателями на первый и последний узел. Размер списка понадобится нам в реализации интерфейса класса(публичные методы). Перечисление и приватный метод рассмотрим вместе.

Метод findElement

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

// Приватный метод, позволяющий найти нужный узел в списке  // Без использования typename, возникают проблемы распознавания // включенной структуры Node, как типа, поэтому необходимо это явно указать  template<typename Item> typename LinkedList<Item>::Node& LinkedList<Item>::findElement(int pos, int count) const  {																						   	LinkedList<Item>::Node* current;   // Указатель на узел 												 // Теперь в зависимости от значения count будет осуществляться поиск	 // либо сверху вниз, либо снизу вверх // (при удалении элементов может быть невозможен поиск снизу вверх) // При удалении элементов, например из центра списка,  // при прохождении его от первого элемента, наткнемся на пустую область памяти // В этом случае придется идти от последнего элемента к нужному нам 	if (count == up)							 	{											 		current = first; 		for (int k = 1; k <= pos; k++) 			current = current->next; 	} 	else 	{ 		current = last; 		for (int k = size - 2; k >= pos; k--) 			current = current->prev; 	}  	return *current; }

Начнем с сигнатуры метода. Возвращаемым значением будет ссылка на искомый узел, что позволяет редактировать непосредственно сам узел и экономит ресурсы, так как тогда не создается временный объект. Параметр функции pos определяет позицию искомого узла, а параметр count определяет направление поиска: сверху вниз(down), снизу вверх(up — по умолчанию). Квалификатор const говорит о том, что метод не изменяет объект, вызвавший его.

Публичная часть(интерфейс)

Методы Add

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

// Основной метод, добавляющий узел (newNode) // Будет использоваться в остальных перегрузках метода Add template<typename Item> LinkedList<Item>& LinkedList<Item>::Add(const Item& item, int pos)	 {						 	// Создаем новый узел и инициализируем им указатель 	LinkedList<Item>::Node* temp = new LinkedList<Item>::Node; 	// Устанавливаем содержимое нового узла 	temp->item = item;												  	// Если позиция указывает на позицию за последним элементом, то 	if (pos >= size) 	{ 		// новый узел становится последним и 		// указатель на следующий элемент узла устанавливается в "0" 		last = temp;										 		temp->next = nullptr; 	} 	else	// В ином случае  	{ // указатель на следующий элемент устанавливается на узел,  // который ранее стоял на этой позиции (oldNode), 		temp->next = &findElement(pos);						 // а указатель на предыдущий узел узла oldNode устанавливается на newNode 		(temp->next)->prev = temp;	 	} // В итого новый узел и узел перед ним(если он есть) связаны,  // осталось связать наш узел с предыдущим  // Т.к. либо перед, либо после, либо же по обе стороны от нашего узла  // могут отсутствовать другие узлы, // то логично было разделить связывание newNode c последующим и предыдущим узлами // Это избавляет нас от сильной вложенности и путаницы  	// Если позиция = 0, то узел становится первым 	if (pos == 0) 	{ 		temp->prev = nullptr; 		first = temp; 	} 	else 		// В ином случае, если размер не равен нулю 		// (вдруг пользователь указал ненулевую позицию, а список пуст), 		// то связываем newNode с предыдущим узлом 		if (size != 0)							 		{													 			temp->prev = &findElement(pos - 1); 			temp->prev->next = temp; 		}  	size++;	// Увеличиваем значение размера списка  	// Возвращаем, используя ссылку, объект, который вызвал метод, 	// чтобы можно было воспользоваться конструкцией вида: list.Add().Add() 	return *this;											 }

Далее просто покажу код остальных перегрузок метода Add с подробными комментариями.

// Добавление узла в конец списка template<typename Item> LinkedList<Item>& LinkedList<Item>::Add(const Item& item) { // Вызываем метод добавления узла, передавая ему содержимое item и указывая, // что надо добавить узел в конец при помощи поля size  //(гарантирует, что попали на позицию за последним элементом) 	return Add(item, size);									 }

// Добавление массива элементов item[] в список, // где number - количество элементов массива, // которые необходимо добавить, а pos указывает на позицию // с которой начинается добавление узлов template<typename Item> LinkedList<Item>& LinkedList<Item>::Add(const Item item[], int number, int pos) { 	// Цикл, вызывающий метод Add, который добавляет по одному элементу в список 	for (int i = 0; i < number; i++, pos++) 	{ 		Add(item[i], pos); 	} 	return *this; }

// Добавление массива в конец списка  template<typename Item> LinkedList<Item>& LinkedList<Item>::Add(const Item item[], int number) { 	// Вызывает предыдущую перегрузку метода, 	// передавая указание, что надо добавить массив в конец списка 	return Add(item, number, size); }

// Добавление в список другого списка // Узлы добавляются, начиная с указанной позиции template<typename Item> LinkedList<Item>& LinkedList<Item>::Add(const LinkedList<Item>& list, int pos) { 	// Используется тот же подход, что и с добавлением элементов массива 	// в список 	for (int i = 0; i < list.size; i++, pos++) 	{ 		// Используется перегрузка операции [] 		Add(list[i], pos); 	}  	return *this; }

О перегрузке оператора [] будет написано ниже.

// Добавление в конец списка другого списка template<typename Item> LinkedList<Item>& LinkedList<Item>::Add(const LinkedList<Item>& list) { 	// Используется тот же принцип, что и при добавлении 	// элементов массива в конец списка 	return Add(list, size); }

Конструкторы класса

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

template<typename Item> LinkedList<Item>::LinkedList() { 	// Установка всех полей в "0" 	size = 0; 	first = nullptr; 	last = nullptr; }

Прочие конструкторы тоже не заключают в своей реализации особых сложностей.

template<typename Item> LinkedList<Item>::LinkedList(Item item)	// Создание одного узла { 	size = 1;	// Установка размера списка в 1 	// Создание узла и установка на него указателей 	first = last = new LinkedList<Item>::Node;         // Через указатель first устанавливаем поля созданного узла 	first->prev = nullptr;	 	first->next = nullptr; 	first->item = item; } 

// Конструктор, инициализирующий созданный объект списком template<typename Item> LinkedList<Item>::LinkedList(const LinkedList<Item>& ll) {  	// Для начала установим указатели в "0" 	// на случай, если будет совершена попытка инициализировать 	// созданный объект пустым списком 	first = last = nullptr; 	size = 0;  	// Просто вызываем метод добавления элемента, 	// который внутри себя выставит все нужные поля объекта 	for (int i = 0; i < ll.size; i++) 	{ 		Add(ll[i], i); 	}  }

Перегрузка оператора []

Были реализованы две перегрузки оператора, одна для работы с константным объектом, другая — с неконстантным.

template<typename Item> Item& LinkedList<Item>::operator[](int i) { 	// Небольшой костыль 	// В дальнейшем можно добавить создание исключений 	if (i < 0 || i >= size) 		std::cout << "Выход за границы массива";  	// С помощью приватного метода ищется нужный элемент 	// и возвращается его полезное содержимое 	return findElement(i).item; }

// То же самое, но для работы с константными объектами template<typename Item> Item LinkedList<Item>::operator[](int i) const { 	if (i < 0 || i >= size) 		std::cout << "Выход за границы массива";  	return findElement(i).item; }

Метод Delete

Удаление узлов в списке я поделил на два этапа:

1. Удаление узлов
2. «Сшивание» оставшихся узлов между собой

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

// По умолчанию удаляется один элемент, на который указывает pos template<typename Item> LinkedList<Item>& LinkedList<Item>::Delete(int pos, int range) {  	// Очередной костыль) 	if (pos < 0 || pos >= size) 		std::cout << "Выход за границы массива";  	// Так как в методе findElement используется поле size, 	// то до полного "сшивания" списка размер не должен изменяться, 	// в ином случае поиск будет осуществляться неверно. 	// Поэтому в самом методе используется tempSize 	int tempSize = size;  	// Первый  этап  	// Последовательно удаляем нужное количество элементов, 	// начиная с указанной позиции 	for (int i = pos; i < pos + range && i < size; i++, tempSize--) 		delete &findElement(i, down);  	// Второй этап  	// Если были удалены все элементы, 	// то просто устанавливаем все указатели в "0" 	if (tempSize == 0) 		first = last = nullptr; 	else 	{ 		// В ином случае возможны три варианта: 		// 1) Удалено определенное количество элементов, начиная с первого 		// 2) Удалены узлы(не с первого) вплоть до последнего включительно 		// 3) Удалены узлы(не с первого), но не доходя до последнего узла  		if (pos == 0)	// 1) 		{ 			// Обновляем первый элемент списка 			first = &findElement(pos + range, down); 			first->prev = nullptr; 		} 		else 		   if (pos + range >= size)	// 2) 		   { 			// Обновляем последний элемент списка 				last = &findElement(pos - 1); 				last->next = nullptr; 		    } 		    else						// 3) 		    { // Сшиваем конец одного куска списка с началом другого // down указывает нам о том, что поиск элемента идет сверху вниз // Логично, что в одних случаях надо идти сверху вниз, // а в других - наоборот // Это вызвано появлением "пустого" участка в центре списка, ибо два куска его // еще не сшиты между собой. Но у нас имеются указатели last и first, // каждый из которых указывает на отдельный кусок и можно таким образом  //проводить поиск в каждом из них 		       findElement(pos - 1).next = &findElement(pos + range, down); 		       findElement(pos + range, down).prev = &findElement(pos - 1); 		     } 				 	} 	 	// Обновляем значение размера списка 	size = tempSize;  	return *this; }

// Удаление элемента в конце списка template<typename Item> LinkedList<Item>& LinkedList<Item>::Delete() { 	// Просто вызовем иную перегрузку, передав координаты конца 	return Delete(size - 1); }

Деструктор класса

При выделении памяти операцией new необходимо реализовать деструктор, а не полагаться на создаваемый компилятором, ибо он производит так называемое «поверхностное» удаление. Нам же необходимо удалить все узлы, перед удалением самого объекта.

template<typename Item> LinkedList<Item>::~LinkedList() { 	// Чтобы не дублировать код удаления всех элементов, 	// можно просто вызвать функцию Delete, передав ей параметры для 	// удаления всех узлов в списке 	Delete(0, size); } 

Перегрузка оператора +

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

Стоит напомнить, что метод вызывается объектом, расположенным слева от знака +, а параметром является объект справа.

template<typename Item> LinkedList<Item> LinkedList<Item>::operator+(const LinkedList<Item>& list) const { 	// Создаем временный объект, инициализируя 	// вызвавшим его объектом 	LinkedList<Item> temp(*this); 	// Добавляем второй список 	temp.Add(list); 	return temp; }

Перегрузка оператора =

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

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

template<typename Item> const LinkedList<Item>& LinkedList<Item>::operator=(const LinkedList<Item>& list) { 	// Очистка списка	 	if (size != 0) 		this->~LinkedList(); 	  	// Запись в список новых узлов 	Add(list);  	// можно использовать так: list1 = list2 = list3; 	return list; 	// Если бы возвращаемое значение было void, то метод бы работал, но 	// нельзя было бы использовать цепочку из приравниваний } 

Метод size

Пожалуй, тут комментарий излишни.

template<typename Item> int LinkedList<Item>::Size() { 	return size; } 

Заключение

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