Thread: Dynamic array size (Linked list ?)

  1. #1
    Registered User
    Join Date
    Jan 2018
    Posts
    3

    Dynamic array size (Linked list ?)

    Hello,

    How can we create an array which size would grow as the user enter an input ? (Maybe linked lists ?)

    Here is a piece of code that I have written where I have a fixed input, 128 characters long :

    Code:
    #include <stdio.h>
    #include <string.h>
    
    #define MAX_SIZE 128
    
    int main(int argc, char **argv)
    {
        printf("Input : ");
        char user_input[MAX_SIZE];
        fgets(user_input,MAX_SIZE,stdin);
    
        printf("You Wrote : \n");
        printf(" %s \n", user_input);
        
        const int ARRAY_SIZE = strlen(user_input);
        printf("%d characters found \n", ARRAY_SIZE);
        
        return 0;
    }
    By the way is this piece of code "safe" ?

    Regards

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,907
    A linked list, generally speaking, is a good data structure to hold a list of things that can grow (or shrink) significantly in size. However, a dynamically allocated array can grow and shrink significantly as well.

    Summary of trade-offs:
    Dynamic array:

    • Must exist as a single, contiguous block of memory which, as it grows larger, can become difficult to find space for
    • Given that the memory is contiguous, it allows random access to any elements in a single operation (O(1) time), like arr[456].
    • Native support in the C language via malloc/calloc/realloc/free makes implementation fairly simple.

    Linked list:

    • Each node is allocated at some arbitrary place in memory, as needed, so you don't need a single, large, contiguous block.
    • Given the arbitrary location of each node, there is no random access. To get to the Nth node, you must "walk" from the beginning of the list to that node, meaning it takes N steps (O(N) time).
    • You have to pick how much you want to store in each node. One character would be wasteful. 4MB would probably be overkill.
    • No native support, so you have to write your own or find a third party library.

    A lot of this depends on how much input you really actually need to store all at once. You can store quite a bit in a dynamic array before it becomes impractical, on the order of megabytes, without any issue.

    • If it's a small amount, like up to 128 chars, a fixed array is probably best.
    • If it's more than that, say up to a few megabytes (millions of chars), a dynamic array is probably a good choice. If going that route, don't grow the array by 1 character at a time; it's inefficient. There are strategies for growing the array in ways that balance the number of reallocations/growths with not wasting too much memory.
    • If you need many megabytes or more, consider a linked list and/or files.

    Yes, your code looks safe. One small suggestion: for the size parameter to fgets, use sizeof(user_input). That way, if you change the name of the constant from MAX_SIZE to something like MAX_INPUT_CHARS, you only need to worry about changing the array definition; no need to worry about forgetting to change the fgets call.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,850
    Quote Originally Posted by anduril462
    • Native support in the C language via malloc/calloc/realloc/free makes implementation fairly simple.
    • If it's more than that, say up to a few megabytes (millions of chars), a dynamic array is probably a good choice. If going that route, don't grow the array by 1 character at a time; it's inefficient. There are strategies for growing the array in ways that balance the number of reallocations/growths with not wasting too much memory.
    I think that once you start keeping track of size and capacity separately so as to implement closer-to-optimal growth strategies, implementation ceases to be "fairly simple"
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. I need help with dynamic array of Linked List
    By Ashish Patel in forum C Programming
    Replies: 1
    Last Post: 01-29-2014, 02:43 PM
  2. Dynamic List Char Array & Double Linked List
    By Roadrunner2015 in forum C Programming
    Replies: 18
    Last Post: 10-20-2013, 01:31 PM
  3. Size of Linked List
    By Pana in forum C Programming
    Replies: 15
    Last Post: 09-05-2013, 10:25 AM
  4. Which do you prefer, dynamic array or double linked list?
    By ITAmember in forum C Programming
    Replies: 14
    Last Post: 06-03-2009, 01:46 AM
  5. Linked list and dynamic array
    By jk1998 in forum C++ Programming
    Replies: 3
    Last Post: 04-04-2007, 12:03 PM

Tags for this Thread