Listy wskaźnikowe to jedne z najważniejszych dynamicznych struktur danych, które umożliwiają elastyczne zarządzanie pamięcią i szybkie wstawianie oraz usuwanie elementów. W przeciwieństwie do tablic, listy wskaźnikowe nie wymagają alokowania z góry określonej ilości pamięci, co czyni je bardzo użytecznymi w sytuacjach, gdy liczba elementów w strukturze danych może się zmieniać w czasie działania programu. W tej lekcji szczegółowo omówimy, jak implementować różne rodzaje list wskaźnikowych, takie jak listy jednokierunkowe, dwukierunkowe i cykliczne. Przedstawimy również podstawowe operacje, które można na nich wykonywać, w tym wstawianie, usuwanie i przeszukiwanie, oraz omówimy najlepsze praktyki, które należy stosować podczas pracy z listami wskaźnikowymi.

Podstawowa struktura listy jednokierunkowej

Lista jednokierunkowa (ang. singly linked list) składa się z serii węzłów, z których każdy zawiera wartość oraz wskaźnik na następny węzeł. Ostatni węzeł w liście wskazuje na null, co oznacza koniec listy. Oto, jak wygląda podstawowa definicja struktury węzła w języku C++:

struct Node {
    int data; // Przechowuje wartość
    Node* next; // Wskaźnik na następny węzeł
    Node(int value) : data(value), next(nullptr) {}
};

Węzeł składa się z dwóch części: danych (wartość) oraz wskaźnika next, który wskazuje na kolejny węzeł w liście. W konstruktorze węzła inicjalizujemy wartość oraz ustawiamy wskaźnik next na nullptr, co oznacza, że nowo utworzony węzeł nie wskazuje na żaden inny węzeł.

Tworzenie listy jednokierunkowej

Aby utworzyć listę jednokierunkową, potrzebujemy wskaźnika na pierwszy węzeł, zwanego głową (ang. head). Oto przykład klasy implementującej listę jednokierunkową:

class SinglyLinkedList {
private:
    Node* head; // Wskaźnik na pierwszy węzeł

public:
    SinglyLinkedList() : head(nullptr) {}

    // Metoda do wstawiania nowego węzła na początku listy
    void insertAtBeginning(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    // Metoda do wstawiania nowego węzła na końcu listy
    void insertAtEnd(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // Metoda do wyświetlania listy
    void display() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

    // Metoda do usuwania węzła z listy
    void deleteNode(int value) {
        if (!head) return;
        if (head->data == value) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }
        Node* temp = head;
        while (temp->next && temp->next->data != value) {
            temp = temp->next;
        }
        if (temp->next) {
            Node* nodeToDelete = temp->next;
            temp->next = temp->next->next;
            delete nodeToDelete;
        }
    }

    ~SinglyLinkedList() {
        Node* temp;
        while (head) {
            temp = head;
            head = head->next;
            delete temp;
        }
    }
};

W powyższym przykładzie zdefiniowaliśmy klasę SinglyLinkedList, która zawiera metody do wstawiania węzłów na początku i na końcu listy, wyświetlania listy oraz usuwania węzłów. Konstruktor klasy inicjalizuje wskaźnik head jako nullptr, a destruktor zwalnia pamięć zajmowaną przez węzły, aby uniknąć przecieków pamięci.

Podstawowe operacje na listach wskaźnikowych

Listy wskaźnikowe pozwalają na wykonywanie różnych operacji, takich jak:

• Wstawianie: Możemy wstawiać nowe węzły na początku, na końcu lub w dowolnym miejscu listy.
• Usuwanie: Możemy usuwać węzły z listy na podstawie wartości lub pozycji.
• Przeszukiwanie: Możemy przeszukiwać listę, aby znaleźć węzeł o określonej wartości.
• Wyświetlanie: Możemy iterować przez listę i wyświetlać wartości wszystkich węzłów.

Wstawianie węzłów

Wstawianie węzłów na początku listy jest bardzo szybkie i ma złożoność czasową O(1). Wstawianie węzłów na końcu listy wymaga przejścia przez całą listę, co ma złożoność O(n). W przypadku wstawiania w dowolnym miejscu musimy najpierw znaleźć odpowiednią pozycję, co również ma złożoność O(n).

Usuwanie węzłów

Usuwanie węzła wymaga znalezienia węzła poprzedzającego węzeł, który chcemy usunąć. Złożoność czasowa tej operacji wynosi O(n) w najgorszym przypadku. Jeśli węzeł, który chcemy usunąć, znajduje się na początku listy, operacja ma złożoność O(1).

Listy dwukierunkowe (Doubly Linked Lists)

Listy dwukierunkowe to rozszerzenie list jednokierunkowych, w których każdy węzeł zawiera dwa wskaźniki: jeden wskazujący na następny węzeł i drugi wskazujący na poprzedni węzeł. Dzięki temu można łatwiej nawigować w obu kierunkach, co sprawia, że niektóre operacje, takie jak usuwanie węzła, są bardziej efektywne.

struct DoublyNode {
    int data;
    DoublyNode* next;
    DoublyNode* prev;
    DoublyNode(int value) : data(value), next(nullptr), prev(nullptr) {}
};

Każdy węzeł w liście dwukierunkowej ma wskaźnik next wskazujący na następny węzeł oraz wskaźnik prev wskazujący na poprzedni węzeł. Dzięki temu możemy poruszać się po liście w obu kierunkach.

Implementacja listy dwukierunkowej

class DoublyLinkedList {
private:
    DoublyNode* head;

public:
    DoublyLinkedList() : head(nullptr) {}

    // Metoda do wstawiania nowego węzła na początku listy
    void insertAtBeginning(int value) {
        DoublyNode* newNode = new DoublyNode(value);
        if (head) {
            head->prev = newNode;
        }
        newNode->next = head;
        head = newNode;
    }

    // Metoda do wyświetlania listy od początku do końca
    void displayForward() {
        DoublyNode* temp = head;
        while (temp) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

    // Destruktor zwalniający pamięć
    ~DoublyLinkedList() {
        DoublyNode* temp;
        while (head) {
            temp = head;
            head = head->next;
            delete temp;
        }
    }
};

W przypadku list dwukierunkowych możemy łatwiej usuwać węzły, ponieważ mamy bezpośredni dostęp do węzła poprzedzającego, co upraszcza operację usuwania. Listy dwukierunkowe są jednak bardziej złożone i wymagają dodatkowej pamięci na przechowywanie wskaźnika prev.

Listy cykliczne

Listy cykliczne to listy, w których ostatni węzeł wskazuje z powrotem na pierwszy węzeł, tworząc zamknięty cykl. Mogą być jednokierunkowe lub dwukierunkowe i są używane w sytuacjach, gdy konieczne jest cykliczne przechodzenie przez elementy, na przykład w implementacji kolejek cyklicznych.

Podsumowanie

Listy wskaźnikowe są kluczowymi strukturami danych, które umożliwiają dynamiczne zarządzanie pamięcią i elastyczne operacje na danych. W tej lekcji omówiliśmy różne rodzaje list, ich implementację oraz podstawowe operacje, które można na nich wykonywać. Dzięki tej wiedzy będziesz w stanie tworzyć bardziej zaawansowane struktury danych i optymalizować swoje programy pod kątem wydajności.

Następny temat ==> Podstawowe operacje na listach