-
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
-
> 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.
-
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 = NULL;
*Head = new; // head become new
}
}
int main()
{
struct node *head = NULL;
insert ( &head, 1);
insert ( &head, 2);
return 0;
}
I am expecting output like 1-> 2-> NULL
But program gives list like this
1 -> NULL;
2 -> NULL
-
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 );
}