Adding items to a linked list-CodePudding

I'd like to add an element to a list of element. My list is a struct containing a double, an integer and a pointer to the next element. Could someone tell me how to do the Add function please

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

typedef struct Liste Liste;
struct Liste{
    double c;
    int n;
    Liste* next; // pointe sur l'élément suivant
};

void Add(Liste array, Liste item) {
    Liste* last = array.next;
    while (last != NULL) {
        last = last->next;
    }
    array.next = &item;
    printf("%p\n", array.next);
}

int main(){
    Liste array = {12.4, 4, NULL};
    printf("%f\n", array.c);
    Liste item = {15.4, 7, NULL};
    Add(array, item);
    printf("%p\n", array.next);
    return 0;
}

CodePudding user response：

Pass-by-value

In Add, C makes a copy of all the function parameters; their scope is the function itself. When one returns, the function parameters are popped from the stack and there is no way to get them back, as you have seen. The way to mutate structures is to pass a pointer to the structure, then modify that pointer using the structure pointer dereference operator, (arrow ->.)

Design

The reason one would use a linked-list is it is very cheap to reorder it, but the head of your linked-list is fixed, so you can't change it. You might change this by delineating the container, the list itself, from the contents. This is similar to using a double-pointer, but I think less confusing.

struct Noeud {
    double c;
    int n;
    struct Noeud* next; // pointe sur l'élément suivant
};

struct Liste {
    struct Noeud *tete; // singly-linked-list est defini par un pointer seul
};

Then you can add, (I've included assert.h.)

/* `O(n)` */
static void AddQueue(struct Liste *liste, struct Noeud *item) {
    assert(liste && item && item->next == NULL);
    struct Noeud* last = liste->tete;
    if(last == NULL) { // case spécieux
        liste->tete = item;
    } else {
        while (last->next != NULL) {
            last = last->next;
        }
        last->next = item;
    }
}

However, it's much simpler and asymptotically faster to add at the beginning of the list.

CodePudding user response：

Pointerstructures like a linked list are powerful tools with a wide rage of application. But first you have to understand pointers.

A pointer is a datastructure which contains the address of a datastructure.

Whenever you call a function the arguments of it are copied (pushed) to the stack.

If the arguments require a lot of storage space you use a pointer instead.

the code below uses pointers to create a linked list

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"


typedef struct List List;

struct List{
  double c;
  int n;
  List *next; 
};


void AddItemEnd( List *RootItem, List *Item )
{
  List *Last = RootItem;
  while( Last->next != NULL )
  {
    Last = Last->next;
  }
  Last->next = Item;
}

void AddItemAtPos( List *RootItem, List *Item, unsigned int Pos )
{
  if( Pos == 0 )
  {
    Item->next = RootItem;
  }
  else
  {
    List *TempItem = RootItem;
    for( unsigned int i = 1; i < Pos && TempItem->next != NULL;   i  )
    {
      TempItem = TempItem->next;
    }

    Item->next = TempItem->next;
    TempItem->next = Item;
  }
}


void RemoveItemAtPos( List *RootItem, unsigned int Pos )
{
  if( Pos == 0 )
  {
    free( (void*) RootItem );
  }
  else
  {
    List *TempItem = RootItem;

    for( unsigned int i = 1; i < Pos && TempItem->next != NULL;   i  )
    {
      TempItem = TempItem->next;
    }

    if( TempItem->next == NULL )
    {
      return;

    }else if( TempItem->next->next != NULL )
    {
      List *ItemToDelete = TempItem->next;
      TempItem->next = TempItem->next->next;
      free( (void*) ItemToDelete );
    
    }else
    {
      free( (void*) TempItem->next );
      TempItem->next =NULL;
    }
  }
}



int main(void) {
  List *RootItem = malloc( sizeof( List )); 
  RootItem->c = 12.4;
  RootItem->n =  4;
  RootItem->next = NULL;

  List *Item1 = malloc( sizeof(List ));
  Item1->c = 15.4; 
  Item1->n = 7;
  Item1->next = NULL ;

  AddItemEnd( RootItem, Item1 );

  List *IterationItem;

  printf( "List created with AddItemEnd()\n\n" );
  for( IterationItem = RootItem; IterationItem != NULL; IterationItem = IterationItem->next )
  {
    printf( "c: %lf\nn: %d\n\n", IterationItem->c, IterationItem->n );
  }



  List *item2 = malloc( sizeof( List ));
  item2->c = 23.4;
  item2->n = 1846;
  item2->next = NULL ;

  AddItemAtPos( RootItem, item2, 1 );

  printf( "\n\nList extended with AddItemAtPos()\n\n");
  for( IterationItem = RootItem; IterationItem != NULL; IterationItem = IterationItem->next )
  {
    printf( "c: %lf\nn: %d\n\n", IterationItem->c, IterationItem->n );
  }
  
  RemoveItemAtPos(RootItem, 1 );

  printf( "\n\nList after RemoveItemAtPos()\n\n");
  for( IterationItem = RootItem; IterationItem != NULL; IterationItem = IterationItem->next )
  {
    printf( "c: %lf\nn: %d\n\n", IterationItem->c, IterationItem->n );
  }
  free( (void*) RootItem );
  free( (void*) item2 );

  return 0;
}

CodePudding user response：

The key elements when dealing with lists is pointers and using memory allocation.

If we disregard your add function and just do a simple example you will probably get the geist of it.

First allocate you starting list like this

Liste* array = malloc(sizeof(Liste));

Now you have one uninitialized block of memory that array points to. You then need to initialize it.

array->c = 12.4;
array->n = 4;
array->next = NULL;

in order to add a new entry to your list you need to again allocate memory for the next node and initialize it plus set the previous node next pointer to point to it i.e. array->next.

Liste* item = malloc(sizeof(Liste));
item->c = 15.4;
item->n = 7;
item->next = NULL;
array->next = item;

now you have a list of two elements where array points to the first

printing your short list

Liste* p = array;
while (p != NULL)
{
  printf("%lf %d %p\n", p->c, p->n, p->next);
  p = p->next;
}