linked list (tsz. linked lists)
A láncolt lista (linked list) egy dinamikus adatszerkezet, amely csomópontokból (node-okból) áll. Minden csomópont tartalmaz egy adatmezőt és egy mutatót a következő elemre. A láncolt listák lehetnek: 1. Egyszeresen láncolt lista (Singly Linked List - SLL) 2. Kétszeresen láncolt lista (Doubly Linked List - DLL) 3. Ciklikus láncolt lista (Circular Linked List - CLL)
Az egyszeresen láncolt lista minden csomópontja egy mutatóval rendelkezik a következő elemre.
#include <iostream>
// Csomópont struktúra
struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {} // Konstruktor
};
// Egyszeresen láncolt lista osztály
class SinglyLinkedList {
private:
Node* head; // Fej csomópont
public:
SinglyLinkedList() : head(nullptr) {}
// Ú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) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
// Adott érték törlése a listából
void deleteValue(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* 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;
}
Lista elemei: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr 3-as törlése után: 1 -> 2 -> 4 -> 5 -> nullptr
✅ O(1) beszúrás az elejére,
✅ O(n) beszúrás a végére (végig kell iterálni),
✅ O(n) törlés és keresés,
✅ Dinamikusan növekszik, nincs fix méret.
A kétszeresen láncolt lista minden csomópontja tartalmaz egy mutatót az előző és egy mutatót a következő elemre.
#include <iostream>
// Csomópont struktúra
struct Node {
int data;
Node* next;
Node* prev;
Node(int d) : data(d), next(nullptr), prev(nullptr) {}
};
// Kétszeresen láncolt lista osztály
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// Beszúrás a lista elejére
void insertAtBeginning(int value) {
Node* newNode = new Node(value);
if (!head) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
// Beszúrás a lista végére
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (!tail) {
head = tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
}
// Lista kiírása előre és visszafelé
void printList() {
Node* temp = head;
std::cout << "Lista előrefelé: ";
while (temp) {
std::cout << temp->data << " <-> ";
temp = temp->next;
}
std::cout << "nullptr\n";
}
// Destruktor
~DoublyLinkedList() {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
}
};
// Főprogram
int main() {
DoublyLinkedList list;
list.insertAtBeginning(2);
list.insertAtBeginning(1);
list.insertAtEnd(3);
list.insertAtEnd(4);
list.printList();
return 0;
}
Lista előrefelé: 1 <-> 2 <-> 3 <-> 4 <-> nullptr
✅ Gyors előre és hátra iteráció
✅ O(1) beszúrás az elejére és végére
✅ O(n) keresés és törlés
A ciklikus láncolt listában az utolsó elem a fejre mutat, így a lista nem ér véget.
Felhasználási területek: - Körkörös buffer (pl. CPU ütemezés). - Játékokban szereplő játékosok ciklikus kezelése.
Ha szeretnéd, megmutathatok egy ciklikus láncolt lista implementációt is! 🚀
| Láncolt lista típusa | Előnyök | Hátrányok |
|---|---|---|
| Egyszeresen láncolt lista | Egyszerű, kevesebb memória | Lassú visszafelé keresés |
| Kétszeresen láncolt lista | Kényelmes előre-hátra iteráció | Több memória kell (prev pointer)
|
| Ciklikus láncolt lista | Nem kell ellenőrizni a végét | Bonyolultabb megvalósítás |