Einfach verkette Liste in C

single-linked-list.c

#include <stdlib.h>
#define null 0
#define true 1
#define false 0


// Der Typ des gespeicherten Wertes
#define valuetype unsigned int

// ein Listenknoten
typedef struct
{
    valuetype value; // gespeicherter Wert
    listnode* next; // nächster Knoten
} listnode;

typedef struct
{
    listnode* head; // Listenkopf
} list;

typedef unsigned char bool;



// Erstellt eine neue Liste
list* New()
{
    list* l = (list*)malloc(sizeof(list));

    l->head = null;

    return l;
}

listnode* NewNode(valuetype val)
{
    listnode* n = (listnode*)malloc(sizeof(list));

    n->next = null;
    n->value = val;

    return n;
}

void Destroy(void* p)
{
    if (p)
        free(p);
}


// Fügt den gegebenen Wert am Ende der Liste hinzu und gibt den Index des neuen Elementes zurück
int Add(list* l, valuetype value)
{
    if (l)
    {
        listnode* elem = l->head;
        int index = 0;

        if (elem)
        {
            while (elem && elem->next)
            {
                elem = elem->next;
                index++;
            }

            elem->next = NewNode(value);
        }
        else
            l->head = NewNode(value);

        return index;
    }
}

// Gibt die Länge der Liste zurück
int GetLength(list* l)
{
    listnode* elem = l->head;
    int count = 0;

    while (elem)
    {
        elem = elem->next;
        ++count;
    }

    return count;
}

// Gibt den Wert des i-ten Eintrags zurück (Index beginnt mit 0 für das erste Element)
// Gibt 0 zurück, wenn der Index außerhalb der Liste ist
valuetype GetValue(list* l, int index)
{
    listnode* elem = l->head;

    while (elem && index)
    {
        elem = elem->next;
        --index;
    }

    if (elem)
        return elem->value;
    else
        return null;
}

// Fügt den gegebenen Wert am geg. Index in der Liste ein (also der neue Wert hat den geg. Index -- alle folgenden Elemente rutschen um einen Index weiter)
// Wenn der Index nicht innerhalb der Liste ist (also nicht kleiner als die Listenlänge), dann wird nichts getan
// Die funktion gibt 1 zurück, wenn das Einfügen erfolgreich war -- sonst 0
bool InsertAt(list* l, int index, valuetype value)
{
    listnode* elem = l->head;
    listnode* prev = null;

    while (elem && index)
    {
        prev = elem;
        elem = elem->next;
        --index;
    }

    if (index == 1)
        Add(l, value);
    if (!index)
    {
        listnode* _new = NewNode(value);

        prev->next = _new;
        _new->next = elem;
    }
    else
        return false;

    return true;
}

// Entfernt das letzte Listenelement und gibt dessen gespeicherten Wert zurück
valuetype RemoveEnd(list* l)
{
    return RemoveAt(l, GetLength(l) - 1);
}

// Entfernt das Element an der i-ten Stelle und gibt dessen gespeicherten Wert zurück (oder 0, wenn der Index außerhalb der List ist)
valuetype RemoveAt(list* l, int index)
{
    listnode* elem = l->head;
    valuetype value = null;

    if (elem)
        if (index)
        {
            listnode* prev = l->head;

            while (elem->next && index)
            {
                prev = elem;
                elem = elem->next;
                --index;
            }

            if (index <= 1)
            {
                value = elem->value;
                prev->next = elem->next;
            }

            Destroy(elem);
        }
        else
        {
            value = elem->value;
            l->head = null;

            Destroy(elem);
        }

    return value;
}

// Löscht eine Liste
bool DeleteList(list* l)
{
    if (l)
    {
        listnode* elem = l->head;

        while (elem)
        {
            listnode* ref = elem;

            elem = elem->next;
            ref->next = null;

            Destroy(ref);
        }

        Destroy(l);

        return true;
    }

    return false;
}

// Löscht eine Liste ab dem gegebenen Index
void DeleteListFrom(list* l, int index)
{
    if (index)
    {
        listnode* elem = l->head;
        listnode* prev;

        while (elem->next && index)
        {
            prev = elem;
            elem = elem->next;
            --index;
        }

        prev = null;

        while (elem)
        {
            listnode* ref = elem;

            elem = elem->next;
            ref->next = null;

            Destroy(ref);
        }

        Destroy(l);
    }
    else
        DeleteList(l);
}




int main(void)
{
    list* list_1 = New();

    Add(list_1, 3);
    Add(list_1, 1);
    Add(list_1, 5);

    InsertAt(list_1, 0, 4);
    InsertAt(list_1, 1, 2);


    DeleteList(list_1); // <----- Wichtig !!!
}