Предыдущая статья: “Структуры данных: массивы”
Связный список — это последовательность структур данных, связанных ссылками. Это последовательность ссылок, в которой содержатся элементы. В каждой ссылке есть связь с другой ссылкой. Связный список — это вторая по частоте использования (после массива) структура данных.
Вот термины, необходимые для понимания концепции связных списков:
- Ссылка. В каждой ссылке связного списка могут храниться данные, называемые элементом.
- Следующая ссылка. В каждой ссылке связного списка содержится ссылка на следующую ссылку (Next).
- Связный список содержит ссылку (связку) на первую ссылку (First).
Представление связного списка
Связный список можно представить в виде цепочки узлов, где каждый узел указывает на следующий:
Здесь надо учитывать следующие важные моменты:
- Связный список содержит элемент ссылки, называемой first (первой).
- Каждая ссылка имеет поле или поля данных и поле ссылки, называемой next (следующей).
- Каждая ссылка связана со следующей посредством своей ссылки next.
- Последняя ссылка содержит ссылку со значением null, обозначающую конец списка.
Типы связных списков
Различают следующие типы связных списков:
- Односвязный (однонаправленный) с переходом по элементам только вперед.
- Двусвязный (двунаправленный) с переходом по элементам вперед и назад.
- Кольцевой (циклический, замкнутый), в последнем элементе которого содержится ссылка на первый элемент, а в первом — на последний.
Базовые операции
Это основные операции, проводимые над списками:
- Вставка, то есть добавление элемента в начало списка.
- Удаление элемента из начала списка.
- Отображение полного списка.
- Поиск элемента по заданному ключу.
- Удаление элемента по заданному ключу.
Вставка
Добавление нового узла в связный список проходит в несколько этапов. Поэтому изучим эту операцию поэтапно. Сначала создается узел с той же структурой и находится место для его добавления:
Вставим узел B (NewNode) между левым A (LeftNode) и правым C (RightNode) узлами. Затем направим B.next на C:
NewNode.next −> RightNode;Выглядит это так:
Теперь узел next слева должен указывать на добавленный узел:
LeftNode.next −> NewNode;
Так новый узел окажется посередине двух узлов. Новый список должен выглядеть так:
Аналогичные этапы будут пройдены при вставке узла в начало списка. При вставке в конец списка новый узел будет указывать на NULL, а на сам новый узел будет указывать предпоследний узел.
Удаление
Удаление узла тоже проходит в несколько этапов. Снова изучим операцию поэтапно. Сначала с помощью алгоритмов поиска находится целевой узел, подлежащий удалению:
Узел слева от целевого узла (предыдущий) теперь должен указывать на узел справа от него (следующий):
LeftNode.next −> TargetNode.next;
Так будет удалена ссылка, указывавшая на целевой узел. Теперь, используя следующий код, удаляем то, на что указывает целевой узел:
TargetNode.next −> NULL;
Как использовать удаленный узел? Сохраним в памяти или же просто освободим память и полностью сотрем этот узел:
Обратная операция
Это сложная операция. Сделаем так, чтобы на последний узел указывал головной, и перевернем весь связный список:
Сначала переходим к концу списка. Он должен указывать на NULL. Сделаем так, чтобы он указывал на предыдущий узел:
Необходимо, чтобы последний узел не был последним. Для этого нужен некий временный узел, который выглядит как головной узел, указывающий на последний. Сделаем так, чтобы каждый узел слева указывал на свой предыдущий:
За исключением первого узла, на который указывает головной узел, каждый узел должен указывать на предыдущий и быть для него последующим. Первый узел будет указывать на NULL:
Используя временный узел, сделаем так, чтобы головной узел указывал на новый первый узел:
Связный список теперь перевернут. Вот реализация связного списка на языке программирования C:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
//отобразить список
void printList() {
struct node *ptr = head;
printf("\n[ ");
//начать с начала
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//установить указатель на первую позицию
void insertFirst(int key, int data) {
//создать ссылку
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
//указать на старый первый элемент
link->next = head;
//указать на новый первый элемент
head = link;
}
//удалить первый элемент
struct node* deleteFirst() {
//сохранить ссылку на первый указатель
struct node *tempLink = head;
//дать следующему элементу ссылку в качестве первого элемента
head = head->next;
//возвратить ссылку на удаленный элемент
return tempLink;
}
//проверить пустой ли список
bool isEmpty() {
return head == NULL;
}
int length() {
int length = 0;
struct node *current;
for(current = head; current != NULL; current = current->next) {
length++;
}
return length;
}
//найти ссылку по ключу
struct node* find(int key) {
//начать с первого указателя
struct node* current = head;
//если список пустой
if(head == NULL) {
return NULL;
}
//навигация по списку
while(current->key != key) {
//если элемент последний
if(current->next == NULL) {
return NULL;
} else {
//перейти на следующий элемент
current = current->next;
}
}
//если элемент найден, возвратить ссылку на него
return current;
}
//удалить ссылку с заданным ключом
struct node* delete(int key) {
//начать с первого элемента
struct node* current = head;
struct node* previous = NULL;
//если список пуст
if(head == NULL) {
return NULL;
}
//навигация по списку
while(current->key != key) {
//если элемент последний
if(current->next == NULL) {
return NULL;
} else {
//сохранить ссылку на текущий указатель
previous = current;
//перейти к следующей ссылке
current = current->next;
}
}
//найдено совпадение, обновить ссылку
if(current == head) {
//присвоить указателю на первый элемент значение указателя на второй элемент
head = head->next;
} else {
//перейти к следующему указателю
previous->next = current->next;
}
return current;
}
void sort() {
int i, j, k, tempKey, tempData;
struct node *current;
struct node *next;
int size = length();
k = size ;
for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head;
next = head->next;
for ( j = 1 ; j < k ; j++ ) {
if ( current->data > next->data ) {
tempData = current->data;
current->data = next->data;
next->data = tempData;
tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}
current = current->next;
next = next->next;
}
}
}
void reverse(struct node** head_ref) {
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
void main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("Original List: ");
//вывести список
printList();
while(!isEmpty()) {
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}
printf("\nList after deleting all items: ");
printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nRestored List: ");
printList();
printf("\n");
struct node *foundLink = find(4);
if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}
delete(4);
printf("List after deleting an item: ");
printList();
printf("\n");
foundLink = find(4);
if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}
printf("\n");
sort();
printf("List after sorting the data: ");
printList();
reverse(&head);
printf("\nList after reversing the data: ");
printList();
}Вывод:
Original List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Deleted value:(6,56)
Deleted value:(5,40)
Deleted value:(4,1)
Deleted value:(3,30)
Deleted value:(2,20)
Deleted value:(1,10)
List after deleting all items:
[ ]
Restored List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Element found: (4,1)
List after deleting an item:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
Element not found.
List after sorting the data:
[ (1,10) (2,20) (3,30) (5,40) (6,56) ]
List after reversing the data:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]Читайте также:
- Почему теория графов круче, чем вы думали
- Как не опустить руки во время обучения чему-то новому?
- Связный список в деталях
Читайте нас в Telegram, VK и Яндекс.Дзен
