Pojedinačno povezani popis u strukturama podataka

Što je pojedinačno povezani popis?

Pojedinačno povezani popis je linearna i jednosmjerna struktura podataka, gdje se podaci spremaju na čvorove, a svaki čvor je povezan preko veze sa svojim sljedećim čvorom. Svaki čvor sadrži podatkovno polje i vezu na sljedeći čvor. Jednostruko povezani popisi mogu se kretati samo u jednom smjeru, dok se dvostruko povezani popisi mogu kretati u oba smjera.

Ovo je struktura čvorova pojedinačno povezanog popisa:

Zašto koristiti povezani popis preko polja?

Postoji nekoliko slučajeva kada je bolje koristiti povezani popis nego Poredak. Evo nekoliko scenarija:

• Nepoznat broj elemenata: Kada ne znate koliko elemenata trebate pohraniti tijekom izvođenja programa, možete koristiti povezani popis. Memorija se dodjeljuje dinamički dok dodajete elemente na povezane popise.
• Nasumični pristup: U scenariju u kojem ne trebate koristiti nasumični pristup iz elemenata, možete koristiti povezani popis.
• Umetanje u sredini: Umetanje u sredinu niza je složen zadatak. Zato što trebate gurnuti druge elemente udesno. Međutim, povezani popis omogućuje vam dodavanje elementa na bilo koje mjesto koje želite.

Operacije pojedinačno povezanog popisa

Pojedinačno povezani popis dobar je za dinamičku dodjelu memorije. Omogućuje sve osnovne operacije povezanog popisa, tj. umetanje, brisanje, pretraživanje, ažuriranje, spajanje dvaju povezanih popisa, kretanje itd.

Ovdje ćemo raspravljati o sljedećoj operaciji povezanog popisa:

• Umetanje u glavu
• Umetanje u rep
• Umetanje nakon čvora
• Umetanje ispred čvora
• Izbrišite glavni čvor
• Izbrišite repni čvor
• Pretraživanje i brisanje čvora
• Prolazak kroz povezani popis

Evo primjera povezane liste s četiri čvora.

Umetanje na čelo pojedinačno povezanog popisa

Ovo je jednostavna operacija. Općenito, poznato je kao guranje pojedinačno povezanog popisa. Morate stvoriti novi čvor i postaviti ga na početak povezanog popisa.

Da bismo izvršili ovu operaciju, moramo ispuniti dva važna uvjeta. oni su

1. Ako je popis prazan, tada će novostvoreni čvor biti glavni čvor, a sljedeći čvor glave bit će ”NULL”.
2. Ako popis nije prazan, novi čvor će biti glavni čvor, a sljedeći će pokazivati ​​na prethodni glavni čvor.

Evo pseudokoda za umetanje čvora na početak povezanog popisa:

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

Umetanje na kraj pojedinačno povezanog popisa

Umetanje čvora na kraj povezanog popisa ima neke sličnosti s umetanjem u glavu. Sve što trebate učiniti je prijeći do krajnjeg čvora ili repnog čvora. Zatim usmjerite "sljedeći" čvor krajnjeg čvora na novostvoreni čvor. Ako je glavni čvor nula, novi čvor će biti glavni čvor.

Evo koraka:

Korak 1) Krećite se dok "sljedeći" čvor trenutnog čvora ne postane null.

Korak 2) Stvorite novi čvor s navedenom vrijednošću.

Korak 3) Dodijelite novi čvor kao sljedeći čvor repnog čvora.

Pseudokod za umetanje čvora na kraju pojedinačne liste:

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

Umetanje nakon čvora u pojedinačno povezanom popisu

Umetanje nakon čvora ima dva dijela: traženje čvora i prilaganje nakon traženog čvora. Moramo proći sve čvorove. Za svaki čvor moramo se upariti s elementom pretraživanja. Ako postoji podudaranje, tada ćemo dodati novi čvor nakon traženog čvora.

Evo koraka:

Korak 1) Krećite se sljedećim čvorom dok vrijednost trenutnog čvora ne bude jednaka traženoj stavci.

Korak 2) Sljedeći pokazivač novog čvora bit će sljedeći pokazivač trenutnog čvora.

Korak 3) Sljedeći čvor trenutnog čvora bit će novi čvor.

Evo pseudokoda za umetanje čvora nakon čvora:

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

Umetanje ispred čvora u pojedinačno povezanom popisu

Ova je funkcija vrlo slična umetanju nakon čvora. Moramo stvoriti novi čvor i prelaziti povezanim popisom sve dok trenutni čvor ne odgovara čvoru pretraživanja. Nakon toga ćemo dodati novi čvor kao prethodni čvor trenutnog čvora.

Evo koraka:

Korak 1) Krećite se dok vrijednost sljedećeg čvora ne bude jednaka traženoj stavci.

Korak 2) Napravite novi čvor i dodijelite čvoru "sljedeći" sa sljedećim do sljedećeg čvora trenutnog čvora.

Korak 3) Dodijelite novi čvor kao sljedeći čvor trenutnog čvora.

Evo pseudokoda:

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

Izbrišite glavu pojedinačno povezanog popisa

U svakoj funkciji povezanog popisa, pokazivač glave naveden je kao parametar. Morate izbrisati glavni čvor i napraviti sljedeći čvor glavnog čvora kao novi zaglavlje povezane liste. Također moramo osloboditi memoriju izbrisanog čvora. U suprotnom, memorija će biti označena kao zauzeta kada joj drugi program pokuša pristupiti.

Evo koraka za brisanje glave pojedinačno povezanog popisa:

Korak 1) Dodijelite sljedeći čvor čvora glave kao novu glavu.

Korak 2) Oslobodite memoriju koju je dodijelio prethodni glavni čvor.

Korak 3) Vratite novi glavni čvor.

Pseudokod za brisanje glavnog čvora:

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

Izbrišite rep pojedinačno povezane liste

Brisanje repnog čvora je poznatije od brisanja glavnog čvora. Razlika je u tome što moramo prijeći do kraja povezanog popisa i izbrisati ga. U pojedinačno povezanom popisu, čvor sa sljedećim čvorom kao "NULL" je repni čvor.

Evo koraka za brisanje repnog čvora povezanog popisa:

Korak 1) Traverza prije repnog čvora. Spremite trenutni čvor.

Korak 2) Oslobodite memoriju sljedećeg čvora trenutnog čvora.

Korak 3) Postavite sljedeći čvor trenutnog čvora kao NULL.

Evo pseudokoda za brisanje repnog čvora:

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

Pretražite i izbrišite čvor s pojedinačno povezanog popisa

Ova funkcija ima dva zadatka, pretraživanje i brisanje. Moramo pretraživati ​​do kraja pojedinačno povezanih popisa. Ako pronađemo sličan čvor, izbrisat ćemo ga. Nakon toga trebamo spojiti ili povezati lijevi i desni čvor izbrisanog čvora. Evo koraka za to:

Korak 1) Krećite se do kraja povezanog popisa. Provjerite je li trenutni čvor jednak čvoru pretraživanja ili ne.

Korak 2) Ako se bilo koji čvor podudara, pohranite pokazivač čvora na trenutni čvor.

Korak 3) "Sljedeći" od prethodnog čvora bit će sljedeći čvor trenutnog čvora.

Korak 4) Izbrišite i oslobodite memoriju trenutnog čvora.

Pseudokod za pretraživanje i brisanje čvora s pojedinačno povezanog popisa:

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)

Pređite jednostruko povezani popis

Pojedinačno povezani popis ima samo funkcionalnost za kretanje od glave do repa. Nema pokazivača na prethodni čvor; zato ne možemo preći pojedinačno povezani popis obrnutim redoslijedom. Preći ćemo svaki čvor i ispisivati ​​vrijednost trenutnog čvora dok ne dobijemo nulu.

Evo koraka:

Korak 1) Prelazimo svaki čvor dok ne dobijemo null kao sljedeći čvor.

Korak 2) Ispiši vrijednost trenutnog čvora.

Pseudo-kod za obilazak jednostruko povezane liste:

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

Primjer pojedinačno povezanog popisa u 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);
}

Izlaz:

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

Primjer pojedinačno povezanog popisa u Python program

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

Izlaz:

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

Složenost pojedinačno povezanog popisa

Postoje dvije vrste složenosti: vremenska složenost i prostorna složenost. Najgora i prosječna vremenska složenost slučaja ista je za pojedinačno povezani popis.

Vremenska složenost u najboljem slučaju:

• Umetanje u glavu može se izvesti u O(1). Budući da ne trebamo prelaziti unutar povezanog popisa.
• Operacija pretraživanja i brisanja može se izvršiti u O(1) ako je element pretraživanja prisutan u glavnom čvoru.

Vremenska složenost za prosječan slučaj:

• Umetanje unutar povezanog popisa trajat će O(n) ako je "n" elemenata prisutno u pojedinačno povezanom popisu.
• Pretraživanje i brisanje također mogu uzeti O(n), budući da element pretraživanja može biti prisutan u repnom čvoru. U tom slučaju, trebali biste proći cijeli popis.

Prostorna složenost jednostruko povezanog popisa

Pojedinačno povezani popis dinamički dodjeljuje memoriju. Ako želimo pohraniti n elemenata, alocirati će n memorijskih jedinica. Dakle, kompleksnost prostora je O(n).