Like Tree5Likes

Linked Lists

This is a discussion on Linked Lists within the C Programming forums, part of the General Programming Boards category; How would you put a word into a linked list so that the linked list contains each letter of that ...

  1. #1
    Registered User
    Join Date
    May 2013
    Posts
    17

    Lightbulb Linked Lists

    How would you put a word into a linked list so that the linked list contains each letter of that word...so for example if I want to put "cat" into the linked list I want it to be like this "c" "a" "t" ...so each letter is separately placed in the linked lists

  2. #2
    Registered User
    Join Date
    Jun 2013
    Posts
    66
    Are you sure you want each node in the list to represent a single character? That is a very wasteful design given that each character has at least the additional overhead of a pointer.

  3. #3
    Registered User
    Join Date
    May 2013
    Posts
    17
    Yes that is the way I would have to write it unfortunately

  4. #4
    Registered User
    Join Date
    May 2013
    Posts
    17
    To be more specific, I will be reading in the word from an input file and then converting that string to a linked list so that I can manipulate the word according to the remaining commands in the file ...So if I have cat in the file and then the next command is to remove the 'a' in cat I can do so within this linked lists

  5. #5
    Registered User
    Join Date
    Jun 2013
    Posts
    66
    That's a shame. But as far as how to go about it, it is quite simple and essentially nothing changes with how a list of any other type might be managed:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
        {
        char c;
        struct node *next;
        } node;
    
    node *generate_list(const char *s)
        {
        node *list = NULL;
        node *end = NULL;
    
        for (; *s != '\0'; s++)
            {
            if (list == NULL)
                {
                list = (node*)malloc(sizeof(node));
                list->c = *s;
                list->next = NULL;
                end = list;
                }
            else
                {
                end->next = (node*)malloc(sizeof(node));
                end = end->next;
                end->c = *s;
                end->next = NULL;
                }
            }
    
        return list;
        }
    
    int main(void)
        {
        node *list = generate_list("cat");
        node *p;
    
        for (p = list; p != NULL; p = p->next)
            {
            printf("%c\n", p->c);
            }
    
        return EXIT_SUCCESS;
        }

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You just did his homework for him, sonjared.

    It's best to let him at least post his attempt at coding the assignment, and then advise him a bit at a time. Let him or her, work for it, so they learn by practicing and studying, instead of simply copy/pasting your answer.

    It is hard to resist answering such - believe me, I know.
    Salem and iMalc like this.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,157
    Could the OP be looking on how to implement trie type structures? Wiki article:

    Trie - Wikipedia, the free encyclopedia

  8. #8
    Registered User
    Join Date
    Jun 2013
    Posts
    66
    You just did his homework for him, sonjared.
    I disagree. Look at the description of the problem from post #4 and you'll see that generating a list from a string is a very small part of the program. Also, given the utterly simple nature of the solution, it would be condescending to walk the OP through it rather than offer example code that can be used as a template.

    Doing homework for someone, in my opinion, constitutes offering something that could be turned in immediately for a grade with little or no effort expended on the part of the student. I do not see how I did that in this case, unless he lied about his requirements, in which case it is impossible to know where the line is to avoid crossing it.
    Last edited by sonjared; 07-01-2013 at 06:46 AM.

  9. #9
    Stoned Witch Barney McGrew's Avatar
    Join Date
    Oct 2012
    Location
    astaylea
    Posts
    420
    Code:
    list = (node*)malloc(sizeof(node));
    What if malloc fails?

  10. #10
    Registered User
    Join Date
    Jun 2013
    Posts
    66
    Quote Originally Posted by Barney McGrew View Post
    Code:
    list = (node*)malloc(sizeof(node));
    What if malloc fails?
    Good question. Another good question would be what if the host system does not release allocated memory on process termination. How would you solve those two problems?

    Another improvement could be merging the if-else, since there is code duplication in the allocation and initialization of a new node.

  11. #11
    Stoned Witch Barney McGrew's Avatar
    Join Date
    Oct 2012
    Location
    astaylea
    Posts
    420
    How would you solve those two problems?
    If it were for an example I'd probably handle the null pointer and just terminate without freeing the memory. That way your program wouldn't invoke undefined behaviour, so it would still be compliant with the C standard.

    On the other hand, if I were writing a program for the system that you describe, a simple method might be to wrap my own allocator around malloc.

    Another improvement could be merging the if-else, since there is code duplication in the allocation and initialization of a new node.
    Yup, I see two good options there. The first is to use a node ** to refer to the current node, and the second is to build the list in reverse, then reverse it manually.

  12. #12
    Registered User
    Join Date
    Jun 2013
    Posts
    66
    If it were for an example I'd probably handle the null pointer and just terminate without freeing the memory.
    This opens up an interesting discussion. If malloc fails and the program has not previously requested sufficient memory to complete execution, what other option is there than to terminate as gracefully as possible? Is it worth trying to recover? Obviously the answer depends somewhat on the application in question, but what to do when malloc fails can be a surprisingly deep problem. Often the best answer is to clean up what is possible and then terminate.

    The first is to use a node ** to refer to the current node, and the second is to build the list in reverse, then reverse it manually.
    I hadn't considered building the list in reverse, though performance-wise it probably wouldn't be an issue given that the string is unlikely to be excessively long. The solution I had in mind was also a node**.

    That way your program wouldn't invoke undefined behaviour, so it would still be compliant with the C standard.
    Just so that it is clear, I left checking for errors and freeing memory out of the example intentionally. The kind of scaffolding that should be in production code would obscure the meat of the example, which in this case was the loop over a string and appending of nodes to a list.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Quote Originally Posted by sonjared View Post
    given the utterly simple nature of the solution, it would be condescending to walk the OP through it rather than offer example code that can be used as a template.
    That all depends on their competency level. If the person has no clue about programming at all, then explaining just a few variable declarations would not be condescending.

    What you posted might well be appropriate in some cases where the OP is clearly reasonably knowledgeable.
    But I think what we are saying is that most of us would have not so much given the benefit of the doubt, and experience shows we would more likely than not have been right. Generally where people do have reasonable subject knowledge, they inevitably make it obvious immediately.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    801
    I know this is gonna sound nooby but, malloc can fail? O_o

    Well, I guess you can run out of available memory but can malloc fail in any other case?

    And on a slightly related note, I heard about the memory manager Hoard. They claim the command to use it is "LD_PRELOAD=/path/libhoard.so" but how do I actually check if Hoard's libraries are being used instead of the standard malloc one?

  15. #15
    Left
    Join Date
    Oct 2011
    Posts
    816
    Quote Originally Posted by MutantJohn View Post
    Well, I guess you can run out of available memory but can malloc fail in any other case?
    Yes. Most operating systems can impose per-process limits the processes are not allowed to exceed, even if there is technically more memory available. For example, in Linux these can be queried using getrlimit().

    Quote Originally Posted by MutantJohn View Post
    They claim the command to use it is "LD_PRELOAD=/path/libhoard.so" but how do I actually check if Hoard's libraries are being used instead of the standard malloc one?
    Using the dynamic linker (include <dlfcn.h>, and link using -ldl). For example:
    Code:
    #define  _GNU_SOURCE
    #include <stdio.h>
    #include <dlfcn.h>
    
    #ifndef   LIBC_NAME
    #define   LIBC_NAME "libc.so.6"
    #endif
    
    #ifndef   LIBHOARD_NAME
    #define   LIBHOARD_NAME "libhoard.so"
    #endif
    
    int main(void)
    {
        void    *libhoard_handle, *libhoard_malloc;
        void    *libc_handle, *libc_malloc;
        void    *current_malloc;
    
        libc_handle = dlopen(LIBC_NAME, RTLD_NOW | RTLD_NOLOAD | RTLD_GLOBAL);
        if (!libc_handle) {
            fprintf(stderr, "%s\n", dlerror());
            return 1;
        }
    
        current_malloc = dlsym(RTLD_DEFAULT, "malloc");
        libc_malloc = dlsym(libc_handle, "malloc");
        if (current_malloc == libc_malloc) {
    
            fprintf(stderr, "malloc() is from standard C library (%s)\n", LIBC_NAME);
    
        } else {
    
            libhoard_handle = dlopen(LIBHOARD_NAME, RTLD_NOW | RTLD_NOLOAD | RTLD_GLOBAL);
            if (libhoard_handle) {
    
                libhoard_malloc = dlsym(libhoard_handle, "malloc");
                if (current_malloc == libhoard_malloc) {
    
                    fprintf(stderr, "malloc() is from Hoard library (%s)\n", LIBHOARD_NAME);
    
                } else {
    
                    fprintf(stderr, "malloc() is from an unknown library.\n");
                }
    
                dlclose(libhoard_handle);
    
            } else {
    
                fprintf(stderr, "%s: Hoard library not loaded.\n", LIBHOARD_NAME);
    
            }
        }
    
        dlclose(libc_handle);
    
        return 0;
    }
    But really, you normally just want to know if the Hoard library is loaded or not. Here is a simple function, library_loaded(), that will return nonzero if the named library (say, "libhoard.so" or "libc.so.6") is loaded, zero if not loaded.
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <dlfcn.h>
    
    int library_loaded(const char *const name)
    {
        void *handle;
        int   retval;
    
        if (!name || !*name)
            return 0;
    
        handle = dlopen(name, RTLD_NOW | RTLD_NOLOAD | RTLD_GLOBAL);
        if (handle != NULL) {
            retval = 1;
            dlclose(handle);
        } else
            retval = 0;
    
        return retval;
    }
    
    int main(int argc, char *argv[])
    {
        int arg;
    
        if (argc < 2 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
            fprintf(stderr, "\nUsage: %s LIBRARY ...\n\n", argv[0]);
            return 1;
        }
    
        for (arg = 1; arg < argc; arg++)
            if (library_loaded(argv[arg]))
                printf("%s: Loaded\n", argv[arg]);
            else
                printf("%s: Not loaded\n", argv[arg]);
    
        return 0;
    }
    If you save the above as libtest.c, you can compile and run it using
    Code:
    gcc -W -Wall libtest.c -ldl -o libtest
    ./libtest libc.so.6 libhoard.so
    env LD_PRELOAD=/path/libhoard.so ./libtest libc.so.6 libhoard.so

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked Dynamic Lists Vs Unrolled Linked Lists
    By lantzvillian in forum C Programming
    Replies: 6
    Last Post: 02-14-2012, 12:07 PM
  2. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  3. Question about Linked lists of lists
    By hear_no_evil in forum C Programming
    Replies: 2
    Last Post: 11-08-2004, 01:49 AM
  4. question on linked lists(stack with linked lists)
    By dionys in forum C Programming
    Replies: 1
    Last Post: 06-02-2004, 11:08 AM
  5. Linked List of Linked lists Revisited.
    By Qui in forum C++ Programming
    Replies: 11
    Last Post: 04-11-2004, 09:45 PM

Tags for this Thread


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