Lineární seznam

Z Wikipedie, otevřené encyklopedie

Lineární seznam (také lineární spojový seznam) je dynamická datová struktura, vzdáleně podobná poli (umožňuje uchovat velké množství hodnot ale jiným způsobem), obsahující jednu a více datových položek (struktur) stejného typu, které jsou navzájem lineárně provázany vzájemnýmí odkazy pomocí ukazatelů nebo referencí. Aby byl seznam lineární, nesmí existovat cykly ve vzájemných odkazech.

Lineární seznamy mohou existovat jednosměrné a obousměrné. V jednosměrném seznamu odkazuje každá položka na položku následující a v obousměrném seznamu odkazuje položka na následující i předcházející položky. Zavádí se také ukazatel nebo reference na aktuální (vybraný) prvek seznamu. Na konci (a začátku) seznamu musí být definována zarážka označující konec seznamu. Pokud vytvoříme cyklus tak, že konec seznamu navážeme na jeho počátek, jedná se o kruhový seznam.

[editovat] Příklad

Příklad v programovacím jazyce C.

#include <stdio.h>   /* for printf */
#include <stdlib.h>  /* for malloc */
 
typedef struct ns {
        int data;
        struct ns *next;
} node;
 
node *list_add(node **p, int i) {
    node *n = malloc(sizeof(node)); /* you normally don't cast a return value for malloc */
    n->next = *p;
    *p = n;
    n->data = i;
    return n;
}
 
void list_remove(node **p) { /* remove head */
    if (*p != NULL) {
        node *n = *p;
        *p = (*p)->next;
        free(n);
    }
}
 
node **list_search(node **n, int i) {
    while (*n != NULL) {
        if ((*n)->data == i) {
            return n;
        }
        n = &(*n)->next;
    }
    return NULL;
}
 
void list_print(node *n) {
    if (n == NULL) {
        printf("list is empty\n");
    }
    while (n != NULL) {
        printf("print %p %p %d\n", n, n->next, n->data);
        n = n->next;
    }
}
 
int main(void) {
    node *n = NULL;
 
    list_add(&n, 0); /* list: 0 */
    list_add(&n, 1); /* list: 1 0 */
    list_add(&n, 2); /* list: 2 1 0 */
    list_add(&n, 3); /* list: 3 2 1 0 */
    list_add(&n, 4); /* list: 4 3 2 1 0 */
    list_print(n);
    list_remove(&n);            /* remove first (4) */
    list_remove(&n->next);      /* remove new second (2) */
    list_remove(list_search(&n, 1)); /* remove cell containing 1 (first) */
    list_remove(&n->next);      /* remove second to last node (0) */
    list_remove(&n);            /* remove last (3) */
    list_print(n);
 
    return 0;
}