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

Co je to samostatně propojený seznam?

Singly Linked List je lineární a jednosměrná datová struktura, kde jsou data uložena na uzlech a každý uzel je připojen prostřednictvím odkazu na svůj další uzel. Každý uzel obsahuje datové pole a odkaz na další uzel. Jednotlivě propojené seznamy lze procházet pouze jedním směrem, zatímco Dvojitě propojené seznamy lze procházet oběma směry.

Zde je struktura uzlů Jednotlivě propojeného seznamu:

Proč používat propojený seznam přes pole?

Existuje několik případů, kdy je lepší použít Linked List spíše než Řada. Zde je několik scénářů:

• Neznámý počet prvků: Když nevíte, kolik prvků musíte uložit během běhu programu, můžete použít Propojený seznam. Paměť je přidělována dynamicky při přidávání prvků do propojených seznamů.
• Náhodný přístup: Ve scénáři, kde nepotřebujete používat náhodný přístup z prvků, můžete použít Propojený seznam.
• Vložení uprostřed: Vkládání doprostřed pole je složitý úkol. Protože je potřeba posouvat další prvky doprava. Propojený seznam vám však umožňuje přidat prvek na libovolné místo.

OperaJednotně propojený seznam

Singly Linked List je dobrý pro dynamické přidělování paměti. Poskytuje všechny základní operace propojeného seznamu, tj. vkládání, mazání, vyhledávání, aktualizaci, slučování dvou propojených seznamů, procházení atd.

Zde probereme následující operace propojeného seznamu:

• 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.

Vložení na začátek Jednotlivě propojeného seznamu

Jedná se o jednoduchou operaci. Obecně je to známé jako posouvání jednotlivě propojeného seznamu. Musíte vytvořit nový uzel a umístit jej na začátek propojeného seznamu.

K provedení této operace musíme splnit dvě důležité podmínky. Jsou

1. Pokud je seznam prázdný, pak nově vytvořený uzel bude hlavní uzel a další uzel hlavy bude „NULL“.
2. Pokud seznam není prázdný, nový uzel bude hlavní uzel a další bude ukazovat 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

Vložení na konec Jednotlivě propojeného seznamu

Vložení uzlu na konec propojeného seznamu má určité podobnosti s vkládáním do hlavy. Vše, co musíte udělat, je přejít do koncového nebo koncového uzlu. Potom nasměrujte „další“ uzel koncového uzlu na nově vytvořený uzel. Pokud je hlavní uzel null, nový uzel bude hlavním uzlem.

Zde jsou kroky:

Krok 1) Procházejte, dokud se „další“ uzel aktuálního uzlu nestane nulovým.

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 vložení uzlu na konec jednotlivého seznamu:

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

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

Vkládání za uzel má dvě části: Vyhledejte uzel a připojte za vyhledaný uzel. Musíme projít všechny uzly. Pro každý uzel se musíme shodovat s vyhledávacím prvkem. Pokud existuje shoda, přidáme nový uzel za hledaný uzel.

Zde jsou kroky:

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

Krok 2) Další ukazatel nového uzlu bude dalším ukazatelem aktuálního uzlu.

Krok 3) Další uzel aktuálního uzlu bude nový uzel.

Zde je pseudokód pro vložení uzlu za uzel:

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

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

Tato funkce je velmi podobná vkládání za uzel. Musíme vytvořit nový uzel a procházet propojený seznam, dokud aktuální uzel neodpovídá vyhledávacímu uzlu. Poté přidáme nový uzel jako předchozí uzel aktuálního uzlu.

Zde jsou kroky:

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

Krok 2) Vytvořte nový uzel a přiřaďte „další“ uzlu dalšímu dalšímu uzlu aktuálního uzlu.

Krok 3) Přiřaďte nový uzel jako další uzel aktuálního uzlu.

Zde je pseudokód:

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

Odstraňte hlavičku samostatně propojeného seznamu

V každé funkci propojeného seznamu je jako parametr poskytnut ukazatel záhlaví. Musíte odstranit hlavní uzel a vytvořit další uzel hlavního uzlu jako nový hlavní uzel propojeného seznamu. Musíme také uvolnit paměť odstraněného uzlu. Jinak bude paměť označena jako obsazená, když se k ní jiný program pokusí přistupovat.

Zde jsou kroky pro odstranění hlavy jednotlivě propojeného seznamu:

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

Krok 2) Uvolněte přidělenou paměť předchozím hlavním uzlem.

Krok 3) Vraťte nový uzel hlavy.

Pseudokód pro smazání hlavního uzlu:

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

Odstraňte konec samostatně propojeného seznamu

Odstranění koncového uzlu je známější s odstraněním hlavového uzlu. Rozdíl je v tom, že musíme přejít na konec propojeného seznamu a odstranit jej. V jednoduše propojeném seznamu je koncovým uzlem uzel s dalším uzlem jako „NULL“.

Zde jsou kroky pro odstranění koncového uzlu propojeného seznamu:

Krok 1) Traverz před ocasním uzlem. Uložte aktuální uzel.

Krok 2) Uvolněte paměť dalšího uzlu aktuálního uzlu.

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

Zde je pseudokód pro smazání koncového uzlu:

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

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

Tato funkce má dva úkoly, vyhledávání a mazání. Musíme hledat až do konce jednotlivě propojených seznamů. Pokud najdeme podobný uzel, smažeme jej. Poté musíme sloučit nebo propojit levý a pravý uzel odstraněného uzlu. Zde jsou kroky, jak to provést:

Krok 1) Procházet až na konec propojeného seznamu. Zkontrolujte, zda se aktuální uzel rovná vyhledávacímu uzlu nebo ne.

Krok 2) Pokud některý uzel odpovídá, uložte ukazatel na uzel na aktuální uzel.

Krok 3) „Další“ předchozího uzlu bude dalším uzlem aktuálního uzlu.

Krok 4) Vymažte a uvolněte paměť aktuálního uzlu.

Pseudokód pro vyhledávání a odstranění uzlu z jednotlivě propojeného seznamu:

function searchAndDelete( head, searchItem ):
	while head.next.next is not NULL  and head.next.value is not equals searchItem :
		head = head.next
	head.next = head.next.next
	delete(head.next)

Procházet jednotlivě propojený seznam

Jednotlivě propojený seznam má pouze funkci pro procházení od hlavy k patě. Neexistují žádné body ukazatele na předchozí uzel; proto nemůžeme procházet jednotlivě propojený seznam v opačném pořadí. Budeme procházet každým uzlem a tisknout hodnotu aktuálního uzlu, dokud nedostaneme hodnotu null.

Zde jsou kroky:

Krok 1) Procházejte každý uzel, dokud nedostaneme hodnotu null jako další uzel.

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

Pseudokód pro procházení jednoduše propojeného seznamu:

function traverse( head ):
		while head.next is not NULL:
			print the value of the head
			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);
  }
  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 = new Node();
  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);
      }else{
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
}
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 = new 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 Program

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.')
    return  
  def insertAtEnd(self,value):
    if self.head is None:
      self.insertAtHead(value)
    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):
    temp = Node()
    if self.head is searchItem:
      temp = self.head
      self.head = self.head.next
    else:
      currentNode = self.head
      while currentNode.next is not None:
        if currentNode.next.data is searchItem:
          temp = currentNode.next
          currentNode.next = currentNode.next.next
        else:
          currentNode = currentNode.next
    print(f'Deleted node\t{searchItem}')
    return
  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
    print(f'Inserted {value} after node\t{searchItem}')
    return 
  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
    print(f'Inserted {value} before node\t{searchItem}')
    return
  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. Nejhorší a průměrná časová složitost případu je stejná pro Singly Linked List.

Časová náročnost pro lepší případ:

• Vložení do hlavy lze provést v O(1). Protože nepotřebujeme procházet uvnitř propojeného seznamu.
• Operaci vyhledávání a mazání lze provést v O(1), pokud je vyhledávací prvek přítomen v hlavním uzlu.

Časová složitost pro průměrný případ:

• Vložení do propojeného seznamu bude trvat O(n), pokud je v seznamu jednotlivě propojeno prvků „n“.
• Hledání a mazání může trvat také O(n), protože vyhledávací prvek může být přítomen v koncovém uzlu. V takovém případě byste měli projít celý seznam.

Prostorová složitost jednotlivě propojeného seznamu

Singly Linked List dynamicky přiděluje paměť. Pokud chceme uložit n prvků, alokuje n paměťových jednotek. Prostorová složitost je tedy O(n).