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

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

Link - Каждая ссылка связанного списка может хранить данные, называемые элементом.
Next - Каждая ссылка связанного списка содержит ссылку на следующую ссылку под названием «Далее».
Prev - Каждая ссылка связанного списка содержит ссылку на предыдущую ссылку под названием Prev.
LinkedList - Связанный список содержит ссылку для подключения к первой ссылке с именем «Первая» и к последней ссылке с именем «Последняя».

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

В соответствии с приведенной выше иллюстрацией следует учитывать следующие важные моменты.

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

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

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

Insertion - Добавляет элемент в начало списка.
Deletion - Удаляет элемент в начале списка.
Insert Last - Добавляет элемент в конец списка.
Delete Last - Удаляет элемент из конца списка.
Insert After - Добавляет элемент после элемента списка.
Delete - Удаляет элемент из списка с помощью клавиши.
Display forward - Отображает полный список в прямом порядке.
Display backward - Отображает полный список в обратном порядке.

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

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

пример

//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, щелкните здесь .