New approach for adding a new Node to a Linked List

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;
}

The code give above is the popularly wrong version of a function for adding a new node at the head of a linked list. Generally the correct versions are like,

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

I worked out another but simple function for the purpose which worked fine.

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;
}

But I haven't seen this being used or discussed in code and tutorials and thus I am curious to know if this approach has some flaw.

Answer 1

The flaw is that you're relying on the caller to perform the last step of updating the head pointer to the list.

If the caller neglects to do this, the compiler will not complain, and for all intents and purposes the list will appear to not have changed (and you'll have leaked the memory for a node).

Answer 2

I see no problems in any of the mentioned correct code. To change or not to change the head is a matter of design - and how to return modified list. Good interface is implemented in std::list<> as an example where OOP is used, such approach is free of potential problems. head pointer is hidden and you can modify it as you want, and since caller do not store head explicitly, its reference to the list is always correct.

one things which looks ugly (when you use C++, not C) is a malloc, better to use 'new'.

Answer 3

Your approach is incompatible with the idea that addNode is a method on the list, more commonly used in OO languages.

Personally I think

list.add(element)

is a huge lot more intuitive than

list = add(list, element)

Dozens of "collections" libraries can't be wrong...

Answer 4

This is how linked lists work in most functional languages. For example, in ML you might do something like this:

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

The :: syntax is actually a function which takes two parameters (0 and ls) and returns a new list which has 0 as the first element. Lists in ML are actually defined as list nodes, so :: is actually written very similarly to the addNewNode function you proposed.

In other words: congratulations, you have created an immutable linked list implementation in C! Understanding this is actually a fairly important first step to functional languages, so it's really a good thing to know.

Answer 5

Afaik, that's the way how the lists in glib work and I'm sure the gtk folks weren't the first that use that way, so I wouldn't call it a new approach. I personally prefer to have a base structure, that holds the node count, first- and last-pointer.

Answer 6

This is not new. As pointed out by quinmars, glib has done it like this for over 10 years. It's a great idea, so congratulations for figuring it out.

One nitpick about your code, though: don't cast the return value of malloc() in C, and don't repeat the type name in the use of sizeof. Your allocation line should read like this:

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

See? Shorter, tighter, easier to read, harder to mess up. Better! :)