Üksiklingitud loend andmestruktuurides

Mis on üksikult lingitud loend?

Üksikult lingitud loend (Singly Linked List) on lineaarne ja ühesuunaline andmestruktuur, kus andmed salvestatakse sõlmedesse ja iga sõlm on lingi kaudu ühendatud järgmise sõlmega. Iga sõlm sisaldab andmevälja ja linki järgmise sõlmega. Üksikult lingitud loendeid saab läbida ainult ühes suunas, samas kui Topeltlingitud loend läbida saab mõlemas suunas.

Siin on üksikult lingitud loendi sõlme struktuur:

Lingitud loendi sõlme struktuur

Miks kasutada lingitud loendit massiivi kohal?

Mitmed stsenaariumid eelistavad seotud loendit loendile Array:

• Tundmatu arv elemente: Kui nõutav elementide arv pole kompileerimise ajal teada, jaotab lingitud loend mälu dünaamiliselt elementide lisamisel.
• Juhuslik juurdepääs: Kui juhuslikku indekseeritud juurdepääsu pole vaja, on sobiv valik lingitud loend.
• Sisestamine keskele: Massiivi keskele lisamine nõuab elementide nihutamist. Lingitud loend (linked list) võimaldab elementide lisamist mis tahes positsioonile, kirjutades ümber vaid mõned pointerid.

Operaüksikult lingitud nimekirja

Üksikult lingitud loend sobib hästi mälu dünaamiliseks eraldamiseks. See toetab lingitud loendi standardtoiminguid, st lisamist, kustutamist, otsimist, uuendamist, kahe loendi ühendamist ja läbimist.

Selles artiklis käsitletakse järgmisi toiminguid:

• Sisestamine peas
• Sisestamine sabas
• Sisestamine pärast sõlme
• Sisestamine enne sõlme
• Kustutage peasõlm
• Kustutage saba sõlm
• Otsige ja kustutage sõlm
• Lingitud loendi läbimine

Siin on näide nelja sõlmega lingitud loendist.

Näide üksikult lingitud loendist

Lisamine üksikult lingitud loendi algusesse

See on lihtne toiming. Üldiselt tuntakse seda üksikult lingitud loendile (Singly Linked List) lisamisena. Luuakse uus sõlm ja asetatakse loendi algusesse.

Selle toimingu sooritamiseks järgige kahte olulist tingimust:

1. Kui loend on tühi, saab äsja loodud sõlmest peasõlm ja selle järgmine pointer on NULL.
2. Kui loend pole tühi, saab uuest sõlmest peasõlm ja selle järgmine pointer osutab eelmisele peasõlmele.

Siin on pseudokood sõlme lisamiseks lingitud loendi algusesse:

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

Sisestamine peas

Lisamine üksikult lingitud loendi lõppu

Lingitud loendi lõppu sõlme lisamine sarnaneb loendi algusesse lisamisega. Liikuge sabasõlmeni ja seejärel suunake selle järgmine kursor uuele sõlmele. Kui pea on NULL, saab uuest sõlmest pea.

Step 1) Liigu läbi kuni järgmine Praeguse sõlme pointer muutub NULL-iks.

Step 2) Looge määratud väärtusega uus sõlm.

Step 3) Määrake uus sõlm sabasõlme järgmiseks sõlmeks.

Pseudokood üksikute loendite lõppu lisamiseks:

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

Sisestamine saba juures

Lisamine pärast sõlme üksikult lingitud loendis

Sõlme järele lisamine koosneb kahest osast: sihtsõlme otsimine ja uue sõlme lisamine selle järele. Loendi läbimine kuni vaste leidmiseni ja uue sõlme lisamine.

Step 1) Liigutakse seni, kuni praeguse sõlme väärtus võrdub otsinguüksusega.

Step 2) Määrake uue sõlme järgmine osuti praeguse sõlme juurde järgmine osuti.

Step 3) Suuna praeguse sõlme järgmine pointer uuele sõlmele.

Pseudokood:

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

Sõlme lisamine sõlme järel üksikult lingitud loendisse

Lisamine enne sõlme üksikult lingitud loendis

See sarnaneb lisamisega pärast sõlme. Liigutakse seni, kuni järgmine sõlm vastab otsinguväärtusele, seejärel lisatakse uus sõlm enne seda.

Step 1) Liikuge seni, kuni järgmise sõlme väärtus võrdub otsinguüksusega.

Step 2) Loo uus sõlm ja määra selle järgmine osuti praeguse sõlme juurde järgmine.

Step 3) Suuna praeguse sõlme järgmine uue sõlme juurde.

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

Sõlme sisestamine üksikult lingitud loendis sõlme ette

Kustuta üksikult lingitud loendi pea

Parameetrina antakse päisviide. Peasõlm eemaldatakse ja järgmisest sõlmest saab uus peasõlm. Mälulekete vältimiseks tuleb kustutatud sõlme mälu vabastada.

Step 1) Määrake pea järgmine sõlm uueks peaks.

Step 2) Vabastage eelmise peasõlme eraldatud mälu.

Step 3) Tagasta uus peasõlm.

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

Lingitud loendi pea kustutamine

Kustuta üksikult lingitud loendi saba

Sabasõlme kustutamine sarnaneb peasõlme kustutamisega. Erinevus seisneb selles, et on vaja läbida loendi lõppu. Üksikult lingitud loendis on sõlm, mille järgmine pointer on NULL on sabasõlm.

Step 1) Liigu läbi kuni vahetult enne sabasõlme. Salvesta praegune sõlm.

Step 2) Vabastage järgmise sõlme (saba) mälu.

Step 3) Määra praeguse sõlme järgmise sõlme väärtuseks NULL.

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

Üksiklingitud loendi saba kustutamine

Sõlme otsimine ja kustutamine üksikult lingitud loendist

See funktsioon täidab kahte ülesannet: otsimine ja kustutamine. Liigub loendis lõpuni. Kui leitakse sobiv sõlm, eemaldab see ja lingib eelmise sõlme uuesti. järgmine osuti.

Step 1) Liigu nimekirja lõpuni. Kontrolli, kas praegune sõlm võrdub otsingusõlmega.

Step 2) Kui vaste leitakse, salvestatakse pointer praegusele sõlmele.

Step 3) . järgmine Eelmise sõlme sõlmest saab praeguse sõlme järgmine sõlm.

Step 4) Kustuta praegune sõlm ja vabasta selle mälu.

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)

Otsige ja kustutage sõlm üksikult lingitud loendist

Läbida üksikult lingitud loend

Üksikult lingitud loend toetab läbimist ainult algusest lõpuni. Eelmisele sõlmele puudub pointer, seega pole tagasiliikumine võimalik. Iga sõlme külastatakse kordamööda, prindides selle väärtuse kuni NULL-ini.

Step 1) Läbi iga sõlme, kuni jõutakse NULL-ini.

Step 2) Printige praeguse sõlme väärtus.

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

Üksiklingitud loendi näide 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äljund

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

Üksiklingitud loendi näide 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äljund

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

Üksiklingitud loendi keerukus

Keerukust on kahte tüüpi: ajaline keerukus ja ruumiline keerukus. Halvima ja keskmise juhtumi ajaline keerukus on üksikult lingitud loendi puhul sama.

Parima stsenaariumi ajaline keerukus:

• Loendi pähe lisamine on võimalik funktsioonis O(1). Loendi sees pole vaja läbida.
• Otsingut ja kustutamist saab teha O(1)-s, kui sihtelement asub peasõlmes.

Juhtumi keskmine ajaline keerukus:

• Lisamine lingitud loendisse võtab väärtuse O(n), kus n on elementide koguarv.
• Otsing ja kustutamine võivad samuti võtta O(n), sest sihtelement võib asuda ükskõik kus kuni sabasõlmeni.

Üksikult seotud loendi ruumi keerukus

Üksikult lingitud loend (Singly Linked List) eraldab mälu dünaamiliselt. Salvestamiseks n elemente, see eraldab n mäluühikuid. Seega on ruumi keerukus O(n).

Üksikult seotud loendi rakendused

Üksikult lingitud loendid esinevad paljudes kohtades, kus ainult edasiliikumine ja dünaamiline mälu on kasulikud:

• Pinud ja järjekorrad: Sõlmedest ehitatud LIFO-pinude ja FIFO-järjekordade alussalvestus.
• Räsitabeli aheldamine: Kokkupõrked lahendatakse kirjete aheldamise teel iga ämbri kohta üksikult lingitud loendisse.
• Kõrvalkohtade loendid: Hõredates graafides kasutatakse iga tipu jaoks üksikult lingitud naabrite loendit.
• Sümbolite tabelid: Kompilaatorid ja interpreteerijad aheldavad identifikaatorid ühekordselt lingitud loendiks iga ulatuse kohta.
• Mälu jaoturid: Vaba nimekirjaga jaoturid track vaba plokki üheselt lingitud loendina.

KKK