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:

Solmun rakenne linkitetyssä luettelossa
Solmun rakenne linkitetyssä luettelossa

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.

Esimerkki yksittäisestä linkitetystä luettelosta
Esimerkki yksittäisestä linkitetystä luettelosta

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

  1. Jos lista on tyhjä, uusi solmu on pääsolmu ja pään seuraava solmu on ”NULL”.
  2. 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
Kiinnitys päähän
Kiinnitys päähän

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
Kiinnitys hännän kohdalle
Kiinnitys hännän kohdalle

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
Solmun lisääminen solmun perään yksitellen linkitetyssä luettelossa
Solmun lisääminen solmun perään Singly Linked List -luettelossa

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
Solmun lisääminen ennen solmua yksitellen linkitetyssä luettelossa
Solmun lisääminen solmun eteen yksitellen linkitetyssä luettelossa

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
Linkitetyn luettelon pään poistaminen
Linkitetyn luettelon otsikon poistaminen

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
Yksittäin linkitetyn luettelon loppuosa poistetaan
Yksittäin linkitetyn luettelon loppuosa poistetaan

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)
Etsi ja poista solmu erikseen linkitetystä luettelosta
Etsi ja poista solmu Singly Linked List -luettelosta

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