C Academy · Oppitunti

Yksisuuntaiset linkitetyt listat

Solmut ja osoittimet.

Oppitunti 1/413 vaihetta

Yksisuuntaiset linkitetyt listat on ilmainen C Academy-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu C Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. C Academy-kurssilla on yhteensä 4 oppituntia.

Mikä on linkitetty lista?

Linkitetty lista on ketju pieniä rakenteita, joita kutsutaan solmuiksi. Jokainen solmu sisältää arvon ja osoittimen seuraavaan solmuun.

Toisin kuin taulukon alkioiden, solmujen ei tarvitse sijaita peräkkäin muistissa, ja listaa voi kasvattaa tai pienentää helposti.

#include <stdio.h>

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

int main(void) {
    printf("A node holds a value and a next pointer\n");
    return 0;
}

Solmun määrittäminen

Solmurakenne sisältää datan sekä seuraavaan solmuun osoittavan struct Node *next -jäsenen.

Osoitintyyppi viittaa samaan rakenteeseen, mikä mahdollistaa solmujen ketjuttamisen.

#include <stdio.h>

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

int main(void) {
    struct Node n;
    n.value = 42;
    n.next = NULL;
    printf("value=%d, next is NULL: %d\n", n.value, n.next == NULL);
    return 0;
}

Pääosoitin

Lista tunnistetaan yhdestä osoittimesta, joka osoittaa sen ensimmäiseen solmuun. Tätä kutsutaan pääksi (head).

Tyhjä lista tarkoittaa yksinkertaisesti sitä, että head on arvoltaan NULL.

#include <stdio.h>

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

int main(void) {
    struct Node *head = NULL;
    printf("List is empty: %d\n", head == NULL);
    return 0;
}

Solmun varaaminen

Solmut luodaan yleensä keosta malloc-funktion avulla, jotta ne säilyvät luovan funktion suorituksen päätyttyä.

Tarkistakaa aina palautusarvo ja muistakaa vapauttaa solmut myöhemmin.

#include <stdio.h>
#include <stdlib.h>

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

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 7;
    n->next = NULL;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Nuolioperaattori

Kun teillä on osoitin rakenteeseen, käyttäkää jäsenten käsittelyyn operaattoria ->. n->value tarkoittaa samaa kuin (*n).value.

Tulette käyttämään nuolioperaattoria jatkuvasti linkitettyjen listojen kanssa.

#include <stdio.h>
#include <stdlib.h>

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

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 99;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Kahden solmun linkittäminen

Yhdistääksenne solmut asettakaa ensimmäisen solmun next osoittamaan toiseen solmuun. Viimeisen solmun next pysyy arvossa NULL merkitsemässä listan loppua.

#include <stdio.h>
#include <stdlib.h>

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

int main(void) {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    a->value = 1; a->next = b;
    b->value = 2; b->next = NULL;
    printf("%d -> %d\n", a->value, a->next->value);
    free(a); free(b);
    return 0;
}

Apufunktio solmujen luomiseen

Muistin varaaminen toistuvasti on työlästä, joten käärikää se apufunktioon, joka varaa muistin, alustaa uuden solmun ja palauttaa sen.

#include <stdio.h>
#include <stdlib.h>

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

struct Node *make(int v) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = v;
    n->next = NULL;
    return n;
}

int main(void) {
    struct Node *n = make(5);
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Pienen listan rakentaminen

Rakentakaa apufunktion avulla kolmen solmun lista 1 -> 2 -> 3 ketjuttamalla next-osoittimet.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    printf("%d %d %d\n", head->value, head->next->value, head->next->next->value);
    return 0;
}

Listan tulostaminen

Tulostaaksenne jokaisen arvon aloittakaa head-solmusta ja seuratkaa next-osoittimia, kunnes saavutatte arvon NULL.

Tämä läpikäyntimalli on lähes kaikkien listaoperaatioiden perusta.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    for (struct Node *p = head; p; p = p->next)
        printf("%d ", p->value);
    printf("\n");
    return 0;
}

Taulukot ja linkitetyt listat

Taulukot tarjoavat nopean indeksipääsyn, mutta niiden koko on kiinteä. Linkitetyissä listoissa alkioiden lisääminen ja poistaminen on helppoa, mutta niiden käyttö on hitaampaa, koska alkio on saavutettava kävelemällä listan läpi.

Valitkaa ratkaisu sen perusteella, mitkä operaatiot ovat ohjelmassanne yleisimpiä.

#include <stdio.h>

int main(void) {
    printf("Array: O(1) index, costly resize\n");
    printf("List:  O(n) index, cheap insert/delete\n");
    return 0;
}

Koko listan vapauttaminen

Jokainen malloc-varattu solmu on vapautettava. Käykää lista läpi, mutta tallentakaa seuraava osoitin ennen kunkin solmun vapauttamista, muuten menetätte ketjun loppuosan.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    struct Node *p = head;
    while (p) {
        struct Node *nxt = p->next;
        free(p);
        p = nxt;
    }
    printf("freed all nodes\n");
    return 0;
}

Pikatarkistus

Testatkaa, miten hyvin ymmärrätte linkitetyn listan rakenteen.

Vastaa interaktiivisessa oppitunnissa

Kertaus

Opitte yksihaaraisten linkitettyjen listojen perusteet:

Solmu sisältää arvon ja next-osoittimen; head osoittaa ensimmäiseen solmuun.
Varatkaa solmut malloc-funktiolla ja käsitelkää jäseniä ->-operaattorilla.
Viimeisen solmun next on NULL; käykää lista läpi seuraamalla osoittimia.
Vapauttakaa aina jokainen solmu ja tallentakaa next ennen vapauttamista.

Aloita maksutta

Opi C tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 39
Oppitunnit: 144

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Yksisuuntaiset linkitetyt listat” ilmainen?

Kyllä – oppitunnin ”Yksisuuntaiset linkitetyt listat” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko C Academy-kurssin, päivitä CoddyKit PROhon. C Academy-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Yksisuuntaiset linkitetyt listat”?

Solmut ja osoittimet. Harjoittelet C Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni C Academy-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin C Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.

Kuinka kauan ”Yksisuuntaiset linkitetyt listat”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä C Academy-oppitunnilla?

Kyllä. Jokainen C Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

← Takaisin: C Academy