linked list

[Bill Cunningham]

Can someone show me a very simple example of a linked list in C? The
simplest possible.

Bill

[Bill Cunningham]

I have this

struct list{
int number=1;
struct list *next;
};

I only want to go to the next page right now.

Bill

[pete]

Bill Cunningham wrote:
>
> Can someone show me a very simple example
> of a linked list in C? The simplest possible.

/* BEGIN d_append.c */
/*
** Demonstration of use of int list functions.
*/
#include <stdio.h>
#include <stdlib.h>

#define NUMBERS 15,14,13,7,20,9,8,12,11,6

#define NMEMB(A) (sizeof (A) / sizeof *(A))

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

typedef struct d_node d_type;

int d_fprintf(const d_type *node, FILE *stream);
d_type *d_append(d_type **head, d_type *tail, int data);
void d_free(d_type *node);

int
main(void)
{
d_type *head = NULL;
d_type *tail = NULL;
int numbers[] = {NUMBERS};
int *ptr = numbers;
int *const after = numbers + NMEMB(numbers);

puts("/* BEGIN d_append.c output */");
puts("\nOriginal order of list of ints:");
do {
tail = d_append(&head, tail, *ptr);
if (tail == NULL) {
puts("malloc trouble!");
break;
}
} while (++ptr != after);
d_fprintf(head, stdout);
d_free(head);
puts("\n/* END d_append.c output */");
return 0;
}

int
d_fprintf(const d_type *node, FILE *stream)
{
int rc = 0;

while (node != NULL) {
if (0 > (rc = fprintf(stream, "%d\n", node -> data))) {
break;
}
node = node -> next;
}
return rc;
}

d_type *
d_append(d_type **head, d_type *tail, int data)
{
d_type *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -> next = NULL;
node -> data = data;
if (*head != NULL) {
tail -> next = node;
} else {
*head = node;
}
}
return node;
}

void
d_free(d_type *node)
{
d_type *next_node;

while (node != NULL) {
next_node = node -> next;
free(node);
node = next_node;
}
}

/* END d_append.c */


--
pete

[Bill Cunningham]

pete wrote:
>
> /* BEGIN d_append.c */
> /*
> ** Demonstration of use of int list functions.
> */
> #include <stdio.h>
> #include <stdlib.h>
>
> #define NUMBERS 15,14,13,7,20,9,8,12,11,6
>
> #define NMEMB(A) (sizeof (A) / sizeof *(A))
>
> struct d_node {
> struct d_node *next;
> int data;
> };
>
> typedef struct d_node d_type;

Wow if this is simple I'd hate to see complex. Whew. One step at a time
I guess.

> int d_fprintf(const d_type *node, FILE *stream);
> d_type *d_append(d_type **head, d_type *tail, int data);

I've never worked with pointers to pointers. Except in the command line.
What's head and tail for? I only used next. I don't want to try interation
and reversing functions yet.

[...]

Bill

[pete]

Bill Cunningham wrote:
>
> pete wrote:
> >
> > /* BEGIN d_append.c */
> > /*
> > ** Demonstration of use of int list functions.
> > */
> > #include <stdio.h>
> > #include <stdlib.h>
> >
> > #define NUMBERS 15,14,13,7,20,9,8,12,11,6
> >
> > #define NMEMB(A) (sizeof (A) / sizeof *(A))
> >
> > struct d_node {
> > struct d_node *next;
> > int data;
> > };
> >
> > typedef struct d_node d_type;
>
> Wow if this is simple I'd hate to see complex.
> Whew. One step at a time
> I guess.
>
> > int d_fprintf(const d_type *node, FILE *stream);
> > d_type *d_append(d_type **head, d_type *tail, int data);
>
> I've never worked with pointers to pointers.
> Except in the command line.
> What's head and tail for?

head points to the first node of the linked list.
tail points to the last node of the linked list.

>I only used next.

What can you do with a linked list,
by only using next?

I simplified it:

/* BEGIN d_start.c */

/*
** Demonstration of use of int list functions.

** d_start
** d_append_0

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

#define NUMBERS 15,14,13,7,20,9,8,12,11,6

#define NMEMB(A) (sizeof (A) / sizeof *(A))

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

int d_fprintf(const struct d_node *node, FILE *stream);
struct d_node *d_start(int data);
struct d_node *d_append_0(struct d_node *tail, int data);
void d_free(struct d_node *node);

int
main(void)
{
struct d_node *head;
struct d_node *tail;

int numbers[] = {NUMBERS};
int *ptr = numbers;
int *const after = numbers + NMEMB(numbers);

puts("/* BEGIN d_start.c output */");

puts("\nOriginal order of list of ints:");

head = tail = d_start(*ptr);
if (head != NULL) {
while (++ptr != after) {
tail = d_append_0(tail, *ptr);

if (tail == NULL) {
puts("malloc trouble!");
break;
}
}

} else {
puts("malloc trouble!");
}
d_fprintf(head, stdout);
d_free(head);
puts("\n/* END d_start.c output */");
return 0;
}

int
d_fprintf(const struct d_node *node, FILE *stream)

{
int rc = 0;

while (node != NULL) {
if (0 > (rc = fprintf(stream, "%d\n", node -> data))) {
break;
}
node = node -> next;
}
return rc;
}

struct d_node *
d_start(int data)
{
struct d_node *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -> next = NULL;
node -> data = data;
}

return node;
}

struct d_node *
d_append_0(struct d_node *tail, int data)
{
struct d_node *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -> next = NULL;
node -> data = data;

tail -> next = node;
}

return node;
}

void
d_free(struct d_node *node)
{
struct d_node *next_node;

while (node != NULL) {
next_node = node -> next;
free(node);
node = next_node;
}
}

/* END d_start.c */



--
pete

[Bill Cunningham]

Thanks much for your help Pete. But maybe I should stay away from linked
lists for now. I thought that they might be simpler than a binary tree but
my C is not up to par enough to handle such things IMO. But I will save your
code and I will study it in my own time. Do I have your permission to repost
this code giving you credit of course if I have questions later with other
about linked lists? This is kind of a slow list anyway so I might study and
repost it here.

Sincerely
Bill

[pete]

Bill Cunningham wrote:

> Do I have your permission to repost
> this code giving you credit of course
> if I have questions later with other
> about linked lists?

Yes.

All that that last program does
is to declare a list node type

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

and then to make a linked list by using two functions.

struct d_node *d_start(int data);
struct d_node *d_append_0(struct d_node *tail, int data);

and then to display the list data using one function

int d_fprintf(const struct d_node *node, FILE *stream);

and then to deallocate the list using one function

void d_free(struct d_node *node);



--
pete

[pete]

This is as simple as I could make it,
without getting hung up on the meaning of the word "simple".

/* BEGIN list_linked.c */

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

int
main(void)
{
struct list {
struct list *next;
int data;
};
struct list *head;
struct list *tail;
int number[] = {15,14,13,7,20,9,8,12,11,6};
unsigned index;

puts("/* BEGIN list_linked.c output */\n");
puts("Original order of list of int:");
head = malloc(sizeof *head);
tail = head;
if (tail != NULL) {
index = 0;
tail -> data = number[index];
while (sizeof number / sizeof *number > ++index) {
tail -> next = malloc(sizeof *(tail -> next));
if (tail -> next == NULL) {

puts("malloc trouble!");
break;
}

tail = tail -> next;
tail -> data = number[index];
}
tail -> next = NULL;

} else {
puts("malloc trouble!");
}

for (tail = head; tail != NULL; tail = tail -> next) {
printf("%d\n", tail -> data);
}
while (head != NULL) {
tail = head -> next;
free(head);
head = tail;
}
puts("\n/* END list_linked.c output */");
return 0;
}

/* END list_linked.c */


--
pete

[Pascal J. Bourguignon]

Perhaps you'll find this version simplier, but it's essentially the same:


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

typedef struct pair { int car; struct pair* cdr; } pair;

pair* cons(int a,pair* d){
pair* c=malloc(sizeof(pair));
if(c){ c->car=a; c->cdr=d; }
return(c);}

pair* cdr(pair* c){ return(c?c->cdr:c); }
int car(pair* c){ return(c?c->car:0); }

typedef int (*ifun)(int,int);

int reduce(ifun fun,pair* list,int initial){
return(list
? reduce(fun,cdr(list),fun(car(list),initial))
: initial);}

int plus(int a,int b){ return(a+b); }

int main(){
printf("%d\n",reduce(plus,cons(1,cons(2,cons(3,NULL))),0));
return(0);
}

--
__Pascal J. Bourguignon__