Thread: please give me small and easy example for linked lists

  1. #1
    Registered User
    Join Date
    Jul 2007
    Posts
    88

    please give me small and easy example for linked lists

    I don`t really understand those linked lists.
    http://www.cprogramming.com/tutorial/lesson15.html

    A am asking for some extra examples. A linked list with just 3 items and without if, for, while, cin,.. would be fine enough.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    #include <iostream>
    using namespace std;
    
    struct list 
    {
        int id;
        struct list *next;
    };
    
    void print(list *h)
    {
        list *p;
        p = h;
    	cout << "Listing of linked list" << endl;
        // Have to use some loop construction here, so use "while". 
        while(p) {
           cout << "id=" << p->id << endl;
           p = p->next;
        }
    }
    
    int main(void)
    {
        list *head = 0;   // head is the first item of the list. 
        list *item;
    
        // Get a "new" item (and set head to this value)
        head = item = new list;
    
        item->id = 1;
        item->next = 0;
        // we now have one item in the list. 
    
        // Show us what's in the list. 
        print(head);
    
        // Lets add another one - first allocate new item and let "next" point to it. 
        item->next = new list;
        // Move on so that item is the new item. 
        item = item->next;  
        item->id = 2;
        item->next = 0;
    
        // We should now see two items.
        print(head);
    
        // And one more. 
        item->next = new list;
        // Move on so that item is the new item. 
        item = item->next;  
        item->id = 3;
        item->next = 0;
        
        print(head);
    
        // Finally, clean up the list - again, this is not possible to do without a while 
        // (not in a generic fashion at least)
        item = head; 
        head = 0;    // Mark the list empty. 
        while(item) {
            // We are about to delete "item", so we pick the "next" element up before we 
            // delete it - using data after delete is invalid.
            list *temp = item->next;
            delete item;
            item = temp;
        }
        return 0;   // All done, ok.
    }
    --
    Mats
    Last edited by matsp; 08-20-2007 at 12:14 PM.

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by matsp View Post
    Code:
        // Finally, clean up the list - again, this is not possible to do without a while 
        // (not in a generic fashion at least)
    Recursion?

    Code:
    void delete_list(list *head)
    {
        if(head)
        {
            list *next = head->next;
            delete head;
            delete_list(next);
        }
    }
    It's tail-recursive, so the compiler should be able to optimize it.

    Not necessarily recommending it, just responding to your "impossible" claim.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by brewbuck View Post
    Recursion?

    Code:
    void delete_list(list *head)
    {
        if(head)
        {
            list *next = head->next;
            delete head;
            delete_list(next);
        }
    }
    It's tail-recursive, so the compiler should be able to optimize it.

    Not necessarily recommending it, just responding to your "impossible" claim.
    Well, that would mean a separate function to delete the list - I wanted to keep the code as small as possible, with no "unnecessary" functions - and of course, it just goes to show that this list is full of pedants - I'm one of them. :-)

  5. #5
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by matsp View Post
    Well, that would mean a separate function to delete the list
    Why would you want to code list-deletion in-line everywhere it is required?

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by brewbuck View Post
    Why would you want to code list-deletion in-line everywhere it is required?
    No, that's not what I'm saying - I said I wanted this example to be as small and easy to follow as possible - adding functions can confuse things. Of course, if I were to use linked list in my application (assuming I had to do that, and not just use some pre-written library functions), I would of course have separate functions for inserting a new item, removing a selected item [if this is needed] and destruction of the entire list. But if someone asks for a SIMPLE example, I'm not going to write something more complicated just becasue I can avoid a while by using a recursive function. Recursion can make it hard to understand too (at least, it took me a little while to understand that - but maybe I'm just a bit thick... ;-) )

    --
    Mats

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    A linked list with just 3 items is no simpler than a linked list with any number of items.

    I'm also not sure if it is possible to do it with if, for and while (the recursive function still needs if).

    If you don't understand the examples because of if, for and while, may-be you should learn about these first.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    Registered User
    Join Date
    Jul 2006
    Posts
    162
    i want to know how to bake a cookie, but i don't want it to use butter, or dough... honestly how hard can it be, just a simple cookie... no ingredients...

    i'm sorry that's not how it works. you need to learn how to mix the ingredients, even for just a cookie.


    i hate it when people use "easy" and "simple" to describe what they want, not realizing what's involved. even not realizing how simple -that- really is. it's just a matter of time and understanding.

    lol, "adding functions can confuse things" - oh gosh.
    http://www.cplusplus.com/doc/tutorial/functions.html

    is that better?
    Last edited by simpleid; 08-20-2007 at 01:20 PM.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I wanted this example to be as small and easy to follow as possible - adding functions can confuse things
    Personally, I find that well selected and well named functions make code, even example code, much easier to follow. It beats trying to figure out why a particular block of code exists in the first place, and helps to skip over that block of code once I understand why it is there.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by sept View Post
    A am asking for some extra examples. A linked list with just 3 items and without if, for, while, cin,.. would be fine enough.
    Implementations will differ, but usually a list node contains two parts: the datum, and a reference of some sort to other nodes. So, if you had a singly linked list of integers it might look like this:
    Code:
    +------+    +------+    +-------+
    | 1 |*-|--->| 2 |*-|--->| 3 | *-|---> NULL
    +------+    +------+    +-------+
    Create, manipulate, and maintain the data structure in your code.

  11. #11
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    I decided to take a crack at it.

    I am afraid this is in C, but here is a barebones example of what a list is. It only implements the simplest of list methods (add to head and print).
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct IntList {
       int data;
       struct IntList * next;
    };
    
    /**
     * Adds data to the beginning of the list.  Modifies the structure of the list.
     * @param head The list to modify.
     * @param addMe The data to add to the list.
     */
    void IntList_add2head (struct IntList ** head, int addMe) {
      
       // Create a new node to be inserted into the list. 
       struct IntList * NewNode = malloc (sizeof (struct IntList));
       NewNode->data = addMe;
    
       // Make the new node precede the head of the list.
       NewNode->next = *head;
    
       // Make the head point at the new node.
       *head = NewNode;
    }
    
    /**
     * Prints the contents of the list.
     * Output should look like...
     *    HEAD -> 5 -> 1 -> 7 -> NULL
     * @param head The list to print.
     */
    void IntList_print (struct IntList * head) {
       struct IntList * curr_node;
    
       printf ("HEAD ->");
       // The structure of this for loop is characteristic of linked lists.
       for (curr_node = head; curr_node != NULL; curr_node = curr_node->next) {
          printf (" %d ->", curr_node->data);
       }
       printf (" NULL\n");
    }
    
    int main (void) {
       // The end of a list is always NULL.  So, an empty list is one where
       // the head is NULL.
       struct IntList * head = NULL;
    
       printf ("Welcome to the linked list example.\n");
    
       // Repeatedly prompt the user for input and add items to the list.
       for (;;) {
          int new_value;
    
          printf ("\n");
          IntList_print (head);
          printf ("Input a number (x to exit): ");
          if (scanf ("%d", &new_value) != 1)
             break;
          IntList_add2head (&head, new_value);
       }
    
       return 0;
    }
    Callou collei we'll code the way
    Of prime numbers and pings!

  12. #12
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    Linked List is a cakewalk... Just do simpler programming if you're not comfortable with for loops or whatever else you said, all knowledge of basic programming is required to do linked lists... they come AFTER you learn everything else like memory and loops.

    If it helps you, try to draw a example on paper first to figure out what needs to happen to create/destroy/add/remove... then you can search/sort/ect... step by step, don't code 5 pages of code and expect it to work...

  13. #13
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Quote Originally Posted by sept View Post
    I don`t really understand those linked lists.
    http://www.cprogramming.com/tutorial/lesson15.html

    A am asking for some extra examples. A linked list with just 3 items and without if, for, while, cin,.. would be fine enough.
    Something like this perhaps?

    Code:
    #include <iostream>
    
    struct node
    {
        int data;
        node* next;
    };
    
    void print(node* head)
    {
        while( head )
        {
            std::cout << head->data << '\n';
            head = head->next;
        }
    }
    
    int main()
    {
        node n1;  //Statically creating the nodes rather than 'new'
        node n2;
        node n3;
        node n4;
    
        n1.data = 5;
        n2.data = 10;
        n3.data = 20;
        n4.data = 50;
    
        node* head = &n1;  //pointer to the start of the list
    
        n1.next = &n2;
        n2.next = &n3;
        n3.next = &n4;
        n4.next = 0;   //NULL pointer - end of singly-linked list
    
        print( head );
    }
    There are no algorithms here, perhaps that's what you were after? Its not really a linked list, being that all the nodes are statically allocated, but it follows the same linked node pattern which underpins the concept of a linked list.

  14. #14
    Registered User NM156's Avatar
    Join Date
    Apr 2008
    Posts
    1

    Modified example: Load linked list from file

    Thanks for the integer example. I needed to load a linked list from a text file, so I am posting a version that does that.

    The thing that drove me crazy for a while was that I wasn't malloc-ing (is that a word? :-) the space for the new data string in the new node, and then strcpy-ing (again?) the data into the newly allocated string of the node. Without those two steps, the same data was getting assigned to each node.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define INPUT_LIMIT 101
    
    char input_expression[INPUT_LIMIT] = {'\0'};   
    
    struct StrList {
       char* data;
       struct StrList * next;
    };
    
    /**
     * Adds data to the beginning of the list.  Modifies the structure of the list.
     * @param head The list to modify.
     * @param addMe The data to add to the list.
     */
    void StrList_add2head (struct StrList ** head, char* addMe) {
      
       // Create a new node to be inserted into the list. 
       struct StrList * NewNode = malloc (sizeof (struct StrList));
    
      // The following two steps are critical to preserve the node's data...
    
       if ((NewNode->data = malloc(strlen(addMe) + 1)) == NULL) {
          perror("malloc"); return;
       }
    
       strcpy(NewNode->data,addMe);
    
       // Make the new node precede the head of the list.
       NewNode->next = *head;
    
       // Make the head point at the new node.
       *head = NewNode;
    }
    
    /**
     * Prints the contents of the list.
     * Output should look like...
     *    HEAD -> str1 -> str2 -> str3 -> NULL
     * @param head The list to print.
     */
    void StrList_print (struct StrList * head) {
       struct StrList * curr_node;
    
       printf ("HEAD ->");
       // The structure of this for loop is characteristic of linked lists.
       for (curr_node = head; curr_node != NULL; curr_node = curr_node->next) {
          printf (" %s ->", curr_node->data);
       }
       printf (" NULL\n");
    }
    
    int main (void) {
       // The end of a list is always NULL.  So, an empty list is one where
       // the head is NULL.
       struct StrList * head = NULL;
    
          FILE *file;
          char buf[20];
          float result;
          
          printf("Enter file name >>> ");
          scanf("%s", buf);
          file = fopen(buf, "r");
          if (file == NULL) 
          {
    	fprintf(stderr, "file %s not found\n", buf);
    	return 1;
          }
    
       printf ("Begin linked list example.\n");
    
       while (fgets(input_expression,INPUT_LIMIT,file)) 
       {
          int new_value;
    
          printf ("\n");
          StrList_print (head);
    
          StrList_add2head (&head, input_expression);
       }
    
       return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. An small easy Metaball tutorial
    By MipZhaP in forum Game Programming
    Replies: 5
    Last Post: 08-26-2004, 12:11 PM
  2. Replies: 1
    Last Post: 11-16-2001, 06:22 PM