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

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

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

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

  • Ссылка. В каждой ссылке связного списка могут храниться данные, называемые элементом.
  • Следующая ссылка. В каждой ссылке связного списка содержится ссылка на следующую ссылку (Next).
  • Предыдущая ссылка. В каждой ссылке связного списка содержится ссылка на предыдущую ссылку (Prev).
  • Связный список содержит ссылку (связку) на первую ссылку (First) и на последнюю ссылку (Last).

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

Здесь надо учитывать следующие важные моменты:

  • Двусвязный (двунаправленный) список содержит элемент ссылок  —  first (первой) и last (последней).
  • Каждая ссылка имеет поле или поля данных и два поля ссылки  —  next (следующей) и prev (предыдущей).
  • Каждая ссылка связана со следующей посредством своей ссылки next.
  • Каждая ссылка связана с предыдущей посредством своей ссылки prev.
  • Последняя ссылка содержит ссылку со значением null, обозначающую конец списка.

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

Это основные операции, проводимые над списками:

  • Вставка, то есть добавление элемента в начало списка.
  • Удаление элемента из начала списка.
  • Вставка последним, то есть добавление элемента в конец списка.
  • Удаление последнего, то есть удаление элемента из конца списка.
  • Вставка после, то есть добавление элемента после какого-то элемента списка.
  • Удаление элемента из списка по заданному ключу.
  • Отображение вперед полного списка в прямом порядке.
  • Отображение назад полного списка в обратном порядке.

Вставка

В этом коде показана операция вставки в начало двусвязного (двунаправленного) списка:

Пример

//вставляем ссылку на первое место
void insertFirst(int key, int data) {

   //создаем ссылку
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //делаем ее последней ссылкой
      last = link;
   } else {
      //меняем первую предыдущую ссылку
      head->prev = link;
   }

   //указываем ей на прежнюю первую ссылку
   link->next = head;
	
   //указываем первой на новую первую ссылку
   head = link;
}

Удаление

В этом коде показана операция удаления в начале двусвязного (двунаправленного) списка:

Пример

//удаляем первый элемент
struct node* deleteFirst() {

   //сохраняем ссылку на первую ссылку
   struct node *tempLink = head;
	
   //если только одна ссылка
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //возвращаем удаленную ссылку
   return tempLink;
}


Вставка в конце операции


В этом коде показана операция вставки в последнее место двусвязного (двунаправленного) списка:


Пример


//вставляем ссылку в последнее место
void insertLast(int key, int data) {
   //создаем ссылку
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //делаем ее последней ссылкой
      last = link;
   } else {
      //делаем ссылку новой последней ссылкой
      last->next = link;     
      
      //обозначаем прежний последний узел как предыдущий для новой ссылки
      link->prev = last;
   }
   //указываем последней на новый последний узел
   last = link;
}


Реализация на языке программирования C:


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
   int data;
   int key;
	
   struct node *next;
   struct node *prev;
};

//Указатель показывает на начало списка
struct node *head = NULL;

//Указатель показывает на конец списка
struct node *last = NULL;

struct node *current = NULL;

//пуст ли список
bool isEmpty() {
   return head == NULL;
}

int length() {
   int length = 0;
   struct node *current;
	
   for(current = head; current != NULL; current = current->next){
      length++;
   }
	
   return length;
}

//показать список с первого элемента по последний
void displayForward() {

   //начать с начала списка
   struct node *ptr = head;
	
   //выводить пока не конец списка
   printf("\n[ ");
	
   while(ptr != NULL) {        
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
	
   printf(" ]");
}

//показать список с последнего по первый элемент
void displayBackward() {

   //начать с конца списка
   struct node *ptr = last;
	
   //выводить пока не начало списка
   printf("\n[ ");
	
   while(ptr != NULL) {    
	
      //вывести данные
      printf("(%d,%d) ",ptr->key,ptr->data);
		
      //перейти к следующему элементу
      ptr = ptr ->prev;
      
   }
	
}

//вставить элемент в начало списка
void insertFirst(int key, int data) {

   //создать элемент
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //поставить элемент в конец
      last = link;
   } else {
      //update first prev link обновить у первого элемента ссылку на предыдущий элемент
      head->prev = link;
   }

   //установить указатель на прошлый первый элемент
   link->next = head;
	
   //point first to new first link установить указатель списка первого элемента на новый первый элемент
   head = link;
}

//добавить элемент в конец списка
void insertLast(int key, int data) {

   //создать указатель на элемент
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //сделать последним элементом
      last = link;
   } else {
      //сделать элемент новым последним элементом
      last->next = link;     
      
      //установить указатель с нового элемента на прошлый последний элемент
      link->prev = last;
   }

   //сделать элемент последним в списке
   last = link;
}

//удалить первый элемент
struct node* deleteFirst() {

   //сохранить ссылку на первый элемент
   struct node *tempLink = head;
	
   //если один элемент
   if(head->next == NULL){
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
   //return the deleted link возвратить удаленный элемент
   return tempLink;
}

//удалить последний элемент 

struct node* deleteLast() {
   //сохранить ссылку на последний элемент
   struct node *tempLink = last;
	
   //если один элемент
   if(head->next == NULL) {
      head = NULL;
   } else {
      last->prev->next = NULL;
   }
	
   last = last->prev;
	
   //возвратить удаленный элемент
   return tempLink;
}

//удалить элемент с заданным ключом
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 {
      //установить у прошлого элемента ссылку на следующий от текущего
      current->prev->next = current->next;
   }    

   if(current == last) {
      //изменить указатель на последний элемент
      last = current->prev;
   } else {
      current->next->prev = current->prev;
   }
	
   return current;
}

bool insertAfter(int key, int newKey, int data) {
   //начать с первого элемента
   struct node *current = head; 
	
   //если лист пуст
   if(head == NULL) {
      return false;
   }

   //продвигаться по списку
   while(current->key != key) {
	
      //если это последний элемент
      if(current->next == NULL) {
         return false;
      } else {           
         //перейти к следующему
         current = current->next;
      }
   }
	
   //создать указатель на новый элемент
   struct node *newLink = (struct node*) malloc(sizeof(struct node));
   newLink->key = newKey;
   newLink->data = data;

   if(current == last) {
      newLink->next = NULL; 
      last = newLink; 
   } else {
      newLink->next = current->next;         
      current->next->prev = newLink;
   }
	
   newLink->prev = current; 
   current->next = newLink; 
   return true; 
}

void main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 

   printf("\nList (First to Last): ");  
   displayForward();
	
   printf("\n");
   printf("\nList (Last to first): "); 
   displayBackward();

   printf("\nList , after deleting first record: ");
   deleteFirst();        
   displayForward();

   printf("\nList , after deleting last record: ");  
   deleteLast();
   displayForward();

   printf("\nList , insert after key(4) : ");  
   insertAfter(4,7, 13);
   displayForward();

   printf("\nList  , after delete key(4) : ");  
   delete(4);
   displayForward();
}




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



Читайте нас в Telegram, VK и Яндекс.Дзен

 





 





 
Предыдущая статья7 бесплатных шаблонов React для разработки проектов
Следующая статьяЧетыре метода, которые повысят качество работы с Pandas