Структуры данных: связный список



Книга Структуры данных: связный список

Предыдущая статья: “Структуры данных: массивы

Связный список  —  это последовательность структур данных, связанных ссылками. Это последовательность ссылок, в которой содержатся элементы. В каждой ссылке есть связь с другой ссылкой. Связный список  —  это вторая по частоте использования (после массива) структура данных.

Вот термины, необходимые для понимания концепции связных списков:

  • Ссылка. В каждой ссылке связного списка могут храниться данные, называемые элементом.
  • Следующая ссылка. В каждой ссылке связного списка содержится ссылка на следующую ссылку (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) ]

659   0  
    Ничего не найдено.

Добавить ответ:
Отменить.