I've been trying to code a link list in c and though it seems fairly straight forward I'm getting strange output.

My link list nodes:

struct OBJECT {
    int Status;
    struct OBJECT *P_LINK;
    struct OBJECT *N_LINK;
    struct VALUE *P_VALUE;
};

Link list

struct llist {
    struct OBJECT *head;
    struct OBJECT *tail;
    int size;
};

Constructors for LL and OBJECT

struct OBJECT * new_OBJECT(struct VALUE *item,int stat) {
    struct OBJECT *node;
    node = (struct OBJECT *) malloc (sizeof (struct OBJECT));
    if (node == NULL) {
        fprintf(stderr, "new_OBJECT() : malloc error");
        return NULL;
    }
    node->P_VALUE = item;
    node->P_LINK = 0;
    node->N_LINK = 0;
    node->Status = stat;
    printf("    Object value is: %s\n\n",node->P_VALUE->VALUE);
    return node;
};  
struct llist * new_list() {   /* function name */
    struct llist *lst;
    lst = (struct llist *) malloc(sizeof(struct llist));
    /* malloc returns 0 on error */
    if (lst == NULL) {
        fprintf(stderr, "new_list() : malloc error");
        return NULL;
    }
    /* initialize the list size and the list head */
    lst->head = (struct OBJECT *) calloc( 1, sizeof(struct OBJECT ) );

    lst->tail = (struct OBJECT *) calloc( 1, sizeof(struct OBJECT ) );
  
    lst->size = 0;
    return lst;
};

Insert function

struct llist * l_insert_H(struct llist *ls, char type, char * value, int status) {
    struct OBJECT *node;
    struct VALUE *val;
    /* get a new OBJECT && new VALUE */
    val= new_VALUE(type, value);
    node = new_OBJECT(val,status);
    if (node == NULL) { return 0; }
    //l_append(ls,node);
    /* insert the node at the head of the list */
    if(ls->size==0){
        ls->head=node;
        ls->tail=node;
        printf("\n******printing ls with 1st element\n");
         l_print(ls);
    }
    else{
        ls->tail->N_LINK=node;
        node->P_LINK=ls->tail;
        ls->tail=node;
        l_print(ls);
    }
    (ls->size)++;
    printf("Adding value: %s: %d\n\n",node->P_VALUE->VALUE,ls->size);
    return ls;
};

My main()

main (int argc, char *argv[])
{
    extern TKN get_token(FILE *);
    TKN Token;
    FILE *Input;
    int TokenNr = 1, LineNr = 1, Done = 0, k;
    Input = fopen(argv[1], "r");
    
    struct llist *Ids;
    struct llist *Numbers;
    struct llist *Seps;
    struct llist *Unknown;
    Ids = new_list();
    Numbers = new_list();
    Seps = new_list();
    Unknown = new_list();
    char * tmp;
    
 while (!Done) 
 {
   Token = get_token( Input ); 
   switch (Token.Code)
     {
        case 'I':
            {
                   /* process identifier Ids < 20 char I, length string*/
                printf("(%d,%d) Symbol: Identifier %s\n",TokenNr, LineNr,Token.String);
                tmp=Token.String;
                l_insert_H(Ids, 'I', tmp, 0);
                printf("\n\n^^^^^back to main loop\n\n");
                l_print(Ids);
                 TokenNr = TokenNr+1;
                break;
            } 
         case 'N': 
         {
             //process integer number 'N'  
             printf("(%d,%d) Symbol: Integer number %s\n",TokenNr,LineNr,Token.String);
             printf("***************::%s***************\n",Token.String);
             
             l_insert_H(Numbers, 'N', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'F':
         {
             // process real number 
             printf("(%d,%d) Symbol: Real number %s\n",TokenNr,LineNr, Token.String);
             printf("***************::%s\n\n***************\n",Token.String);
             
             l_insert_H(Numbers, 'F', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'W':
         {
             printf("White symbol received\n");
             l_insert_H(Seps, 'W', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'T':
         {
             printf("Terminators received\n");
             l_insert_H(Seps, 'T', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         } 
         case 'R':
         {
             printf("Relation symbol received\n");
             l_insert_H(Seps, 'R', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'S':
         {
             printf("Separators symbol received\n");
             l_insert_H(Seps, 'S', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'L':
         {
             printf("New line symbol received\n");
             l_insert_H(Seps, 'L', Token.String, 0);
             LineNr = LineNr+1;
             
             TokenNr = 1;
         }
         case 'U':
         {
             if (Token.String[0] == 'Z'){
                 //l_insert_H(Seps, 'Z', Token.String, 0);
                 Done = 1;
             }
             else 
                 printf("Unprintable character discovered\n");
             break;
             TokenNr = TokenNr+1;
         }
         case 'O':
         {
             printf("(%d,%d) Symbol: Separator %s\n",TokenNr,LineNr,Token.String);
             l_insert_H(Seps, 'O', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'E':
         {
             printf("Error condition: %s\n", Token.String);
             l_insert_H(Unknown, 'E', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         } 
             

    } 
  } /* end while */
    printf("\n\n******************* Printing lists ************************\n\n");
    l_print(Ids);
    
    printf("1. %s\n2. %s\n3. %s\n",Ids->head->P_VALUE->VALUE, Ids->head->N_LINK->P_VALUE->VALUE, Ids->head->N_LINK->N_LINK->P_VALUE->VALUE);
    /*
    l_print(Numbers);
    l_print(Seps);
    l_print(Unknown);
    
    */
}

I've checked my logic and it seems to be right but up on the ith insertion all my previous i-1 nodes are lost and a link list of i copies of the ith node is returned such that i<=2. I'm very confused by this, since I never loop through all the nodes of the LL unless I'm printing them and that doesn't effect the values, yet I'm getting multiple copies of the node being added. Any help would be greatly appreciated.

Your logic for insertion seems fine, except your comment says you're inserting OBJECTs at the head, and you're doing tail insertion. Minor detail. Perhaps your mistake is in the l_print function. Can you show us that?

Can you please give an example of what you did and what the results were that were incorrect?

By the way, in your new_list() function, you create OBJECTs for head and tail without any data. That's unnecessary. If the list is empty, head and tail should just be NULL. Especially since you don't link the two new OBJECTs, head and tail aren't even connected together. For each of them, N_LINK and P_LINK are NULL. Later in your l_insert_H() function, you leave them stranded when you set head and tail to the new node (when size = 0, which it is after new_list() is called).

Your logic for insertion seems fine, except your comment says you're inserting OBJECTs at the head, and you're doing tail insertion. Minor detail. Perhaps your mistake is in the l_print function. Can you show us that?

Can you please give an example of what you did and what the results were that were incorrect?

By the way, in your new_list() function, you create OBJECTs for head and tail without any data. That's unnecessary. If the list is empty, head and tail should just be NULL. Especially since you don't link the two new OBJECTs, head and tail aren't even connected together. For each of them, N_LINK and P_LINK are NULL. Later in your l_insert_H() function, you leave them stranded when you set head and tail to the new node (when size = 0, which it is after new_list() is called).

I started the l_insert as inserting at the head, but changed it for my hw requirement. Here is my printing code:

void l_print(struct llist *ls){
    struct OBJECT *curr;
    int i=0;
    curr=ls->head;
    printf ("Inside list printing\n");
    for( i=0; i<ls->size;i++){
        printf("%d. element: %s\n",i,curr->P_VALUE->VALUE);
        curr=curr->N_LINK;

    }
    
}

I've attached my full program with the scanner and other functions that I don't yet use. I can compile with cc -<outfilename> my.c scanner.c and if I run the program with ./a.out scan.h, my output shows that my linklists is being reset after each node (OBJECT) is added.

scan.h

#include <stdio.h>
#define  MAX_STRING    32
typedef struct t_node
 {
  char  Code;
  char  String[ MAX_STRING ];
 }  TKN,  *TKN_PTR;

scan.c

/* This scanner recognizes identifiers returning the token I */
/* integers returing the token N, reals returning the token F, */
/* white spaces (blancs and tabs mapped into just one white */
/* space) returning the token W, unprintable characters returning */
/* the token U, and other characters, returning the token O. */
/* In all casses the recognized lexeme is stored in the string */
/* variable Toke.String. */

#include "scan.h"

TKN  get_token (FILE *Input )
  {
   typedef struct  pt_entry
    {
     int    Action,
              Data;
    }  pt_node;

static pt_node  PT[ 11 ][ 8 ] = {
    {{ 'S',  9  }, { 'S',  8  }, { 'S',  2  }, { 'S',  1  },
     { 'S',  1  }, { 'S',  8  }, { 'S',  8  }, { 'S', 10  }},
     
    {{ 'A', 'I' }, { 'A', 'I' }, { 'S',  1  }, { 'S',  1  },
     { 'S',  1  }, { 'A', 'I' }, { 'A', 'I' }, { 'A', 'I' }},
     
    {{ 'A', 'N' }, { 'A', 'N' }, { 'S',  2  }, { 'S',  5  },
     { 'A', 'N' }, { 'S',  3  }, { 'A', 'N' }, { 'A', 'N' }},
     
    {{ 'A', 'E' }, { 'A', 'E' }, { 'S',  4  }, { 'A', 'E' },
     { 'A', 'E' }, { 'A', 'E' }, { 'A', 'E' }, { 'A', 'E' }},
     
    {{ 'A', 'F' }, { 'A', 'F' }, { 'S',  4  }, { 'S',  5  },
     { 'A', 'F' }, { 'A', 'F' }, { 'A', 'F' }, { 'A', 'F' }},
     
    {{ 'A', 'E' }, { 'A', 'E' }, { 'S',  7  }, { 'A', 'E' },
     { 'A', 'E' }, { 'A', 'E' }, { 'S',  6  }, { 'A', 'E' }},
     
    {{ 'A', 'E' }, { 'A', 'E' }, { 'S',  7  }, { 'A', 'E' },
     { 'A', 'E' }, { 'A', 'E' }, { 'A', 'E' }, { 'A', 'E' }},
     
    {{ 'A', 'F' }, { 'A', 'F' }, { 'S',  7  }, { 'A', 'F' },
     { 'A', 'F' }, { 'A', 'F' }, { 'A', 'F' }, { 'A', 'F' }},
     
    {{ 'A', 'O' }, { 'A', 'O' }, { 'A', 'O' }, { 'A', 'O' },
     { 'A', 'O' }, { 'A', 'O' }, { 'A', 'O' }, { 'A', 'O' }},
     
    {{ 'A', 'U' }, { 'A', 'U' }, { 'A', 'U' }, { 'A', 'U' },
     { 'A', 'U' }, { 'A', 'U' }, { 'A', 'U' }, { 'A', 'U' }},
     
    {{ 'A', 'W' }, { 'A', 'W' }, { 'A', 'W' }, { 'A', 'W' },
     { 'A', 'W' }, { 'A', 'W' }, { 'A', 'W' }, { 'S', 10  }} 
};

static int  TOKENS[ ] = {
      0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
      7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 1, 6, 5, 1, 
      2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 
      1, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
      4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 
      1, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
      4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 0  
};

int  C, R = 0, S = 0, ch;
TKN  Tkn;
ch = getc(Input);
if (( ch != EOF ) && (ch != '\n'))
  C = TOKENS[ ch ];
else if (ch == EOF)
    {
     Tkn.Code = 'U';
     Tkn.String[ 0 ] = 'Z';
     Tkn.String[ 1 ] = '\0';
     return ( Tkn );
    }
 else
    {
        Tkn.Code = 'L';
        Tkn.String[0] = '\n';
        Tkn.String[1] = '\0';
     return (Tkn); 
    } 
 while (1) 
      if ( PT[ R ][ C ].Action == 'S' )
       {
        Tkn.String[ S++ ] = ch;
        ch = getc(Input);
    if (ch == '\n') 
          {
           Tkn.String[ S ] = '\0';
           R = PT[ R ][ C ].Data;
           C = TOKENS[ ch ];
           Tkn.Code = PT[ R ][ C ].Data; 
           ungetc(ch, Input);
           return (Tkn);
      } 
    else
          {
           R = PT[ R ][ C ].Data;
           C = TOKENS[ ch ];
      }
       }
     else
       {
        Tkn.String[ S ] = '\0';
        Tkn.Code = PT[ R ][ C ].Data; 
        ungetc(ch, Input);
        return (Tkn);
       }
}
/* Note: this scanner assumes that the length of the longest string */
/* it recognizes is a constant MAX_STRING decleared in the application */
/* where it is  used */

my.c

/* Calling sequence: "a.out Filename" where Filename contains */
#include "scan.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


struct VALUE {
    char TYPE;
    int LENGTH;
    char *VALUE;
};
struct OBJECT {
    int Status;
    struct OBJECT *P_LINK;
    struct OBJECT *N_LINK;
    struct VALUE *P_VALUE;
}; 
struct llist {
    struct OBJECT *head;
    struct OBJECT *tail;
    int size;
};
struct VALUE * new_VALUE(char type, char *value){
    struct VALUE *val;
    val = (struct VALUE *) malloc (sizeof (struct VALUE));
    if(val==NULL){
        fprintf(stderr,"new_VALUE() : malloc error");
        return NULL;
    }
    val->TYPE=type;
    val->VALUE=value;
    printf("value is: %s", val->VALUE);
    /* need to calc LENGTH */
    val->LENGTH=0;
    return val;
};
void l_print(struct llist *ls){
    struct OBJECT *curr;
    int i=0;
    curr=ls->head;
    printf ("Inside list printing\n");
    for( i=0; i<ls->size;i++){
        printf("%d. element: %s\n",i,curr->P_VALUE->VALUE);
        curr=curr->N_LINK;

    }
    
}

struct OBJECT * new_OBJECT(struct VALUE *item,int stat) {
    struct OBJECT *node;
    node = (struct OBJECT *) malloc (sizeof (struct OBJECT));
    if (node == NULL) {
        fprintf(stderr, "new_OBJECT() : malloc error");
        return NULL;
    }
    node->P_VALUE = item;
    node->P_LINK = 0;
    node->N_LINK = 0;
    node->Status = stat;
    printf("    Object value is: %s\n\n",node->P_VALUE->VALUE);
    return node;
};  
struct llist * new_list() {   /* function name */
    struct llist *lst;
    /* our first use of malloc().  Allocates enough space for a 
     llist structure, casts the void pointer returned by malloc() to 
     the correct type (struct llist pointer) and stores that pointer in lst.*/
    lst = (struct llist *) malloc(sizeof(struct llist));
    
    /* malloc returns 0 on error */
    if (lst == NULL) {
        fprintf(stderr, "new_list() : malloc error");
        return NULL;
    }
    
    /* initialize the list size and the list head */
    lst->head = (struct OBJECT *) calloc( 1, sizeof(struct OBJECT ) );

    lst->tail = (struct OBJECT *) calloc( 1, sizeof(struct OBJECT ) );
  
    lst->size = 0;
    return lst;
}; 
int l_append(struct llist *ls, struct OBJECT *obj){
    ls->tail->N_LINK=obj;
    ls->tail=obj;
};
struct llist * l_insert_H(struct llist *ls, char type, char * value, int status) {
    struct OBJECT *node;
    struct VALUE *val;
    /* get a new OBJECT && new VALUE */
    val= new_VALUE(type, value);
    node = new_OBJECT(val,status);
    if (node == NULL) { return 0; }
    //l_append(ls,node);
    /* insert the node at the head of the list */
    if(ls->size==0){
        ls->head=node;
        ls->tail=node;
        printf("\n******printing ls with 1st element\n");
         l_print(ls);
    }
    else{
        ls->tail->N_LINK=node;
        node->P_LINK=ls->tail;
        ls->tail=node;
        l_print(ls);
    }
    (ls->size)++;
    printf("Adding value: %s: %d\n\n",node->P_VALUE->VALUE,ls->size);
    return ls;
};



int l_delete(struct llist *ls, char *value) {
    struct OBJECT *node;
    struct OBJECT *prev;
    struct OBJECT *next;
    struct VALUE *tVal;
    int found = 0;
    /* iterate through the list looking for 'item'. */
    for (node = ls->head; node != NULL && found==0; node = node->N_LINK) {
        if ((node->P_VALUE->VALUE)==value){
            found =1;
            next = node->N_LINK;
            if (node == ls->head) {
                ls->head = next;
                next->P_LINK = 0;
            } 
            else if (node == ls->tail){
                prev->N_LINK=0;
                ls->tail=prev;
            }
            else{
                prev->N_LINK = next;
                next->P_LINK = prev;
            }
        }
        prev = node;
    }
    if (found == 0) {
        printf("Item not found\n");
        return 0; /* 'item' not found */
    }
    
    (ls->size)--;
    
    /* free the memory we allocated for the list node we're no longer using */
    free(node);
    return 1;
};

main (int argc, char *argv[])
{
    extern TKN get_token(FILE *);
    TKN Token;
    FILE *Input;
    int TokenNr = 1, LineNr = 1, Done = 0, k;
    Input = fopen(argv[1], "r");
    
    struct llist *Ids;
    struct llist *Numbers;
    struct llist *Seps;
    struct llist *Unknown;
    Ids = new_list();
    Numbers = new_list();
    Seps = new_list();
    Unknown = new_list();
    char * tmp;
    
 while (!Done) 
 {
   Token = get_token( Input ); 
   switch (Token.Code)
     {
        case 'I':
            {
                   /* process identifier Ids < 20 char I, length string*/
                printf("(%d,%d) Symbol: Identifier %s\n",TokenNr, LineNr,Token.String);
                tmp=Token.String;
                l_insert_H(Ids, 'I', tmp, 0);
                printf("\n\n^^^^^back to main loop\n\n");
                l_print(Ids);
                 TokenNr = TokenNr+1;
                break;
            } 
         case 'N': 
         {
             //process integer number 'N'  
             printf("(%d,%d) Symbol: Integer number %s\n",TokenNr,LineNr,Token.String);
             printf("***************::%s***************\n",Token.String);
             
             l_insert_H(Numbers, 'N', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'F':
         {
             // process real number 
             printf("(%d,%d) Symbol: Real number %s\n",TokenNr,LineNr, Token.String);
             printf("***************::%s\n\n***************\n",Token.String);
             
             l_insert_H(Numbers, 'F', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'W':
         {
             printf("White symbol received\n");
             l_insert_H(Seps, 'W', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'T':
         {
             printf("Terminators received\n");
             l_insert_H(Seps, 'T', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         } 
         case 'R':
         {
             printf("Relation symbol received\n");
             l_insert_H(Seps, 'R', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'S':
         {
             printf("Separators symbol received\n");
             l_insert_H(Seps, 'S', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'L':
         {
             printf("New line symbol received\n");
             l_insert_H(Seps, 'L', Token.String, 0);
             LineNr = LineNr+1;
             
             TokenNr = 1;
         }
         case 'U':
         {
             if (Token.String[0] == 'Z'){
                 //l_insert_H(Seps, 'Z', Token.String, 0);
                 Done = 1;
             }
             else 
                 printf("Unprintable character discovered\n");
             break;
             TokenNr = TokenNr+1;
         }
         case 'O':
         {
             printf("(%d,%d) Symbol: Separator %s\n",TokenNr,LineNr,Token.String);
             l_insert_H(Seps, 'O', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         }
         case 'E':
         {
             printf("Error condition: %s\n", Token.String);
             l_insert_H(Unknown, 'E', Token.String, 0);
             TokenNr = TokenNr+1;
             break;
         } 
             

    } 
  } /* end while */
    printf("\n\n******************* Printing lists ************************\n\n");
    l_print(Ids);
    
    printf("1. %s\n2. %s\n3. %s\n",Ids->head->P_VALUE->VALUE, Ids->head->N_LINK->P_VALUE->VALUE, Ids->head->N_LINK->N_LINK->P_VALUE->VALUE);
    /*
    l_print(Numbers);
    l_print(Seps);
    l_print(Unknown);
    
    */
}


















/* case 'N': 
 {
 //process integer number 'N'  
printf("(%d,%d) Symbol: Integer number %s\n",TokenNr,LineNr,Token.String);
printf("***************::%s***************\n",Token.String);

l_insert_H(Numbers, 'N', Token.String, 0);
TokenNr = TokenNr+1;
break;
}
case 'F':
{
    // process real number 
    printf("(%d,%d) Symbol: Real number %s\n",TokenNr,LineNr, Token.String);
    printf("***************::%s\n\n***************\n",Token.String);
    
    l_insert_H(Numbers, 'F', Token.String, 0);
    TokenNr = TokenNr+1;
    break;
}
case 'W':
{
    printf("White symbol received\n");
    l_insert_H(Seps, 'W', Token.String, 0);
    TokenNr = TokenNr+1;
    break;
}
case 'T':
{
    printf("Terminators received\n");
    l_insert_H(Seps, 'T', Token.String, 0);
    TokenNr = TokenNr+1;
    break;
} 
case 'R':
{
    printf("Relation symbol received\n");
    l_insert_H(Seps, 'R', Token.String, 0);
    TokenNr = TokenNr+1;
    break;
}
case 'S':
{
    printf("Separators symbol received\n");
    l_insert_H(Seps, 'S', Token.String, 0);
    TokenNr = TokenNr+1;
    break;
}
case 'L':
{
    printf("New line symbol received\n");
    l_insert_H(Seps, 'L', Token.String, 0);
    LineNr = LineNr+1;
    
    TokenNr = 1;
}
case 'U':
{
    if (Token.String[0] == 'Z'){
        //l_insert_H(Seps, 'Z', Token.String, 0);
        Done = 1;
    }
    else 
        printf("Unprintable character discovered\n");
        break;
    TokenNr = TokenNr+1;
}
case 'O':
{
    printf("(%d,%d) Symbol: Separator %s\n",TokenNr,LineNr,Token.String);
    l_insert_H(Seps, 'O', Token.String, 0);
    TokenNr = TokenNr+1;
    break;
}
case 'E':
{
    printf("Error condition: %s\n", Token.String);
    l_insert_H(Unknown, 'E', Token.String, 0);
    TokenNr = TokenNr+1;
    break;
} 

*/

Thanks for your help.

struct VALUE * new_VALUE(char type, char *value){
    ...
    val->VALUE=value;
    ...
};

struct llist * l_insert_H(struct llist *ls, char type, char * value, int status) {
    ...
    struct VALUE *val;
    val= new_VALUE(type, value);
    ...
};
main (int argc, char *argv[])
{
    ...
    TKN Token;
    ...
}

You have only one instance of TKN in your program. That is, every val->VALUE points to the same instance of TKN.String .

A simple fix would be

val->VALUE=strdup(value);
This article has been dead for over six months. Start a new discussion instead.