Egyszeresen láncolt lista

Románul: listă simplu înlănțuită, angolul: singly linked list.

Az elemek nem feltétlenül egymás mellett helyezkednek el a memóriában, helyette minden elem tárolja az értéke mellett a következő elem címét is.

Pl. a 24, 36, 5 sorozat tárolása:

--> [24, *]          [36, *]   [5, NULL]
         +-----------^    +----^

Kódban:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include <iostream>
using namespace std;

struct Node  // egy csomópontja a listának
{
    int ertek;
    Node *next;
};

void kiir(Node *fej)
{
    Node *akt = fej;

    while (akt != NULL) {
        cout << akt->ertek << " ";
        akt = akt->next;
    }
    cout << endl;
}


void beszur_elejere(Node* &fej, int uj_ertek)
{
    Node *uj = new Node;
    uj->ertek = uj_ertek;
    uj->next = fej;

    fej = uj;
}

// adott indexű elem elérése (nem hatékony)
int k_adik_elem(Node *fej, int k)
{
    Node *akt = fej;

    while (k > 0 && akt != NULL) {
        akt = akt->next;
        k--;
    }

    if (akt == NULL) {
        cout << "baj van" << endl;
        return 0;
    }
    else {
        return akt->ertek;
    }
}

void torol_elejerol(Node* &fej)
{
    // ha nem üres, töröljük az első elemét
    // ha üres, akkor maradjon üres
    if (fej == NULL)
        return;

    Node* torolni = fej;
    fej = fej->next;
    delete torolni;
}


int main()
{
    // létrehozás
    Node *n1 = new Node;
    Node *n2 = new Node;
    Node *n3 = new Node;

    n1->ertek = 24;
    n1->next = n2;

    n2->ertek = 36;
    n2->next = n3;

    n3->ertek = 5;
    n3->next = NULL; // spec. érték (0), jelzi, hogy
                     // nincs következő

    /*
    --> [24, *]          [36, *]   [5, NULL]
             +-----------^    +----^
    */

    Node *fej = n1; // a lista feje (eleje)

    kiir(fej);

    beszur_elejere(fej, 1000);

    kiir(fej); // 1000 24 36 5
    /*
    cout << k_adik_elem(fej, 2) << endl; // 36
    cout << k_adik_elem(fej, 0) << endl; // 1000

    cout << k_adik_elem(fej, 30) << endl; // 0
    */

    torol_elejerol(fej);
    torol_elejerol(fej);

    kiir(fej); // 36 5

    return 0;
}

Beszúrás a lista végére:

lehetőség: elmegyünk elemenként a végéig bekötünk utána egy új elemet
lehetőség: folyamatosan könyveljük azt is, hogy hol van a lista utolsó eleme

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
using namespace std;

struct Node  // egy csomópontja a listának
{
    int ertek;
    Node *next;
};

struct Lista
{
    Node *fej;
    Node *utolso;
};

void kiir(Lista &lista)
{
    Node *akt = lista.fej;

    while (akt != NULL) {
        cout << akt->ertek << " ";
        akt = akt->next;
    }
    cout << endl;
}

void beszur_elejere(Lista &lista, int uj_ertek)
{
    Node *uj = new Node;
    uj->ertek = uj_ertek;
    uj->next = lista.fej;

    if (lista.fej == NULL)
        lista.utolso = uj;

    lista.fej = uj;
}

// adott indexű elem elérése (nem hatékony)
int k_adik_elem(Lista &lista, int k)
{
    Node *akt = lista.fej;

    while (k > 0 && akt != NULL) {
        akt = akt->next;
        k--;
    }

    if (akt == NULL) {
        cout << "baj van" << endl;
        return 0;
    }
    else {
        return akt->ertek;
    }
}

void torol_elejerol(Lista &lista)
{
    // ha nem üres, töröljük az első elemét
    // ha üres, akkor maradjon üres
    if (lista.fej == NULL)
        return;

    Node* torolni = lista.fej;
    lista.fej = lista.fej->next;
    if (lista.fej == NULL)
        lista.utolso = NULL;
    delete torolni;
}

Lista letrehoz_ures()
{
    Lista lista;
    lista.fej = NULL;
    lista.utolso = NULL;
    return lista;
}

void beszur_vegere(Lista &lista, int uj_ertek)
{
    Node *uj = new Node;
    uj->ertek = uj_ertek;
    uj->next = NULL;

    if (lista.utolso == NULL) {
        lista.fej = uj;
        lista.utolso = uj;
    }
    else {
        lista.utolso->next = uj;
        lista.utolso = uj;
    }
}

int main()
{
    Lista lista = letrehoz_ures();

    beszur_vegere(lista, 2);
    beszur_vegere(lista, 3);
    beszur_vegere(lista, 4);

    kiir(lista); // 2 3 4

    beszur_elejere(lista, 1);

    kiir(lista); // 1 2 3 4

    torol_elejerol(lista);
    torol_elejerol(lista);

    kiir(lista); // 3 4

    return 0;
}

Duplán láncolt listák

               +---------v       +------v
--> [NULL, 20, * ]       [ *, 2, * ]    [ *, 9, NULL]
    ^----------------------+              |
                         ^----------------+

    20  <->  2  <->  9

Kódban:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;

struct Node
{
    int ertek;
    Node *prev;
    Node *next;
};

int main()
{
    // építsük fel a 10, 20 elemeket
    // tartalmazó listát:

    Node *n1 = new Node;
    Node *n2 = new Node;

    n1->ertek = 10;
    n2->ertek = 20;

    n1->prev = NULL;
    n1->next = n2;

    n2->prev = n1;
    n2->next = NULL;

    Node *fej = n1;
    // ....

    return 0;
}

Absztrakt adatszerkezetek:

Az „absztrakt” szó arra utal, hogy nem azt adjuk meg, hogy hogy lesz tárolva, hanem csak milyen viselkedést várunk el tőle.

verem:

absztrakt adatszerkezet, elemeket tárol,
műveletek:
- elem betevése
- elem törlése
- melyik elem van a tetején?
viselkedés: LIFO sorrendben történnek (last in, first out) == amelyik elem legutóbb került be, azt fogjuk először kivenni

sor:

absztrakt adatszerkezet, elemeket tárol,
műveletek:
- elem betevése
- elem törlése
- melyik lenne a következő kivett elem?
viselkedés: FIFO sorrendben történnek (first in, first out) == amelyik elem legrégebben került be, azt fogjuk először kivenni

Következik: verem és sor implementálása

tömbbel
láncolással (egyszeresen láncolt listával)

Verem implementálása tömbbel

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// a végére teszünk be és a végéről
// törlünk

// * * * * * _ _ _ _ _
//           ^ide jön be az új
#include <iostream>
using namespace std;

struct Verem
{
    int elemek[1000];
    int n;
};

void init(Verem &v)
{
    v.n = 0;
}

// betesz egy elemet a verem végére
void push(Verem &v, int ertek)
{
    v.elemek[v.n] = ertek;
    v.n++;
}

// kivesz egy elemet a verem végéről
int pop(Verem &v)
{
    if (v.n == 0) {
        cout << "hiba";
        return 0;
    }

    int ertek = v.elemek[v.n - 1];
    v.n--;
    return ertek;
}

// visszatéríti a tetején levő elemet
int top(Verem &v)
{
    if (v.n == 0) {
        cout << "hiba";
        return 0;
    }

    return v.elemek[v.n - 1];
}

int main ()
{
    Verem x;
    init(x);

    push(x, 10);
    push(x, 20);
    push(x, 30);

    cout << top(x) << endl; // 30
    cout << pop(x) << endl; // 30
    cout << pop(x) << endl; // 20
    cout << pop(x) << endl; // 10

    return 0;
}

Verem implementálása láncolt listával

elég lesz egyszeres láncolás
a lista eleje lesz a verem teteje

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
using namespace std;

struct Node
{
    int ertek;
    Node *next;
};

void init(Node* &v)
{
    v = NULL;
}

void push(Node* &v, int ertek)
{
    Node *uj = new Node;
    uj->ertek = ertek;
    uj->next = v;
    v = uj;
}

int pop(Node* &v)
{
    if (v == NULL) {
        cout << "hiba";
        return 0;
    }

    int ertek = v->ertek;
    Node* torolni = v;

    v = v->next;

    delete torolni;
    return ertek;
}

int top(Node* &v)
{
    if (v == NULL) {
        cout << "hiba";
        return 0;
    }

    return v->ertek;
}

int main()
{
    Node *verem;

    push(verem, 10);
    push(verem, 20);
    push(verem, 30);

    cout << top(verem) << endl; // 30
    cout << pop(verem) << endl; // 30
    cout << pop(verem) << endl; // 20
    cout << pop(verem) << endl; // 10

    return 0;
}

Sor implementálása tömbbel

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
using namespace std;

struct Sor
{
    int elemek[1000];
    int bal, jobb;
};

void init(Sor &s)
{
    s.bal = 0;
    s.jobb = -1;
}

void push(Sor &s, int ertek)
{
    s.jobb++;
    s.elemek[s.jobb] = ertek;
}

int pop(Sor &s)
{
    if (s.bal > s.jobb) {
        cout << "hiba";
        return 0;
    }

    s.bal++;
    return s.elemek[s.bal-1];
}


int main ()
{
    Sor s;
    init(s);

    push(s, 10);
    push(s, 20);
    push(s, 30);

    cout << pop(s) << endl; // 10
    cout << pop(s) << endl; // 20
    cout << pop(s) << endl; // 30

    // pop(s); // hiba

    return 0;
}

Sor implementálása láncolt listával

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
using namespace std;

struct Node
{
    int ertek;
    Node *next;
};

struct Sor
{
    Node *elso;
    Node *utolso;
};

void init(Sor &s)
{
    s.elso = NULL;
    s.utolso = NULL;
}

int pop(Sor &s)
{
    if (s.elso == NULL) {
        cout << "hiba" << endl;
        return 0;
    }


    Node* torolni = s.elso;
    s.elso = s.elso->next;
    if (s.elso == NULL)
        s.utolso = NULL;

    int ertek = torolni->ertek;
    delete torolni;
    return ertek;
}

void push(Sor &s, int uj_ertek)
{
    Node *uj = new Node;
    uj->ertek = uj_ertek;
    uj->next = NULL;

    if (s.utolso == NULL) {
        s.elso = uj;
        s.utolso = uj;
    }
    else {
        s.utolso->next = uj;
        s.utolso = uj;
    }
}

int main ()
{
    Sor s;
    init(s);

    push(s, 10);
    push(s, 20);
    push(s, 30);

    cout << pop(s) << endl; // 10
    cout << pop(s) << endl; // 20

    push(s, 40);

    cout << pop(s) << endl; // 30
    cout << pop(s) << endl; // 40

    // pop(s); // hiba

    return 0;
}