Spojkový zoznam

Ako uložiť dáta?

  • Papierik
  • Notes
  • Kalendár
  • Tabuľka v Exceli
  • Databáza
  • Textový súbor

Ktorá metóda je najlepšia ?

Záleži od požiadaviek, každá má svoje výhody a nevýhody

INFO: Použi počítač...

Ktorá metóda uloženia je najlepšia ?

  • čo najjednoduchšia práca?
  • čo najrýchlejšie vyhľadanie?
  • čo najmenej potrebnej pamäte?
  • čo najrýchlejšia modifikácia? (vymazanie a pridanie)

Zabudované typy

  • premenné na jeden záznam
  • polia na viac záznamov
  • polia štruktúr na viac zložitejších záznamov

Polia

  • jednoduché
  • pozná ich prekladač
  • konštatný čas výberu n-tého prvku

Typická práca s poľom

int pole[10] = {1,2,3,4,5,6,7,8,9,10};
int stvrty = pole[3];
for (int i = 0; i < 10; i++){
    printf("%d\n",pole[`i]);
}

Typická práca s dynamickým poľom

int* pole = malloc(sizeof(int) * 10);
for (int i = 0; i < 10; i++){
    pole[i] = i;
}
int stvrty = pole[3];
free(pole);

Nevýhody polí

  • Lineárny čas vloženia nového prvku
  • Lineárny čas vyhľadania hodnoty

Lineárna zložitosť je dosť zlá

Algoritmus vloženia nového prvku

  • Musím posunúť všetky prvky napravo
  • Nemusím mať dosť miesta
    • pole je potrebné alokovať nanovo

Algoritmus vloženia nového prvku

for (c = n - 1; c >= position - 1; c--)
  array[c+1] = array[c];

array[position-1] = value;

https://www.programmingsimplified.com/c/source-code/c-program-insert-element-in-array

Údajové štruktúry

  • spojkové zoznamy
  • binárne vyhľadávacie stromy
  • N-árne vyhľadávacie stromy
  • hashovacie tabuľky

Viac v predmete "Údajové štruktúry a algoritmy"

Spojkový zoznam

Spojkový zoznam

  • umožňuje pridanie alebo zmazanie prvku kdekoľvek bez toho aby sme museli posúvať prvky.
  • Pamätáme si pozíciu začiatku.
  • Ostatné prvky si musíme vyhľadať.

Jazyk C, ani štandardná knižnica nepoznajú spojkový zoznam.

  - Musíme si ho naprogramovať

Ako vyzerá spojkový zoznam

  • Každý prvok obsahuje obsahuje odkaz na ďalší prvok.
  • Každý prvok je dynamicky alokovaný.
sll

Ako vyzerá spojkový zoznam

https://www.slovakrail.sk/fileadmin/Obrazky2/fotogaleria_nova/radenie_vlakov/2019/1_zmena/Kosice1_.jpg

Jeden prvok spojkového zoznamu

struct node {
    // Ľubovoľné premenné
    int value;
    // Odkaz na ďalší prvok
    struct node* next;
};

Vytvorenie prvku spojkového zoznamu

struct node* create_node(int value){
    struct node* linked_list = calloc(1,sizeof(struct node));
    linked_list->value = 1;
    linked_list->next = NULL;
    return linked_list;
}

Dynamická alokácia pamäte

(struct node*)malloc(sizeof(struct node));
  • Operátor sizeof
  • Operátor pretypovania (struct node*)

Jeden prvok spojkového zoznamu

  +------------+
  | 'a' | NULL |
  +------------+
#aabb

Viacprvkový spojkový zoznam

   +-------------+      +-------------+      +------------+
   | 'a' | #aa01 | -->  | 'a' | #aabb | -->  | 'a' | NULL |
   +-------------+      +-------------+      +------------+
#0a01                #aa01                #aabb

Pridanie prvku do spojkového zoznamu

  1. Vytvoríme nový prvok
  2. Zapíšeme jeho adresu do predošlého prvku

Pridanie nového prvku na začiatok

// Vytvoríme zoznam a poznačíme si začiatok
struct node* old_node = create_node(1);
struct node* zaciatok = old_node;

// Pridáme nový prvok
struct node* new_node = create_node(2);
// Zaradíme za neho starý prvok
new_node->next = old_node;
// Zmeníme začiatok
zaciatok = new_node;

// Uvoľníme pamäť
free(next_node);
free(linked_list)

Pridanie nového prvku na začiatok (funkcia)

Prvý argument je vždy starý začiatok spojkového zoznamu. Funkcia vždy vráti nový začiatok spojkového zoznamu.

struct node* add(struct node* start,int value) {
    struct node* item = create_node(value);
    item->next = start;
    return item;
}

Pridanie nového prvku na začiatok (funkcia)

Použitie

// Zoznam je prázdny
struct node* zaciatok = NULL;
zaciatok = add(zaciatok,1);
zaciatok = add(zaciatok,2);
zaciatok = add(zaciatok,3);
// 3->2->1

Pridanie nového prvku na koniec

struct node* add_end(struct node* list,int value) {
    struct node* item = create_node(value);
    if (list == NULL){
        return item;
    }
    struct node* first = list;
    while (list->next != NULL){
        list = list->next;
    }
    list->next = item;
    return first;
}

Prechádzanie spojkového zoznamu

  1. Zoberiem prvý prvok
  2. Ak je prvok nulový, skončím
  3. Zoberiem ďalší prvok a pokračujem bodom 2.

Prechádzanie spojkového zoznamu

for(struct node* this = linked_list;this != NULL;this = this->next){
    if (this->value == 'a'){
        printf("Nasiel som a");
    }
}

Rekurzívne zrušenie celého spojkového zoznamu

void delete(struct node* list){
    if (list!=NULL){
        delete(list->next);
        free(list);
    }
}

Fragmentácia pamäte

  • Pamäť je organizovaná do blokov a je podobná papierovej páske.
  • O pridelenie pamäte sa stará operačný systém.
  • Vyhradenie malého množstva pamäte často zaberie celý blok
  • Spojkový zoznam je neefektívny vzhľadom na spotrebu pamäte.

https://stackoverflow.com/questions/3770457/what-is-memory-fragmentation

Spojkový zoznam spôsobuje fragmentáciu pamäte

Spojkový zoznam nie je dobrý ak:

  • potrebujeme sa rýchlo pozrieť do prostriedku alebo na koniec
  • potrebujeme uložiť veľmi veľa záznamov

Spojkový zoznam je dobrý ak:

  • potrebujeme rýchlo vložiť niečo na začiatok alebo do prostriedku
  • neviem koľko miesta budeme potrebovať
Reload?