Listy wskaźnikowe to dynamiczne struktury danych, które są szeroko stosowane w programowaniu ze względu na swoją elastyczność i wydajność. W tej lekcji szczegółowo omówimy trzy podstawowe typy list wskaźnikowych: listy jednokierunkowe, dwukierunkowe i cykliczne. Każda z tych struktur ma swoje unikalne cechy, zalety i zastosowania, a zrozumienie ich działania i implementacji jest kluczowe dla efektywnego wykorzystania dynamicznych struktur danych.

Listy jednokierunkowe (Singly Linked Lists)

Lista jednokierunkowa to najprostszy typ listy wskaźnikowej, w której każdy węzeł zawiera wartość oraz wskaźnik na następny węzeł. Ostatni węzeł w liście wskazuje na nullptr, co oznacza koniec listy. Listy jednokierunkowe są łatwe do zaimplementowania i efektywne, gdy potrzebujemy jedynie poruszać się w jednym kierunku.

Struktura węzła

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

Każdy węzeł składa się z danych oraz wskaźnika next, który wskazuje na następny węzeł. Głowa (ang. head) listy jest wskaźnikiem na pierwszy węzeł.

Podstawowe operacje na listach jednokierunkowych

• Wstawianie: Możemy wstawiać elementy na początku, na końcu lub w środku listy. Operacja wstawiania na początku ma złożoność O(1), podczas gdy wstawianie na końcu ma złożoność O(n).
• Usuwanie: Usuwanie elementu z początku listy jest szybkie (O(1)), ale usuwanie z końca lub środka wymaga przejścia przez całą listę (O(n)).
• Przeszukiwanie: Przeszukiwanie listy ma złożoność O(n), ponieważ musimy przejść przez każdy węzeł, aby znaleźć element.

Przykład implementacji

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

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

    // Wstawianie na początku
    void insertAtBeginning(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    // Wstawianie na końcu
    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;
    }

    // Usuwanie elementu z początku
    void deleteFromBeginning() {
        if (!head) return;
        Node* temp = head;
        head = head->next;
        delete temp;
    }

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

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

Lista jednokierunkowa jest prostą i efektywną strukturą danych, ale ma pewne ograniczenia. Na przykład, nie możemy łatwo poruszać się wstecz, co może być problematyczne w niektórych zastosowaniach.

Listy dwukierunkowe (Doubly Linked Lists)

Lista dwukierunkowa to rozszerzenie listy jednokierunkowej, w której 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żemy poruszać się w obu kierunkach, co zwiększa elastyczność i ułatwia wykonywanie niektórych operacji, takich jak usuwanie węzła.

Struktura węzła

struct DoublyNode {
    int data; // Wartość przechowywana w węźle
    DoublyNode* next; // Wskaźnik na następny węzeł
    DoublyNode* prev; // Wskaźnik na poprzedni węzeł
    DoublyNode(int value) : data(value), next(nullptr), prev(nullptr) {}
};

Węzły listy dwukierunkowej mają dodatkowy wskaźnik prev, który wskazuje na poprzedni węzeł, co umożliwia poruszanie się wstecz.

Podstawowe operacje na listach dwukierunkowych

• Wstawianie: Wstawianie elementów na początku, na końcu lub w środku listy jest bardziej elastyczne dzięki wskaźnikom next i prev. Złożoność operacji wstawiania jest taka sama jak w przypadku list jednokierunkowych.
• Usuwanie: Usuwanie elementu z listy dwukierunkowej jest prostsze, ponieważ mamy dostęp do poprzedniego węzła, co pozwala na łatwe aktualizowanie wskaźników. Złożoność tej operacji wynosi O(1) po znalezieniu węzła.
• Przeszukiwanie: Przeszukiwanie listy dwukierunkowej ma złożoność O(n), ale możemy poruszać się w obu kierunkach, co zwiększa elastyczność.

Przykład implementacji

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

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

    // Wstawianie na początku
    void insertAtBeginning(int value) {
        DoublyNode* newNode = new DoublyNode(value);
        if (head) {
            head->prev = newNode;
        }
        newNode->next = head;
        head = newNode;
    }

    // Wstawianie na końcu
    void insertAtEnd(int value) {
        DoublyNode* newNode = new DoublyNode(value);
        if (!head) {
            head = newNode;
            return;
        }
        DoublyNode* temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }

    // Usuwanie elementu
    void deleteNode(int value) {
        DoublyNode* temp = head;
        while (temp && temp->data != value) {
            temp = temp->next;
        }
        if (!temp) return;
        if (temp->prev) {
            temp->prev->next = temp->next;
        } else {
            head = temp->next;
        }
        if (temp->next) {
            temp->next->prev = temp->prev;
        }
        delete temp;
    }

    // Wyświetlanie listy
    void display() {
        DoublyNode* temp = head;
        while (temp) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

    ~DoublyLinkedList() {
        DoublyNode* temp;
        while (head) {
            temp = head;
            head = head->next;
            delete temp;
        }
    }
};

Listy dwukierunkowe są bardziej elastyczne niż listy jednokierunkowe, ale wymagają więcej pamięci, ponieważ każdy węzeł przechowuje dodatkowy wskaźnik prev.

Listy cykliczne (Cyclic Lists)

Lista cykliczna to lista, w której ostatni węzeł wskazuje z powrotem na pierwszy węzeł, tworząc zamknięty cykl. Listy cykliczne mogą być jednokierunkowe lub dwukierunkowe i są używane w sytuacjach, gdy potrzebujemy cyklicznie przechodzić przez elementy, na przykład w implementacji kolejek cyklicznych.

Przykład implementacji listy cyklicznej

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

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

    // Wstawianie na końcu
    void insertAtEnd(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
            head->next = head;
            return;
        }
        Node* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = head;
    }

    // Wyświetlanie listy
    void display() {
        if (!head) return;
        Node* temp = head;
        do {
            std::cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
        std::cout << std::endl;
    }

    ~CyclicLinkedList() {
        if (!head) return;
        Node* temp = head;
        do {
            Node* nextNode = temp->next;
            delete temp;
            temp = nextNode;
        } while (temp != head);
    }
};

W przypadku list cyklicznych musimy uważać, aby nie wpaść w nieskończoną pętlę podczas iterowania przez elementy. Cykliczne listy są użyteczne w aplikacjach, gdzie wymagane jest cykliczne przechodzenie przez elementy, na przykład w systemach operacyjnych lub grach.

Porównanie różnych typów list

• Listy jednokierunkowe: Są proste do zaimplementowania i efektywne w przypadku, gdy potrzebujemy jedynie poruszać się w jednym kierunku. Są bardziej pamięciooszczędne niż listy dwukierunkowe.
• Listy dwukierunkowe: Umożliwiają poruszanie się w obu kierunkach, co jest bardziej elastyczne, ale wymagają dodatkowej pamięci na przechowywanie wskaźnika prev. Są lepsze do implementacji bardziej złożonych operacji.
• Listy cykliczne: Są używane w specyficznych sytuacjach, gdy konieczne jest cykliczne przechodzenie przez elementy. Mogą być jednokierunkowe lub dwukierunkowe i wymagają ostrożności przy iterowaniu.

Podsumowanie

Listy wskaźnikowe to potężne i elastyczne struktury danych, które znajdują zastosowanie w wielu różnych aplikacjach. W tej lekcji omówiliśmy trzy podstawowe typy list: jednokierunkowe, dwukierunkowe i cykliczne. Każdy z tych typów ma swoje zalety i wady, a wybór odpowiedniej struktury zależy od specyficznych wymagań aplikacji. Dzięki tej wiedzy będziesz mógł efektywnie implementować i wykorzystywać listy wskaźnikowe w swoich projektach.

Następny temat ==> Kolejki i stosy