Узлы в связанном списке связаны через указатели. Указатели представляют собой адрес места в памяти. Порядок в связанном списке определяется указателем в каждом узле. Узел в двухсвязном списке содержит элемент данных и указатель узла на следующий узел. В односвязном списке мы можем перемещаться только в одном направлении.
Первый узел связанного списка является головным, а последний узел — хвостовым. Если head равен NULL, то список пуст.
В C++ узел можно определить с помощью struct, которые содержат элемент данных и указатель на следующий узел.
struct Node
{
T data;
Node * next;
Node(T val): data(val), next(nullptr){}
};Node(T val): data(val), next(nullptr), prev(nullptr) {} — это конструктор для struct Node, который используется для инициализации data, next и prev. T означает, что это общая структура, и данные могут хранить значения всех типов данных.
Объявить голову: Node *head, *tail;
На приведенном выше рис. Узел, содержащий 5, является головным, а узел, содержащий 15, — хвостовым.
Три основные операции, поддерживаемые связным списком, — это поиск, вставка и удаление.
Searching
Функция поиска для двусвязного списка аналогична функции поиска для односвязного списка.
По теме: Односвязный список
В функции search значение передается в качестве аргумента, и его узел возвращается, если он найден, в противном случае появляется сообщение "Нет такого элемента в списке" и возвращается nullptr.
Функция начинает поиск от головы к последнему узлу, и переданное значение сопоставляется с элементом данных каждого узла.
Вот код для итеративного поиска.
struct Node *search(T n)
{ //returns node of the given value
Node *node = head;
while(node != nullptr)
{
if(node->data == n)
return node;
node = node->next;
}
std::cerr << "No such element in the list \n";
return nullptr;
}Вставка
Мы можем вставить узел в начале или в конце связанного списка. Когда мы вставляем узел впереди, указатель следующего узла указывает на начало списка, а затем узел становится новым началом списка. Вставляемое значение передается в качестве аргумента, и создается новый узел, содержащий это значение.
void insertFront(T val)
{
Node *node = new Node(val);
Node *tmp = head;
if (head == nullptr)
{
head = node;
tail = node;
}
else
{
node->next = head;
head = node;
node->next->prev = node;
}
}Когда мы вставляем узел в конце списка, узел добавляется после хвоста, а затем узел становится хвостом списка.
void insertBack(T val)
{
Node *node = new Node(val);
if(tail->next == nullptr)
{
tail->next = node;
tail = node;
}
}Удаление
В функцию deleteNode вводится значение, которое необходимо удалить. Функция ищет узел, содержащий значение, используя функцию search, а затем узел удаляется.
Если искомый узел head, тогда узел, следующий за головой, становится головным, а затем искомый узел удаляется. Узел удаляется, только если существует значение if (node != nullptr).
void deleteVal(T val)
{
Node* find = findVal(val);
Node *tmp = head;
if(tmp == find)
{
head = tmp->next;
}
else
{
while(find != nullptr)
{
if(tmp->next == find)
{
tmp->next = find->next;
find->next->prev = tmp;
delete find;
return;
}
tmp = tmp->next;
}
}
}C++ реализация двусвязного списка
#include <iostream>
template<class T>
class DoublyLinkedList
{
struct Node
{
T data;
Node* next;
Node* prev;
Node(T val): data(val), next(nullptr), prev(nullptr) {}
};
Node *head, *tail;
public:
DoublyLinkedList(): head(nullptr), tail(nullptr) {}
~DoublyLinkedList()
{
Node *tmp = nullptr;
while (head)
{
tmp = head;
head = head->next;
delete tmp;
}
head = nullptr;
}
DoublyLinkedList(const DoublyLinkedList<T> & dll) = delete;
DoublyLinkedList& operator=(DoublyLinkedList const&) = delete;
void insertFront(T val)
{
Node *node = new Node(val);
Node *tmp = head;
if (head == nullptr)
{
head = node;
tail = node;
}
else
{
node->next = head;
head = node;
node->next->prev = node;
}
}
void insertBack(T val)
{
Node *node = new Node(val);
if(tail->next == nullptr)
{
tail->next = node;
tail = node;
}
}
void deleteVal(T val)
{
Node* find = findVal(val);
Node *tmp = head;
if(tmp == find)
{
head = tmp->next;
}
else
{
while(find != nullptr)
{
if(tmp->next == find)
{
tmp->next = find->next;
find->next->prev = tmp;
delete find;
return;
}
tmp = tmp->next;
}
}
}
template <class U>
friend std::ostream & operator<<(std::ostream & os, const DoublyLinkedList<U> & dll){
dll.display(os);
return os;
}
private:
Node *findVal(T n) //returns node of the given number
{
Node *node = head;
while(node != nullptr)
{
if(node->data == n)
return node;
node = node->next;
}
std::cerr << "No such element in the list \n";
return nullptr;
}
void display(std::ostream& out = std::cout) const
{
Node *node = head;
while(node != nullptr)
{
out << node->data << " ";
node = node->next;
}
}
};
int main(){
DoublyLinkedList<int> l1;
l1.insertFront(3);
l1.insertBack(5);
l1.insertBack(12);
l1.insertFront(6);
l1.insertBack(88);
std::cout<<l1<<"\n";
l1.deleteVal(11);
std::cout<<l1<<"\n";
return 0;
}Посмотреть этот код на Github
Ссылка:
Введение в алгоритмы
Руководство по проектированию алгоритмов
Простые структуры данных и алгоритмы
Вам также может понравиться:
Переместить все нечетные числа после четных в односвязный список
Объединить два отсортированных связанных списка (на месте)
Разделить одноциклический связанный список
Двойной циклический связанный список
Обратить связанный список
Поиск длины цикла в связанном списке
Первоначально опубликовано на https://programmercave0.github.io 28 июля 2017 г.
