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

Двойной связанный список представляет собой разновидность связанного списка, в котором навигация возможна обоими способами, как в прямом, так и в обратном направлении, по сравнению с одиночным связанным списком. Ниже приведены важные термины для понимания концепции двусвязного списка.

  • Ссылка - каждая ссылка в связанном списке может хранить данные, называемые элементом.

  • Далее - каждая ссылка в связанном списке содержит ссылку на следующую ссылку с именем Далее.

  • Пред. Каждая ссылка в связанном списке содержит ссылку на предыдущую ссылку под названием Пред.

  • LinkedList - связанный список содержит ссылку на соединение с первой ссылкой с именем First и последней ссылкой с именем Last.

Представление с двойными связями

Двусвязный список

Согласно приведенной выше иллюстрации, ниже приведены важные моменты, которые необходимо учитывать.

  • Вдвойне связанный список содержит элемент ссылки, который называется первым и последним.

  • Каждая ссылка содержит поле (и) данных и два поля ссылки, которые называются next и prev.

  • Каждая ссылка связана со своей следующей ссылкой, используя следующую ссылку.

  • Каждая ссылка связана со своей предыдущей ссылкой, используя свою предыдущую ссылку.

  • Последняя ссылка содержит null ссылку для обозначения конца списка.

Основные операции

Ниже приведены основные операции, поддерживаемые списком.

  • Вставка - добавляет элемент в начало списка.

  • Удаление - удаляет элемент в начале списка.

  • Вставить последний - добавляет элемент в конец списка.

  • Удалить последний - удаляет элемент из конца списка.

  • Вставить после - добавляет элемент после элемента списка.

  • Удалить - удаляет элемент из списка с помощью клавиши.

  • Показывать вперед - отображение полного списка в прямом направлении.

  • Отобразить назад - отображает полный список в обратном порядке.

Операция вставки

Следующий код демонстрирует операцию вставки в начале двусвязного списка.

пример

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
}

Операция удаления

Следующий код демонстрирует операцию удаления в начале двусвязного списка.

пример

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL ) {
      last = NULL ;
   } else {
      head->next->prev = NULL ;
   }
	
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

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

Следующий код демонстрирует операцию вставки в последнюю позицию двусвязного списка.

пример

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

Чтобы увидеть реализацию на языке программирования C, пожалуйста, нажмите здесь .