Singly Linked List in C

[arnuld]

I am learning about linked lists. This works fine without any trouble. Any
advice for improvement or you want me to implement some more operations in
order to improve my understanding of linked lists:


/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* VERISON 0.0
*
*/

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


struct my_struct* add_to_list( struct my_struct *const, const int);
struct my_struct* remove_from_list( struct my_struct *const, const int );
struct my_struct* insert_after_element(struct my_struct *const, const int, const int);

void print_list( const struct my_struct* );


struct my_struct
{
int num;
struct my_struct* next;
};



int main(void)
{
struct my_struct* root_node = malloc( 1 * sizeof(*root_node));
const int i = 1;
const int j = 2;

if( NULL == root_node )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "main");
return EXIT_FAILURE;
}
else
{
root_node->next = 0;
root_node->next = NULL;
}


add_to_list(root_node, i);
add_to_list(root_node, j);

print_list(root_node);

printf("going to remove element with value = %d\n", i);
remove_from_list(root_node, i);
print_list(root_node);


printf("going to insert element after root_node\n");
insert_after_element(root_node, root_node->num, i);
print_list(root_node);

return 0;
}




struct my_struct* add_to_list(struct my_struct *const base_node, const int i )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;
struct my_struct* p = malloc( 1 * sizeof(*p));

if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "add_to_list");
return NULL;
}

p->num = i;
p->next = NULL;

for( ; s != NULL ; s = s->next ) c = s;

c->next = p;


return c->next;
}


struct my_struct* remove_from_list( struct my_struct *const base_node, const int r )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;

for( ; (NULL != s) && (s->num != r); s = s->next ) c = s;

if( s )
{
c->next = s->next;
free(s);
return c;
}

return NULL;
}


struct my_struct* insert_after_element(struct my_struct *const base_node, const int after, const int i)
{
struct my_struct* s = base_node;
struct my_struct* n = NULL;
struct my_struct* p = NULL;

for( ; (NULL != s) && (s->num != after ); s = s->next );

if( NULL == s )
{
printf("No element with number match: %d\n", i);
}
else
{
p = malloc( 1 * sizeof(*p));

if( NULL == p )
{
fprintf(stderr, "IN: %s, %s: malloc() failed\n", __FILE__, "insert_after_element");
return NULL;
}

p->num = i;

n = s->next;
s->next = p;
p->next = n;
}

return p;
}





void print_list( const struct my_struct* p )
{
for( ; NULL != p; p = p->next )
{
printf("Num = %d\n", p->num);
}

printf("\n\n");
}



================== OUTPUT =========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
[arnuld@dune programs]$ ./a.out
Num = 0
Num = 1
Num = 2


going to remove element with value = 1
Num = 0
Num = 2


going to insert element after root_node
Num = 0
Num = 1
Num = 2


[arnuld@dune programs]$

 

[mark.bluemel]

I am learning about linked lists. This works fine without any trouble. Any
advice for improvement or you want me to implement some more operations in
order to improve my understanding of linked lists:

I'll make a few comments, which are just my opinion, off-the-cuff and
certainly not definitive.

/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
 * the list.
 *
 * VERISON 0.0
 *
 */

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

struct my_struct* add_to_list( struct my_struct *const, const int);
struct my_struct* remove_from_list( struct my_struct *const, const int );
struct my_struct* insert_after_element(struct my_struct *const, const int, const int);

You never use the return values from these routines, and I'm not sure
you ever would.

An integer indicating success or failure may be more useful than the
structure.

void print_list( const struct my_struct* );

struct my_struct
{
  int num;
  struct my_struct* next;

};

int main(void)
{
  struct my_struct* root_node = malloc( 1 * sizeof(*root_node));

Your main-line code doesn't really need to know about my_struct
structures, so why do this here?

My design for this sort of thing would have a function something
like :-

void *list_create();

to initialise a list. The returned value (remaining as a void *) would
be my first argument to the other list management functions, which
could assign it to a my_struct * internally.

  const int i = 1;
  const int j = 2;

  if( NULL == root_node )
    {
      fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "main");
      return EXIT_FAILURE;
    }
  else
    {
      root_node->next = 0;
      root_node->next = NULL;

Naturally this belongs in the list initialisation function.

    }

  add_to_list(root_node, i);
  add_to_list(root_node, j);

  print_list(root_node);

  printf("going to remove element with value = %d\n", i);
  remove_from_list(root_node, i);
  print_list(root_node);

  printf("going to insert element after root_node\n");
  insert_after_element(root_node, root_node->num, i);
  print_list(root_node);

  return 0;

}

struct my_struct* add_to_list(struct my_struct *const base_node, const int i )
{
  struct my_struct* s = base_node;
  struct my_struct* c = NULL;
  struct my_struct* p = malloc( 1 * sizeof(*p));

  if( NULL == p )
    {
      fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "add_to_list");
      return NULL;
    }

  p->num = i;
  p->next = NULL;

  for( ; s != NULL ; s = s->next )  c = s;

  c->next = p;

  return c->next;

You don't really need c. Traverse the list until s->next == NULL and
use s.

}

struct my_struct* remove_from_list( struct my_struct *const base_node, const int r )
{
  struct my_struct* s = base_node;
  struct my_struct* c = NULL;

  for( ; (NULL != s) && (s->num != r); s = s->next ) c = s;

  if( s )
    {
      c->next = s->next;
      free(s);
      return c;
    }

  return NULL;

}

struct my_struct* insert_after_element(struct my_struct *const base_node, const int after, const int i)
{
  struct my_struct* s = base_node;
  struct my_struct* n = NULL;
  struct my_struct* p = NULL;

  for( ; (NULL != s) && (s->num != after ); s = s->next );

  if( NULL == s )
    {
      printf("No element with number match: %d\n", i);
    }
  else
    {
      p = malloc( 1 * sizeof(*p));

      if( NULL == p )
        {
          fprintf(stderr, "IN: %s, %s: malloc() failed\n", __FILE__, "insert_after_element");
          return NULL;
        }

      p->num = i;

      n = s->next;
      s->next = p;
      p->next = n;

Reorder these and you don't need n.

    }

  return p;

}

void print_list( const struct my_struct* p )
{
  for( ; NULL != p; p = p->next )
    {
      printf("Num = %d\n", p->num);
    }

  printf("\n\n");

}

Consider this alternative set of interfaces:-

void *create_list(); /* allocate and initialise root node */
int add_to_list( void *list, const int value );
int remove_from_list( void *list, const int value );
int insert_after_element( void *list, const int value, const int
value2 );
void print_list( void *list );
void delete_list( void *list ); /* free all nodes (including the root
node) */

Also consider how you could generalise this easily - for example, what
you could do if the nodes had the form :-

struct my_struct {
void *the_data;
struct my_struct *next;
}

 

[Ben Bacarisse]

I am learning about linked lists. This works fine without any trouble. Any
advice for improvement or you want me to implement some more operations in
order to improve my understanding of linked lists:

Just to complicate the advice, I would keep the return value as a
pointer but I would use it to return the pointer to the list head.
That way you don't need to allocate the first element "by hand" as you
have been doing.

The add operation is then always:

list = add_to_list(list, ...);

and similarly with remove. This really simplifies the code.

If you are using what I consider a rather ugly trick of always having a
dummy first node, then I strongly advice you change that. I don't
think you are doing that because the print function prints it!

I'd make all the function names start with a common prefix
(i.e. list_add, list_remove and so on). It is a shame that this does
not produce natural meaning in English (the "list add" operation adds
a list not an item to a list in plain English) but all programmers
will know what you mean.

/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* VERISON 0.0
*
*/

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


struct my_struct* add_to_list( struct my_struct *const, const int);
struct my_struct* remove_from_list( struct my_struct *const, const int );
struct my_struct* insert_after_element(struct my_struct *const, const int, const int);

void print_list( const struct my_struct* );


struct my_struct
{
int num;
struct my_struct* next;
};



int main(void)
{
struct my_struct* root_node = malloc( 1 * sizeof(*root_node));
const int i = 1;
const int j = 2;

if( NULL == root_node )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "main");
return EXIT_FAILURE;
}
else
{
root_node->next = 0;
root_node->next = NULL;
}


add_to_list(root_node, i);
add_to_list(root_node, j);

print_list(root_node);

printf("going to remove element with value = %d\n", i);
remove_from_list(root_node, i);

If the list had only one element, how would this line have any effect
at all? If the item being removed is the first, then what?

print_list(root_node);


printf("going to insert element after root_node\n");
insert_after_element(root_node, root_node->num, i);
print_list(root_node);

return 0;
}




struct my_struct* add_to_list(struct my_struct *const base_node, const int i )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;
struct my_struct* p = malloc( 1 * sizeof(*p));

if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "add_to_list");
return NULL;
}

p->num = i;
p->next = NULL;

for( ; s != NULL ; s = s->next ) c = s;

c->next = p;


return c->next;

You can only add using this function if there is an element already in
the list. That can't be a clean interface!

}


struct my_struct* remove_from_list( struct my_struct *const base_node, const int r )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;

for( ; (NULL != s) && (s->num != r); s = s->next ) c = s;

if( s )
{
c->next = s->next;
free(s);
return c;

This is not right. If the first element has s->num == r then c ==
NULL and you can't do c->next = anything.

}

return NULL;
}


struct my_struct* insert_after_element(struct my_struct *const base_node, const int after, const int i)
{
struct my_struct* s = base_node;
struct my_struct* n = NULL;
struct my_struct* p = NULL;

for( ; (NULL != s) && (s->num != after ); s = s->next );

if( NULL == s )
{
printf("No element with number match: %d\n", i);
}
else
{
p = malloc( 1 * sizeof(*p));

if( NULL == p )
{
fprintf(stderr, "IN: %s, %s: malloc() failed\n", __FILE__, "insert_after_element");
return NULL;

When you write code like this for the second time, go find the first
and make it into a function.

}

p->num = i;

n = s->next;
s->next = p;
p->next = n;
}

return p;

If your interface to add_list is correct and easy to use, this
function can be written using it. In fact, I'd make that a
challenge. Re-work the add function until you can use it here to
simplify insert_after.

 

[Barry Schwarz]

I am learning about linked lists. This works fine without any trouble. Any
advice for improvement or you want me to implement some more operations in
order to improve my understanding of linked lists:


/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* VERISON 0.0
*
*/

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


struct my_struct* add_to_list( struct my_struct *const, const int);
struct my_struct* remove_from_list( struct my_struct *const, const int );
struct my_struct* insert_after_element(struct my_struct *const, const int, const int);

void print_list( const struct my_struct* );


struct my_struct
{
int num;
struct my_struct* next;
};



int main(void)
{
struct my_struct* root_node = malloc( 1 * sizeof(*root_node));

The inner parentheses are superfluous.

const int i = 1;
const int j = 2;

if( NULL == root_node )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "main");
return EXIT_FAILURE;
}
else
{
root_node->next = 0;
root_node->next = NULL;

Do you really think there is the slightest difference between the two
previous statements?

}


add_to_list(root_node, i);
add_to_list(root_node, j);

print_list(root_node);

printf("going to remove element with value = %d\n", i);
remove_from_list(root_node, i);
print_list(root_node);


printf("going to insert element after root_node\n");
insert_after_element(root_node, root_node->num, i);

At no point have you assigned a value to root_node->num. Attempting
to evaluate it here invokes undefined behavior.

print_list(root_node);

return 0;
}




struct my_struct* add_to_list(struct my_struct *const base_node, const int i )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;
struct my_struct* p = malloc( 1 * sizeof(*p));

if( NULL == p )

Is there some significance to the different spacing you use around
parentheses?

{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "add_to_list");
return NULL;
}

p->num = i;
p->next = NULL;

for( ; s != NULL ; s = s->next ) c = s;

c->next = p;


return c->next;
}


struct my_struct* remove_from_list( struct my_struct *const base_node, const int r )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;

for( ; (NULL != s) && (s->num != r); s = s->next ) c = s;

if( s )
{
c->next = s->next;
free(s);
return c;
}

return NULL;
}


struct my_struct* insert_after_element(struct my_struct *const base_node, const int after, const int i)
{
struct my_struct* s = base_node;
struct my_struct* n = NULL;
struct my_struct* p = NULL;

for( ; (NULL != s) && (s->num != after ); s = s->next );

When s == base_node, this also invokes undefined behavior

if( NULL == s )
{
printf("No element with number match: %d\n", i);
}
else
{
p = malloc( 1 * sizeof(*p));

if( NULL == p )
{
fprintf(stderr, "IN: %s, %s: malloc() failed\n", __FILE__, "insert_after_element");
return NULL;
}

p->num = i;

n = s->next;
s->next = p;
p->next = n;
}

return p;
}





void print_list( const struct my_struct* p )
{
for( ; NULL != p; p = p->next )
{
printf("Num = %d\n", p->num);
}

printf("\n\n");
}



================== OUTPUT =========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
[arnuld@dune programs]$ ./a.out
Num = 0
Num = 1
Num = 2


going to remove element with value = 1
Num = 0
Num = 2


going to insert element after root_node
Num = 0
Num = 1
Num = 2


[arnuld@dune programs]$

 

[arnuld]

Just to complicate the advice, I would keep the return value as a
pointer but I would use it to return the pointer to the list head.
That way you don't need to allocate the first element "by hand" as you
have been doing.

I think I did not understand what you mean ?

The add operation is then always:

list = add_to_list(list, ...);

and similarly with remove. This really simplifies the code.

but then how do I know which element to add or remove, see:

struct my_struct* list_add(struct my_struct *const base_node, const int i )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;
struct my_struct* p = malloc( 1 * sizeof(*p));

if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}

p->num = i;
p->next = NULL;

for( ; s != NULL ; s = s->next );
s = p;

return s;
}

In this case there is only one variable i, which is being passed to
p->num, now if I make 2nd argument 3 dots (...) which means a variable
number of input, then how to pass that value to struct ?

 

[Phil Carmody]

I think I did not understand what you mean ?



but then how do I know which element to add or remove, see:

struct my_struct* list_add(struct my_struct *const base_node, const int i )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;
struct my_struct* p = malloc( 1 * sizeof(*p));

if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}

p->num = i;
p->next = NULL;

for( ; s != NULL ; s = s->next );
s = p;

return s;
}

In this case there is only one variable i, which is being passed to
p->num, now if I make 2nd argument 3 dots (...) which means a variable
number of input, then how to pass that value to struct ?

I'm not too bothered how many variable i's there are - your code
doesn't work. There is no adding of anything to any list, for
example.

And even if it was tweaked to work, it looks like you're proposing
an O(n) algorithm for something that should be O(1). Which is
horrific.

Phil

 

[arnuld]

I'm not too bothered how many variable i's there are - your code
doesn't work. There is no adding of anything to any list, for
example.

Yes, it does not and I don't understand why. I am assigning a newly
malloc()ed pointer to the base node. Even I have a NULL check for malloc()

And even if it was tweaked to work, it looks like you're proposing
an O(n) algorithm for something that should be O(1). Which is
horrific.

Adding an element to the end of a singly-linked list is always O(n).

 

[arnuld]

Here is the new version, which only adds an element to the linked list. I
think I need to understand basics first:

WANTED: To add an element to the singly linked list.
HAPPENS: Nothing is added to the list.



/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* VERISON 0.1
*
*/

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


struct my_struct* list_add( struct my_struct *const, const int);

void list_print( const struct my_struct* );
void list_print_element(const struct my_struct *const );


struct my_struct
{
int num;
struct my_struct* next;
};



int main(void)
{
struct my_struct* root_node = NULL;

list_add(root_node, 1);
list_print(root_node);

return 0;
}


struct my_struct* list_add(struct my_struct *const base_node, const int i )
{
struct my_struct* s = base_node;
struct my_struct* c = s;
struct my_struct* p = malloc( 1 * sizeof(*p) );

if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}

p->num = i;
p->next = NULL;


if( NULL == s )
{
printf("Base Node was NULL, so adding current maloc()ed struct to base\n");
s = p;
}
else
{
printf("Base node is non-NULL, so adding it to the end of the list\n");
for( ; s != NULL ; s = s->next ) c = s;
c = p;
}

return base_node;
}


void list_print( const struct my_struct *const sp )
{
const struct my_struct* p = sp;

for( ; NULL != p; p = p->next )
{
list_print_element(p);
}

printf("\n------------------\n");
}


void list_print_element(const struct my_struct *const p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}

============== OUTPUT ===================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
[arnuld@dune programs]$ ./a.out
Base Node was NULL, so adding current maloc()ed struct to base

 

[arnuld]

The inner parentheses are superfluous.

Just added them for clarity.

Is there some significance to the different spacing you use around
parentheses?

I always use it like that otherwise I can't read properly.

When s == base_node, this also invokes undefined behavior

Corrected in version 0.1 of code I just posted

 

[BartC]

Here is the new version, which only adds an element to the linked list. I
think I need to understand basics first:

WANTED: To add an element to the singly linked list.
HAPPENS: Nothing is added to the list.

I've put a version of your code here. The /* !!!!! */ comment marks where I
think the main problem was.

But I've also changed a few things that I found annoying or made it
unreadable, notably getting rid of the consts (I've never got my mind around
those), and using a typedef 'tnode' instead of those untidy structs
everywhere.

You can also make it a bit simpler if you are happy with the items being
added in reverse order. (And if you need them in order, there are better
ways than searching to the end of the list each time; imagine you have tens
of millions of nodes.)

Note: watch for line-wraps on the string constants, you may need to join
these up again.

/* This C implementation of singly linked list implements 3 operations: add,
remove and insert elements at some specific position in
* the list.
*
* VERSION 0.1a
*
*/

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

struct my_struct
{
int num;
struct my_struct* next;
};

typedef struct my_struct tnode;

tnode* list_add( tnode *, int);

void list_print(tnode* );
void list_print_element(tnode *);


int main(void)
{
tnode* root_node = NULL;

root_node = list_add(root_node, 1); /* !!!!! */
list_add(root_node, 16);
list_add(root_node, 176);
list_add(root_node, 1766);
list_print(root_node);

return 0;
}


/* Create a new node containing data i.
Add it to the linked list base_node, which
can be NULL for any empty list.
Return (possibly updated) base_node
*/
tnode* list_add(tnode *base_node, int i )
{
tnode* s;
tnode* p = malloc(sizeof(tnode));

if(p==NULL) return base_node; /* Do not return NULL here */

p->num = i;
p->next = NULL;

if(base_node==NULL)
{
printf("Base Node was NULL, so adding current malloc()ed struct to
base\n");
base_node = p;
}
else
{
printf("Base node is non-NULL, so adding it to the end of the
list\n");
s = base_node;
while (s->next) s=s->next;
s->next = p;
}

return base_node;
}


void list_print(tnode * sp)
{
tnode* p;

puts("Printout of linked list:");
for(p=sp ; p!=NULL; p = p->next )
{
list_print_element(p);
}

printf("\n------------------\n");
}


void list_print_element(tnode *p)
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}

 

[Ben Bacarisse]

Here is the new version, which only adds an element to the linked list. I
think I need to understand basics first:

WANTED: To add an element to the singly linked list.
HAPPENS: Nothing is added to the list.

int main(void)
{
struct my_struct* root_node = NULL;

list_add(root_node, 1);
list_print(root_node);

This is enough to see the problem. list add can no change root_node.
It is NULL at the start and no matte what the function does it will be
NULL afterwards.

You must decide between one of three different designs:

(a) The list_add operation must always be used in an assignment. It
return the new list: root = list_add(root, ...);

(b) You must pass a pointer to the list pointer so that list_add can
change it: list_add(&root, ...);

(c) You pass a pointer to some overall list structure (not the same as
the node structure) and list_add manipulates that.

The idea of having an unused head element is a version of this design
but I don't like it. If the list is to be more sophisticated (say be
having a head and tail pointer, or extra information list the length)
then (c) is the way to go, but it is a more complicated design.

You really should not get any further until you are certain that you
can see why what you are doing can't work, and why all of the above are
ways to solve this fundamental problem.

For a simple list I suggest (a) but you will get sound advice from
sane and experienced people who will advocate (b) and/or (c). When
you choose, stick with it until you are done -- changing part way
though makes giving advice almost impossible!

 

[Ben Bacarisse]

I think I did not understand what you mean ?

All I mean is that:

struct node *root == NULL;
...
root = list_add(root, 42);

is perfectly valid if list_add allocates a node and return a pointer
to the list. It is particularly easy if the item is added at the
front of the list and there is no reason not to do that as far as I
can see.

If you have to add items to the end of the list you should use another
strategy (see item (c) in my other post) unless you are prepared to
pay the cost of traversing the list just to add an item.

but then how do I know which element to add or remove, see:

struct my_struct* list_add(struct my_struct *const base_node, const int i )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;
struct my_struct* p = malloc( 1 * sizeof(*p));

if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}

p->num = i;
p->next = NULL;

for( ; s != NULL ; s = s->next );
s = p;

return s;
}

In this case there is only one variable i, which is being passed to
p->num, now if I make 2nd argument 3 dots (...) which means a variable
number of input, then how to pass that value to struct ?

Sorry, the ... were to suggest other arguments in a call. ... is not
legal C in a function call! Sorry if this confused you.

Using the return value you'd write code like this:

struct list_node {
struct list_node *next;
int number;
};

struct list_node *make_node(struct list_node *tail, int i)
{
struct list_node *np = malloc(sizeof *np);
if (np) {
np->next = tail;
np->number = i;
}
return np;
}

struct list_node *list_add_head(struct list_node *list, int i)
{
return make_node(list, i);
}

struct list_node *list_add_tail(struct list_node *list, int i)
{
if (list) {
list->next = list_add_tail(list->next, i);
return list;
}
else return make_node(list, i);
}

(Not tested.) I've written both the front adding and the tail adding
version. You can make the tail version iterative if you don't like
recursion, but you really need a different design or a list you can
efficiently add to the end of.

 

[arnuld]

This is enough to see the problem. list add can no change root_node.
It is NULL at the start and no matte what the function does it will be
NULL afterwards.

I know in C everything is passed by value. When you pass a pointer to
some function it is copy of that pointer but that copy still points to the
place where original pointer was pointing. So, I can use it to change
that. Right or wrong ?

You must decide between one of three different designs:

(a) The list_add operation must always be used in an assignment. It
return the new list: root = list_add(root, ...);

Thats what exactly I saw in K&R2. Though I liked option (b) .

(b) You must pass a pointer to the list pointer so that list_add can
change it: list_add(&root, ...);

(c) You pass a pointer to some overall list structure (not the same as
the node structure) and list_add manipulates that.

The idea of having an unused head element is a version of this design
but I don't like it. If the list is to be more sophisticated (say be
having a head and tail pointer, or extra information list the length)
then (c) is the way to go, but it is a more complicated design.

You really should not get any further until you are certain that you can
see why what you are doing can't work, and why all of the above are ways
to solve this fundamental problem.

Lets implement it using (b) (and I have removed some const-edness ) but it
still does not work:


/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* VERISON 0.2
*
*/

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


struct my_struct* list_add( struct my_struct **, const int);

void list_print( const struct my_struct* );
void list_print_element(const struct my_struct *const );


struct my_struct
{
int num;
struct my_struct* next;
};



int main(void)
{
struct my_struct* root_node = NULL;

list_add(&root_node, 1);
list_print(root_node);

return 0;
}


struct my_struct* list_add(struct my_struct ** base_node, const int i )
{
struct my_struct* s = *base_node;
struct my_struct* p = malloc( 1 * sizeof(*p) );

if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}

p->num = i;
p->next = NULL;


if( NULL == s )
{
printf("Base Node was NULL, so adding current maloc()ed struct to base\n");
s = p;
}
else
{
printf("Base node is non-NULL, so adding it to the end of the list\n");
for( ; s->next != NULL ; s = s->next);
s->next = p;
}

return *base_node;
}


void list_print( const struct my_struct *const sp )
{
const struct my_struct* p = sp;

for( ; NULL != p; p = p->next )
{
list_print_element(p);
}

printf("\n------------------\n");
}


void list_print_element(const struct my_struct *const p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}

 

[BartC]

Lets implement it using (b) (and I have removed some const-edness ) but it
still does not work:

list_add(&root_node, 1);

I put in these print statements:

printf("Root node before: %x",root_node);
list_add(&root_node, 1);
printf("Root node after: %x",root_node);

root_node is 0 before, and still 0 after, so is not being changed.

list_add is now returning a value that is not being used, and it's not
changing root_node (for example by using *base_node=something).

 

[Ben Bacarisse]

I know in C everything is passed by value. When you pass a pointer to
some function it is copy of that pointer but that copy still points to the
place where original pointer was pointing. So, I can use it to change
that. Right or wrong ?

Right. Do you see why your code above can't work though?

Lets implement it using (b)
OK/

(and I have removed some const-edness ) but it
still does not work:

struct my_struct
{
int num;
struct my_struct* next;
};

struct my_struct* list_add(struct my_struct ** base_node, const int i )
{
struct my_struct* s = *base_node;
struct my_struct* p = malloc( 1 * sizeof(*p) );
if( NULL == p ) {
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}
p->num = i;
p->next = NULL;
if( NULL == s ) {
printf("Base Node was NULL, so adding current maloc()ed struct to base\n");
s = p;
}
else {
printf("Base node is non-NULL, so adding it to the end of the list\n");
for( ; s->next != NULL ; s = s->next);
s->next = p;
}
return *base_node;
}

I have changed the layout because I think it helps to see the whole
thing. There is no code that changes what base_node points to so
this code, also, will have no effect at all on the list pointer whose
address you pass to it. (The name is bad, BTW. base node is not a
node. It is not even a pointer to one.)

I.e. after a call like list_add(&root, 42); root will be exactly the
same as it was before.

I could just re-write this to work, but surely it would help you more
if you work though what it does to see why it is not correct?

 

[arnuld]

I put in these print statements:

printf("Root node before: %x",root_node);
list_add(&root_node, 1);
printf("Root node after: %x",root_node);

root_node is 0 before, and still 0 after, so is not being changed.

yes, it does not.

list_add is now returning a value that is not being used,

yes, I plan to use it later. Actually, all of the functions I have ever
written for my company always return something (except of function who
just print the information), so I have made it my standard.

and it's not changing root_node (for example by using
*base_node=something).

I see that and I am out of any understanding why it is happening.
This Pointer-business is really shi**ing my brain.

 

[arnuld]

Right. Do you see why your code above can't work though?

No, I don't see why.

I could just re-write this to work, but surely it would help you more
if you work though what it does to see why it is not correct?

yes, I wrote this code and found that out:

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

void change_p1(int** p1, int* p2 );

int main(void)
{
int i = 1;
int j = 2;

int* p1 = &i;
int* p2 = &j;

printf("*p1 = %d\n", *p1);

change_p1(&p1, p2);

printf("*p1 = %d\n", *p1);

return 0;
}


void change_p1(int** p1, int* p2 )
{
*p1 = p2;
}


================= OUTPUT =========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
[arnuld@dune programs]$ ./a.out
*p1 = 1
*p1 = 2
[arnuld@dune programs]$





So, the problem was I was using a local pointer to change the value of the
passed argument. I don't see why it is wrong to do so though. Here is the
new working code:


/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* VERISON 0.3
*
*/

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


struct my_struct* list_add( struct my_struct **, const int);

void list_print( const struct my_struct* );
void list_print_element(const struct my_struct *const );


struct my_struct
{
int num;
struct my_struct* next;
};



int main(void)
{
struct my_struct* list_head = NULL;

printf("List default\n");
list_print(list_head);
printf("List after adding values\n");
list_add(&list_head, 1);
list_add(&list_head, 2);
list_print(list_head);

return 0;
}


struct my_struct* list_add(struct my_struct ** head, const int i )
{
struct my_struct* p = malloc( 1 * sizeof(*p) );

if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}

p->num = i;
p->next = NULL;


if( NULL == *head )
{
/* printf("Base Node was NULL, so adding current maloc()ed struct to base\n"); */
*head = p;
}
else
{
/* printf("Base node is non-NULL, so adding it to the end of the list\n"); */
for( ; (*head)->next != NULL ; *head = (*head)->next);
(*head)->next = p;
}

return *head;
}


void list_print( const struct my_struct *const sp )
{
const struct my_struct* p = sp;

for( ; NULL != p; p = p->next )
{
list_print_element(p);
}

printf("\n------------------\n");
}


void list_print_element(const struct my_struct *const p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}


========================== OUTPUT =================================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
[arnuld@dune programs]$ ./a.out
List default

 

[Beej Jorgensen]

I've taken the liberty of changing all your "struct my_struct *" types
to "int", which is _not_ something you should do, but it might help
illustrate why the code has no effect. (I chopped out most of the
function just to bring attention to the bits necessary for the
demonstration).

int list_add(int *base_node, const int i)
{
int s = *base_node;
int p = 3490; // your malloc used to be here

if( 0 == s )
{
s = p;
}

return *base_node;
}

Say you call this with:

int base = 0; // 0 in lieu of NULL

list_add(&base, 10);

What is there in list_add() that would cause the value of "base" in the
caller to change?

You're definitely on the right track from all the code I've seen posted.

-Beej

 

[Beej Jorgensen]

So, the problem was I was using a local pointer to change the value of the
passed argument. I don't see why it is wrong to do so though.

It was "wrong" because the local pointer was a copy of the passed-in
pointer, and modifying the local copy didn't change anything from the
perspective of the caller.

Let's mess up your toy program in the same way. First, your working
version:

void change_p1(int** p1, int* p2 ) // working
{
*p1 = p2;
}

(Play-by-play: p1 points to X, we dereference p1 to get X, and we assign
p2 into X, thus modifying it. Pretty straightforward.)

Now I'll break it to make it more comparable to the non-working list_add:

void change_p1(int** p1, int* p2 ) // BROKEN
{
int *foo = *p1;
foo = p2;
}

See that I never assigned anything to *p1, so nothing was changed from
the caller's perspective. Only the local value of "foo" changed, which
means nothing to the caller. (Play-by-play: p1 points to X, we use *p1
to get X, we make a copy of X in foo, and then we MODIFY THE COPY OF X
stored in foo. The original X pointed to by p1 is never modified, and
this is why it doesn't work.)

Now just for fun, let's make it work again, still using an intermediate
local variable:

void change_p1(int** p1, int* p2 ) // working again
{
int **frotz = p1;
*frotz = p2;
}

There's nothing stopping us from copying a pointer, so there I've copied
p1 into local variable frotz. p1 and frotz both point to the same thing
now (they're both pointing to the same int*). So I can dereference
either of them and modify what they both point to. (Play-by-play: p1
points to X, we copy p1 into frotz so frotz also points at X, we
dereference frotz to get X , and we assign p2 into it, thus modifying
X.) There are no copies of X in this example; there is only a copy of a
pointer to X.

To repeat myself, since frotz and p1 both point at the same thing, we
could dereference either of them to change what they both point at.
That is, I could have written "*p1 = p2" instead of "*frotz = p2" for
the exact same result, but then I would be right back at your working
example that I started with!

The important part is that we dereference p1 (or a copy of p1) and
assign into it. (If we don't we assign into whatever p1 points at,
we'll never modify it, of course!*) This is missing from the version
labeled "BROKEN", above.

-Beej, needs to sleep

* Please excuse my using the word "assign" to represent "all possible
ways of modifying a piece of data".

 

[arnuld]

Right. Do you see why your code above can't work though?

yes, because I was modifying the local pointer, not the one I go from
argument.

I could just re-write this to work, but surely it would help you more
if you work though what it does to see why it is not correct?

I have rewritten it but now it is not accomdating more than 2
elements. All of the elemets just vanish


/* This C implementation of singly linked list implements 3
operations: add, remove and insert elements at some specific position
in
* the list.
*
* VERISON 0.4
*
*/

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


/* How about always keeping track of tail of list (end of list I mean)
and then pass that to list_add(), that way, list_add() will always
be O(1), rather than O(n)
*/
struct my_struct* list_add( struct my_struct **, const int);

void list_print( const struct my_struct* );
void list_print_element(const struct my_struct *const );


struct my_struct
{
int num;
struct my_struct* next;
};



int main(void)
{
struct my_struct* list_head = NULL;

printf("List default\n");
list_print(list_head);

list_add(&list_head, 1);
list_add(&list_head, 2);
list_add(&list_head, 3);

list_print(list_head);


return 0;
}


struct my_struct* list_add(struct my_struct** head, const int i)
{
struct my_struct* ps = *head;
struct my_struct* p = malloc( 1 * sizeof(*p) );

if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__,
"list_add");
return NULL;
}

p->num = i;
p->next = NULL;


if( NULL == *head )
{
printf("Base Node was NULL, so adding current maloc()ed struct
to base: %d\n\n", p->num);
*head = p;
}
else
{
printf("Base node is non-NULL, so adding it to the end of the
list: %d\n", p->num);
for( ; NULL != (*head)->next; *head = (*head)->next ) ;
(*head)->next = p;
}

return ps;
}



void list_print( const struct my_struct *const sp )
{
const struct my_struct* p = sp;

for( ; NULL != p; p = p->next )
{
list_print_element(p);
}

printf("\n------------------\n");
}


void list_print_element(const struct my_struct *const p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}

============== OUTPUT ================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
[arnuld@dune programs]$ ./a.out
List default

------------------
Base Node was NULL, so adding current maloc()ed struct to base: 1

Base node is non-NULL, so adding it to the end of the list: 2
Base node is non-NULL, so adding it to the end of the list: 3
Num = 2
Num = 3