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

Co to jest lista podwójnie połączona?

Na podwójnie połączonej liście każdy węzeł ma łącza 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 dwa kolejne to wskaźniki następnego i poprzedniego węzła. Te dwa wskaźniki pomagają nam przejść do przodu lub do tyłu od określonego węzła.

Oto podstawowa struktura podwójnie połączonej listy.

Każda połączona lista ma węzeł główny i końcowy. Węzeł główny nie ma węzła „poprzedni” (poprzedni wskaźnik), a węzeł końcowy nie ma węzła „następny”.

Oto kilka ważnych terminów dotyczących listy podwójnie połączonej:

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 środku tego. Na przykład ciąg znaków, słownik, zestaw, mapa skrótów itp. mogą być przechowywane w „Danych”.

Oto podstawowa struktura pojedynczego węzła na podwójnie połączonej liście:

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

Operalisty podwójnie połączonej

Operacje na liście dwukierunkowo powiązanej obejmują dodawanie i usuwanie węzłów, wstawianie i usuwanie węzłów oraz przechodzenie przez listę od góry do dołu.

Oto lista operacji, które możemy wdrożyć przy użyciu listy 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

Zobaczymy implementację i pseudokod wszystkich powyższych operacji.

Wstawienie przed listą podwójnie powiązaną

Wstawienie z przodu oznacza, że musimy utworzyć węzeł na połączonej liście i umieścić go na początku połączonej listy.

Na przykład istnieje dany węzeł „15”. Musimy dodać to do węzła głównego.

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

Nowy węzeł będzie węzłem głównym, jeśli na liście podwójnie połączonej nie ma żadnego węzła.
Jeśli istnieje już węzeł główny, poprzedni węzeł zostanie 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 na końcu listy podwójnie połączonej

„Wstawienie na końcu” oznacza, że utworzymy węzeł na połączonej liście i umieścimy go na końcu.

Aby tego dokonać, możemy zastosować dwie metody:

Metoda 1: Rozpocznij przechodzenie od początku listy podwójnie połączonej, aż „następny” stanie się zerowy. Następnie połącz nowy węzeł z „następnym”.
Metoda 2: Weź ostatni węzeł listy podwójnie połączonej. Następnie „następny” węzeł ostatniego węzła zostanie połączony z nowym węzłem. Teraz nowy węzeł będzie węzłem końcowym.

Oto pseudokod do wstawienia w węźle końcowym:

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

Wstawienie na końcu listy połączonej — Wstawienie na końcu połączonej listy

Wstawienie po węźle

Załóżmy, że mamy istniejącą listę dwukierunkowo powiązaną, taką jak ta:

Chcemy wstawić dany węzeł, który będzie łączony po węźle, który ma wartość „12”.

Oto kroki, jak to zrobić:

Krok 1) Przejdź od głowy 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ępnym” węzłem nowego węzła będzie numer 15.

Oto pseudokod służący do wstawiania węzła po węźle na liście podwójnie połączonej:

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

Wstawienie przed węzłem

Ta operacja jest bardziej podobna do „wstawiania po węźle”. Musimy wyszukać wartość określonego węzła, aby to wykonać. Następnie utworzymy nowy węzeł i wstawimy go przed węzłem wyszukiwanym.

Powiedzmy, że chcemy wstawić dany węzeł „15” przed węzłem „12”. Oto kroki, jak to zrobić:

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”, czy nie.

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

Oto pseudokod służący do wstawiania węzła przed węzłem na podwójnie połączonej liście:

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

Usuń nagłówek podwójnie połączonej listy

Węzeł główny na podwójnie połączonej liście, który nie ma żadnego poprzedniego węzła. Zatem następnym wskaźnikiem będzie nowy węzeł główny, jeśli chcemy usunąć węzeł główny. Musimy także zwolnić pamięć zajmowaną przez węzeł podczas usuwania węzła.

Oto kroki usuwania 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 ustaw węzeł „poprzedni” (poprzedni wskaźnik) na „NULL”. Oznacza to, że odłączamy drugi węzeł od pierwszego węzła.

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

Oto pseudokod do usuwania głowy z podwójnie połączonej listy:

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

Konieczne jest usunięcie przydzielonej pamięci po wykonaniu jakiejkolwiek operacji usuwania. W przeciwnym razie podczas całego czasu działania programu pamięć dla usuniętego bloku pozostanie zajęta. Żadna inna aplikacja nie może użyć tego segmentu pamięci.

Usuń koniec podwójnie połączonej listy.

Ta operacja jest taka sama jak usuwanie głowy. Tutaj zamiast głowy musimy usunąć ogon. Aby zidentyfikować węzeł jako węzeł ogonowy, powinniśmy sprawdzić, czy następny wskaźnik lub następny węzeł jest nullem, czy nie. Po usunięciu ogona musimy zwolnić pamięć.

Operację tę nazywa się także „usuwaniem z tyłu”.

Oto kroki, jak to zrobić:

Krok 1) Przejdź do węzła końcowego listy podwójnie połączonej.

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

Krok 3) Ustaw „następny” węzeł na NULL i zwolnij pamięć węzła końcowego.

Oto pseudokod do usuwania węzła ogonowego:

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

Wyszukaj i usuń węzeł z listy podwójnie połączonej

Ta operacja pozwala nam wyszukać dane konkretnego węzła i usunąć ten węzeł. Musimy wykonać wyszukiwanie liniowe, ponieważ lista powiązana jest liniową strukturą danych. Po usunięciu musimy również zwolnić pamięć.

Oto kroki wyszukiwania i usuwania węzłów na liście dwukierunkowo powiązanej:

Krok 1) Przechodź połączoną listę od początku, aż wartość węzła będzie równa wyszukiwanemu elementowi.

Krok 2) Przypisz zmienną „deleteNode” do dopasowanego węzła.

Krok 3) Przypisz poprzedni węzeł „deleteNode” do następnego węzła.

Krok 4) Zwolnij pamięć „deleteNode”

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

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

Wyszukaj i usuń Operacja — Operacja wyszukiwania i usuwania

Przechodzenie przez podwójnie połączoną listę od przodu

Aby przejść od węzła głównego i iterować po następnym węźle, aż znajdziemy „NULL”. Przechodząc przez każdy węzeł możemy wydrukować wartość węzła. Oto kroki dotyczące przemieszczania się od przodu (kierunek do przodu):

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

Krok 2) Iteruj do następnego węzła głowy, aż otrzymasz „NULL”

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

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

Oto pseudokod umożliwiający przeglądanie listy podwójnie połączonej od początku:

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

Tutaj zwrot nie jest obowiązkowy. Ale dobrą praktyką jest zwrot węzła głównego po operacjach.

Przechodzenie przez podwójnie połączoną listę od tyłu

Ta operacja jest odwrotnością przejścia od przodu. Podejście jest takie samo, z niewielką różnicą. Musimy przejść do węzła końcowego, a następnie przejść od węzła końcowego do węzła przedniego.

Oto kroki, jak przejść od tyłu po podwójnie połączonej liście:

Krok 1) Trasuj aż dotrzemy do węzła ogonowego.

Krok 2) Od węzła końcowego będziemy przechodzić, aż otrzymamy poprzedni węzeł jako „NULL”. „Poprzedni” (poprzedni wskaźnik) będzie miał wartość zerową dla węzła głównego

Krok 3) Przy każdej iteracji będziemy drukować dane węzła.

Oto pseudokod przejścia od tyłu:

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

Różnica między listą pojedynczo i podwójnie połączoną

Główną różnicą pomiędzy listą Singly a listą Double Linked jest liczba linków.

Oto różnica między węzłami listy pojedynczo połączonej a strukturą węzłów listy podwójnie połączonej:

Pole	Lista pojedynczo połączona	Lista podwójnie połączona
Structure	Lista pojedynczo połączona ma jedno pole danych i jedno łącze do następnego węzła.	Lista podwójnie połączona ma jedno pole danych i dwa łącza. Jeden dla poprzedniego węzła i drugi dla następnego węzła.
Przemierzanie	Może przemieszczać się jedynie od głowy do ogona.	Może poruszać się zarówno do przodu, jak i do tyłu.
Pamięć	Zajmuje mniej pamięci.	Zajmuje więcej pamięci niż pojedynczo połączona lista.
dostępność	Listy pojedynczo połączone są mniej wydajne, ponieważ wykorzystują tylko jedno łącze do następnego węzła. Brak łącza do poprzedniego węzła.	Listy podwójnie połączone są bardziej wydajne niż listy pojedynczo połączone.

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

#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);
  }
  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 = new 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 = new node();
  head = listHead;	
  cout<<"Traversal from head:\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 = new node();
  head = (*listHead);
  while(head->next!=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;
  return;
  }
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
Aded 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 head:    10      9       11      5       20      6       7
Deleted Node    7
Traversal from head:    6        20      5       11      9       10
Traversal from head:    10      9       11      5       20      6

Podwójnie połączona lista w Python

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.insertFront(val)
    
    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:
      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 is not 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 is not 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.next is not None and temp.data is not searchItem:
      temp = temp.next
    
    if self.head is None or temp is None:
      return

    if self.head.data is 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))
    return

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

Ogólnie rzecz biorąc, złożoność czasową dzieli się na trzy typy.

Są to:

Najlepsza sprawa
Średnia sprawa
Najgorszy przypadek

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

Wstawienie do head lub tail będzie kosztować O(1). Ponieważ nie musimy przechodzić wewnątrz listy powiązanej. Wskaźnik head i tail może dać nam dostęp do węzła head i tail ze złożonością czasową O(1).
Usunięcie na początku lub na końcu będzie kosztować O(1).
Przeszukanie węzła będzie miało złożoność czasową O(1). Ponieważ węzeł docelowy może być węzłem głównym.

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

Umieszczenie na początku lub na końcu będzie miało złożoność czasową wynoszącą koszt O(1).
Usunięcie początku lub końca będzie miało złożoność czasową rzędu kosztu O(1).
Przeszukiwanie węzła będzie miało złożoność czasową O(n). Ponieważ element wyszukiwania może znajdować się w dowolnym miejscu listy powiązanej. Tutaj „n” to całkowita liczba węzłów obecnych na liście powiązanej.

W najgorszym przypadku złożoność czasowa listy dwukierunkowo powiązanej będzie 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 musimy zwolnić pamięć, której użyliśmy. W przeciwnym razie, w przypadku większej listy powiązanej, spowoduje to wycieki pamięci.

Podsumowanie

Lista połączona jest rodzajem liniowej struktury danych, zbiorem danych reprezentowanych w sposób liniowy.
Lista podwójnie połączona to rodzaj listy połączonej, w której węzeł ma połączenia zarówno z poprzednim, jak i następnym węzłem.
Lista dwukierunkowo powiązana zawiera wszystkie operacje, takie jak dodawanie węzła, usuwanie węzła, wstawianie węzła po lub przed innym węzłem oraz przeglądanie listy od początku do końca.
Lista podwójnie połączona ma jedno pole danych i dwa łącza. Jeden dla poprzedniego węzła i drugi dla następnego węzła.
Złożoność listy dwustronnie powiązanej Najlepszy przypadek, przeciętny przypadek
I najgorszy przypadek.

Możesz lubić:

Co to jest lista podwójnie połączona?

Operalisty podwójnie połączonej

Wstawienie przed listą podwójnie powiązaną

Wstawienie na końcu listy podwójnie połączonej

POWIĄZANE ARTYKUŁY

Wstawienie po węźle

Wstawienie przed węzłem

Usuń nagłówek podwójnie połączonej listy

Usuń koniec podwójnie połączonej listy.

Wyszukaj i usuń węzeł z listy podwójnie połączonej

Przechodzenie przez podwójnie połączoną listę od przodu

Przechodzenie przez podwójnie połączoną listę od tyłu

Różnica między listą pojedynczo i podwójnie połączoną

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

Wydajność

Podwójnie połączona lista w Python

Wydajność

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

Podsumowanie