Double Linked List - Vergesserungen

c.rackwitz

und weil wir hier in C sind, hast du mit dem code schlechte karten. versuchs doch mal mit funktionspointern zu machen. wird sehr lustig

DrGreenthumb

in der C-Version bräuchte man doch gar keine Funktionspointer, ist ja nichts dynamisch.

Einfach create() durch list_create(list*) etc. ersetzen und fertig.

so ok? ...wobei ich glaub das das destroy nicht richtig funzt...

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <string.h>

struct node
{
    void *data;
    struct node *prev;
    struct node *next;
};

struct list
{
    struct node *n;
    struct node *dummy_first;
    struct node *dummy_last;
    unsigned int count;
};

void create(struct list **l)
{
	(*l) = (struct list*)malloc(sizeof(struct list));
    (*l)->dummy_first = (struct node*)malloc(sizeof(struct node));
    (*l)->dummy_last = (struct node*)malloc(sizeof(struct node));

    memset((*l)->dummy_first, NULL, sizeof(struct node));
    memset((*l)->dummy_last, NULL, sizeof(struct node));

	(*l)->n = NULL;
    (*l)->count = 0;
}

void destroy(struct list **l)
{
    struct node *help;

	if((*l)->n) {
		help = (*l)->dummy_first->next;
        while(help != (*l)->dummy_last) {
			(*l)->n->next = (*l)->n->next->next;
            free(help);
            help = (*l)->dummy_first->next;
			(*l)->count--;
        }

		free((*l)->dummy_first);
        free((*l)->dummy_last);
		free((*l));
    }
}

void push_back(struct list *l, void *element)
{
    struct node *temp = (struct node*)malloc(sizeof(struct node));
    temp->data = element;

	if(l->n) {
        temp->prev = l->dummy_last->prev;
        temp->next = l->dummy_last;
        l->dummy_last->prev->next = temp;
    }
    // list == empty
    else {
        l->dummy_first->next = temp;
        l->dummy_last->prev = temp;

        temp->next = l->dummy_last;
        temp->prev = l->dummy_first;
		l->n = l->dummy_first;
    }

    l->count++;
}

void push_front(struct list *l, void *element)
{
    struct node *temp = (struct node*)malloc(sizeof(struct node));
    temp->data = element;

	if(l->n) {
        temp->prev = l->dummy_first;
        temp->next = l->dummy_first->next;
        l->dummy_first->next = temp;
    }
    // list == empty
    else {
        l->dummy_first->next = temp;
        l->dummy_last->prev = temp;

        temp->next = l->dummy_last;
        temp->prev = l->dummy_first;
		l->n = l->dummy_first;
    }

    l->count++;
}

int delete_node(struct list *l, void *element)
{
    struct node *temp = l->dummy_first->next;
    struct node *help = l->dummy_first;

    if(l->n) {
        while(temp != l->dummy_last) {
            if(temp->data == element) {
                help->next = temp->next;
                temp->next->prev = help;
                free(temp);
				l->n = help;
                l->count--;
                return 1;
            }
            help = temp;
            temp = help->next;
        }
    }

    return 0;
}

void printAll(struct list *l)
{
	if(l->n) {
		struct node *temp;
        for(temp = l->dummy_first->next; temp != l->dummy_last; temp = temp->next) {
            printf("%d\n",*((int*)(temp->data)));
        }
    }
}

int main()
{
    int a = 5;
    int b = 10;
    int c = 20;

    struct list *l = NULL;
    create(&l);
    push_back(l, &a);
    push_back(l, &b);
    push_front(l, &c);
    printAll(l);
    delete_node(l, &c);
    printf("\n");
    printAll(l);
    destroy(&l);

    return 0;
}

hellihjb

void create(struct list **l)
{
    (*l)->dummy_first = (struct node*)malloc(sizeof(struct node));
    (*l)->dummy_last = (struct node*)malloc(sizeof(struct node));

warum existieren in einer leeren liste zwei elemente?
wenn initial schon ein (leeres) element existieren soll, sollten first und last aus logistischen gruenden identisch sein.

wenn an das ende einer liste ein element angehaengt wird, sollte man erwarten, dass sich der zeiger auf das letzte element veraendert - das gleiche gilt fuer vorne.

elementare funktionalitaet zum iterieren der liste waere sicher nuetzlich.

hellihjb schrieb:

void create(struct list **l)
{
    (*l)->dummy_first = (struct node*)malloc(sizeof(struct node));
    (*l)->dummy_last = (struct node*)malloc(sizeof(struct node));
warum existieren in einer leeren liste zwei elemente?
wenn initial schon ein (leeres) element existieren soll, sollten first und last aus logistischen gruenden identisch sein.

wenn an das ende einer liste ein element angehaengt wird, sollte man erwarten, dass sich der zeiger auf das letzte element veraendert - das gleiche gilt fuer vorne.

elementare funktionalitaet zum iterieren der liste waere sicher nuetzlich.

das sind 2 dummy knoten! damit kann ich schneller hinten bzw vorne einfuegen!

ich dachte ich mach das so:
NULL -> dummy_first -> element 1 -> element 2 -> element x -> dummy_last -> NULL

dann kann ich vorne einfuegen ueber:

newelement->next = dummy_first->next;
dummy_first->next->prev = newelement;
dummy_first->next = newelement;
newelement->prev = dummy_first;

hellihjb

es macht aber keinen sinn, dass diese beiden zeiger(!) als eigenstaendige nodes existieren.

zur verdeutlichung:

NULL <- element1 <-> element2 <-> element3 <-> element4 <-> element5 -> NULL
        (*first)       (*n)                                  (*last)

NULL <- element1 -> NULL
        (*first)    
        (*last)
        (*n)

so nun ok? kann man noch was verbessern?

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <string.h>

#define SIZE (50)

struct node
{
    void *data;
    struct node *prev;
    struct node *next;
};

struct list
{
    struct node *n;
    struct node *dummy_first;
    struct node *dummy_last;
    unsigned int count;
};

OS_ERROR list_create(struct list **l)
{  	
	(*l) = (struct list*)malloc(sizeof(struct list));
	(*l)->dummy_last = (*l)->dummy_first = (*l)->n = NULL;
    (*l)->count = 0;

	return OS_OKAY;
}

void list_destroy(struct list **l)
{
    struct node *temp = (*l)->dummy_first;

    if((*l)->n) {
		while((*l)->dummy_first != (*l)->dummy_last) {
			list_delete_node((*l), (*l)->n->data);
        }

        free((*l));
		*l = NULL;
    }
}

OS_ERROR list_push_back(struct list *l, void *element)
{
    struct node *temp = (struct node*)malloc(sizeof(struct node));
    temp->data = element;

    if(l->n) {
        temp->prev = l->dummy_last;
        temp->next = NULL;
        l->dummy_last->next = temp;
		l->dummy_last = temp;
    }
    // list == empty
    else {
        l->dummy_first = l->dummy_last = temp;

        temp->prev = temp->next = NULL;
    }

	l->n = l->dummy_first;
    l->count++;
	return OS_OKAY;
}

OS_ERROR list_push_front(struct list *l, void *element)
{
    struct node *temp = (struct node*)malloc(sizeof(struct node));
    temp->data = element;

    if(l->n) {
		temp->prev = NULL;
        temp->next = l->dummy_first;
		l->dummy_first->prev = temp;
        l->dummy_first = temp;
    }
    // list == empty
    else {
        l->dummy_first = l->dummy_last = temp;

        temp->prev = temp->next = NULL;
    }

	l->n = l->dummy_first;
    l->count++;
	return OS_OKAY;
}

int list_delete_node(struct list *l, void *element)
{
    struct node *temp = l->dummy_first;
    struct node *help = l->dummy_first;

    if(l->n) {
        while(temp != NULL) {
            if(temp->data == element) {
				if(temp == l->dummy_first && temp == l->dummy_last) {
					l->dummy_first = l->dummy_last = help = NULL;
				}
				else if(temp == l->dummy_first) {
					help->next->prev = NULL;
					l->dummy_first = help->next;
				}
				else if(temp == l->dummy_last) {
					help->next = NULL;
					l->dummy_last = help;
				}
				else {
					help->next = temp->next;
					temp->next->prev = help;
				}
				free(temp);
				l->n = l->dummy_first;
				l->count--;
				return 1;
            }
            help = temp;
            temp = temp->next;
        }
    }

    return 0;
}

void list_get_first(struct list *l, void **element)
{
	*element = l->dummy_first->data;
}

void list_get_last(struct list *l, void **element)
{
	*element = l->dummy_last->data;
}

void list_printAll(struct list *l)
{
	struct node *temp;

    if(l->n) {
        for(temp = l->dummy_first; temp != NULL; temp = temp->next) {
            printf("%d\n",*((int*)(temp->data)));
        }
    }
}

int main()
{
    int data_table[SIZE];
	int i = 0;
	int a = 5;
    int b = 10;
    int c = 20;
	void *result;

    struct list *l = NULL;

	list_create(&l);

	for(i = 0; i < SIZE; i++)
	{
		data_table[i] = i;
		list_push_back(l, &data_table[i]);
	}

	list_push_front(l, &c);

	list_printAll(l);

	list_get_first(l, &result);
	printf("First: %d\n", *(int*)result);
	list_get_last(l, &result);
	printf("Last: %d\n", *(int*)result);

    list_delete_node(l, &c);
	//delete_node(l, &b);
	//delete_node(l, &a);

	printf("\n");
    list_printAll(l);

	list_destroy(&l);

    return 0;
}

hellihjb

wenn's laeuft und die funktionalitaet fuer dich hinreichend ist, kann man's so lassen.
die doppelpointer-konstruktionen sind eigentlich ueberfluessig.
"list_create" koennte die neue liste gleich zurueckliefern und NULL als fehlercode nutzen.
in "list_destroy" ist der doppelpointer nur fuer's NULL-setzen noetig - auf eine geloeschte liste zuzugreifen waere aber ohnehin ein programmierfehler.
genauso die getter:

void* list_get_first(struct list *l)
{
    return l->dummy_first->data;
}

nuetzliche funktionalitaet waere evtl noch sowas:

list_begin(list);
while (!list_end(list))
{
  void *item= list_get_current_item(list);
  if (item==...)
    list_delete_current_item(list);
  else
    list_next(list);
}

wenn ich list_delete_node aufrufe und das element in der liste wird nicht gefunden, soll dann das current_item auf NULL zeigen wenn die funktion verlassen wird? ...ich lass mal meine doppelpointer, mal schaun was schoener ist...

erweiterung:

void list_begin(struct list *l)
{
	l->n = l->dummy_first;
}

int list_end(struct list *l)
{
	if(!l->n)
		return 1;

	return 0;
}

void list_get_current_item(struct list *l, void **current_item)
{
	*current_item = l->n->data;
}

void list_delete_current_item(struct list *l)
{
	struct node *temp = l->n;

	// if 1 element in the list
	if(temp == l->dummy_first && temp == l->dummy_last) {
		l->dummy_first = l->dummy_last = NULL;
		l->n = NULL;
	}
	// if current item == first element
	else if(temp == l->dummy_first) {
		temp->next->prev = NULL;
		l->dummy_first = temp->next;
		l->n = l->dummy_first;
	}
	// if current item == last element
	else if(temp == l->dummy_last) {
 		temp->prev->next = NULL;
		l->dummy_last = temp->prev;
		l->n = l->dummy_last;
	}
	// if element in the middle
	else {
		temp->prev->next = temp->next;
		temp->next->prev = temp->prev;
		l->n = temp->next;
	}

	free(temp);
	l->count--;
}

void list_next(struct list *l)
{
	if(l->n)
		l->n = l->n->next;
}

void list_prev(struct list *l)
{
	if(l->n)
		l->n = l->n->prev;
}

int list_delete_node(struct list *l, void *element)
{
	int found = 0;
	void *item;

	list_begin(l);
	while (!list_end(l))
	{
		list_get_current_item(l, &item);
		if (item == element) {
			found = 1;
			list_delete_current_item(l);
			break;
		}
		else
			list_next(l);
	}

	if(!found)
		return 0;

	return 1;
}

hellihjb

wenn ich list_delete_node aufrufe und das element in der liste wird nicht gefunden, soll dann das current_item auf NULL zeigen wenn die funktion verlassen wird?

das "current_item" kann man als zustand der liste sehen und sollte nicht veraendert werden - sofern das element dabei nicht geloescht wird.
ein geeignetes verhalten dafuer waere zb zum naechsten oder vorherigen element zu gehen.
auf der anderen seite ist das deine datenstruktur und sollte auch deinen anforderungen entsprechen. am besten du suchst dir mal mehrere konkrete einsatzzwecke fuer deine liste.

damit waere die liste selbst das aktuelle element.
kann man machen; muss man aber nicht.

da taucht ja ein problem auf merke ich gerade, dann kann ich keinen pointer auf das erste bzw. letzte element speichern....weil dann jeder knoten einen anderen pointer auf das letzte element hat, wenn ich nur push_back mache....hmmmm

mit liste als das aktuelle element...deshalb sowas wohl ungeeignet in bezug auf last, first:

typedef struct doubleLinkedList
{
    void *data;
    struct doubleLinkedList *previous;
    struct doubleLinkedList *next;
    struct doubleLinkedList *first;
    struct doubleLinkedList *last;
}doubleLinkedList;

void list_push_back(doubleLinkedList **list, void *element)
{
    doubleLinkedList *temp = (doubleLinkedList*)malloc(sizeof(doubleLinkedList));
    temp->data = element;
    temp->first = NULL;
    temp->last = NULL;

    if(*list) {
	temp->previous = (*list)->last;
        temp->next = NULL;
        (*list)->last->next = temp;
	(*list)->last = temp;
    }
    // begin node
    else {
        temp->next = NULL;
        temp->previous = NULL;
        (*list) = temp;
	(*list)->first = temp;
	(*list)->last = temp;
    }
}

void list_getFirst(doubleLinkedList **list, void **element)
{
	*element = (*list)->first->data;
}

void list_getLast(doubleLinkedList **list, void **element)
{
	*element = (*list)->last->data;
}

void list_printAll(doubleLinkedList **list)
{
    doubleLinkedList *temp = *list;

    while(temp != NULL) {
        printf("%d\n",*((int*)(temp->data)));
        temp = temp->next;
    }
}

int main()
{
    doubleLinkedList *l = NULL;
    int i = 5;
    int j = 10;
    int k = 20;
    void *result;

    list_push_back(&l, &i);
    list_push_back(&l, &j);
    list_push_back(&l, &k);

    list_printAll(&l);

    list_getFirst(&l, &result);
    printf("First: %d\n",*((int*)result));

    list_getLast(&l, &result);
    printf("Last: %d\n",*((int*)result));

    return 0;
}

hellihjb

weil dann jeder knoten einen anderen pointer auf das letzte element hat, wenn ich nur push_back mache

den ansatz hattest du doch sowieso schon verworfen indem du die node-struktur eingefuehrt hast:

struct node
{
    void *data;
    struct node *prev;
    struct node *next;
};