Adding a node at the TAIL in a linked list

[Sputnik]

struct node {
  int data;
  struct node* next;
};

void Push(struct node** headRef, int data) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->data = data;
  newNode->next = *headRef; // The '*' to dereferences back to the real head
  *headRef = newNode; // ditto
}

struct node* BuildWithSpecialCase() {
  struct node* head = NULL;
  struct node* tail;
  int i;
  // Deal with the head node here, and set the tail pointer
  Push(&head, 1);
  tail = head;
  // Do all the other nodes using 'tail'
  for (i=2; i<6; i++) {
    Push(&(tail->next), i); // add node at tail->next
    tail = tail->next; // advance tail to point to last node
  }
  return(head); // head == {1, 2, 3, 4, 5};
}

Line 14 says tail points to whatever head points to which points to the only node with value 1. Then line 17 is where I have a problem. Now we are passing tails "next" pointer. But what is it pointing to? That next pointer is not really declared, its pointing to an open piece of memory/garbage (we havent explicitly told it NULL), so we're passing a dangerous pointer are we not?
So anyway moving onto the function push, we allocate a new node and set its data value. Now line 4 becomes another problem. The newnode next pointer now points to headref (which is a passed value tail->next). So now it also points to that same piece of undeclared nothingness. Then headref (tail->next) is set back to point to newnode so now its pointing to something valid and not an undeclared piece of space. Ultimately what we have is newnode pointing to garbage. Can anyone decipher this?

[Sputnik]

Wait, I think I got it.

line 20: tail points to what head points to. Head points to the newnode. This first newnode has data value 1 and its next pointer set to NULL. Because we initially pushed it as NULL.

Thus, tail->next is actually also pointing to NULL and not garbage/open memory as I assumed.

This is all still very difficult.

Anybody use memory maps/drawings to help themselves in such problems?

[andywestken]

The code is OK, though rather cryptic.

head is nulled, in BuildWithSpecialCase()

So the line in Push()

newNode->next = *headRef;

is setting the value of next to NULL, as that was the value of head.

Why the code does not just set next to NULL explicitly is beyond me. The standard list traversal routines rely on a NULL link to terminate.

The comment "The '*' to dereferences back to the real head" doesn't make sense to me. If this is some sort of attempt at a circular buffer, the code is even more wrong!

[Sputnik]

My biggest problem was passing tail->next in line 23. I wasnt sure what it meant.

But now I see that it tail-next is simply a pointer pointing to what the first newnode was poitning to. And that happened to be NULL so its legit.

I think what they meant by the comment "The '*' to dereferences back to the real head", means you are dereferencing the pointer itself not its copy. Remember if this was not done, the value of headref would be local to the function Push! Then you would be passing the very pointer as a copy and not a reference!

Definitely cryptic! But rewarding once its understood.

I must confess, I'm a C masochist.

[Intrexa]

If this is just a linked list, the tail does not point to the head. That is a circularly linked list. A newly declared pointer is automatically NULL.

You should use new instead of malloc

[andywestken]

Well, as it stands the code is not acting as a circular list.

I would have thought you'd have to pass the current head to Push to close the circle?

The code below (I left the evil C malloc as it was) produces this o/p

node: data = 1, next = 0x00036fa8
node: data = 2, next = 0x00036fe0
node: data = 3, next = 0x00032920
node: data = 4, next = 0x00032958
node: data = 5, next = 0x00032990
node: data = 6, next = 0x00000000

which is not a close loop!

#include <cstdio>
#include <cstdlib>
using namespace std;

struct node
{
	int data;
	struct node* next;
};

void Push(struct node** headRef, int data) {
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
  newNode->data = data;
  newNode->next = *headRef; // The '*' to dereferences back to the real head
  *headRef = newNode; // ditto
}

struct node* BuildWithSpecialCase(int count) {
  struct node* head = NULL;
  struct node* tail;
  int i;
  // Deal with the head node here, and set the tail pointer
  Push(&head, 1);
  tail = head;
  // Do all the other nodes using 'tail'
  for (i=2; i<=count; i++) {
    Push(&(tail->next), i); // add node at tail->next
    tail = tail->next; // advance tail to point to last node
  }
  return(head); // head == {1, 2, 3, 4, 5};
}

void main ()
{
	int count = 6;

	node* n = BuildWithSpecialCase(count);

	node* m = n;

	while(n)
	{
		printf("node: data = %d, next = 0x%0x\n", n->data, n->next);
		n = n->next;
	}

	/* should free list here */
}

[Sputnik]

Its not cicular, its a simple list that adds on at the tail end.

BTW guys, does malloc use memory such that its contigous? i.e. every time you call to malloc, does all that info go into far apart seperate chunks of memory or are they neatly lined up next to one another?

[andywestken]

I only know about the WIN32 heap and the old CRT small block heap.

The block that's allocated internally will be the amount requested rounded up to the nearest number of some block size. So there can be a gap between the end of the memory you requested and the start of the next block, even if the two blocks are are allocated next to each other.

A new block might not be allocated contiguously if a previously allocated block or blocks have been freed. The heap will try and reuse it.

In the case of the debug heap, the internal blocks also have headers and footer, which are used to detect overruns.

[Sputnik]

Hey guys sorry to beat a dead horse here, but I was going over this again and I noticed another problem I have, line 8:

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

Malloc by default returns void so shouldnt it be cast to struct node? i.e:

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

[andywestken]

I don't thing the cast is needed for proper C code, in a .c file, which is what it looks like.

If it was C++ I would expect the cast (and you'd need it!). But the struct would be superfluous, too!

Evil C

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

Saintly C++

node* newNode = (node*)malloc(sizeof(node));

[DSLq5Di1]

"Saintly C++" would use static_cast! :-)

[andywestken]

Maybe that "Heavenly C++"?

But then what about?

node* newNode = new node();

[DSLq5Di1]

Heavenly has a nice ring to it, using new.. now thats just "Smart C++". ^^

[Sputnik]

andywestken wrote:

I don't thing the cast is needed for proper C code, in a .c file, which is what it looks like.

So what youre saying is that the struct node pointer "newnode" is going to point to void (because thats what malloc returns) and there is nothing wrong with it? Then why do we declare a pointer a type when it can point to a different type??

[andywestken]

I'm saying the C is lazier than C++ about casting from void* to a typed pointer.

So the following

char* pEvil = malloc(lot_of_space);

is perfectly valid C (unless this has been removed in the latest version?)

Including a cast makes sure the code carries on compiling if you switch the compile from C -> C++. I also think that it's far better style.

I always code in C++, so the only time I've encountered this issue is when I've "ported" C to C-style C++ (that is, nicked a routing from legacy C code). One of the problems I encounter during such "ports" is exactly this issue!

Andy

P.S. I have an uneasy feeling that in C, you can cast any pointer type to void* as well as from, without a cast.

[Sputnik]

Andy, you are 100% correct. I was reading about it: This is a must read!

Originally, the C language did not enjoy the void pointer. In those dark ages the char pointer was used as a generic pointer, so the definition of malloc looked something like this:

char *malloc(size)
int size;

Of course, this tended to cause problems when trying to assign a char pointer to, say, a double pointer. Because of this a cast was required:

double *p;
p = (double *)malloc ( n * sizeof ( double ) );

However, with the advent of the ISO C standard a new generic pointer was created, the void pointer. A void pointer can be assigned to any pointer type (except function pointers) safely and without the need for a cast. Thanks to this, the calls to malloc were simplified:

double *p;
p = malloc ( n * sizeof ( double ) );

However, many still prefer to cast malloc because they feel it makes the intentions of the memory allocation more clear. There is nothing wrong with this except in the event that stdlib.h, the header which declares malloc, is not included. If the return of malloc is cast then the error which would be flagged is hidden, resulting in a difficult to find bug. Also, during maintenance, if the type of the pointer changes but the cast is not changed, once again there is a difficult to find bug. The method most experienced programmers choose is:

p = malloc ( n * sizeof *p );

There is no cast for malloc since there is no need for one, and instead of using sizeof ( type ) to determine the size of the block, sizeof *ptr is used. By dereferencing the pointer and taking its size, the proper value is given without having to worry about modifying the allocation request if the type of the pointer changes.

So should you cast malloc? No, that is the preferred method. However, you should use whichever you like provided you are aware of the issues.