Lista pojedynczo połączona w strukturach danych

Co to jest lista pojedynczo połączona?

Lista jednokierunkowa 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 kolejnym węzłem. Każdy węzeł zawiera pole danych i łącze do następnego węzła. Listy jednokierunkowe można przeglądać tylko w jednym kierunku, podczas gdy Lista podwójnie połączona można przejechać w obu kierunkach.

Oto struktura węzłów listy jednokierunkowo powiązanej:

Struktura węzła na liście połączonej

Dlaczego warto używać listy powiązanej, a nie tablicy?

W kilku scenariuszach preferowana jest lista powiązana zamiast Szyk:

• Nieznana liczba elementów: Jeśli wymagana liczba elementów nie jest znana w momencie kompilacji, lista powiązana przydziela pamięć dynamicznie w miarę dodawania elementów.
• Losowy dostęp: Lista powiązana jest odpowiednim wyborem, gdy nie jest potrzebny losowy dostęp indeksowany.
• Wstawienie w środku: Wstawianie w środku tablicy wymaga przesunięcia elementów. Lista powiązana umożliwia wstawianie w dowolnym miejscu poprzez przepisanie zaledwie kilku wskaźników.

Operalisty pojedynczo połączonej

Lista jednokierunkowa (SLS) dobrze nadaje się do dynamicznego przydzielania pamięci. Obsługuje standardowe operacje listy jednokierunkowej, takie jak wstawianie, usuwanie, wyszukiwanie, aktualizowanie, scalanie dwóch list i przechodzenie między nimi.

W tym artykule omówiono następujące operacje:

• 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 listy powiązanej z czterema węzłami.

Przykład listy pojedynczo połączonej

Wstawianie na początku listy jednokierunkowo powiązanej

To prosta operacja. Jest ona powszechnie znana jako wpychanie na listę jednokierunkową. Nowy węzeł jest tworzony i umieszczany na początku listy.

Aby wykonać tę operację, należy spełnić dwa ważne warunki:

1. Jeżeli lista jest pusta, nowo utworzony węzeł staje się węzłem głównym, a jego Następny wskaźnik jest NULL.
2. Jeżeli lista nie jest pusta, nowy węzeł staje się węzłem głównym i jego Następny wskaźnik wskazuje na poprzedni węzeł główny.

Oto pseudokod umożliwiający wstawienie węzła na początku listy powiązanej:

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

Wkładanie na głowę

Wstawianie na końcu listy jednokierunkowo powiązanej

Wstawianie węzła na końcu listy powiązanej jest podobne do wstawiania na początku. Przejdź do węzła końcowego, a następnie skieruj go Następny wskaźnik do nowego węzła. Jeśli głowa jest NULL, nowy węzeł staje się głową.

Krok 1) Przemierzaj aż do Następny wskaźnik bieżącego węzła staje się NULL.

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 wstawiania 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:
    head = head.next
  head.next = newNode
  newNode.next = NULL

Wstawka na ogonie

Wstawianie po węźle na liście jednokierunkowo połączonej

Wstawianie za węzłem składa się z dwóch części: wyszukania węzła docelowego i dołączenia nowego węzła po nim. Przejrzyj listę, aż znajdziesz pasujący węzeł, a następnie wklej nowy węzeł.

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

Krok 2) Ustaw nowy węzeł Następny wskaźnik do bieżącego węzła Następny wskaźnik.

Krok 3) Wskaż bieżący węzeł Następny wskaźnik do nowego węzła.

Pseudokod:

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

Wstawianie węzła za węzłem na liście pojedynczo połączonej

Wstawianie przed węzłem na liście jednokierunkowo powiązanej

Działa to podobnie do wstawiania za węzłem. Przechodź, aż kolejny węzeł będzie pasował do szukanej wartości, a następnie wstaw nowy węzeł przed nim.

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

Krok 2) Utwórz nowy węzeł i ustaw jego Następny wskaźnik do bieżącego węzła Następny.

Krok 3) Wskaż bieżący węzeł Następny do nowego węzła.

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

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

Usuń nagłówek listy jednokierunkowej

Wskaźnik węzła głównego jest podawany jako parametr. Węzeł główny jest usuwany, a następny węzeł staje się nowym węzłem głównym. Pamięć usuniętego węzła musi zostać zwolniona, aby uniknąć wycieków pamięci.

Krok 1) Przypisz następny węzeł głowy jako nową głowę.

Krok 2) Zwolnij przydzieloną pamięć poprzedniego węzła głównego.

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

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

Usuwanie nagłówka połączonej listy

Usuń ogon listy jednokierunkowej

Usunięcie węzła końcowego jest podobne do usunięcia węzła głównego. Różnica polega na tym, że wymagane jest przejście do końca listy. W liście jednokierunkowej węzeł, którego Następny wskaźnik jest NULL, jest to węzeł ogonowy.

Krok 1) Przesuń do momentu tuż przed węzłem końcowym. Zapisz bieżący węzeł.

Krok 2) Zwolnij pamięć następnego węzła (ogona).

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

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

Usuwanie końca listy pojedynczo połączonej

Wyszukiwanie i usuwanie węzła z listy pojedynczo połączonej

Ta funkcja wykonuje dwa zadania: wyszukiwanie i usuwanie. Przechodzi do końca listy. Jeśli zostanie znaleziony pasujący węzeł, usuwa go i ponownie łączy z poprzednim węzłem. Następny wskaźnik.

Krok 1) Przejdź do końca listy. Sprawdź, czy bieżący węzeł jest taki sam, jak węzeł wyszukiwania.

Krok 2) Jeśli znaleziono dopasowanie, zapisz wskaźnik do bieżącego węzła.

Krok 3) Następny poprzedniego węzła staje się następnym węzłem bieżącego węzła.

Krok 4) Usuń bieżący węzeł i zwolnij jego pamięć.

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)

Wyszukaj i usuń węzeł z listy Singly Linked List

Przechodzenie przez listę jednokierunkowo powiązaną

Lista jednokierunkowa obsługuje tylko przechodzenie od początku do końca. Brak wskaźnika do poprzedniego węzła uniemożliwia przechodzenie w tył. Każdy węzeł jest odwiedzany po kolei, wyświetlając swoją wartość aż do osiągnięcia NULL.

Krok 1) Przechodź przez każdy węzeł, aż osiągniesz NULL.

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

function traverse(head):
  while head is not NULL:
    print head.value
    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);
    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);
}

Wydajność

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

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

Wydajność

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. Najgorszy i średni przypadek złożoności czasowej są takie same dla listy jednokierunkowej.

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

• Wstawienie na początku listy można wykonać w tempie O(1). Nie jest wymagane przechodzenie przez listę.
• Wyszukiwanie i usuwanie można wykonać w trybie O(1), jeśli element docelowy znajduje się w węźle głównym.

Średnia złożoność czasowa przypadku:

• Wstawienie do listy powiązanej zajmuje O(n), gdzie n jest całkowitą liczbą elementów.
• Wyszukiwanie i usuwanie również może trwać O(n), ponieważ element docelowy może znajdować się w dowolnym miejscu aż do węzła końcowego.

Złożoność przestrzenna listy jednokierunkowo powiązanej

Lista jednokierunkowa dynamicznie przydziela pamięć. Do przechowywania n elementy, przydziela n jednostek pamięci. Zatem złożoność przestrzenna wynosi O(n).

Zastosowania listy jednokierunkowo powiązanej

Listy jednokierunkowo powiązane pojawiają się w wielu miejscach, w których przydatne jest przeglądanie tylko do przodu i pamięć dynamiczna:

• Stosy i kolejki: Podstawowa pamięć masowa dla stosów LIFO i kolejek FIFO zbudowanych z węzłów.
• Łańcuchowanie tablic mieszających: Kolizje rozwiązuje się poprzez łączenie wpisów w pojedynczo powiązaną listę według kontenera.
• Listy sąsiedztwa: W grafach rzadkich dla każdego wierzchołka stosowana jest pojedynczo powiązana lista sąsiadów.
• Tabele symboli: Kompilatory i interpretatory łączą identyfikatory w pojedynczo powiązaną listę według zakresu.
• Alokatory pamięci: Alokatory list wolnych track wolnych bloków jako lista jednokierunkowo powiązana.

FAQ