Implementaçao de Listas em C

Implementação simples de listas duplamente ligadas em C.

Ficheiro: list.h

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 2008 Diogo Sousa
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef LIST_H_
#define LIST_H_

#include <stddef.h>

typedef struct list_node 
{
    void *data;

    struct list_node *next; 
    struct list_node *prev;
} list_node;

typedef struct list
{
    struct list_node *head; 
    struct list_node *tail;

    size_t size;
} list;

extern void list_init(list *);
extern size_t list_size(list *);

extern list_node *list_head(list *);
extern list_node *list_tail(list *);

extern list_node *list_add(list *, void *);
extern list_node *list_add_head(list *, void *);
extern list_node *list_add_tail(list *, void *);

extern void *list_del(list *, list_node *);

extern void list_free(list *, void (*callback)(void *));

#define list_node_data(list_node,type) (*((type *)(list_node)->data))
#define list_node_data_ptr(list_node,type) ((type *)(list_node)->data)
#define list_node_next(list_node) ((list_node)->next)
#define list_node_prev(list_node) ((list_node)->prev)

#endif

Ficheiro: list.c

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 2008 Diogo Sousa
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "list.h"
#include "xalloc.h"

void
list_init(list *list)
{
    list->head=NULL;
    list->tail=NULL;
    list->size=0;
}

size_t
list_size(list *list)
{
    return list->size;
}

list_node *
list_head(list *list)
{
    return list->head;
}

list_node *
list_tail(list *list)
{
    return list->tail;
}

list_node *
list_add(list *list, void *data)
{
    return list_add_tail(list,data);
}

list_node *
list_add_head(list *list, void *data)
{
    list_node *list_node;

    list_node=xmalloc(sizeof(*list_node));
    list_node->data=data;
    list_node->next=list->head;
    list_node->prev=NULL;

    if (list->head == NULL)
        list->head=list_node;
    else
        list->head->prev=list_node;

    list->head=list_node;

    list->size++;

    return list_node;
}

list_node *
list_add_tail(list *list, void *data)
{
    list_node *list_node;

    list_node=xmalloc(sizeof(*list_node));
    list_node->data=data;
    list_node->next=NULL;
    list_node->prev=list->tail;

    if (list->head == NULL)
        list->head=list_node;
    else
        list->tail->next=list_node;

    list->tail=list_node;

    list->size++;

    return list_node;
}

void *
list_del(list *list, list_node *node)
{
    void *data;

    if (node->next != NULL)
        node->next->prev=node->prev;

    if (node->prev != NULL)
        node->prev->next=node->next;

    if (list->tail == node)
        list->tail=node->prev;

    if (list->head == node)
        list->head=node->next;

    list->size--;

    data=node->data;

    free(node);

    return data;
}

void 
list_free(list *list, void (*callback)(void *))
{
    struct list_node *i;
    struct list_node *next;

    for (i=list_head(list); i != NULL; i=next)
    {
        if (callback != NULL)
            callback(i->data);

        next=i->next;

        free(i);
    }
}

Exemplo de uso

#include <stdio.h>
#include "list.h"

int
main(void)
{
    list list;
    list_node *node;
    struct list_node *i;
    int n[]={5,6,7,8};

    // inicialização da lista
    list_init(&list);

    // adiciona 5 na cauda da lista
    list_add_tail(&list,&n[0]);
    // adiciona 6 na cauda da lista, e devolve o nodo adicionado
    node=list_add_tail(&list,&n[1]);
    // adiciona 7 na cauda da lista
    list_add_tail(&list,&n[2]);
    // adiciona 8 na cauda da lista
    list_add_tail(&list,&n[3]);
    // adiciona 8 na cabeça da lista
    list_add_head(&list,&n[3]);

    // percorre os elementos da lista e imprime-os
    for (i=list_head(&list); i != NULL; i=list_node_next(i))
        printf("%d ",list_node_data(i,int));

    // elimina node (6) da lista
    list_del(&list,node);

    putchar(' | ');

    // percorre os elementos da lista e imprime-os (o elemento 6 foi removido)
    for (i=list_head(&list); i != NULL; i=list_node_next(i))
        printf("%d ",list_node_data(i,int));

    // liberta o espaço ocupado pela lista
    list_free(&list,NULL);

    return 0;
}