Yksittäin linkitetty luettelo tietorakenteissa
Mikä on yksittäin linkitetty luettelo?
Singly Linked List on lineaarinen ja yksisuuntainen tietorakenne, jossa tiedot tallennetaan solmuihin ja jokainen solmu on yhdistetty linkin kautta seuraavaan solmuun. Jokainen solmu sisältää tietokentän ja linkin seuraavaan solmuun. Yksittäin linkitettyjä luetteloita voidaan kulkea vain yhteen suuntaan, kun taas kaksoislinkitettyjen luetteloiden läpi voidaan kulkea molempiin suuntiin.
Tässä on yksittäin linkitetyn luettelon solmurakenne:

Miksi käyttää linkitettyä listaa taulukon yli?
On useita tapauksia, joissa on parempi käyttää linkitettyä luetteloa Ryhmä. Tässä on joitain skenaarioita:
- Tuntematon määrä elementtejä: Jos et tiedä kuinka monta elementtiä sinun on tallennettava ohjelman ajon aikana, voit käyttää linkitettyjen luetteloa. Muisti varataan dynaamisesti, kun lisäät elementtejä linkitettyihin luetteloihin.
- Satunnainen pääsy: Skenaariossa, jossa sinun ei tarvitse käyttää elementtien satunnaiskäyttöä, voit käyttää linkitettyä luetteloa.
- Lisäys keskelle: Lisääminen taulukon keskelle on monimutkainen tehtävä. Koska sinun täytyy työntää muita elementtejä oikealle. Linkitetyn luettelon avulla voit kuitenkin lisätä elementin mihin tahansa haluamaasi paikkaan.
OperaSingly Linked List
Singly Linked List on hyvä muistin dynaamiseen varaamiseen. Se tarjoaa kaikki linkitetyn luettelon perustoiminnot, kuten lisäämisen, poistamisen, haun, päivittämisen, kahden linkitetyn luettelon yhdistämisen, läpikulkua jne.
Tässä käsitellään seuraavaa linkitetyn luettelon toimintaa:
- 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ä luettelosta, jossa on neljä solmua.
Lisäys yksittäin linkitetyn luettelon alkuun
Tämä on yksinkertainen toimenpide. Yleensä se tunnetaan yksitellen linkitetyn luettelon työntämisenä. Sinun on luotava uusi solmu ja asetettava se linkitetyn luettelon alkuun.
Tämän toiminnon suorittamiseksi meidän on noudatettava kahta tärkeää ehtoa. He ovat
- Jos lista on tyhjä, uusi solmu on pääsolmu ja pään seuraava solmu on ”NULL”.
- Jos luettelo ei ole tyhjä, uusi solmu on pääsolmu ja seuraava osoittaa edelliseen pääsolmuun.
Tässä on pseudokoodi solmun lisäämiseksi linkitetyn luettelon alkuun:
function insertAtHead( head, value ): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
Lisäys yksittäin linkitetyn luettelon loppuun
Solmun lisäämisellä linkitetyn luettelon loppuun on joitakin yhtäläisyyksiä päähän lisäämisen kanssa. Sinun tarvitsee vain kulkea päätesolmuun tai loppusolmuun. Osoita sitten loppusolmun "seuraava" solmu äskettäin luotuun solmuun. Jos pääsolmu on nolla, uusi solmu on pääsolmu.
Tässä ovat vaiheet:
Vaihe 1) Kulje, kunnes nykyisen solmun "seuraava" solmu muuttuu tyhjäksi.
Vaihe 2) Luo uusi solmu määritetyllä arvolla.
Vaihe 3) Määritä uusi solmu häntäsolmun seuraavaksi solmuksi.
Pseudokoodi solmun lisäämiseksi yksittäisluettelon loppuun:
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
Lisäys solmun jälkeen yksitellen linkitetyssä luettelossa
Solmun jälkeen lisäämisessä on kaksi osaa: Etsi solmu ja liitä etsityn solmun jälkeen. Meidän täytyy kulkea kaikkien solmujen läpi. Jokaisen solmun on täsmättävä hakuelementin kanssa. Jos osuma löytyy, lisäämme uuden solmun haetun solmun jälkeen.
Tässä ovat vaiheet:
Vaihe 1) Kulje seuraavaa solmua, kunnes nykyisen solmun arvo on yhtä suuri kuin hakukohde.
Vaihe 2) Uuden solmun seuraava osoitin on nykyisen solmun seuraava osoitin.
Vaihe 3) Nykyisen solmun seuraava solmu on uusi solmu.
Tässä on pseudokoodi solmun lisäämiseksi solmun jälkeen:
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
Lisäys ennen solmua yksitellen linkitetyssä luettelossa
Tämä toiminto on paljon samanlainen kuin lisäys solmun jälkeen. Meidän on luotava uusi solmu ja kuljetettava linkitetty luettelo, kunnes nykyinen solmu vastaa hakusolmua. Tämän jälkeen lisäämme uuden solmun nykyisen solmun edelliseksi solmuksi.
Tässä ovat vaiheet:
Vaihe 1) Kulje, kunnes seuraavan solmun arvo on yhtä suuri kuin hakukohde.
Vaihe 2) Luo uusi solmu ja määritä solmun "seuraava" nykyisen solmun seuraavaan solmuun.
Vaihe 3) Määritä uusi solmu nykyisen solmun seuraavaksi solmuksi.
Tässä pseudokoodi:
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
Poista yksitellen linkitetyn luettelon pää
Jokaisessa linkitetyn luettelon funktiossa pääosoitin annetaan parametrina. Sinun on poistettava pääsolmu ja tehtävä pääsolmun seuraava solmu linkitetyn luettelon uudeksi pääksi. Meidän on myös vapautettava poistetun solmun muisti. Muussa tapauksessa muisti merkitään varatuksi, kun toinen ohjelma yrittää käyttää sitä.
Yksittäisen linkitetyn luettelon otsikon poistaminen tapahtuu seuraavasti:
Vaihe 1) Määritä pääsolmun seuraava solmu uudeksi pääksi.
Vaihe 2) Vapauta edellisen pääsolmun varaama muisti.
Vaihe 3) Palauta uusi pääsolmu.
Pseudokoodi pääsolmun poistamiseksi:
function deleteHead( head ): temp = head head = head.next free( temp ) return head
Poista yksitellen linkitetyn luettelon loppuosa
Tail-solmun poistaminen on tutumpaa kuin pääsolmun poistaminen. Erona on, että meidän on siirryttävä linkitetyn luettelon loppuun ja poistettava se. Yksittäin linkitetyssä luettelossa solmu, jonka seuraava solmu on "NULL", on loppusolmu.
Tässä on vaiheet linkitetyn luettelon loppusolmun poistamiseksi:
Vaihe 1) Kulje ennen häntäsolmua. Tallenna nykyinen solmu.
Vaihe 2) Vapauta nykyisen solmun seuraavan solmun muisti.
Vaihe 3) Aseta nykyisen solmun seuraavaksi solmuksi NULL.
Tässä on pseudokoodi häntäsolmun poistamiseen:
function deleteTail( head ): while head.next.next is not NULL: head = head.next free( head.next ) head.next = NULL
Hae ja poista solmu erikseen linkitetystä luettelosta
Tällä toiminnolla on kaksi tehtävää, haku ja poistaminen. Meidän on etsittävä yksittäin linkitettyjen luetteloiden loppuun asti. Jos löydämme samanlaisen solmun, poistamme sen. Sen jälkeen meidän on yhdistettävä tai linkitettävä poistetun solmun vasen ja oikea solmu. Tässä on ohjeet tämän tekemiseen:
Vaihe 1) Kulje linkitetyn luettelon loppuun asti. Tarkista, onko nykyinen solmu sama kuin hakusolmu vai ei.
Vaihe 2) Jos jokin solmu täsmää, tallenna solmun osoitin nykyiseen solmuun.
Vaihe 3) Edellisen solmun "seuraava" on nykyisen solmun seuraava solmu.
Vaihe 4) Poista ja vapauta nykyisen solmun muisti.
Pseudokoodi hakuun ja solmun poistamiseen yksittäin linkitetystä luettelosta:
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)
Selaa yksitellen linkitetty luettelo
Yksittäin linkitetyllä listalla on vain toiminnallisuus päästä häntään kulkemiseen. Edelliseen solmuun ei ole osoitinpisteitä; siksi emme voi kulkea yksittäislinkitettyjen luetteloa käänteisessä järjestyksessä. Kuljemme jokaisen solmun läpi ja tulostamme nykyisen solmun arvon, kunnes saamme nollan.
Tässä ovat vaiheet:
Vaihe 1) Kulje jokaisen solmun läpi, kunnes saamme seuraavan solmun nollan.
Vaihe 2) Tulosta nykyisen solmun arvo.
Pseudokoodi yksitellen linkitetyn luettelon läpikulkuun:
function traverse( head ): while head.next is not NULL: print the value of the head 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); } 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); }
lähtö:
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 Ohjelma
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()
lähtö:
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
Monimutkaisuutta on kahta tyyppiä: aika- ja tilamonimutkaisuus. Huonoin ja keskimääräinen tapauksen monimutkaisuus on sama Singly Linked List -luettelossa.
Aika monimutkaisuus parhaassa tapauksessa:
- Päähän asettaminen voidaan tehdä kohdassa O(1). Koska meidän ei tarvitse kulkea linkitetyn luettelon sisällä.
- Haku- ja poistotoiminto voidaan tehdä kohdassa O(1), jos hakuelementti on pääsolmussa.
Keskimääräisen tapauksen aika monimutkaisuus:
- Lisääminen linkitetyn luettelon sisällä kestää O(n), jos "n" elementtiä on yksitellen linkitetyssä luettelossa.
- Haku ja poistaminen voivat kestää myös O(n), koska hakuelementti voi olla läsnä häntäsolmussa. Siinä tapauksessa sinun tulee käydä läpi koko luettelo.
Yksittäin linkitetyn luettelon monimutkaisuus
Singly Linked List varaa muistia dynaamisesti. Jos haluamme tallentaa n elementtiä, se varaa n muistiyksikköä. Joten avaruuden kompleksisuus on O(n).