std::list

Angol

Főnév

(informatika) Az std::list a C++ Standard Template Library (STL) egyik konténere, amely kettős láncolt listát valósít meg. Minden elem külön memóriablokkban van eltárolva, és minden elem tartalmaz:

egy előző elemre mutató pointert,
egy következő elemre mutató pointert,
magát az adatot.

NULL <- [ data | prev | next ] <-> [ data | prev | next ] <-> [ data | prev | next ] -> NULL

Különbség más konténerektől

Nem szomszédos memóriában tárolja az elemeket (ellentétben pl. std::vector-ral).
Nem támogat véletlenszerű hozzáférést indexeléssel (list[3] nem lehetséges).
Hatékony beszúrás és törlés tetszőleges helyen.

Hogyan használjuk?

Fejléc

#include <list>

Deklaráció

std::list<int> myList;

Alapműveletek

myList.push_back(10);  // hozzáad hátulra
myList.push_front(5);  // hozzáad előre
myList.pop_back();     // utolsó elem törlése
myList.pop_front();    // első elem törlése

Iterálás

for (auto it = myList.begin(); it != myList.end(); ++it) {
    std::cout << *it << " ";
}

vagy modern C++:

for (int value : myList) {
    std::cout << value << " ";
}

Fontos metódusok

Metódus	Funkció
`push_back(value)`	Hozzáadás a lista végére
`push_front(value)`	Hozzáadás az elejére
`pop_back()`	Utolsó elem törlése
`pop_front()`	Első elem törlése
`insert(pos, value)`	Elem beszúrása a pozíció előtt
`erase(pos)`	Adott pozíciójú elem törlése
`size()`	Lista mérete
`empty()`	Üres-e a lista?
`clear()`	Összes elem törlése
`reverse()`	Lista megfordítása
`sort()`	Rendezés (csak ha az elemek összehasonlíthatók)
`unique()`	Egymást követő duplikált elemek törlése
`remove(value)`	Minden előfordulás törlése

Iterator típusok

Az std::list teljesen támogatja az STL iterátor modellt:

begin() → az első elemre mutató iterator
end() → a lista végét jelző iterator (utolsó elem után)

További típusok:

rbegin() / rend() → fordított irányú iterátorok (reverse iterátorok)
cbegin() / cend() → konstans iterátorok (nem lehet velük módosítani az elemeket)

Példa

#include <iostream>
#include <list>

int main() {
    std::list<int> numbers = {3, 1, 4, 1, 5, 9};

    numbers.push_front(2);
    numbers.push_back(6);

    std::cout << "List elements: ";
    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    numbers.sort();
    std::cout << "Sorted list: ";
    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    numbers.unique();  // Duplikáltak törlése
    std::cout << "Unique list: ";
    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

Előnyök és hátrányok

✅ Előnyök

Hatékony beszúrás és törlés bárhol (O(1), ha iterátor adott)
Stabil iterátorok (más elemek hozzáadása/törlése nem érvényteleníti őket)
Kényelmes megfordítás (reverse()) és rendezés (sort())
Jó FIFO vagy LIFO adatstruktúrákhoz (pl. queue, stack)

❌ Hátrányok

Nincs véletlenszerű hozzáférés → nem tudsz list[5]-öt írni → O(n) idő, ha keresni akarsz
Magasabb memóriahasználat (minden elemhez két pointer kell)
Általános lineáris hozzáférési idő (ellentétben a vector O(1) indexelésével)
Iteráció lassabb, mert nem szomszédos memóriában vannak az elemek

Mikor használjunk `std::list`-et?

Használható, ha:

gyakran kell beszúrni vagy törölni a lista közepén vagy elején.
fontos, hogy iterátorok érvényesek maradjanak a módosítások után.
FIFO (queue) vagy LIFO (stack) viselkedést akarsz.

Ne használd, ha:

gyakori indexalapú elérés kell (használj inkább std::vector-t).
memóriatakarékosság fontos.
nagyon nagy lista, amit sokszor bejársz (vector cache-barátabb).

Tipikus alkalmazások

Queue / FIFO implementációk
Undo / redo lista (pl. szövegszerkesztőkben)
Stack alternatíva
Folyamatosan változó lista (beszúrások, törlések tetszőleges helyen)

std::list vs std::vector

Jellemző	std::list	std::vector
Véletlenszerű hozzáférés	Lassú (O(n))	Gyors (O(1))
Beszúrás/törlés középen	Gyors (O(1), ha iterátor adott)	Lassú (O(n))
Memóriakezelés	Lassabb, több pointer	Cache-barát, tömbalapú
Iterátor stabilitás	Magas	Csak bizonyos esetekben stabil
FIFO / LIFO	Nagyon jó	Lehetséges, de nem optimális

Összefoglalás

Az std::list egy kettős láncolt lista implementációja a C++ STL-ben.
Kiemelkedően jó, ha gyakran kell elemeket beszúrni/törölni a lista tetszőleges pontján.
Cserébe lassú az indexalapú elérés, és nagyobb a memóriaigénye.
Modern C++-ban sok esetben a std::vector jobb választás, de az std::list-nek megvannak a maga speciális helyei.

Aranyszabály: 👉 Ha szekvenciális feldolgozás és gyakori szerkesztés kell → std::list 👉 Ha gyors hozzáférés index alapján kell → std::vector

További információk

std::list - Szótár.net (en-hu)
std::list - Sztaki (en-hu)
std::list - Merriam–Webster
std::list - Cambridge
std::list - WordNet
std::list - Яндекс (en-ru)
std::list - Google (en-hu)
std::list - Wikidata
std::list - Wikipédia (angol)