Yksittäin linkitetty luettelo tietorakenteissa

Mikä on yksittäin linkitetty luettelo?

Yksinkertaisesti linkitetty lista on lineaarinen ja yksisuuntainen tietorakenne, jossa data tallennetaan solmuihin ja jokainen solmu on yhteydessä linkin kautta seuraavaan solmuunsa. Jokainen solmu sisältää datakentän ja linkin seuraavaan solmuun. Yksinkertaisesti linkitettyjä listoja voidaan käydä läpi vain yhteen suuntaan, kun taas Kaksoislinkitetty lista voidaan kulkea molempiin suuntiin.

Tässä on yksinkertaisesti linkitetyn listan solmurakenne:

Solmun rakenne linkitetyssä luettelossa

Miksi käyttää linkitettyä listaa taulukon päällä?

Useat skenaariot suosivat linkitettyä listaa Ryhmä:

• Tuntematon määrä elementtejä: Kun vaadittavien elementtien lukumäärää ei tiedetä käännösaikana, linkitetty lista varaa muistia dynaamisesti elementtien lisäyksen myötä.
• Satunnainen pääsy: Kun satunnaista indeksoitua pääsyä ei tarvita, linkitetty lista on sopiva vaihtoehto.
• Lisäys keskelle: Taulukon keskelle lisääminen vaatii elementtien siirtämistä. Linkitetty lista sallii elementtien lisäämisen mihin tahansa kohtaan kirjoittamalla uudelleen vain muutaman osoittimen.

OperaSingly Linked List

Yksinkertaisesti linkitetty lista sopii hyvin muistin dynaamiseen allokointiin. Se tukee linkitetyn listan perusoperaatioita, kuten lisäystä, poistamista, etsimistä, päivittämistä, kahden listan yhdistämistä ja läpikäymistä.

Tässä artikkelissa käsitellään seuraavia toimintoja:

• Kiinnitys päähän
• Kiinnitys hännän kohdalle
• Lisääminen solmun jälkeen
• Lisääminen ennen solmua
• Poista pääsolmu
• Poista häntäsolmu
• Etsi ja poista solmu
• Linkitettyjen luettelon läpikäyminen

Tässä on esimerkki linkitetystä listasta, jossa on neljä solmua.

Esimerkki yksittäisestä linkitetystä luettelosta

Lisäys yksinkertaisesti linkitetyn listan kärkeen

Tämä on yksinkertainen operaatio. Se tunnetaan yleisesti nimellä "pushing" (lisääminen) yksittäin linkitettyyn listaan. Uusi solmu luodaan ja sijoitetaan listan alkuun.

Suorittaaksesi tämän toiminnon, noudata kahta tärkeää ehtoa:

1. Jos lista on tyhjä, juuri luodusta solmusta tulee pääsolmu ja sen seuraava osoitin on NULL.
2. Jos lista ei ole tyhjä, uudesta solmusta tulee pääsolmu ja sen seuraava osoitin osoittaa edelliseen pääsolmuun.

Tässä on pseudokoodi solmun lisäämiseksi linkitetyn listan alkuun:

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

Kiinnitys päähän

Lisäys yksinkertaisesti linkitetyn listan loppuun

Solmun lisääminen linkitetyn listan loppuun on samanlaista kuin lisääminen listan alkuun. Siirry häntäsolmuun ja osoita sen seuraava osoitin uuteen solmuun. Jos head-solmu on NULL, uudesta solmusta tulee head-solmu.

Vaihe 1) Kulje, kunnes seuraava Nykyisen solmun osoitin muuttuu NULL:ksi.

Vaihe 2) Luo uusi solmu määritetyllä arvolla.

Vaihe 3) Määritä uusi solmu häntäsolmun seuraavaksi solmuksi.

Pseudokoodi yksittäislistan loppuun lisäämiseen:

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

Kiinnitys hännän kohdalle

Lisäys solmun jälkeen yksinkertaisesti linkitettyyn listaan

Solmun lisääminen solmun jälkeen tapahtuu kahdessa vaiheessa: etsitään kohdesolmu ja liitetään uusi solmu sen jälkeen. Listaa käydään läpi, kunnes löytyy osuma, ja uusi solmu liitetään siihen.

Vaihe 1) Käy läpi, kunnes nykyisen solmun arvo on yhtä suuri kuin etsittävä alkio.

Vaihe 2) Aseta uuden solmun seuraava osoitin nykyiseen solmuun seuraava osoitin.

Vaihe 3) Osoita nykyisen solmun seuraava osoitin uuteen solmuun.

Pseudokoodi:

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

Solmun lisääminen solmun perään Singly Linked List -luettelossa

Lisäys ennen solmua yksinkertaisesti linkitettyyn listaan

Tämä on samanlaista kuin lisäys solmun jälkeen. Käydään läpi, kunnes seuraava solmu vastaa hakuarvoa, ja lisätään sitten uusi solmu sen eteen.

Vaihe 1) Kulje, kunnes seuraavan solmun arvo on yhtä suuri kuin hakukohde.

Vaihe 2) Luo uusi solmu ja aseta sen seuraava osoitin nykyiseen solmuun seuraava.

Vaihe 3) Osoita nykyisen solmun seuraava uuteen solmuun.

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

Solmun lisääminen solmun eteen yksitellen linkitetyssä luettelossa

Poista yksittäin linkitetyn listan pää

Pääsolmun osoitin annetaan parametrina. Pääsolmu poistetaan ja seuraavasta solmusta tulee uusi pääsolmu. Poistetun solmun muisti on vapautettava muistivuotojen välttämiseksi.

Vaihe 1) Määritä pään seuraava solmu uudeksi pääksi.

Vaihe 2) Vapauta edellisen pääsolmun varattu muisti.

Vaihe 3) Palauta uusi pääsolmu.

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

Linkitetyn luettelon otsikon poistaminen

Poista yksittäin linkitetyn listan häntä

Häntäsolmun poistaminen on samanlaista kuin pääsolmun poistaminen. Ero on siinä, että listan loppuun on mentävä. Yksinkertaisesti linkitetyssä listassa solmu, jonka seuraava osoitin on NULL, joka on häntäsolmu.

Vaihe 1) Siirrytään juuri ennen häntäsolmua. Tallenna nykyinen solmu.

Vaihe 2) Vapauta seuraavan solmun (häntä) muisti.

Vaihe 3) Aseta nykyisen solmun seuraavan solmun arvoksi NULL.

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

Yksittäin linkitetyn luettelon loppuosa poistetaan

Solmun etsiminen ja poistaminen yksittäin linkitetystä listasta

Tämä funktio suorittaa kaksi tehtävää: haun ja poiston. Se käy läpi listan loppuun asti. Jos vastaava solmu löytyy, se poistetaan ja linkitetään uudelleen edellisen solmun solmuun. seuraava osoitin.

Vaihe 1) Käy läpi listan loppuun asti. Tarkista, onko nykyinen solmu sama kuin etsittävä solmu.

Vaihe 2) Jos osuma löytyy, tallenna osoitin nykyiseen solmuun.

Vaihe 3) seuraava Edellisen solmun solmusta tulee nykyisen solmun seuraava solmu.

Vaihe 4) Poista nykyinen solmu ja vapauta sen muisti.

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)

Etsi ja poista solmu Singly Linked List -luettelosta

Yksinkertaisesti linkitettyjen listojen läpikäyminen

Yksinkertaisesti linkitetty lista tukee läpikulkua vain päästä häntään. Edelliseen solmuun ei ole osoitinta, joten taaksepäin läpikulku ei ole mahdollinen. Jokaista solmua käydään vuorotellen ja sen arvo tulostetaan, kunnes saavutetaan NULL.

Vaihe 1) Käy läpi jokainen solmu, kunnes saavutetaan NULL.

Vaihe 2) Tulosta nykyisen solmun arvo.

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

Esimerkki yksittäisestä linkitetystä luettelosta 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);
}

ulostulo

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

Esimerkki yksittäisestä linkitetystä luettelosta 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()

ulostulo

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

Yksittäin linkitetyn luettelon monimutkaisuus

Kompleksisuutta on kahdenlaisia: aikakompleksisuus ja tilakompleksisuus. Pahimman ja keskimääräisen tapauksen aikakompleksisuus ovat samat yksinkertaisesti linkitetyllä listalla.

Parhaan mahdollisen tapauksen aikakompleksisuus:

• Listan alkuun lisäys voidaan tehdä O(1):ssä. Listan sisällä ei tarvitse kulkea.
• Haku ja poisto voidaan tehdä O(1):ssä, jos kohdeelementti on pääsolmussa.

Keskimääräinen tapauksen käsittelyaikakompleksisuus:

• Lisäys linkitettyyn listaan ​​vaatii O(n), missä n on elementtien kokonaismäärä.
• Myös haku ja poisto voivat ottaa O(n):n, koska kohdeelementti voi sijaita missä tahansa häntäsolmuun asti.

Yksinkertaisesti linkitettyjen listojen avaruuskompleksisuus

Yksinkertaisesti linkitetty lista varaa muistia dynaamisesti. Tallentaakseen n elementtejä, se allokoi n muistiyksiköitä. Joten tilakompleksisuus on O(n).

Yksinkertaisesti linkitettyjen listojen sovellukset

Yksinkertaisesti linkitettyjä listoja esiintyy monissa paikoissa, joissa vain eteenpäin suuntautuva läpikulku ja dynaaminen muisti ovat hyödyllisiä:

• Pinot ja jonot: Solmuista rakennettujen LIFO-pinojen ja FIFO-jonojen pohjana oleva tallennustila.
• Hajautustaulukon ketjutus: Törmäykset ratkaistaan ​​ketjuttamalla merkinnät yksittäisesti linkitettyyn listaan ​​​​säilöä kohden.
• Vierekkäisyysluettelot: Harvat graafit käyttävät jokaiselle solmulle erikseen linkitettyä naapuriliistaa.
• Symbolitaulukot: Kääntäjät ja tulkit ketjuttavat tunnisteet yksittäin linkitettyyn listaan ​​​​alueittain.
• Muistin allokaattorit: Vapaalistaiset allokaattorit track vapaata lohkoa yksinkertaisesti linkitettynä listana.

UKK