Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #2172 > unrolled thread

linked list

Back to article view | Back to comp.programming

Contents

  linked list "Bill Cunningham" <nospam@nspam.invalid> - 2012-09-06 17:58 -0400
    Re: linked list "Bill Cunningham" <nospam@nspam.invalid> - 2012-09-06 18:04 -0400
    Re: linked list pete <pfiland@mindspring.com> - 2012-09-06 18:22 -0400
      Re: linked list "Bill Cunningham" <nospam@nspam.invalid> - 2012-09-06 18:28 -0400
        Re: linked list pete <pfiland@mindspring.com> - 2012-09-06 20:52 -0400
          Re: linked list "Bill Cunningham" <nospam@nspam.invalid> - 2012-09-07 17:25 -0400
            Re: linked list pete <pfiland@mindspring.com> - 2012-09-08 09:35 -0400
    Re: linked list pete <pfiland@mindspring.com> - 2012-09-08 14:49 -0400
    Re: linked list Pascal J. Bourguignon <pjb@informatimago.com> - 2012-10-06 01:32 +0000

#2172 — linked list

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

Bill

[toc] | [next] | [standalone]

#2173

I have this

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

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

Bill

[toc] | [prev] | [next] | [standalone]

#2174

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

[toc] | [prev] | [next] | [standalone]

#2175

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

[toc] | [prev] | [next] | [standalone]

#2176

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

[toc] | [prev] | [next] | [standalone]

#2181

pete wrote:
> 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?

    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

[toc] | [prev] | [next] | [standalone]

#2182

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

[toc] | [prev] | [next] | [standalone]

#2183

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

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

[toc] | [prev] | [next] | [standalone]

#2291

"Bill Cunningham" <nospam@nspam.invalid> wrote:
> Can someone show me a very simple example of a linked list in C? The 
> simplest possible.
> 
> Bill
 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__

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web