Linked Lists

úvod do spojkových zoznamov, jednosmerný spojkový zoznam, CRUD operácie

Polia

  • (slide) O poliach sme prvýkrát hovorili už v zimnom semestri na predmete Základy algoritmizácie a programovania. Sú veľmi užitočné, pretože je do nich možné ukladať typovo rovnaké údaje, pričom v pamäti sú uložené súvislo za sebou (lineárne).

    Array
  • S takto uloženými a reprezentovanými údajmi vie pracovať aj mnoho knižničných funkcií, napr. funkcie z knižnice string.h vedia pracovať s jednorozmernými poliami znakov (reťazcami), funkcie bsearch() a qsort() dokážu vyhľadávať alebo triediť takto uložené údaje, a iné.

  • Jednou z nevýhod polí je však ich fixná veľkosť. Problém teda nastane vtedy, keď budem chcieť do poľa uložiť taký počet položiek, ktorý presahuje veľkosť poľa. S tým už máme bohaté skúsenosti aj zo zadaní, kedy sa síce môže javiť, že je všetko v poriadku, ale až valgrind alebo prípadný Segmentation fault vám prezradí, že je niečo v neporiadku.

  • S týmto problémom súvisí aj operácia vytvorenia poľa. Pretože pole môžem vytvoriť až vtedy, keď viem, koľko prvkov do neho budem ukladať.

  • Ale - ak mi veľkosť poľa nestačí, ako do neho vložím ďalší prvok?

  • (slide) Ďalším problémom, ktorý súvisí s takto orgranizovanými údajmi, je fakt, že vykonávať základné CRUD operácie (Create Retrieve Update Delete) nie je úplne triviálne a obyčajne sú tieto operácie aj veľmi drahé. Ich zložitosť je \[ O(n) \]

  • S niektorými operáciami ste sa priamo stretli počas riešenia zadania K - ako ste postupovali, keď ste napr. potrebovali vložiť prvok na správne miesto v zozname Hall of Fame?

File System

  • Pozrime sa na to, ako je organizované ukladanie súborov v rámci súborového systému na disku. Najprv sa však pokúsme zadefinovať, že čo to vlastne ten súbor je?

  • (slide) Jedna z definícií termínu súbor môže byť:

    In C programming, file is a place on your physical disk where information is stored. (www.programiz.com)

  • Súbory sú teda akési kontajnery na ukladanie údajov, ktoré sa fyzicky nachádzajú uložené na disku.

  • (slide) Súbory nie sú na disku uložené ako jeden kus. Sú rozkúskované a následne uložené v blokoch fixnej dĺžky. Jeden súbor môže teda na disku zaberať vzhľadom na svoju veľkosť niekoľko takýchto blokov.

    File System
  • Ak sa pozrieme na príklad zo slajdu, tak jeden blok má veľkosť 5B. Ak teda chceme uložiť reťazec "Hello, world!" do súboru, bude uložený do 3 takýchto blokov.

  • Tento spôsob ukladania údajov je veľmi výhodný, nakoľko pomocou neho je možné uložiť akékoľvek množstvo údajov (teoreticky súbor o akejkoľvek dĺžke). Stačí len vstupné údaje “rozbiť” do potrebného množstva týchto blokov a v uvedenej (poprepájanej) podobe ich uložiť.

  • Podobný spôsob sa napríklad používa aj pri prenose údajov v sieti, kde sa údaje rozbijú do menších celkov nazvaných pakety. Ak sa jeden stratí alebo sa prenesie poškodený, prijímateľ si ho vyžiada znova na základe čísla chýbajúceho paketu, pričom odosielateľ nemá problém požadovaný paket s údajmi zostaviť opätovným vyseknutím potrebných údajov a preposlať ho.

Linked Lists

  • (slide) Okrem samotných údajov však blok so sebou nesie aj informáciu o tom, kde sa nachádza ďalší blok (ďalšia časť súboru). Týmto spôsobom teda môžeme vytvoriť tzv. spojkový zoznam alebo tiež spájaný zoznam, v ktorom sú jednotlivé bloky navzájom prepojené.

  • Pre úplnosť môžeme povedať, že sme vytvorili jednosmerný spojkový zoznam, pretože sa v zozname vieme po položkách pohybovať len jedným smerom - vieme sa dostať zo začiatku na koniec, ale nevieme sa dostať z konca na začiatok.

  • Ako je však možné takýto prístup reprezentovať v jazyku C?

  • (slide) Ak by sme chceli reprezentovať v jazyku C jeden jeho blok, vyzeral by takto:

    struct node {
        char data[6];
        struct node *next;
    };
  • (slide) Táto štruktúra sa však nevolá block ale node, pretože vychádzame z definície, že:

    linked list is a data structure consisting of a group of nodes which together represent a sequence (Wikipedia)

  • Rovnako je možné takýto zoznam reprezentovať planárnym grafom, kde sa slovo uzol (node) bežne používa.

CRUD

  • (slide) Nad zoznamami nás bude zaujímať niekoľko operácií a to konkrétne:

    • create - vloženie/vytvorenie nového uzla
    • retrieve - získanie/vyhľadanie existujúceho uzla
    • update - aktualizovanie/úprava existujúceho uzla
    • delete - odstránenie existujúceho uzla zo zoznamu
  • (slide) Všetky operácie si demonštrujeme na jednoduchom zozname, ktorý najprv vytvoríme, vložíme do neho nové prvky, niektorý z nich vyhľadáme a nakoniec ho postupne vyprázdnime odstránením jednotlivých prvkov. A celý čas sa budeme okrem toho snažiť udržiavať tento zoznam usporiadaný:

    7 12 19 23 37 52
  • (slide) Takže keď sa v zozname budú nachádzať všetky prvky, bude v pamäti vyzerať takto:

    Linked List from Sequence

Štruktúrovaný údajový typ struct node

  • (slide) Začneme tým, že vytvoríme štruktúru struct node, ktorá bude reprezentovať práve jeden uzol. Bude mať dva prvky:

    • data - samotné údaje, a
    • next - adresu ďalšieho prvku v zozname, pričom typ bude práve ukazovateľ na struct node
  • Kód tejto štruktúry bude vyzerať nasledovne:

    struct node {
       int data;
       struct node* next;
    };

Funkcia traverse()

  • (slide) Ešte predtým, než sa pustíme do implementácie samotných CRUD funkcií, vytvoríme si pomocnú funkciu traverse(). Táto funkcia bude mať jeden parameter, ktorý bude referenciou na prvý prvok zoznamu. Funkcia prejde celým zoznamom a vypíše každý prvok na obrazovku. Samozrejme, ak bude zoznam prázdny (referencia na NULL), nevyíše nič.

  • Zdrojový kód tejteo funkcie môže vyzerať nasledovne:

    void traverse(struct node *head){
        struct node* ptr = head;
        while(ptr != NULL){
            printf("%d\n", ptr->data);
            ptr = ptr->next;
        }
    }

Funkcia append()

  • (slide) Jedna z najzákladnejších funkcií na prácu so zoznamami je určite funkcia append(). Pomocou tejto funkcie budeme vedieť pridať prvok na koniec zoznamu. Ak je zoznam prázdny, bude vytvorený. V tom prípade funkcia aktualizuje začiatok zoznamu.

  • Zdrojový kód funkcie bude vyzerať nasledovne:

    void append(struct node** head, int data){
        // create new node
        struct node* node = calloc(1, sizeof(struct node));
        node->data = data;
        node->next = NULL;
    
        // is the list empty?
        if(*head == NULL){
            *head = node;
            return;
        }
    
        // if not, traverse to last element
        struct node* ptr = *head;
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
    
        // append the node
        ptr->next = node;
    }
  • Funkciu môžeme jednoducho otestovať:

    int main(){
        struct node* head = NULL;
    
        append(&head, 7);
        append(&head, 12);
        append(&head, 19);
        append(&head, 23);
        append(&head, 37);
        append(&head, 52);
    
        traverse(head);
    }
  • Ak program spustíme, postupne popripája prvky do zoznamu a nakoniec obsah zoznamu vypíše na obrazovku prvok po prvku.

  • Ak samozrejme spustíme program valgrind, upozorní nás na to, že sme pred skončením programu neuvoľnili pamäť. To budeme robiť až pri mazaní prvkov zo zoznamu.

Refactoring?!

  • Prechádzanie prvkov zoznamu sme aktuálne implementovali pomocou cyklu while. Ten však môžeme zameniť aj za cyklus for. Implementácia funkcie traverse() použitím cyklu for miesto while môže vyzerať takto:

    void traverse(struct node *head){
        for(struct node* ptr = head; ptr != NULL; ptr = ptr->next){
            printf("%d\n", ptr->data);
        }
    }

Funkcia pop()

  • (slide) Máme vytvorenú základnú funkciu na pridanie prvku na koniec zoznamu. Spravíme teda funkciu opačnú - pop(). Tá odstráni posledný prvok zo zoznamu a vráti referenciu naň.

  • Implementácia tejto funkcie môže vyzerať nasledovne:

    struct node* pop(struct node** head){
        if(*head == NULL){
            return NULL;
        }
    
        struct node* ptr = *head;
    
        // only one?
        if(ptr->next == NULL){
            *head = NULL;
            return ptr;
        }
    
        // find the semifinal node
        while(ptr->next->next != NULL){
            ptr = ptr->next;
        }
    
        // prepare the result
        struct node* result = ptr->next;
        ptr->next = NULL;
    
        return result;
    }
  • Funkciu otestujeme tak, že postupne zmažeme celý zoznam odzadu a každý vrátený prvok následne odstránime aj z pamäte. Implementácia môže vyzerať napr. takto:

    // pop all elements from list
    struct node* ptr = pop(&head);
    while(ptr != NULL){
        printf(">> removing %d\n", ptr->data);
        free(ptr);
        ptr = pop(&head);
    }    
    
    // traverse the (empty) list
    traverse(head);

Funkcia insert()

  • (slide) Ďalšiu funkciu, ktorú implementujeme, bude funkcia insert(). Táto funkcia vloží prvok na konkrétnu pozíciu zoznamu. Neprepíše prvok, ktorý sa na danom indexe nachádza, ale vloží ho pred neho. Samozrejme - ak je zoznam prázdny, resp. daný index neexistuje (v zozname sa nachádza menej prvkov), tak prvok sa pripojí na koniec zoznamu.

    void insert(struct node** head, size_t index, int data){
        // create new node
        struct node* node = calloc(1, sizeof(struct node));
        node->data = data;
        node->next = NULL;
    
        // is the list empty?
        if(*head == NULL){
            *head = node;
            return;
        }
    
        // find the element at given index
        struct node* ptr = *head;
        for(int i = 0; i+1 < index; i++){
            // if size of list is less than index, then append
            if(ptr->next == NULL){
                ptr->next = node;
                return;
            }
            ptr = ptr->next;
        }
    
        // insert entry
        node->next = ptr->next;
        ptr->next = node;
    }
  • Funkciu môžeme jednoducho otestovať:

    int main(){
        struct node* head = NULL;
    
        // empty list
        insert(&head, 0, 7);
    
        // append to the end
        insert(&head, 99, 52);    
    
        // insert to the given index
        insert(&head, 1, 12);
        insert(&head, 2, 19);
        insert(&head, 3, 23);
        insert(&head, 4, 37);
    
        traverse(head);
    }
  • Ak program spustíme, prvky budú do neho postupne povkladané a nakoniec sa vypíše na obrazovku celý zoznam prvok po prvku.

  • (slide) Keď už vieme naplniť zoznam, môžeme v ňom začať vyhľadávať údaje. Vytvoríme teda funkciu search(), ktorá vráti referenciu na prvý prvok v zozname, ktorý zodpovedá kritériám pre vyhľadávanie. Ak žiadna zhoda nenastane, funkcia vráti NULL.

    struct node* search(struct node* head, int needle){
        struct node* ptr = head;
    
        while(ptr != NULL){
            if(ptr->data == needle){
                return ptr;
            }
            ptr = ptr->next;
        }
    
        return NULL;
    }
  • Funkciu môžeme vyskúšať napr. nasledovným fragmentom kódu. Samozrejme ideálne tak, aby zoznam nebol prázdny.

    int needle;
    printf("What Should I Find: ");
    scanf("%d", &needle);
    
    struct node* ptr = search(head, needle);
    if(ptr != NULL){
        printf("found\n");
    }else{
        printf("not found\n");
    }    

Funkcia delete()

  • (slide) Pre odstránenie položky zo zoznamu vytvoríme funkciu delete(). Táto funkcia bude mať parameter, ktorým bude prvok, ktorý má byť zmazaný. Bude teda rozšírením funkcie search(), kedy akurát prvok nebude len vrátený, ale bude aj odstránený zo zoznamu. Ak sa prvok v zozname nenachádza, vráti NULL.

  • Implementácia funkcie môže vyzerať napr. takto:

    struct node* delete(struct node** head, int needle){
        if(*head == NULL){
            return NULL;
        }
    
        struct node* ptr = *head;
    
        // check head
        if(ptr->data == needle){
            *head = ptr->next;
            ptr->next = NULL;
            return ptr;
        }
    
        // find needle
        while(ptr->next != NULL){
            if(ptr->next->data == needle){
                struct node* result = ptr->next;
                ptr->next = ptr->next->next;
                result->next = NULL;
                return result;
            }
            ptr = ptr->next;
        }
    
        return NULL;
    }    

Funkcia update()

  • (slide) Poslednou funkciou, ktorú si ukážeme, bude funkcia update(). Táto funkcia aktualizuje položku spôsobom, že ju celú vymení za inú.

  • Implementácia funkcie môže vyzerať napr. takto:

    void update(struct node** head, struct node* old, 
                struct node* new){
        if(*head == NULL){
            return;
        }
    
        // is it the first entry?
        if(*head == old){
            new->next = old->next;
            old->next = NULL;
            *head = new;
        }
    
        struct node* ptr = *head;
        // search old entry
        while(ptr->next != NULL){
            if(ptr->next == old){
                new->next = old->next;
                old->next = NULL;
                ptr->next = new;
                return;
            }
            ptr = ptr->next;
        }
    }
  • Za predpokladu, že máme neprázdny zoznam, môžeme overiť správnosť funkcie napríklad takto:

    int needle;
    printf("What Should I Search: ");
    scanf("%d", &needle);
    struct node* old = search(head, needle);
    
    int value;
    printf("Enter New Value: ");
    scanf("%d", &value);
    struct node* new = calloc(1, sizeof(struct node));
    new->data = value;
    update(&head, old, new);
    
    traverse(head);

Finding List Size

  • (slide) Zastavme sa však ešte pri jednom štandardnom probléme - ako zistím veľkosť zoznamu?

  • Pri práci s poľom znakov zistiť veľkosť reťazca znamenalo hľadať najbližší terminátor a rátať, koľko znakov pri tom prejdem. Pri práci s poliami iných údajových typov, sme sa museli o veľkosť starať osobitne pomocou samostatnej premennej.

  • V tomto prípade je situácia podobná tej s poľom znakov - máme totiž jasný koniec zoznamu, ktorý potrebujeme len nájsť a pritom počítať, koľko prvkov sme prešli. Takáto funkcia môže vyzerať nasledovne:

    size_t size(struct node* head){
        size_t counter = 0;
        struct node* ptr = head;
    
        while(ptr != NULL){
            ptr = ptr->next;
            counter++;
        }
    
        return counter;
    }
  • Zložitosť tohto prístupu je opäť lineárna, pretože musím prejsť celým zoznamom prvok po prvku. A to nie je veľmi výhodné.

  • (slide) Môžeme však spraviť fintu a celý zoznam zabaliť do kontajnera, ktorý bude mať len dve položky:

    1. referenciu na začiatok zoznamu, a
    2. počet položiek zoznamu
  • Takýto kontajner môže vyzerať nasledovne:

    struct container {
        struct node* head;
        size_t size;
    };
  • Týmto prístupom sme vyriešili problém so zložitosťou, pretože aktuálne je zložitosť konštantná - 1. Musíme však dodržať to, že akákoľvek operácia, pomocou ktorej dôjde k zmene počtu položiek zoznamu, musí rovnako aktualizovať položku .size.

Conclusion

  • (slide) Dnes sme si ukázali jednu z veľmi dôležitých dátových štruktúr - spojkový zoznam. Vo vyšších programovacích jazykoch sa s ním stretnete v natívnych implementáciách rozličných zoznamov. Jazyk C však takýmto typom nedisponuje a preto si ho musíme vytvoriť sami.

  • Jednosmerný spojkový zoznam však nie je jediným predstaviteľom tohto typu dátových štruktúr. Jednak existujú rozličné typy samotných spojkových zoznamov (napr. obojsmerné, cyklické, …), ale taktiež vieme vytvárať iné štruktúry, ako napr. stromy alebo hash tabuľky (mapy). O tom však nabudúce.