2 implementacje listy jedno kierunkowej - która jest lepsza?

Cześć, w ramach nauki o strukturach danych napisałem dwie najprostsze implementacje listy jednokierunkowej. Obie działają, ale nie wiem czy któraś z nich jest lepsza czy gorsza od drugiej. Różnice są głównie między funkcjami Add, bo jedna przyjmuje wskaźnik i zwraca wskaźnik, a druga nic nie zwraca, tylko przyjmuje wskaźnik na wskaźnik na strukturę i na nim tylko działa.

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

typedef struct MyList
{
    int value;
    struct MyList *Next;
}MyList;
MyList* Add(MyList* Ptr)
{
    MyList *ToReturn=(MyList*)malloc(sizeof(MyList));
    ToReturn->Next=Ptr;
    return ToReturn;
}
void Display(MyList *List)
{
    while(List!=0)
    {
        printf("%d\n", List->value);
        List=List->Next;
    }
}
int main()
{
    MyList *List=NULL;
    List=Add(List);
    List->value=11;
    List=Add(List);
    List->value=22;
    List=Add(List);
    List->value=33;
    Display(List);
    return 0;
}

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

typedef struct MyList
{
    int value;
    struct MyList *Next;
}MyList;
void Add(MyList** Ptr)
{
    (*Ptr)->Next=(MyList*)malloc(sizeof(MyList));
    *Ptr=(*Ptr)->Next;
    (*Ptr)->Next=0;
}
void Display(MyList *List)
{
    while(List!=0)
    {
        printf("%d\n", List->value);
        List=List->Next;
    }
}
int main()
{
    MyList *List=(MyList*)malloc(sizeof(MyList));
    Add(&List);
    MyList *First=List;
    List->value=11;
    Add(&List);
    List->value=22;
    Add(&List);
    List->value=33;
    Display(First);
    return 0;
}

Zauważ, że w swoim pierwszym kodzie tak naprawdę tworzysz listę od tyłu (na wzór stosu; nie masz tam wskaźników na następne elementy, tylko poprzednie) - to musiałbyś poprawić.

@Patryk27: Poprawiłem, choć teraz to wygląda jak drugi kod, który tworzył listę "od przodu". To która wersja jest lepsza?

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

typedef struct MyList
{
    int value;
    struct MyList *Next;
}MyList;
MyList* Add(MyList* Ptr)
{
    Ptr->Next=(MyList*)malloc(sizeof(MyList));
    Ptr=Ptr->Next;
    Ptr->Next=0;
    return Ptr;
}
void Display(MyList *List)
{
    while(List!=0)
    {
        printf("%d\n", List->value);
        List=List->Next;
    }
}
int main()
{
    MyList *List=(MyList*)malloc(sizeof(MyList)), *First=List;
    List->value=11;
    List=Add(List);
    List->value=22;
    List=Add(List);
    List->value=33;
    Display(First);
    return 0;
}

Jest już nieco lepiej ;-)

Teraz stwórz taką funkcję Add, która automatycznie będzie dodawała wskaźnik na końcu listy - czyli niezależnie od tego czy przekażesz jej głowę, czy ogon, będzie funkcjonowała poprawnie.

@Patryk27: Funkcja z drugiego kodu w pierwszym poście właśnie nie zwraca nowego wskaźnika, tylko działa na obecnym, tzn. dodaje nowy element na końcu.

Tak, natomiast jeśli przekażesz jej głowę już wypełnionej listy, zadziała błędnie (tzn. mylnie).

Chodzi o to, aby Twoja nowa funkcja Add zawsze mogła przyjąć dowolny element już istniejącej listy, a i tak dopisywała nowy na końcu, a nie tuż za tym przekazanym elementem (tak jak jest teraz).

ta która działa poprawnie i jest szybsza

@Patryk27: Zrobiłem to, ale coś nie działa tak jak trzeba i nie jestem wstanie znaleźć błędu mimo wielu prób. Wydaje mi się, że problem leży w funkcji main. Zrobiłem w niej kopię wskaźnika, który wskazuje na pierwszy element listy i w pewnym momencie przekazałem go do funkcji Add, aby sprawdzić czy ta funkcja poradzi sobie z dodaniem elementu na koniec. I właśnie tu jest problem, bo jak nie używam tej zmiennej, to wszystko działa prawidłowo.

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

typedef struct MyList
{
    int value;
    struct MyList *Next;
}MyList;
void Add(MyList** Ptr)
{
    while((*Ptr)->Next!=0) *Ptr=(*Ptr)->Next;//Ma umożliwić obsłużenie dowolnego elemntu listy.
    (*Ptr)->Next=(MyList*)malloc(sizeof(MyList));
    *Ptr=(*Ptr)->Next;
    (*Ptr)->Next=0;
}
void Display(MyList *List)
{
    while(List!=0)
    {
        printf("%d\n", List->value);
        List=List->Next;
    }
}
int main()
{
    MyList *List=(MyList*)malloc(sizeof(MyList)), *First=List, *ToTest=List;
    List->Next=0;
    List->value=11;
    Add(&List);
    List->value=22;
    Add(&ToTest);//Problematyczna część.
    List->value=33;
    Display(First);
    return 0;
}

To co tutaj robisz to niesamowite czary. Popatrz na log z valgrinda. Zrobiłem screeny, bo popsuł mi się coś schowek w Virtual Boksie...

Powinno być coś w podobie:

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

typedef struct node
{
    int value;
    struct node *next;
}node;

typedef struct list
{
    node *root;
    node *last;
}list;


void addFirst(list *list, int value)
{
    node *element = malloc(sizeof(node));
    element->value = value;
    element->next = list->root;

    if(!list->root)
        list->last = element;
    list->root = element;
}

void addLast(list *list, int value)
{
    node *element = malloc(sizeof(node));
    element->value = value;

    if (!list->last) list->root = list->last = element;
    else
    {
        list->last->next = element;
        list->last = element;
    }
}

void destroy(list *list)
{
    node *tmp = list->root;
    while(tmp)
    {
        node *current = tmp;
        tmp = tmp->next;
        free(current);
        current = NULL;
    }
}

int main()
{
    list mylist = { NULL, NULL };
    addLast(&mylist, 5);
    addFirst(&mylist, 10);
    addFirst(&mylist, 20);
    addFirst(&mylist, 30);
    addFirst(&mylist, 40);
    addLast(&mylist, 60);
    addFirst(&mylist, 70);
    addLast(&mylist, 80);
    addLast(&mylist, 90);
    destroy(&mylist);

    return 0;
}

Pisane trochę na szybko.

@grzesiek51114: Są wycieki pamięci, ponieważ nie zrobiłem funkcji do usuwania listy. Wiem, że ostatni kod nie działał prawidłowo, dlatego też wrzuciłem go tutaj z prośbą o znalezienie błędu.