4. Double Linked List - Vergesserungen

Double Linked List - Vergesserungen

  • ?

    hi,
    programmiert man in c ein insert fuer eine double linked list indem man den pointer auf die list als pointer auf pointer uebergibt?

    struct doubleLinkedList
{
	void *data;
	struct doubleLinkedList *previous;
	struct doubleLinkedList *next;
};

void addNode(doubleLinkedList **list, void *element)
{
	doubleLinkedList *temp = (doubleLinkedList*)malloc(sizeof(struct doubleLinkedList));
	temp->data = element;

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

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

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

int main()
{
	doubleLinkedList *l = NULL;
	int i = 5;
	int j = 10;

	addNode(&l, &i);
	addNode(&l, &j);

	printAll(&l);

	return 0;
}
    0
  • H

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

    0
  • ?

    faellt dir was besseres ein?

    0
  • ?

    ich verwende fuer meine double linked list 2 dummy nodes: dummy_first - alle elemente - dummy last
    ...recht hilfreich bei einfuegen vorne bzw hinten...aber ich muss die dummy nodes global machen...faellt euch was besseres ein?

    0
  • H

    ich wuerde eine zusaetzliche struktur "list" machen, die das was jetzt "doubleLinkedList" ist, als erstes/letztes/aktuelles element enthaellt.
    je nachdem was du genau mit der datenstruktur vor hast, kannst du dir ueberlegen, ob die funktionen die typischerweise auf listen nicht performant sind, entsprechend geschickter geloest werden sollen:
    - ein zaehler der die aktuelle elementanzahl protokoliert
    - eine hash-funktion die schnelleren zugriff/suche auf den eintraegen ermoeglicht
    usw...

    0
  • N

    falls es euch interessiert: eine bewährter listen-code (aus dem windoofs kernel)

    //
//  Doubly-linked list manipulation routines.  Implemented as macros
//  but logically these are procedures.
//

typedef struct _LIST_ENTRY 
{
   struct _LIST_ENTRY * volatile Flink;
   struct _LIST_ENTRY * volatile Blink;
} LIST_ENTRY, *PLIST_ENTRY;

#define CONTAINING_RECORD(address, type, field) \
   ((type *)( \
   (unsigned char*)(address) - \
   (unsigned char*)(&((type *)0)->field)))

#define InitializeListHead(ListHead) (\
    (ListHead)->Flink = (ListHead)->Blink = (ListHead))

#define IsListEmpty(ListHead) \
    ((ListHead)->Flink == (ListHead))

#define RemoveHeadList(ListHead) \
    (ListHead)->Flink;\
    {RemoveEntryList((ListHead)->Flink)}

#define RemoveTailList(ListHead) \
    (ListHead)->Blink;\
    {RemoveEntryList((ListHead)->Blink)}

#define RemoveEntryList(Entry) {\
    PLIST_ENTRY _EX_Blink;\
    PLIST_ENTRY _EX_Flink;\
    _EX_Flink = (Entry)->Flink;\
    _EX_Blink = (Entry)->Blink;\
    _EX_Blink->Flink = _EX_Flink;\
    _EX_Flink->Blink = _EX_Blink;\
    }

#define InsertTailList(ListHead,Entry) {\
    PLIST_ENTRY _EX_Blink;\
    PLIST_ENTRY _EX_ListHead;\
    _EX_ListHead = (ListHead);\
    _EX_Blink = _EX_ListHead->Blink;\
    (Entry)->Flink = _EX_ListHead;\
    (Entry)->Blink = _EX_Blink;\
    _EX_Blink->Flink = (Entry);\
    _EX_ListHead->Blink = (Entry);\
    }

#define InsertHeadList(ListHead,Entry) {\
    PLIST_ENTRY _EX_Flink;\
    PLIST_ENTRY _EX_ListHead;\
    _EX_ListHead = (ListHead);\
    _EX_Flink = _EX_ListHead->Flink;\
    (Entry)->Flink = _EX_Flink;\
    (Entry)->Blink = _EX_ListHead;\
    _EX_Flink->Blink = (Entry);\
    _EX_ListHead->Flink = (Entry);\
    }

    und so kann man's benutzen:

    #include <stdio.h>
#include <stdlib.h>

// eine kleine struct die 'linklist enabled' ist
typedef struct demo
{
   char name[256];
   LIST_ENTRY link;  // wichtig: ein liste entry
} DEMO;

// testing....
void main (void)
{
   int s;
   LIST_ENTRY l1;  // listenkopf

   // ... muss einmalig initialisiert werden
   InitializeListHead (&l1);

   // liste füllen mit 10 elementen
   for (s=0; s<10; s++)
   {
      struct demo *p = malloc (sizeof(struct demo));   // eine struct anlegen
      sprintf (p->name, "ListEntry #%d", s);           // einen kleinen text dort hinein
      InsertHeadList (&l1, &p->link);                  // ...und ab in die liste
   }

   // rückwärts ausgeben (von vorne nach hinten)
   for (s=0; s<10; s++)
   {
      LIST_ENTRY *lp;                                  
      DEMO *d;
      lp = RemoveHeadList (&l1);                      // erstes element der liste holen
      d = CONTAINING_RECORD (lp, DEMO, link);         // einen 'struct demo' pointer daraus machen
      printf ("%s\n", d->name);                       // ausgeben...
      free (d);                                       // und wech damit ;)
   } 
}
    0
  • ?

    falls es euch interessiert: eine bewährter listen-code (aus dem windoofs kernel)

    wer hat dir erlaubt das zu posten? das ist illegal!

    0
  • N

    jh schrieb:

    das ist illegal!

    ist es nicht!

    0
  • ?

    meinst du so?

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

struct list 
{
	node *l;
	node *dummy_first;
	node *dummy_last;
	unsigned int count;

	void create();
	void destroy();
	void push_back(void *element);
	void push_front(void *element);
	bool delete_node(void *element);
	void printAll();
};

void list::create()
{
	dummy_first = (node*)malloc(sizeof(struct node));
	dummy_last = (node*)malloc(sizeof(struct node));

	memset(dummy_first, NULL, sizeof(struct node));
	memset(dummy_last, NULL, sizeof(struct node));

	l = NULL;
}

void list::destroy()
{
	node *help = dummy_first->next;

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

	free(dummy_first);
	free(dummy_last);
}

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

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

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

	count++;
}

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

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

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

	count++;
}

bool list::delete_node(void *element)
{
	node *temp = dummy_first->next;
	node *help = dummy_first;

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

	return false;
}

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

int main()
{
	uInt32 a = 5;
        uInt32 b = 10;
	uInt32 c = 20;
	list l;
	l.create();
	l.push_back(&a);
	l.push_back(&b);
	l.push_front(&c);
	l.printAll();
	l.delete_node(&c);
	printf("\n");
	l.printAll();
	l.destroy();

        return 0;
}

    aber wenn ich list:: verwende ist das ja c++?

    0
  • ?

    ok, geht doch..da ja in ner struct alles public ist...

    0
  • C

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

    0
  • D

    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.

    0
  • ?

    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;
}
    0
  • H
     

    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.

    0
  • ?

    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;
    0
  • H

    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)
    0
  • ?

    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;
}
    0
  • H

    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);
}
    0
  • ?

    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;
}
    0
  • H

    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.

    0
Anmelden zum Antworten