Neuer Ansatz für das Hinzufügen eines neuen Knotens zu einer verknüpften Liste

Question

void addNewNode (struct node *head, int n)
{
    struct node* temp = (struct node*) malloc(sizeof(struct node));
    temp -> data = n;
    temp -> link = head;
    head = temp;
}

Der oben angegebene Code ist die populär falsche Version einer Funktion zum Hinzufügen eines neuen Knotens am Kopf einer verknüpften Liste. Im Allgemeinen sind die korrekten Versionen wie folgt,

void addNewNode (struct node **head, int n);
void addNewNode (struct node * &head, int n);

Ich habe eine andere, einfache Funktion für diesen Zweck entwickelt, die gut funktioniert.

struct node* addNewNode (struct node *head, int n)
{
    struct node* temp = (struct node*) malloc(sizeof(struct node));
    temp -> data = n;
    temp -> link = head;
    return temp;
}

Aber ich habe nicht gesehen, dass dies in Code und Tutorials verwendet oder diskutiert wird, und daher bin ich neugierig zu wissen, ob dieser Ansatz einen Fehler hat.

Answer 1

Der Fehler liegt darin, dass Sie sich darauf verlassen, dass der Aufrufer den letzten Schritt der Aktualisierung des Kopfzeigers auf die Liste durchführt.

Wenn der Aufrufer dies unterlässt, wird sich der Compiler nicht beschweren, und die Liste wird so aussehen, als hätte sie sich nicht geändert (und Sie haben den Speicher für einen Knoten ausgelassen).

Answer 2

So funktionieren verknüpfte Listen in den meisten funktionalen Sprachen. In ML könnten Sie zum Beispiel so vorgehen:

val ls = [1, 2, 3, 4]
val newList = 0 :: ls

Le site :: Syntax ist eigentlich eine Funktion, die zwei Parameter benötigt ( 0 y ls ) und gibt eine neue Liste zurück, die Folgendes enthält 0 als erstes Element. Listen in ML sind eigentlich als Listenknoten definiert, also :: ist eigentlich sehr ähnlich geschrieben wie die addNewNode Funktion, die Sie vorgeschlagen haben.

Mit anderen Worten: Herzlichen Glückwunsch, Sie haben eine unveränderliche Linked-List-Implementierung in C erstellt! Dies zu verstehen, ist ein wichtiger erster Schritt zu funktionalen Sprachen, also ist es wirklich gut zu wissen.

Answer 3

Ihr Ansatz ist unvereinbar mit der Idee, dass addNode ist eine Methode auf der Liste, die häufiger in OO-Sprachen verwendet wird.

Persönlich denke ich

list.add(element)

ist sehr viel intuitiver als

list = add(list, element)

Dutzende von "Sammlungen" Bibliotheken können nicht falsch sein...

Answer 4

Afaik, das ist die Art und Weise, wie die Listen in Glib funktionieren und ich bin sicher, dass die Gtk-Leute nicht die ersten waren, die diese Methode verwenden, also würde ich es nicht als neuen Ansatz bezeichnen. Ich persönlich ziehe es vor, eine Basisstruktur zu haben, die die Knotenanzahl, den ersten und den letzten Zeiger enthält.

Answer 5

Das ist nicht neu. Wie von quinmars erwähnt, macht glib das schon seit über 10 Jahren so. Es ist eine großartige Idee, und ich gratuliere Ihnen, dass Sie das herausgefunden haben.

Ein kleiner Kritikpunkt an Ihrem Code: Sie sollten den Rückgabewert von malloc() in C, und wiederholen Sie den Typnamen nicht bei der Verwendung von sizeof . Ihre Zuweisungszeile sollte folgendermaßen aussehen:

struct node* temp = malloc(sizeof *temp);

Sehen Sie? Kürzer, straffer, leichter zu lesen, schwieriger zu verwechseln. Besser! :)