Ugrás a tartalomhoz

singly linked list

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

singly linked list (tsz. singly linked lists)

  1. (informatika) egyszeresen láncolt lista

Egy egyszeresen láncolt lista (singly linked list) egy dinamikusan allokált adatszerkezet, amely csomópontokból (node-okból) áll. Minden csomópont egy adatmezőt és egy mutatót a következő elemre tartalmaz. Az első csomópontot fejnek (head) nevezzük, az utolsót pedig faroknak (tail), amelynek a következőre mutató értéke nullptr.


Egyszerű C++ implementáció egy alapvető osztállyal

#include <iostream>

// Csomópont struktúra
struct Node {
    int data;
    Node* next;
    
    Node(int d) : data(d), next(nullptr) {} // Konstruktor
};

// Láncolt lista osztály
class SinglyLinkedList {
private:
    Node* head; // Fej csomópont

public:
    SinglyLinkedList() : head(nullptr) {} // Konstruktor
    
    // Új elem beszúrása a lista elejére
    void insertAtBeginning(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    // Új elem beszúrása a lista végére
    void insertAtEnd(int value) {
        Node* newNode = new Node(value);
        if (!head) { // Ha üres a lista
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) { // Utolsó elem megkeresése
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // Adott érték törlése a listából
    void deleteValue(int value) {
        if (!head) return; // Ha üres a lista

        if (head->data == value) { // Ha az első elem a törlendő
            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) { // Ha megtaláltuk az elemet
            Node* toDelete = temp->next;
            temp->next = temp->next->next;
            delete toDelete;
        }
    }

    // Lista kiírása
    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "nullptr" << std::endl;
    }

    // Destruktor (memóriaszivárgás elkerülése)
    ~SinglyLinkedList() {
        Node* temp;
        while (head) {
            temp = head;
            head = head->next;
            delete temp;
        }
    }
};

// Főprogram
int main() {
    SinglyLinkedList list;
    
    list.insertAtBeginning(3);
    list.insertAtBeginning(2);
    list.insertAtBeginning(1);
    
    list.insertAtEnd(4);
    list.insertAtEnd(5);

    std::cout << "Lista elemei: ";
    list.printList();

    list.deleteValue(3);
    std::cout << "3-as törlése után: ";
    list.printList();

    return 0;
}

Magyarázat

  1. Beszúrás az elejére (insertAtBeginning): Új csomópontot hoz létre, és a meglévő head mutatót átállítja az új elemre.
  2. Beszúrás a végére (insertAtEnd): Végigiterál a listán, és az utolsó elem next mutatóját beállítja az új csomópontra.
  3. Törlés (deleteValue): Megkeresi az adott értéket és eltávolítja a listából.
  4. Kiíratás (printList): Végigmegy a listán, és kiírja az elemeket.
  5. Destruktor (~SinglyLinkedList): Törli az összes csomópontot, hogy elkerülje a memóriaszivárgást.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=singly_linked_list&oldid=3490136”