Jednotlivě propojený seznam v datových strukturách

Co je to samostatně propojený seznam?

Jednoduchě propojený seznam je lineární a jednosměrná datová struktura, kde jsou data uložena na uzlech a každý uzel je propojen odkazem s dalším uzlem. Každý uzel obsahuje datové pole a odkaz na další uzel. Jednoduchě propojené seznamy lze procházet pouze jedním směrem, zatímco Dvojitě propojený seznam lze projíždět v obou směrech.

Zde je struktura uzlů jednoducho propojeného seznamu:

Struktura uzlu v propojeném seznamu

Proč používat propojený seznam nad polem?

Několik scénářů upřednostňuje propojený seznam před Řada:

• Neznámý počet prvků: Pokud požadovaný počet prvků není v době kompilace znám, propojený seznam alokuje paměť dynamicky, jakmile se prvky přidávají.
• Náhodný přístup: Pokud není potřeba náhodný indexovaný přístup, je vhodnou volbou propojený seznam.
• Vložení uprostřed: Vkládání doprostřed pole vyžaduje posun prvků. Spojený seznam umožňuje vkládání na libovolnou pozici přepsáním pouze několika ukazatelů.

OperaJednotně propojený seznam

Jednoduchý propojený seznam je vhodný pro dynamickou alokaci paměti. Podporuje standardní operace propojeného seznamu, tj. vkládání, mazání, vyhledávání, aktualizaci, slučování dvou seznamů a procházení.

V tomto článku jsou popsány následující operace:

• Vkládání na hlavu
• Vkládání na ocas
• Vkládání za uzel
• Vkládání před uzel
• Odstraňte hlavní uzel
• Odstraňte ocasní uzel
• Vyhledejte a odstraňte uzel
• Procházení propojeného seznamu

Zde je příklad propojeného seznamu se čtyřmi uzly.

Příklad samostatně propojeného seznamu

Vložení na začátek jednoduše propojeného seznamu

Toto je jednoduchá operace. Obecně se nazývá vložení do jednoducho propojeného seznamu. Vytvoří se nový uzel a umístí se na začátek seznamu.

Pro provedení této operace je třeba dodržet dvě důležité podmínky:

1. Pokud je seznam prázdný, nově vytvořený uzel se stane hlavním uzlem a jeho další ukazatel je NULL.
2. Pokud seznam není prázdný, nový uzel se stane hlavním uzlem a jeho další ukazatel ukazuje na předchozí hlavní uzel.

Zde je pseudokód pro vložení uzlu na začátek propojeného seznamu:

function insertAtHead(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  else:
    newNode.next = head
    return newNode

Vkládání na hlavu

Vložení na konec jednoduše propojeného seznamu

Vložení uzlu na konec propojeného seznamu je podobné vložení na začátek. Přejděte k koncovému uzlu a poté ukažte jeho další ukazatel na nový uzel. Pokud je záhlaví NULL, stane se novým uzlem záhlaví.

Krok 1) Projděte až do další ukazatel aktuálního uzlu se stane NULL.

Krok 2) Vytvořte nový uzel se zadanou hodnotou.

Krok 3) Přiřaďte nový uzel jako další uzel koncového uzlu.

Pseudokód pro vkládání na konec seznamu s jedním prvkem:

function insertAtEnd(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  while head.next is not NULL:
    head = head.next
  head.next = newNode
  newNode.next = NULL

Vkládání na ocas

Vložení za uzel v jednopropojeném seznamu

Vkládání za uzel má dvě části: hledání cílového uzlu a připojení nového uzlu za něj. Procházení seznamu, dokud se nenajde shoda, a poté vložení nového uzlu.

Krok 1) Procházejte, dokud se hodnota aktuálního uzlu nerovná hledané položce.

Krok 2) Nastavte nový uzel další ukazatel na aktuální uzel další ukazatel.

Krok 3) Ukažte aktuální uzel další ukazatel na nový uzel.

Pseudokód:

function insertAfter(head, value, searchItem):
  newNode = Node(value)
  while head.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Vložení uzlu za uzel v Jednotně propojeném seznamu

Vložení před uzel v jednopropojeném seznamu

Toto je podobné vkládání za uzel. Procházejte, dokud se další uzel neshoduje s hledanou hodnotou, a poté vložte nový uzel před něj.

Krok 1) Procházejte, dokud se hodnota dalšího uzlu nerovná hledané položce.

Krok 2) Vytvořte nový uzel a nastavte jeho další ukazatel na aktuální uzel další.

Krok 3) Ukažte aktuální uzel další k novému uzlu.

function insertBefore(head, value, searchItem):
  newNode = Node(value)
  while head.next.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Vložení uzlu před uzel v Jednotně propojeném seznamu

Odstranění záhlaví jednoduše propojeného seznamu

Ukazatel na hlavičku je zadán jako parametr. Hlavní uzel je odstraněn a další uzel se stává novým hlavním uzlem. Paměť odstraněného uzlu musí být uvolněna, aby se zabránilo únikům paměti.

Krok 1) Přiřaďte další uzel hlavice jako novou hlavu.

Krok 2) Uvolněte alokovanou paměť předchozího hlavního uzlu.

Krok 3) Vraťte nový uzel hlavy.

function deleteHead(head):
  temp = head
  head = head.next
  free(temp)
  return head

Odstranění hlavičky propojeného seznamu

Odstranění konce jednoduše propojeného seznamu

Smazání koncového uzlu je podobné smazání úvodního uzlu. Rozdíl je v tom, že je vyžadován průchod na konec seznamu. V jednoducho propojeném seznamu je uzel, jehož další ukazatel je NULL, což je koncový uzel.

Krok 1) Projeďte trasou až těsně před koncový uzel. Uložte aktuální uzel.

Krok 2) Uvolněte paměť dalšího uzlu (ocasu).

Krok 3) Nastaví další uzel aktuálního uzlu na hodnotu NULL.

function deleteTail(head):
  while head.next.next is not NULL:
    head = head.next
  free(head.next)
  head.next = NULL

Odstranění konce seznamu Singly Linked List

Vyhledání a odstranění uzlu z jednoducho propojeného seznamu

Tato funkce provádí dva úkoly: vyhledávání a mazání. Prochází až do konce seznamu. Pokud je nalezen odpovídající uzel, odstraní ho a znovu propojí předchozí uzel. další ukazatel.

Krok 1) Projděte si seznam až do konce. Zkontrolujte, zda se aktuální uzel shoduje s hledaným uzlem.

Krok 2) Pokud je nalezena shoda, uložte ukazatel na aktuální uzel.

Krok 3) Jedno další předchozího uzlu se stane dalším uzlem aktuálního uzlu.

Krok 4) Smažte aktuální uzel a uvolněte jeho paměť.

function searchAndDelete(head, searchItem):
  while head.next.next is not NULL and head.next.value != searchItem:
    head = head.next
  temp = head.next
  head.next = head.next.next
  free(temp)

Vyhledejte a odstraňte uzel z Jednotně propojeného seznamu

Procházení jednoduše propojeného seznamu

Jednoducho propojený seznam podporuje procházení pouze od začátku do konce. Neexistuje žádný ukazatel na předchozí uzel, takže zpětné procházení není možné. Každý uzel je navštěvován postupně a jeho hodnota je vytištěna, dokud není dosaženo hodnoty NULL.

Krok 1) Procházejte každým uzlem, dokud nedosáhnete hodnoty NULL.

Krok 2) Vytiskněte hodnotu aktuálního uzlu.

function traverse(head):
  while head is not NULL:
    print head.value
    head = head.next

Příklad samostatně propojeného seznamu v C++

#include<iostream>
using namespace std;
struct Node{
  int data;
  struct Node *next;
};
void insertAtHead(Node* &head, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  if(head != NULL){
    newNode->next = head;
  }
  head = newNode;
  cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
  if(head == NULL){
    insertAtHead(head, value);
    return;
  }
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *temp = head;
  while(temp->next != NULL){
    temp = temp->next;
  }
  temp->next = newNode;
  cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
  Node *temp = NULL;
  if((*headPtr)->data == searchItem){
    temp = *headPtr;
    *headPtr = (*headPtr)->next;
    free(temp);
  } else {
    Node *currentNode = *headPtr;
    while(currentNode->next != NULL){
      if(currentNode->next->data == searchItem){
        temp = currentNode->next;
        currentNode->next = currentNode->next->next;
        free(temp);
        break;
      } else {
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
void insertAfter(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->next->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){
  Node* tempNode = headPointer;
  cout<<"Traversal from head:\t";
  while(tempNode != NULL){
    cout<<tempNode->data;
    if(tempNode->next)
      cout<<" --> ";
    tempNode = tempNode->next;
  }
  cout<<endl;
}
int main(){
  Node *head = NULL;
  insertAtHead(head, 5);
  insertAtHead(head, 6);
  insertAtHead(head, 7);
  insertEnd(head, 9);
  traverse(head);
  searchAndDelete(&head, 6);
  traverse(head);
  insertAfter(head, 7, 10);
  insertBefore(head, 9, 11);
  traverse(head);
}

Výstup

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

Příklad samostatně propojeného seznamu v Python

class Node:
  def __init__(self, data=None, next=None):
    self.data = data
    self.next = next
class SinglyLinkedList:
  def __init__(self):
    self.head = None
  def insertAtHead(self, value):
    newNode = Node(data=value)
    if self.head is not None:
      newNode.next = self.head
    self.head = newNode
    print(f'Added {newNode.data} at the front.')
  def insertAtEnd(self, value):
    if self.head is None:
      self.insertAtHead(value)
      return
    newNode = Node(value)
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    print(f'Added {newNode.data} at the end.')
  def searchAndDelete(self, searchItem):
    if self.head is None:
      return
    if self.head.data == searchItem:
      self.head = self.head.next
      print(f'Deleted node\t{searchItem}')
      return
    currentNode = self.head
    while currentNode.next is not None:
      if currentNode.next.data == searchItem:
        currentNode.next = currentNode.next.next
        print(f'Deleted node\t{searchItem}')
        return
      currentNode = currentNode.next
  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
    print(f'Inserted {value} after node\t{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
    print(f'Inserted {value} before node\t{searchItem}')
  def traverse(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
singlyLinkedList = SinglyLinkedList()
singlyLinkedList.insertAtHead(5)
singlyLinkedList.insertAtHead(6)
singlyLinkedList.insertAtHead(7)
singlyLinkedList.insertAtEnd(9)
singlyLinkedList.traverse()
singlyLinkedList.searchAndDelete(6)
singlyLinkedList.traverse()
singlyLinkedList.insertAfter(7, 10)
singlyLinkedList.insertBefore(9, 11)
singlyLinkedList.traverse()

Výstup

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

Složitost jednotlivě propojeného seznamu

Existují dva druhy složitosti: časová složitost a prostorová složitost. Časová složitost v nejhorším a průměrném případě je pro jednoduchou vazbu shodná.

Časová složitost v nejlepším případě:

• Vkládání na začátek seznamu lze provést za O(1). Není nutné procházet seznam.
• Vyhledávání a mazání lze provést za O(1), pokud se cílový prvek nachází v hlavním uzlu.

Průměrná časová složitost případu:

• Vložení dovnitř propojeného seznamu trvá O(n), kde n je celkový počet prvků.
• Vyhledávání a mazání mohou také trvat O(n), protože cílový prvek se může nacházet kdekoli až k koncovému uzlu.

Prostorová složitost jednoduše propojeného seznamu

Jednoduchý seznam dynamicky alokuje paměť. Pro uložení n prvky, alokuje n paměťových jednotek. Prostorová složitost je tedy O(n).

Aplikace jednoduše propojeného seznamu

Jednoducho propojené seznamy se objevují na mnoha místech, kde je užitečné procházení pouze vpřed a dynamická paměť:

• Zásobníky a fronty: Základní úložiště pro LIFO zásobníky a FIFO fronty vytvořené z uzlů.
• Řetězení hašovacích tabulek: Kolize se řeší zřetězením položek do jednoduše propojeného seznamu pro každý segment.
• Seznamy sousedství: Řídké grafy používají pro každý vrchol jednoduchou vazbu (single Linked List of Neighbors).
• Tabulky symbolů: Kompilátory a interprety řetězí identifikátory do jednopropojeného seznamu (Singly Linked List) pro každý obor platnosti.
• Alokátory paměti: Alokátory z volného seznamu track volných bloků jako jednoduše propojený seznam.

Nejčastější dotazy