Egyedül linkelt lista az adatstruktúrákban

Mi az az egyedileg linkelt lista?

Az egyszeresen láncolt lista egy lineáris és egyirányú adatstruktúra, ahol az adatok a csomópontokon tárolódnak, és minden csomópont egy linken keresztül kapcsolódik a következő csomóponthoz. Minden csomópont tartalmaz egy adatmezőt és egy linket a következő csomóponthoz. Az egyszeresen láncolt listák csak egy irányban haladhatnak be, míg egy Duplán linkelt lista mindkét irányban átjárható.

Íme egy egyszeresen láncolt lista csomópont-struktúrája:

Csomópont szerkezete egy linkelt listában

Miért használjunk láncolt listát tömb felett?

Számos forgatókönyv a láncolt listát részesíti előnyben a Sor:

• Ismeretlen számú elem: Amikor a szükséges elemszám nem ismert fordítási időben, a láncolt lista dinamikusan osztja ki a memóriát az elemek hozzáadásával.
• Véletlenszerű hozzáférés: Amikor nincs szükség véletlenszerű indexelt hozzáférésre, a láncolt lista a megfelelő választás.
• Beillesztés középen: Egy tömb közepére történő beszúrás elemek eltolását igényli. Egy láncolt lista lehetővé teszi a beszúrást bármely pozícióba, mindössze néhány mutató átírásával.

Operaaz egyedileg összekapcsolt lista

Az egyszeresen láncolt lista alkalmas a memória dinamikus lefoglalására. Támogatja a láncolt lista standard műveleteit, azaz a beszúrást, törlést, keresést, frissítést, két lista egyesítését és bejárását.

A következő műveleteket tárgyaljuk ebben a cikkben:

• Beillesztés a fejnél
• Beillesztés a faroknál
• Beszúrás egy csomópont után
• Beszúrás egy csomópont elé
• Törölje a fejcsomópontot
• Törölje a farok csomópontot
• Keressen és töröljön egy csomópontot
• A linkelt lista bejárása

Íme egy példa egy négy csomópontot tartalmazó láncolt listára.

Példa egy egyedileg linkelt listára

Beszúrás egy egyszeresen láncolt lista élére

Ez egy egyszerű művelet. Általában egyszeresen láncolt listára való ráhelyezésként ismert. Egy új csomópont jön létre, és a lista elejére kerül.

A művelet végrehajtásához két fontos feltételnek kell megfelelnie:

1. Ha a lista üres, az újonnan létrehozott csomópont lesz a főcsomópont, és annak következő a mutató NULL.
2. Ha a lista nem üres, az új csomópont lesz a főcsomópont, és annak következő A mutató az előző főcsomópontra mutat.

Itt egy pszeudokód egy csomópont beszúrásához egy láncolt lista élére:

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

Beillesztés a fejnél

Beszúrás egy egyszeresen láncolt lista végére

Egy láncolt lista végére egy csomópont beszúrása hasonló a lista elejére történő beszúráshoz. Menjünk át a végcsomópontig, majd mutassunk rá. következő mutató az új csomópontra. Ha a fejléc NULL, az új csomópont lesz a fejléc.

Step 1) Áthaladás addig, amíg a következő Az aktuális csomópont mutatója NULL értékűvé válik.

Step 2) Hozzon létre egy új csomópontot a megadott értékkel.

Step 3) Rendelje hozzá az új csomópontot a végcsomópont következő csomópontjaként.

A pszeudokód egy lista végére történő beszúráshoz:

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

Beillesztés a faroknál

Beszúrás egy csomópont után egy egyszeresen láncolt listában

Egy csomópont utáni beszúrás két részből áll: a célcsomópont keresése és egy új csomópont hozzárendelése utána. A lista bejárása, amíg egyezést nem talál, majd az új csomópont beillesztése.

Step 1) Addig haladjon, amíg az aktuális csomópont értéke meg nem egyezik a keresési elemmel.

Step 2) Állítsa be az új csomópontokat következő mutató az aktuális csomópontra következő mutató.

Step 3) Mutasson az aktuális csomópontra következő mutató az új csomópontra.

Pszeudokód:

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

Csomópont beszúrása egy csomópont után az egyszeri hivatkozások listáján

Beszúrás egy csomópont elé egy egyszeresen láncolt listában

Ez hasonló a csomópont utáni beszúráshoz. Addig haladunk, amíg a következő csomópont meg nem egyezik a keresési értékkel, majd elé illesszük be az új csomópontot.

Step 1) Haladjon addig, amíg a következő csomópont értéke megegyezik a keresési elemmel.

Step 2) Hozz létre egy új csomópontot, és állítsd be a következő mutató az aktuális csomópontra következő.

Step 3) Mutasson az aktuális csomópontra következő az új csomóponthoz.

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

Csomópont beszúrása egy csomópont elé az egyszeresen csatolt listában

Törölje az egyszeresen láncolt lista fejlécét

A fejléc mutató paraméterként van megadva. A fejléc csomópont eltávolításra kerül, és a következő csomópont lesz az új fejléc. A törölt csomópont memóriáját fel kell szabadítani a memóriaszivárgás elkerülése érdekében.

Step 1) Rendelje hozzá a fej következő csomópontját új fejként.

Step 2) Szabadítsa fel az előző főcsomópont lefoglalt memóriáját.

Step 3) Adja vissza az új fejcsomópontot.

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

Hivatkozott lista fejlécének törlése

Törölje az egyszeresen láncolt lista végét

A farokcsomópont törlése hasonló a fejcsomópont törléséhez. A különbség az, hogy a lista végére kell bejárni. Egyszeresen láncolt listában az a csomópont, amelynek a következő A NULL mutató a farokcsomópont.

Step 1) Közvetlenül a farokcsomópont előtt haladjon. Mentse el az aktuális csomópontot.

Step 2) Szabadítsd fel a következő csomópont (a farok) memóriáját.

Step 3) Állítsa az aktuális csomópont következő csomópontját NULL értékre.

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

Az Egyedül linkelt lista végének törlése

Csomópont keresése és törlése egyszeresen láncolt listából

Ez a függvény két feladatot lát el: keresést és törlést. Bejárja a lista végét. Ha talál egyező csomópontot, eltávolítja azt, és újra összekapcsolja az előző csomópontot. következő mutató.

Step 1) Menj végig a listán. Ellenőrizd, hogy az aktuális csomópont megegyezik-e a keresési csomóponttal.

Step 2) Ha egyezést talál, akkor egy mutatót tárol az aktuális csomópontra.

Step 3) Az következő Az előző csomópont csomópontja lesz az aktuális csomópont következő csomópontja.

Step 4) Töröld az aktuális csomópontot és szabadítsd fel a memóriáját.

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)

Csomópont keresése és törlése az egyszeri hivatkozások listájából

Egyszeresen láncolt lista bejárása

Egyszeresen láncolt lista csak a fejtől a végéig tartó bejárást támogatja. Nincs mutató az előző csomópontra, így a visszafelé történő bejárás nem lehetséges. Minden csomópontot sorban meglátogat a rendszer, és kinyomtatja az értékét, amíg el nem éri a NULL értéket.

Step 1) Minden csomópontot addig kell bejárni, amíg el nem éri a NULL értéket.

Step 2) Nyomtassa ki az aktuális csomópont értékét.

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

Példa az egyedileg linkelt listára 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);
}

teljesítmény

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élda az egyedileg linkelt listára 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()

teljesítmény

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

Az egyedileg összekapcsolt lista összetettsége

Kétféle bonyolultság létezik: az időbonyolultság és a térbonyolultság. Az egyszeresen láncolt listák esetében a legrosszabb és az átlagos eset időbonyolultsága megegyezik.

Legjobb eset időbeli komplexitása:

• A lista elejének beszúrása O(1)-ben végezhető el. A lista belsejében nem szükséges bejárni.
• A keresés és törlés O(1)-ben végezhető el, ha a cél elem a főcsomóponton van.

Átlagos esetidő-bonyolultság:

• Egy láncolt listába való beszúrás O(n)-t vesz igénybe, ahol n az elemek teljes száma.
• A keresés és a törlés is O(n) értéket vehet fel, mivel a cél elem a farokcsomópontig bárhol elhelyezkedhet.

Az egyszeresen láncolt lista térbeli komplexitása

Az egyszeresen láncolt lista dinamikusan osztja ki a memóriát. Tároláshoz n elemeket, kiosztja n memóriaegységek. Tehát a térkomplexitás O(n).

Az egyszeresen láncolt lista alkalmazásai

Az egyszeresen láncolt listák számos olyan helyen jelennek meg, ahol az előre irányuló bejárás és a dinamikus memória hasznos:

• Vermek és várólisták: Csomópontokból felépített LIFO-vermek és FIFO-sorok mögöttes tárolója.
• Hash tábla láncolása: Az ütközéseket úgy oldjuk meg, hogy a bejegyzéseket vödörenként egy egyszeresen láncolt listába láncoljuk.
• Szomszédsági listák: A ritka gráfok minden csúcshoz egy egyszeresen kapcsolt szomszédlistát használnak.
• Szimbólumtáblázatok: A fordítóprogramok és értelmezők hatókörönként egyszeresen láncolt listává láncolják az azonosítókat.
• Memóriafoglalók: Szabad listás allokátorok track szabad blokk egyszeresen láncolt listaként.

GYIK