Lista podwójnie połączona: C++, Python (Code Przykład)

Czym jest lista dwukierunkowo powiązana?

W liście dwukierunkowej każdy węzeł ma linki zarówno do poprzedniego, jak i następnego węzła. Każdy węzeł składa się z trzech elementów: jeden przechowuje dane, a pozostałe dwa to wskaźniki do następnego i poprzedniego węzła. Te dwa wskaźniki pomagają poruszać się do przodu lub do tyłu od danego węzła.

Oto podstawowa struktura listy dwukierunkowej.

Struktura listy podwójnie połączonej

Każda lista powiązana ma węzeł główny i węzeł końcowy. Węzeł główny nie ma prev (poprzedni wskaźnik) węzeł, a węzeł ogonowy nie ma Następny węzeł.

Oto kilka ważnych terminów dotyczących listy dwukierunkowo powiązanej:

• Poprzednia: Każdy węzeł jest połączony z poprzednim węzłem. Służy jako wskaźnik lub łącze.
• Dalej: Każdy węzeł jest połączony z następnym węzłem. Służy jako wskaźnik lub łącze.
• Data: Służy do przechowywania danych w węźle. Dane mogą zawierać inne Struktury danych W polu danych można przechowywać na przykład ciągi znaków, słowniki, zestawy, mapy skrótów i inne struktury.

Oto podstawowa struktura pojedynczego węzła na liście dwukierunkowo powiązanej:

Struktura węzła na liście podwójnie połączonej

Operalisty podwójnie połączonej

Operacje na liście dwukierunkowo powiązanej obejmują dodawanie, usuwanie, wstawianie i usuwanie węzłów, a także przechodzenie listy z góry na dół lub z dołu do góry.

Oto lista operacji, które można wdrożyć na liście dwukierunkowo powiązanej:

• Wstawka z przodu
• Wstawienie w ogon lub ostatni węzeł
• Wstawienie po węźle
• Wstawienie przed węzłem
• Usunięcie z przodu
• Usunięcie z ogona
• Wyszukaj i usuń węzeł
• Przejdź od głowy do ogona
• Przejdź ogonem do głowy

Poniżej przedstawiono implementację i pseudokod dla każdej z tych operacji.

Wstawianie na początku listy dwukierunkowo powiązanej

Wstawienie na początku oznacza utworzenie węzła na liście powiązanej i umieszczenie go na początku listy.

Na przykład istnieje dany węzeł 15Należy go dodać jako węzeł główny.

Podczas wykonywania tej operacji należy spełnić dwa ważne warunki:

1. Nowy węzeł staje się węzłem głównym, jeśli lista podwójnie powiązana jest pusta.
2. Jeżeli istnieje już węzeł główny, poprzedni węzeł zostaje zastąpiony nowym węzłem.

Oto pseudokod dla tej operacji:

function insertAtFront(ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = newNode
  newNode.next = ListHead
  newNode.prev = NULL
  return ListHead

Wstawienie w węźle przednim

Wstawianie na końcu listy dwukierunkowo powiązanej

Wstawienie na końcu oznacza utworzenie węzła na liście powiązanej i umieszczenie go na końcu.

Istnieją dwie metody wykonania tej operacji:

• Metoda 1: Rozpocznij przeglądanie od początku listy dwukierunkowo powiązanej, aż do Następny staje się nullem. Następnie połącz nowy węzeł z Następny wskaźnik.
• Metoda 2: Weź ostatni węzeł listy dwukierunkowej. Następnie Następny Wskaźnik ostatniego węzła wskazuje na nowy węzeł. Nowy węzeł staje się węzłem końcowym.

Oto pseudokod do wstawienia w węźle ogonowym:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Wstawienie na końcu połączonej listy

Wstawienie po węźle

Rozważmy istniejącą listę dwukierunkowo powiązaną, taką jak poniżej:

Celem jest wstawienie danego węzła, który będzie połączony po węźle z wartością 12.

Krok 1) Przejdź od nagłówka do ostatniego węzła. Sprawdź, który węzeł ma wartość 12.

Krok 2) Utwórz nowy węzeł i przypisz go jako kolejny wskaźnik węzła 12, Następny węzeł nowego węzła będzie wynosił 15.

Oto pseudokod umożliwiający wstawienie węzła po węźle na liście dwukierunkowo powiązanej:

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Wstawienie po węźle

Wstawianie przed węzłem

Ta operacja jest podobna do wstawiania za węzłem. Wyszukiwana jest konkretna wartość węzła, a następnie tworzony jest nowy węzeł i wstawiany przed węzłem szukanym.

Aby wstawić dany węzeł 15 przed węzłem 12, wykonaj następujące kroki:

Krok 1) Przejdź przez połączoną listę od węzła głównego do węzła końcowego.

Krok 2) Sprawdź, czy następny wskaźnik bieżącego węzła ma wartość 12.

Krok 3) Wstaw nowy węzeł jako Następny węzeł bieżącego węzła.

Oto pseudokod umożliwiający wstawienie węzła przed węzłem w liście dwukierunkowo powiązanej:

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.next.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Wstawianie węzła przed węzłem

Usuń nagłówek listy dwukierunkowo powiązanej

Węzeł główny na liście dwukierunkowej nie ma żadnego poprzedniego węzła. Dlatego Następny Wskaźnik staje się nowym węzłem głównym po usunięciu bieżącego węzła. Wymagane jest również zwolnienie pamięci zajmowanej przez usunięty węzeł.

Oto kroki umożliwiające usunięcie węzła głównego:

Krok 1) Przypisz zmienną do bieżącego węzła głównego.

Krok 2) Odwiedź Następny węzeł bieżącego węzła głównego i wykonaj prev wskaźnik NULL. Spowoduje to odłączenie drugiego węzła od pierwszego.

Krok 3) Zwolnij pamięć zajmowaną przez poprzedni węzeł główny.

Oto pseudokod służący do usuwania nagłówka z listy dwukierunkowo powiązanej:

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

Usuwanie węzła głównego

Wymagane jest zwolnienie przydzielonej pamięci po każdym usunięciu. W przeciwnym razie pamięć dla usuniętego bloku pozostanie zajęta przez cały czas działania programu i żadna inna aplikacja nie będzie mogła wykorzystać tego segmentu pamięci.

Usuń ogon listy dwukierunkowo powiązanej

Operacja ta jest podobna do usuwania głowy. Zamiast głowy usuwany jest ogon. Aby zidentyfikować węzeł jako ogon, należy sprawdzić, czy kolejny wskaźnik jest pusty. Po usunięciu ogona należy zwolnić pamięć.

Operację tę nazywa się również usunięcie z tyłu.

Oto kroki, aby to zrobić:

Krok 1) Przechodź aż do węzła końcowego listy dwukierunkowo powiązanej.

Krok 2) Przypisz zmienną lub wskaźnik do węzła końcowego.

Krok 3) Ustaw Następny wskaźnik do NULL i zwolnij pamięć węzła ogonowego.

Oto pseudokod służący do usuwania węzła ogonowego:

function deleteTail(ListHead):
  head = ListHead
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  Tail = ListHead
  ListHead.prev.next = NULL
  free memory(Tail)
  return head

Wyszukiwanie i usuwanie węzła z listy dwukierunkowo powiązanej

Ta operacja wyszukuje określoną wartość węzła i usuwa ten węzeł. Wymagane jest wyszukiwanie liniowe, ponieważ lista powiązana jest liniową strukturą danych. Po usunięciu należy zwolnić pamięć.

Oto kroki umożliwiające wyszukanie i usunięcie węzła na liście dwukierunkowo powiązanej:

Krok 1) Przejrzyj listę powiązaną od nagłówka do momentu, aż wartość węzła będzie równa szukanemu elementowi.

Krok 2) Przypisz zmienną usuńwęzeł do dopasowanego węzła.

Krok 3) Połącz poprzedni węzeł usuńwęzeł do następnego węzła i ustaw następny węzeł prev wskaźnik do poprzedniego węzła.

Krok 4) Uwolnij pamięć usuńwęzeł.

Oto pseudokod umożliwiający wyszukiwanie i usuwanie węzłów z listy powiązanej:

function searchAndDelete(ListHead, searchItem):
  head = ListHead
  while head.value not equals searchItem:
    head = head.next
  deleteNode = head
  head.prev.next = head.next
  if head.next is not NULL:
    head.next.prev = head.prev
  free memory(deleteNode)
  return ListHead

Operacja wyszukiwania i usuwania

Przechodzenie listy dwukierunkowo powiązanej od przodu

Przejście od węzła głównego iteruje po kolejnym węźle, aż do znalezienia wartości NULL. Podczas przechodzenia każdego węzła można wyświetlić wartość. Oto kroki przejścia w kierunku do przodu:

Krok 1) Przypisz wskaźnik lub zmienną do bieżącego węzła głównego.

Krok 2) Przechodź do następnego węzła nagłówka, aż otrzymasz NULL.

Krok 3) Wyświetlaj dane węzła w każdej iteracji.

Krok 4) Zwróć węzeł główny.

Oto pseudokod umożliwiający przeglądanie listy dwukierunkowo powiązanej od przodu:

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals NULL:
    print head.data
    head = head.next
  return ListHead

Zwrot nie jest obowiązkowy. Jednak zwrócenie węzła głównego po operacjach jest dobrą praktyką.

Przechodzenie listy dwukierunkowo powiązanej od tyłu

Ta operacja jest odwrotnością przejścia od przodu. Podejście jest takie samo, z jedną małą różnicą: najpierw dotrzyj do węzła końcowego, a następnie idź tyłem do początku, używając prev wskaźnik.

Oto kroki umożliwiające przejście listy dwukierunkowo powiązanej od tyłu:

Krok 1) Kontynuuj, aż dotrzesz do węzła ogonowego.

Krok 2) Z węzła ogonowego przejdź za pomocą prev dopóki poprzedni węzeł nie będzie NULL. prev wskaźnik dla węzła głównego jest pusty.

Krok 3) Przy każdej iteracji drukuj dane węzła.

Oto pseudokod umożliwiający przejście od tyłu:

function traverseFromBack(ListHead):
  head = ListHead
  while head.next is not NULL:
    head = head.next
  tail = head
  while tail is not NULL:
    print tail.value
    tail = tail.prev
  return ListHead

Różnica między listą pojedynczo i podwójnie powiązaną

Główną różnicą pomiędzy listą pojedynczo powiązaną a listą dwustronnie powiązaną jest liczba połączeń, jakie posiada każdy węzeł.

Oto różnica pomiędzy węzłami listy jednokierunkowo powiązanej i listy dwukierunkowo powiązanej:

Podwójnie połączona lista w C++

Poniżej znajduje się kompletny C++ implementacja listy dwukierunkowo powiązanej z operacjami wstawiania, usuwania, wyszukiwania i przechodzenia.

#include<iostream>
using namespace std;
struct node{
  int data;
  struct node *next;
  struct node *prev;
};
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead != NULL){
    listHead->prev = newNode;
    newNode->next = listHead;
  }
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
}
void insertEnd(node* &listHead, int value){
  if(listHead == NULL){
    insertFront(listHead, value);
    return;
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL){
    head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
}
void insertAfter(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
}
void insertBefore(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->next->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;
}
void traverseFromFront(node *listHead){
  node* head = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\t";
  while(head->next != NULL){
    head = head->next;
  }
  node *tail = head;
  while(tail != NULL){
    cout<<tail->data<<"\t";
    tail = tail->prev;
  }
  cout<<endl;
}
void searchAndDelete(node **listHead, int searchItem){
  node* head = (*listHead);
  while(head != NULL && head->data != searchItem){
    head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
    *listHead = head->next;
  }
  if(head->next != NULL){
    head->next->prev = head->prev;
  }
  if(head->prev != NULL){
    head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
int main(){
  node *head = NULL;
  insertFront(head, 5);
  insertFront(head, 6);
  insertFront(head, 7);
  insertEnd(head, 9);
  insertEnd(head, 10);
  insertAfter(head, 5, 11);
  insertBefore(head, 5, 20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head, 7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

Wydajność

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7  6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

Podwójnie połączona lista w Python

Poniżej znajduje się kompletny Python implementacja listy dwukierunkowo powiązanej przy użyciu klas dla węzłów i samej listy.

class Node:
  def __init__(self, data=None, prev=None, next=None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None
  def insertFront(self, val):
    newNode = Node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))
  def insertEnd(self, val):
    newNode = Node(data=val)
    if self.head is None:
      self.head = newNode
      print("Added {} at the end".format(val))
      return
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))
  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp is not None:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from tail:\t", end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data), end="")
      tail = tail.prev
    print()
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value, searchItem))
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value, searchItem))
  def searchAndDelete(self, searchItem):
    temp = self.head
    while temp is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == temp.data:
      self.head = temp.next
    if temp.next is not None:
      temp.next.prev = temp.prev
    if temp.prev is not None:
      temp.prev.next = temp.next
    print("Deleted Node\t{}".format(searchItem))
doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

Wydajność

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7  6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6  7
Deleted Node    7
Traversing from head:   6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6

Złożoność listy dwukierunkowo powiązanej

Złożoność czasową dzieli się generalnie na trzy typy: najlepszy przypadek, przypadek średni i przypadek najgorszy.

Złożoność czasowa w najlepszym przypadku dla listy dwukierunkowo powiązanej:

1. Wstawienie na początku lub na końcu listy wiąże się z kosztem O(1), ponieważ nie jest wymagane przechodzenie przez nią. Wskaźniki na początek i koniec listy umożliwiają bezpośredni dostęp do węzłów na początku i na końcu listy.
2. Usunięcie początku lub końca kosztuje O(1).
3. Przeszukanie węzła kosztuje O(1), gdy węzeł docelowy jest węzłem głównym.

Złożoność czasowa w przeciętnym przypadku dla listy dwukierunkowo powiązanej:

1. Wstawienie za głowę lub ogon kosztuje O(1).
2. Usunięcie początku lub końca kosztuje O(1).
3. Przeszukanie węzła kosztuje O(n), ponieważ cel może znajdować się w dowolnym miejscu listy. W tym przypadku n jest całkowitą liczbą węzłów.

W najgorszym przypadku złożoność czasowa listy dwukierunkowej jest taka sama, jak w przypadku przeciętnym.

Złożoność pamięci listy dwukierunkowo powiązanej

Złożoność pamięci wynosi O(n), gdzie n to całkowita liczba węzłów. Podczas implementacji listy powiązanej pamięć musi zostać zwolniona. W przeciwnym razie większe listy powiązane powodują wycieki pamięci.

Zastosowania listy dwukierunkowo powiązanej

Listy dwukierunkowo powiązane są wykorzystywane w wielu rzeczywistych strukturach danych, ponieważ dwukierunkowe przechodzenie między nimi upraszcza wiele typowych operacji.

• Pamięć podręczna LRU: Pamięci podręczne używane najrzadziej korzystają z listy dwukierunkowo powiązanej z mapą skrótów umożliwiającą przenoszenie na wierzch i usuwanie z szybkością O(1).
• Historia przeglądarki: Nawigacja wstecz i dalej pozwala przeglądać listę w obu kierunkach.
• Cofanie i ponawianie stosów: Edytory i środowiska IDE track wersji dokumentu ze wskaźnikami prev i next.
• Deque: Doublekolejki zakończone są push i pop z obu końców w czasie O(1).
• Listy odtwarzania muzyki: Poprzedni i następny tracPrzyciski k działają na zasadzie strzałek do przodu i do tyłu.

FAQ