Основы структур данных и алгоритмов
Реализация связанного списка в C ++
Все, что вам нужно знать для реализации базового связанного списка на языке C Plus Plus
Связанный список - это список, состоящий из связывания узлов вместе. Если эти слова вам незнакомы, не волнуйтесь, мы начнем с основ, поэтому они будут объяснены в ходе изучения этой статьи. Первый шаг в понимании более сложной структуры данных начинается с понимания гораздо более простой структуры. Давайте познакомимся с тем, что на самом деле является связным списком.
Связанный список
В информатике связанный список - это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти.
Приведенное выше определение в Википедии звучит немного расплывчато и трудно для понимания. Давайте сначала проанализируем это. Список - это упорядоченная структура данных, в которой элементы хранятся в определенном порядке. Обычно порядок определяется вставкой. А связанный список - это просто список, состоящий из узлов, которые ссылаются на следующий узел, и так далее. В отличие от массива, который построен из блока памяти, разбитого на куски, он построен из вещей, которые мы обычно называем узлами. Подумайте, узел как блок памяти, в котором хранятся только две вещи: данные и ссылка. Эти данные могут быть чем угодно, от простого int до сложных вещей, а ссылка - это просто ссылка (или указатель для тех, кто занимается C ++) на следующий узел. Следовательно, структура данных, сформированная из последовательности этих взаимосвязанных узлов, называется Связанным списком.
Связанный список - это очень объектно-ориентированный вид структуры данных, что означает, что в нем есть идеи ООП. Он состоит из подэлементов, которые каким-то образом изменяемы и более гибкие, чем массив.
Но почему именно связанный список? Связанные списки часто используются из-за их эффективности при вставке и удалении. Когда нам нужны постоянные вставки / удаления из списка, мы используем связанный список. Как вы можете видеть на приведенной выше иллюстрации, добавить или удалить узел просто, так как для этого требуется просто настроить значение указателя.
Реализация связанного списка
Простой способ реализовать связанный список - создать класс Node и вручную связать их вместе. Но для лучшего дизайна мы собираемся создать класс LinkedList, который обрабатывает все. Этот класс содержит узлы и предоставляет внешний интерфейс для доступа к нему других.
Но сначала давайте создадим класс List ADT, чтобы мы понимали, каковы фактические свойства списка. Для простоты мы определим простой список целых чисел и связанный список int, и мы будем следовать операциям, определенным на странице Википедии для списка.
#ifndef INTLIST_H_
#define INTLIST_H_
class intList {
public:
virtual intList(){};
virtual ~intList(){};
virtual bool isEmpty() = 0;
virtual void prepend(int c) = 0;
virtual void append(int c) = 0;
virtual int getHead() = 0;
virtual intList *tail() = 0;
};
#endi
Приведенный выше код определяет интерфейс или основное значение того, что значит быть списком. Это не связанный список, а более особый стиль списка. Теперь позвольте унаследовать этот список и создать файл заголовка связанного списка.
#ifndef INTLINKEDLIST_H_
#define INTLINKEDLIST_H_
#include <cstddef>
#include "intList.h"
using std::size_t;
class intLinkedList : public intList {
private:
intNode *head // our head node
size_t length;
public:
intLinkedList(); // constructor
~intLinkedList(); //destructor
bool isEmpty();
void append(int data);
void prepend(int data);
int getHead();
intLinkedList * tail();
};
#endif
Итак, в приведенном выше классе у нас просто есть простое объявление методов, которое позволяет разумно управлять всеми узлами в связанном списке. Следовательно, у нас должен быть частный узел внутри класса Linked List (т.е. без внешнего доступа), и только этот класс контролирует доступ и управляет своей структурой внутри. Давай создадим его.
//Note: I have just copies above class
class intLinkedList : public intList {
private:
// our private node class
class intNode {
private:
intNode* next; // pointer to the next node
int data; // our actual int data
public:
intNode();
intNode(intNode * next, int data);
~intNode();
int getData();
intNode * getNext();
void setNext(intNode *);
}
intNode *head // our head node
size_t length;
public:
intLinkedList(); // constructor
~intLinkedList(); //destructor
bool isEmpty();
void append(int data);
void prepend(int data);
int getHead();
intLinkedList * tail();
};
#endif
Над классом не так сложно, как кажется. Он просто содержит набор методов, которые необходимо реализовать для создания связанного списка, и содержит частный класс с именем intNode, который также является набором методов и свойств для каждого узла внутри связанного списка. Давайте реализуем каждый метод по очереди.
Примечание. Для улучшения дизайна мы следуем концепциям ООП с учетом C ++. Итак, ADT списка выше находится внутри intList.h, а класс связанного списка находится внутри intLinkedList.h, и теперь мы собираемся реализовать все функции внутри intLinkedList.cpp.
Наш частный класс Node
// Node default constructor
intLinkedList::intNode::intNode() {
data = 0;
next = nullptr;
}
// Node parameterized constructor
intLinkedList::intNode::intNode(intNode *nextNode, int actualData) {
data = actualData;
next = nextNode;
}
// we don't have to do anything in this destructor as we are not creating anything in heap inside node
intLinkedList::intNode::~intNode() {}
// Returns the actual data
int intLinkedList::intNode::getData() { return data; }
// Returns next node
intLinkedList::intNode *intLinkedList::intNode::getNext() {
return next;
}
// set the next node
void intLinkedList::intNode::setNext(intNode *nextNode) {
next = nextNode;
}
Конструкторы и деструктор LinkedList
// Linked list default constructor, sets initial length to zero and head to null poiner (you can also write 0 instead of nullptr)
intLinkedList::intLinkedList() {
head = nullptr;
length = 0;
}
// When we append to the linkedlist we called new keyword (see below) which created the nodes inside heap. So when we are done with the linkedlist we have to delete those nodes inside this function
intLinkedList::~intLinkedList(){
// if the head is not empty (meaning if the list has elements)
if(head != nullptr){
intNode * currentNode = head;
while(current->getNext() != nullptr){ //until the end
delete current;
current = current->getNext();
}
}
}
Обратите внимание на использование оператора delete. Этот оператор только освобождает память на другом конце указателя, но не очищает все. Итак, все данные по-прежнему находятся там, и, следовательно, мы могли бы вызвать current->getNext().
пустой
Это самая простая функция. Мы используем длину для возврата логического значения. Вы также можете проверить, nullptr голова или нет.
bool intLinkedList::isEmpty() { return length == 0; }
Подготовить
void intLinkedList::prepend(int data) {
// create a node to contain that data
intNode *newNode = new intNode(head, data)
// next node must be the old head
// adjust out head point to the new one
head = newNode;
// increase the length of linked list
length++;
}
Добавить
void intLinkedList::append(int data) {
// get to the end of the list
// if the list is empty, simply prepend
if (head == nullptr) {
prepend(c);
} else {
intNode *current = head;
while (current->getNext() != nullptr) {
current = current->getNext();
}
intNode *newNode = new intNode(nullptr, c);
current->setNext(newNode);
}
length++;
}
getHead
Просто возвращает данные, содержащиеся внутри первого узла.
int intLinkedList::getHead() {
return head->getData();
}
getTail
Возвращает остальные элементы, кроме головы, в виде списка. Просто выполните итерацию, используя указатель getNext(), и создайте новый список, как только мы передадим заголовок.
intLinkedList *intLinkedList::tail() {
intLinkedList *newList = new intLinkedList();
if (head != nullptr) {
intNode *current = head->getNext();
while (current != nullptr) {
newList->append(current->getData());
current = current->getNext();
}
}
return newList;
}
Заключение
Теперь вы можете создать любой тип связного списка. Выше приведены все методы, реализованные для связанного списка типа int. Мы рассмотрели int как тип, потому что его легче понять. Мы могли бы легко реализовать связанный список шаблонов, но это для другой статьи. Надеюсь, вы хорошо понимаете, если у вас возникнут какие-либо сомнения, не стесняйтесь обращаться ко мне. А пока желаю хороших выходных.
