Attempting Linked Lists

This is a discussion on Attempting Linked Lists within the C Programming forums, part of the General Programming Boards category; Ok I know what a linked list is and I want to code one. Its been a while since I ...

  1. #1
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218

    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

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,500
    doubly linked list tail pointer in struct
    Draw that on paper for yourself.
    Draw a node that you want to insert.

    You need to move two next pointers, and two prev pointers to insert the node. As you change each pointer, write the line of code which corresponds to the line you just moved.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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];
            }
        }         
    }

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by mike_g View Post
    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?

  5. #5
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    You don't need to continue pointing to each node. You only need to keep track of the head node. Try something like this:
    Code:
    NODE *insert_new_node(NODE **head)
    {
      NODE *newnode;
    
      // Allocate memory for the new node
      if(!(newnode = malloc(sizeof(*newnode))))
        return NULL;
    
      /* Place node initialization stuff here... */
    
      // Insert the new node at the head of the list
      newnode->next = *head;
      *head = newnode;
    
      return newnode;
    }
    If you understand what you're doing, you're not learning anything.

  6. #6
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by mike_g View Post
    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.

  8. #8
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

  9. #9
    Massively Single Player AverageSoftware's Avatar
    Join Date
    May 2007
    Location
    Buffalo, NY
    Posts
    141
    Quote Originally Posted by mike_g View Post
    Also what do the double asterisks mean? As in: list **head
    list **head is a pointer to a list pointer.

    I also don't know how to call this function. This was my, wrong, guess:
    Code:
    head=NewNode(&head);
    The call is correct, your head is not. head should be a list*, set to NULL initially. The first call to NewNode will create the first node.
    There is no greater sign that a computing technology is worthless than the association of the word "solution" with it.

  10. #10
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    One additional note about:
    Code:
    head=NewNode(&head);
    The reason I made the function return a pointer to the new head was to allow you to still take care of the list on an allocation failure. The way your call works, if the new node allocation fails, you end up setting head to NULL in the calling function and there's no way to continue gracefully. It's the same reason it's suggested to use a temporary pointer while using realloc(). e.g.:
    Code:
    tmp = realloc(oldchunk, newsize);
    if(tmp == NULL)
      // You can continue playing with oldchunk even though realloc() failed
    else
      oldchunk = tmp;
    vs.
    Code:
    oldchunk = realloc(oldchunk, newsize);
    if(oldchunk == NULL)
      // Screwed because you just lost your pointer to oldchunk
    If you understand what you're doing, you're not learning anything.

  11. #11
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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?

  12. #12
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    After your struct definition, try adding this:
    Code:
    typedef struct list list;
    If you understand what you're doing, you're not learning anything.

  13. #13
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Nice one, it works

  14. #14
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    I'm coding some functions for my linked list. At the moment I'm doing a sort. I had a look at the psuedo code in the FAQ, it looked confusing, so I just started off coding something off the top of my head. Its an inefficient bubble sort type thing that swaps pointers.

    When I compile I get an error message at both the for loops. Heres what they say:
    Code:
    'for' loop initial declaration used outside C99 mode
    And heres my function:
    Code:
    void SortList(list *here)
    {
        list *there;
        list *temp;
        int compare;
        int entries=CountList(here);
        
        for(int i=0; i<entries; i++)
        {
            while(here != NULL)
            {
                for(int n=0; n<i; n++)
                {
                    here=here->next;
                    if(here == NULL) return;
                }
                
                there=here->next;
                if(strcmp(here->data, there->data) >0)
                {
                    temp=here->next;
                    here->next=there->next;
                    there->next=temp;
                }
                here=there;
            }    
        } 
    }
    Last edited by mike_g; 06-14-2007 at 05:50 PM.

  15. #15
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    >_< found what it was. I just have to declare the variables i and n before the for loops. Really dumb mistake.

    [edit] Lol what a stupid function I made. Now I end up with entries that point to themselves o_0[/edit]
    Last edited by mike_g; 06-14-2007 at 05:58 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 04:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 10:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21