Operations with pointers in linked lists

Question

Generally, I know that a pointer stores the memory address of another value located in computer memory, for example:

int firstvalue= 5
int * p1;
p1 = &firstvalue;  // p1 = address of firstvalue

What happens if we define an operation like the following in a linked list? Does *current=*list means that the value pointed to by current equals to the value pointed to by list? And what does it mean if we define ecur=current?

int function(struct list_t **list){
    struct list_t *ecur=NULL;
    struct list_t *current=*list;
    ecur=current;
}

Update: What does it do *list=remove(*list, param1, param2)? And why is that?

remove is a function that returns a modified list of list.

Update 2: Why do we need to define a pointer to pointer in order to modify the list? Is *list a pointer to pointer?

Answer 1

Why do we need to define a pointer to pointer in order to modify the list?

Let me add a complete program, albeit short, to illustrate it better. It defines a simply linked list and builds it while keeping it ordered. Yes, I know it would be easier to simply call qsort(), but I want to demonstrate how adding one level of indirection —the pointer to pointer— allows to insert elements smoothly, without testing for special cases.

// C pointer exercise: sort arguments
#include <stdio.h>
#include <strings.h>
#include <stdlib.h>

struct list
{
    char *arg;
    struct list *next;
};

int main(int argc, char *argv[])
{
    // pointer to base, running pointer and pointer to pointer
    struct list *base = NULL, *p, **pp;

    for (int i = 1; i < argc; ++i)
    {
        struct list *new_entry = malloc(sizeof(struct list));
        if (new_entry)
        {
            new_entry->arg = argv[i];

            // find where to insert new entry
            for (pp = &base; *pp; pp = &(*pp)->next)
                if (strcasecmp(new_entry->arg, (*pp)->arg) < 0)
                    break;

            // insertion in a simply linked list
            new_entry->next = *pp;
            *pp = new_entry;
        }
    }

    // display and cleanup
    for (p = base; p;)
    {
        struct list * tmp = p->next;
        puts(p->arg);
        free(p);
        p = tmp;
    }

    return 0;
}

Answer 2

Why do we need to define a pointer to pointer in order to modify the list? Is *list a pointer to pointer?

Remember that C passes all function arguments by value - the formal argument in the function definition is a different object in memory from the actual argument in the function call. For example:

void swap( int a, int b )
{
  int tmp = a;
  a = b;
  b = tmp;
}

void foo( void )
{
  int x = 1;
  int y = 2;

  swap( x, y );
}

a is a different object in memory than x, and b is a different object in memory than y, so swapping a and b has no effect on x and y. In order to swap the values of x and y, you must pass pointers to them:

void swap( int *a, int *b )
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void foo( void )
{
  int x = 1;
  int y = 2;

  swap( &x, &y );
}

The expression *a is the same as x, so writing to *a is the same as writing to x. Same for *b and y.

So, in order for a function to write to a parameter, you must pass a pointer to that parameter:

void foo ( T *arg )
{
  *arg = new_value(); // writes a new value to the thing arg points to
}

void bar( void )
{
  T var;
  foo( &var );        // write a new value to var
}

This is true for any non-array type T. Let's replace T with a pointer type P *:

void foo( P **arg )
{
  *arg = new_value(); // write a new *pointer* value to the thing arg points to
}

void bar( void )
{
  P *var;
  foo( &var );        // write a new pointer value to var
}

The semantics are exactly the same - all that's changed is the type.

If a function has the potential to modify a list * object (say pointing it at a new list head), then you must pass a pointer to that list * object:

void add_node( struct list_t **list, struct list_t *node )
{
  if ( !*list || (node->value < (*list)->value) ) // make node new head of list
    *list = node;
  else
    // add node somewhere else in the list
}

int main( void )
{
  struct list_t *list = NULL;
  ...
  struct list_t *node = newNode( value );
  add_node( &list, node );
  ...
}

Answer 3

I had a similar knot in my head with this post. I'd like to rearrange your function a bit, so it's easier to understand what's going on:

int function(struct list_t **list)
{
    struct list_t *current = *list;
    struct list_t *ecur    = current;
}

If we call this function with an element foo we essentially get this:

struct list_t foo      = { .data = "foo" };
struct list_t *bar     = &foo;
struct list_t **list   = &bar;
struct list_t *current = *list;
struct list_t *ecur    = current;

We have five declarations and five assignments. For better readability, I'll write everything down without declarations:

foo     = { .data = "foo" };
bar     = &foo;
list    = &bar;
current = *list;
ecur    = current;

Now, let's walk through it:

1. foo is a struct. It contains the above data-field.
2. bar is a pointer to struct. It contains the address of foo
3. list is a pointer to a pointer to struct. It contains the address of bar
4. current is a pointer to struct. It contains the contents of the contents of list, which is the address of foo
5. ecur is a pointer to struct. It's identical to current and contains the address bar

In the end we can simplify the whole example to this:

struct list_t foo   = { .data = "foo" };
struct list_t *ecur = &foo;

What does it all mean?

• list: Because list is a pointer to a pointer you are able to modify bar to point to something completely different, by de-referencing it (*list = ...)
• current/ecur: that's what bar originally pointed too. By de-referencing you could change the data-field itself ((*ecur).data = "banana" or better ecur->data)

I hope I could clarify things and didn't make it worse ;)

Answer 4

The variable list is a pointer to a pointer to a struct list_t. If we (just as an example) assume that the struct is placed at address 2000 and that the unnamed pointer is at address 1000 it will look like this:

Then you have the initialization that adds two new variables. Both as pointer to a struct list_t.

struct list_t *ecur=NULL;
struct list_t *current=*list;

So the picture now becomes:

Notice that current got the same value as the "some-pointer" in the middle because it is *list that was assigned to current.

Then you have the assignment:

ecur=current;

which means that ecur gets the same value as current and gives the picture:

Update: What does it do *list=remove(*list, param1, param2) ?

It changes the value of the "some-pointer" in the middle of the picture. This is for instance needed if the remove function removes the first element in a linked list.

Answer 5

TYPE *p = ptype /*variable of type: TYPE * */;

is not an assignment. It's an initialization, which for an auto-matic (=on-the-stack) p can be rewritten as:

TYPE *p;
p = ptype;

(not TYPE *p; *p=ptype; /*would be a type error*/)

In terms of your example:

struct list_t *current=*list;

sets where current will point to (the same place as what *list points to (*list is also a pointer because list is a doubly-indirect pointer)) without doing anything whatsoever with what current will point at (*current) after the initialization.

All of this is just conceptual, though. Your function doesn't have any externally visible effects so an optimizing compiler should completely delete its body.