Наука о данных

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

08.03.2022

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

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

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

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

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

Представление связного списка

Типы связных списков

Базовые операции

Вставка

Удаление

Обратная операция

Читайте также

Отложенная загрузка изображений с помощью Intersection Observer API

Навигация во Flutter с использованием AutoRoute

Сильные и слабые стороны метавселенной

Тесты

Хорошо ли вы разбираетесь в процессе веб-дизайна?

Насколько хорошо вы разбираетесь в алгоритмах?

Хорошо ли вы разбираетесь в структурах данных и алгоритмах?