Thread: List

I am trying to make a list where current node should point to next node in list

Code:

#include<stdio.h>

#include<stdlib.h>

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

void insert ( struct node ** Head, int value)
{
    struct node *new = malloc(sizeof(struct node));
    
    if ( new != NULL)
    {
        new -> data = value'
        new -> next =         // this line should point to next node in list 
        *Head = new           // head become new 
    }
}

int main()
{
    insert ( &head, 1);
    return 0;
}

How make a list where current node point to next node in list ?

You do

Code:

new -> next = *Head;
*Head = new;

This builds a list by prepending elements to the front of the list.

> Yes I know but I want to add node after current node and I don't understand how to do it
So at the tail of the list then?

insert(1)
insert(2)
insert(3)
insert(4)
gets you
1 -> 2 -> 3 -> 4 -> NULL

If you have some idea that isn't inserting at the head or the tail, you need to show us some examples of what you want.

Here.

Code:

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

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

void insert ( struct node ** Head, int value)
{
    struct node *new = malloc(sizeof(struct node));
    
    if ( new != NULL)
    {
        new -> data = value;
        new -> next = *Head;   // I told you this in post #2       
        *Head = new;           // head become new 
    }
}

void append ( struct node ** Head, int value)
{
    struct node *new = malloc(sizeof(struct node));
    
    if ( new != NULL)
    {
        new -> data = value;
        new -> next =  NULL;     
        if ( !*Head ) {     // Empty list
            *Head = new;    // becomes the new node
        } else {
            struct node *temp = *Head;
            while ( temp->next ) temp = temp->next; // find the last node
            temp->next = new;   // and append
        }
    }
}

int main()
{
    struct node *head = NULL;
    append ( &head, 1);
    append ( &head, 2);
    append ( &head, 3);
    append ( &head, 4);

    for ( struct node *n = head ; n ; n = n->next ) {
        printf("%d->",n->data);
    }
    printf("NULL\n");

    return 0;
}

A better approach using sentinel nodes (less special conditions):

Code:

// Sedgewick method.

#include <stdio.h>

// A "base" node.
struct node { struct node *next; };

// A list (with sentinel nodes).
struct list { struct node head, tail; };

// list initializer
#define LIST_INIT(list__) (struct list){ .head.next = &(list__).tail, .tail.next = &(list__).tail }

_Bool slist_empty( struct list *list )
{ return list->head.next == &list->tail; }

// WARNING: 'node' never can be the tail sentinel node!
// it can be any other node (including sentinel 'head').
void slist_insertAfter( struct node *node, struct node *new )
{
  new->next = node->next;
  node->next = new;
}

// ANY node, including both sentinels, can be used as 'node'.
// return NULL if list is empty or the "deleted" node ptr.
struct node *slist_deleteAfter( struct node *node )
{
  struct node *next;

  next = node->next;
  if ( next == next->next )
    return NULL;

  node->next = next->next;

  return next;
}

void slist_clear( struct list *list, void (*dtor)( void * ) )
{
  while ( 1 )
  {
    struct node *node;

    node = slist_deleteAfter( &list->head );
    if ( ! node )
      break;

    if ( dtor )
      dtor( node );
  }
}

// macro for simple list iteration.
#define for_each(iter__,listptr__) \
  for ( (iter__) = (listptr__)->head.next; (iter__) != (iter__)->next; (iter__) = (iter__)->next )

// macro for list iteration where we can change the list.
// using an auxiliar 'iterator'.
#define for_each_safe(iter__,tmp__,listptr__) \
  for ( (iter__) = (listptr__)->head.next, (tmp__) = (iter__)->next; \
        (iter__) != (iter__)->next; \
        (iter__) = (tmp__) )

//--- test ---
int main( void )
{
  struct list list = LIST_INIT(list);
  struct node *p;

   // Our internal nodes are polymorphic this way.
  struct mynode {
    struct node *next;  // MUST BE the first member.

    int value;
  };

  static struct mynode node[] = { { .value = 0 }, { .value = 1 }, { .value = 2 } };

  // Of course we could do:
  //
  //    struct mynode *q, *r;
  //    q = malloc( siseof *q ); q->value = 2; slist_insertAfter( &list.head, (struct node *)q );
  //    r = malloc( siseof *r ); r->value = 1; slist_insertAfter( (struct node *)q, (struct node *)r ); q = r;
  //    r = malloc( siseof *r ); r->value = 0; slist_insertAfter( (struct node *)q, (struct node *)r );
  //
  // Notice that memory allocation have nothing to do with the list internals.

  slist_insertAfter( &list.head, (struct node *)&node[2] );
  slist_insertAfter( (struct node *)&node[2], (struct node *)&node[1] );
  slist_insertAfter( (struct node *)&node[1], (struct node *)&node[0] );

  for_each( p, &list )
  {
    struct mynode *q = (struct mynode *)p;

    printf( "%d ", q->value );
  }
  
  putchar( '\n' );

  // if we had allocated the nodes we could do
  //    slist_clear( &list, free );
  slist_clear( &list, NULL );
}