Lista pojedynczo połączona w strukturach danych

Co to jest lista pojedynczo połączona?

Lista Singly Linked List to liniowa i jednokierunkowa struktura danych, w której dane są zapisywane w węzłach, a każdy węzeł jest połączony łączem z następnym węzłem. Każdy węzeł zawiera pole danych i łącze do następnego węzła. Po listach pojedynczo połączonych można poruszać się tylko w jednym kierunku, podczas gdy po listach podwójnie połączonych można poruszać się w obu kierunkach.

Oto struktura węzłów listy pojedynczo połączonej:

Po co używać listy połączonej zamiast tablicy?

Istnieje kilka przypadków, w których lepiej jest użyć listy połączonej niż listy Szyk. Oto kilka scenariuszy:

• Nieznana liczba elementów: Jeśli nie wiesz, ile elementów musisz przechowywać w trakcie działania programu, możesz skorzystać z listy połączonej. Pamięć jest przydzielana dynamicznie w miarę dodawania elementów do połączonych list.
• Losowy dostęp: W scenariuszu, w którym nie musisz korzystać z losowego dostępu z elementów, możesz użyć listy połączonej.
• Wstawienie w środku: Wstawianie w środku tablicy jest złożonym zadaniem. Ponieważ musisz przesunąć inne elementy na prawo. Jednak lista powiązana pozwala dodać element w dowolnej pozycji.

Operalisty pojedynczo połączonej

Singly Linked List jest dobra do dynamicznego przydzielania pamięci. Zapewnia wszystkie podstawowe operacje listy powiązanej, tj. wstawianie, usuwanie, wyszukiwanie, aktualizowanie, scalanie dwóch list powiązanych, przechodzenie itp.

Tutaj omówimy następującą operację na liście powiązanej:

• Wkładanie na głowę
• Wstawka na ogonie
• Wstawianie po węźle
• Wstawianie przed węzłem
• Usuń węzeł główny
• Usuń węzeł ogonowy
• Wyszukaj i usuń węzeł
• Przechodzenie przez listę połączoną

Oto przykład połączonej listy z czterema węzłami.

Wstawienie na początku listy pojedynczo połączonej

To prosta operacja. Ogólnie rzecz biorąc, jest znana jako wpychanie listy jednokierunkowej. Musisz utworzyć nowy węzeł i umieścić go na początku listy kierunkowej.

Aby wykonać tę operację, musimy spełnić dwa ważne warunki. Są to:

1. Jeśli lista będzie pusta, nowo utworzony węzeł będzie węzłem głównym, a następny węzeł głowy będzie miał wartość „NULL”.
2. Jeśli lista nie jest pusta, nowy węzeł będzie węzłem głównym, a następny będzie wskazywał poprzedni węzeł główny.

Oto pseudokod służący do wstawiania węzła na początku połączonej listy:

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

Wstawienie na końcu listy pojedynczo połączonej

Wstawianie węzła na końcu połączonej listy ma pewne podobieństwa z wstawianiem w nagłówku. Wszystko, co musisz zrobić, to przejść do węzła końcowego lub węzła końcowego. Następnie skieruj „następny” węzeł węzła końcowego na nowo utworzony węzeł. Jeśli węzeł główny ma wartość null, nowy węzeł będzie węzłem głównym.

Oto kroki:

Krok 1) Przemierzaj, aż „następny” węzeł bieżącego węzła stanie się pusty.

Krok 2) Utwórz nowy węzeł z określoną wartością.

Krok 3) Przypisz nowy węzeł jako następny węzeł węzła końcowego.

Pseudokod do wstawienia węzła na końcu pojedynczej listy:

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

Wstawienie po węźle na liście pojedynczo połączonej

Wstawianie po węźle składa się z dwóch części: wyszukania węzła i dołączenia po przeszukiwanym węźle. Musimy przejść przez wszystkie węzły. Dla każdego węzła musimy dopasować element wyszukiwania. Jeśli znajdzie się dopasowanie, dodamy nowy węzeł po przeszukiwanym węźle.

Oto kroki:

Krok 1) Przechodź przez następny węzeł, aż wartość bieżącego węzła będzie równa wyszukiwanemu elementowi.

Krok 2) Następny wskaźnik nowego węzła będzie następnym wskaźnikiem bieżącego węzła.

Krok 3) Następny węzeł bieżącego węzła będzie nowym węzłem.

Oto pseudokod służący do wstawiania węzła po węźle:

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

Wstawienie przed węzłem na liście pojedynczo połączonej

Ta funkcja jest bardzo podobna do wstawiania po węźle. Musimy utworzyć nowy węzeł i przeglądać połączoną listę, aż bieżący węzeł będzie odpowiadał węzłowi wyszukiwania. Następnie dodamy nowy węzeł jako poprzedni węzeł bieżącego węzła.

Oto kroki:

Krok 1) Przemierzaj, aż wartość następnego węzła będzie równa wyszukiwanemu elementowi.

Krok 2) Utwórz nowy węzeł i przypisz „następny” węzła do następnego węzła bieżącego węzła.

Krok 3) Przypisz nowy węzeł jako następny węzeł bieżącego węzła.

Oto pseudokod:

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

Usuń nagłówek pojedynczo połączonej listy

W każdej funkcji listy łączonej wskaźnik head jest dostarczany jako parametr. Musisz usunąć węzeł head i uczynić następny węzeł head nowym head listy łączonej. Musimy również zwolnić pamięć usuniętego węzła. W przeciwnym razie pamięć zostanie oznaczona jako zajęta, gdy inny program spróbuje uzyskać do niej dostęp.

Oto kroki usuwania nagłówka listy z pojedynczym łączem:

Krok 1) Przypisz następny węzeł węzła głównego jako nową głowę.

Krok 2) Zwolnij przydzieloną pamięć przez poprzedni węzeł główny.

Krok 3) Zwróć nowy węzeł główny.

Pseudokod do usuwania węzła głównego:

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

Usuń koniec pojedynczo połączonej listy

Usuwanie węzła końcowego jest bardziej podobne do usuwania węzła głównego. Różnica polega na tym, że musimy przejść na koniec połączonej listy i ją usunąć. Na liście pojedynczo połączonej węzeł, którego następny węzeł ma wartość „NULL”, jest węzłem końcowym.

Oto kroki usuwania węzła końcowego połączonej listy:

Krok 1) Trawers przed węzłem ogonowym. Zapisz bieżący węzeł.

Krok 2) Zwolnij pamięć następnego węzła bieżącego węzła.

Krok 3) Ustaw następny węzeł bieżącego węzła na NULL.

Oto pseudokod do usuwania węzła ogonowego:

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

Wyszukaj i usuń węzeł z pojedynczo połączonej listy

Ta funkcja ma dwa zadania: wyszukiwanie i usuwanie. Musimy przeszukać do końca pojedynczo połączonych list. Jeśli znajdziemy podobny węzeł, usuniemy go. Następnie musimy scalić lub połączyć lewy i prawy węzeł usuniętego węzła. Oto kroki, jak to zrobić:

Krok 1) Przejdź do końca połączonej listy. Sprawdź, czy bieżący węzeł jest równy węzłowi wyszukiwania, czy nie.

Krok 2) Jeśli którykolwiek węzeł pasuje, zapisz wskaźnik węzła do bieżącego węzła.

Krok 3) „Następny” poprzedniego węzła będzie następnym węzłem bieżącego węzła.

Krok 4) Usuń i zwolnij pamięć bieżącego węzła.

Pseudokod wyszukiwania i usuwania węzła z pojedynczo połączonej listy:

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)

Przechodzenie przez pojedynczo połączoną listę

Lista pojedynczo połączona ma tylko funkcję przechodzenia od początku do końca. Nie ma punktów wskazujących na poprzedni węzeł; dlatego nie możemy przeglądać listy Singly Linked List w odwrotnej kolejności. Będziemy przechodzić przez każdy węzeł i drukować wartość bieżącego węzła, aż otrzymamy wartość null.

Oto kroki:

Krok 1) Przemierzaj każdy węzeł, aż otrzymamy wartość null jako następny węzeł.

Krok 2) Wydrukuj wartość bieżącego węzła.

Pseudokod do przechodzenia przez pojedynczo połączoną listę:

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

Przykład listy pojedynczo połączonej w 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);
}

Wyjście:

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

Przykład listy pojedynczo połączonej w 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()

Wyjście:

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

Złożoność listy jednokierunkowej

Istnieją dwa rodzaje złożoności: złożoność czasowa i złożoność przestrzenna. Najgorsza i średnia złożoność czasowa przypadku jest taka sama dla listy jednokierunkowej.

Złożoność czasowa w najlepszym przypadku:

• Włożenie w głowę można wykonać w O(1). Ponieważ nie musimy przechodzić przez połączoną listę.
• Operację wyszukiwania i usuwania można wykonać w tempie O(1), jeśli element wyszukiwania znajduje się w węźle głównym.

Złożoność czasowa dla przeciętnego przypadku:

• Wstawienie do połączonej listy zajmie O(n), jeśli na liście pojedynczo połączonej znajduje się „n” elementów.
• Wyszukiwanie i usuwanie może również przyjmować O(n), ponieważ element wyszukiwania może znajdować się w węźle końcowym. W takim przypadku należy przejrzeć całą listę.

Złożoność przestrzenna listy jednokierunkowej

Lista jednostronnie powiązana dynamicznie przydziela pamięć. Jeśli chcemy przechowywać n elementów, przydzieli n jednostek pamięci. Zatem złożoność pamięci wynosi O(n).