static entry_t *find_previous_entry_for_key(entry_t *first_entry, int key)
{
  entry_t *previous = first_entry; 
  entry_t *cursor = previous->next;
  while (cursor != NULL) 
  { 
    if (cursor -> key == key)
      {
        return previous;
      }
    cursor = cursor->next;
  }
  return previous;
}

Is there a way to re-write this using a double pointer? The struct for entry t looks like this:

struct entry
{
  int key;       // holds the key
  char *value;   // holds the value
  entry_t *next; // points to the next entry (possibly NULL)
};

CodePudding user response：

Is there a way to re-write this using a double pointer?

I take the question to be whether it is possible to return the result via an out parameter, which would need to be a double pointer because the value to be returned is a (single) pointer. Yes, of course that's possible:

static void find_previous_entry_for_key(entry_t *first_entry, int key,
    entry_t **result)
{
  entry_t *previous = first_entry; 
  // ...

  // return previous;
  *result = previous;
}

Then, instead of calling it like this:

// old way
entry_t *result = find_previous_entry_for_key(head, 42);

one would use

// new way
entry_t *result;
find_previous_entry_for_key(head, 42, &result);

CodePudding user response：

For starters the function is incorrect. It can invoke undefined behavior at least because there is no check whether the pointer first_entry is equal to NULL.

Also within the function the pointer previous is not being changed. So the function always returns the value of the passed to it pointer first_entry due to this assignment.

entry_t *previous = first_entry; 

So the function as it is written does not make a sense.

It seems that the function is designed to return a pointer to a pointer in the list that points to a node with the given value of the parameter key.

Using this function you will be able to insert a new node before the node with the given value of key or to remove a node from the list with the given value of key.

The function declaration and definition can look as shown in the demonstrative program below.

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

typedef struct entry entry_t;

struct entry
{
    int key;       // holds the key
    char *value;   // holds the value
    entry_t *next; // points to the next entry (possibly NULL)
};


void display( const entry_t *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "{ %d, %s } -> ", head->key, head->value );
    }
    
    puts( "null" );
}

static entry_t ** find_previous_entry_for_key( entry_t **first_entry, int key ) 
{
    while ( *first_entry != NULL && ( *first_entry )->key != key )
    {
        first_entry = &( *first_entry )->next;
    }

    return first_entry;
}

int main(void) 
{
    entry_t *head = NULL;
    
    int key = 1;
    char *value = "A";
    
    entry_t **target = find_previous_entry_for_key( &head, key );
    
    entry_t *new_entry = malloc( sizeof( entry_t ) );
    new_entry->key = key;
    new_entry->value = value;
    new_entry->next = *target;
    *target = new_entry;

    display( head );
    
    key = 3;
    value = "C";
    
    target = find_previous_entry_for_key( &head, key );
    
    new_entry = malloc( sizeof( entry_t ) );
    new_entry->key = key;
    new_entry->value = value;
    new_entry->next = *target;
    *target = new_entry;

    display( head );

    int new_key = 2;
    key = 3;
    value = "B";
    
    target = find_previous_entry_for_key( &head, key );
    
    new_entry = malloc( sizeof( entry_t ) );
    new_entry->key = new_key;
    new_entry->value = value;
    new_entry->next = *target;
    *target  = new_entry;

    display( head );
    
    key = 2;
    
    target = find_previous_entry_for_key( &head, key );
    
    
    if ( *target != NULL )
    {
        new_entry = *target;
        *target = ( *target )->next;
        free( new_entry );
    }

    display( head );
    
    key = 1;
    
    target = find_previous_entry_for_key( &head, key );
    
    
    if ( *target != NULL )
    {
        new_entry = *target;
        *target = ( *target )->next;
        free( new_entry );
    }

    display( head );
    
    key = 3;
    
    target = find_previous_entry_for_key( &head, key );
    
    
    if ( *target != NULL )
    {
        new_entry = *target;
        *target = ( *target )->next;
        free( new_entry );
    }

    display( head );
    
    return 0;
}

The program output is

{ 1, A } -> null
{ 1, A } -> { 3, C } -> null
{ 1, A } -> { 2, B } -> { 3, C } -> null
{ 1, A } -> { 3, C } -> null
{ 3, C } -> null
null

As you can see you are able to insert a node with key equal to 2 before the node with key equal to 3. Or you can remove the node before the node with key equal to 2 or the first node using the function.

CodePudding user response：

From smartphone, so I keep it terse.

Yes, in C it is the most elegant way to use an alias, a pointer to a variable.

Normally on has a node* head and you do

node** p = &head;
while (*p && (*p)->key != key) p = &(*p)->next;
*p = (*p)->next; // remove without free

p will point to (is an alias of) either head or a next field. Thus you can remove or insert nodes.

The code above assumes the key is found.

So a previous pointer is not needed as for instance in Java. A unique feature of C.