Thread: Attempting Linked Lists

Ok I know what a linked list is and I want to code one. Its been a while since I used structs so I read a bit of the struct tutorial and the linked list section in the FAQ.

The thing I dont get is how do you code a function that inserts an item into the list. Mainly what I mean here is how do you create an item dynamically?

I had a go at coding a linked list, but I soon realized what I was doing was completely pointless:

Code:

struct list
{
    char data[SIZE];
    struct item *next;
    struct item *last;
}item[100];

o_0

My problem was that I want to create items, as I go. Without having to predefine them something like:

Code:

p = new item;

Or something, but then what should I name 'p' as every item is going to need a unique pointer, if that makes sense. The only pointers I should need to hold though are the first and last pointers on the list as they link to all the other items.

Heres the code I wrote in full. Like I said its useless, because its using an array, and it would be simpler, but slower, to get the object by its array index:

Code:

#include <stdio.h>
#define SIZE 100

struct item
{
    int key;
    char data[SIZE];
    struct item *next;
    struct item *last;
}list[100]; 

void SetupList();


int main()
{        
    SetupList(); 
              
    getchar();
}    


void SetupList()
{
    for(int i=0; i<100; i++)
    {
        list[i].key=i;
        list[i].data[0]='\0';
        if(i == 0)
        {
            list[0].last=NULL;
            list[0].next=&list[1];
        }
        else if(i == 99)    
        {
            list[99].last=&list[98];
            list[99].next=NULL;        
        }
        else
        {
            list[i].last=&list[i-1];
            list[i].next=&list[i+1];
        }
    }         
}

Originally Posted by mike_g

Or something, but then what should I name 'p' as every item is going to need a unique pointer, if that makes sense.

There are a billion objects in the world, and I want to point at each one of them, one after the other. Does this mean I need a billion fingers?

Thanks itsme, I tried to convert the code you posted to work in my prog, but I cant get it to work and I'm unsure as to what I am doing. Heres what I got:

Code:

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100

struct list
{
    char data[SIZE];
    struct list *next;
}; 

list *NewNode(list **head);

int main()
{        
    list head;
    head.data[0]='\0';
    head.next=NULL;
    
    //head=NewNode(&head);
    getchar();
}    

list *NewNode(list **head)
{
    list *newnode;

    if(!(newnode = malloc(sizeof(*newnode))))
        return NULL;
    
    newnode->next=*head; //Next pointer is the existing head
    *head = newnode;     //Make the new node the head
    return newnode;
}

First off when I compile I get an error message at the line in bold: invalid conversion from `void*' to `list*'

Also what do the double asterisks mean? As in: list **head

I also don't know how to call this function. This was my, wrong, guess:

Code:

head=NewNode(&head);

I'm really confused here

Originally Posted by mike_g

First off when I compile I get an error message at the line in bold: invalid conversion from `void*' to `list*'

Sounds like you're accidentally compiling in C++ mode instead of C mode.

Oh yeah, someone mentioned that before when I was using bools in C. At the time I didn't think it would be a problem. Guess I better find out how to set it to compile in C then.

Thanks, I think I am starting to understand this a little bit better now. I changed head to a pointer.

I couldn't find any options in Dev-C++ to set it to compile in C,so I changed the file extension from .cpp to .c

The old error message is gone, but it was replaced by a load of new ones. Basically they are all saying that instances of 'list', 'head', and 'newnode' are undeclared/first use of function. And also that there is a syntax error before the * on this line:

Code:

list *NewNode(list **head);

Saved as a .cpp file the program compiles as long as the malloc bit is commented out, but it crashes when I try and add an entry because, it seems, its not assigning space in memory.

Anyway, heres my code again:

Code:

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100

struct list
{
    char data[SIZE];
    struct list *next;
}; 

list *NewNode(list **head);

int main()
{        
    list *head=NULL;   
    head=NewNode(&head);
    getchar();
}    

list *NewNode(list **head)
{
    list *newnode;

    if(!(newnode = malloc(sizeof(*newnode))))
        return NULL;
    
    newnode->next=*head; //Next pointer is the existing head
    *head = newnode;     //Make the new node the head
    return newnode;
}

Any ideas why it wont compile as a .c?

Nice one, it works