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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

пример

//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, пожалуйста, нажмите здесь .