If I am trying to scan a string of an unknown length, would it be a good approach to scan the input one char at a time and build a linked list of chars to create the string? The only problem I am currently facing is I'm not sure how to handle the string one char at a time without asking the user to enter the string one char at a time, which would be unreasonable. Is there a better approach? I would like to avoid mallocing an arbitrarily large size char array just to accommodate most strings.
3 Answers
In my suggestion having a linked list of chars will be very bad idea as it would consume too much memory for a single string.
Instead, you allocate a nominal sized buffer (say 128 bytes) and keep reading the characters. Once you feel, the buffer is almost full, allocate another buffer of double the current size and copy the contents of first buffer into second one, freeing the first buffer. Like this, you can continue till your string has been read completely.
Also, in most of the programs I have written or seen, an upper limit for string size will be maintained and if the string input appears to be exceeding the size, the program will return an error. The upper limit for string size is determined based on the application context. For Ex: If the string which you are reading is a name it generally cannot exceed more than 32 (or some x value) characters, if it does, then the name is truncated to fit the buffer. In this way the buffer can be allocated first time itself for the upper limit size.
This is just one idea. There may be many other ways in which this can be addressed rather than a linked list.
2 Comments
dmckee --- ex-moderator kitten
Linked-list based string implementation have appeared in the history of computing from time to time. You don't put just one character in a node but 4--32 (still a lot of overhead especially at the low end). The advantage they provided was mostly in terms of controlling memory fragmentation which is rather less of an issue in this era when even very small computers can afford a full service OS .
Jay
@dmckee, I was only referring to the solution of the questioner. His idea of putting one char per node to maintain a string didn't appeal to me.
Ignoring the overkill memory usage of a node-per-char linked-list for a moment and supposing you actually built it and got your string into it. Can you actually work with it?
For example:
- The non-contiguous buffer means many of the standard functions (e.g.
printf(),strlen(),fwrite()) would simply be incompatible or be a pain to work with. - Non-sequence access on the string would be extremely inefficient.
As for a better approach: it really depends on what you're going to do with the string. (For example, if you can process the string as it comes in, maybe you don't even need to hold the entire thing in memory.)
Comments
Store it in an array. Initialize the array with a fixed sized array and while reading the input store them in the array. When array is full and new input comes then create a larger array of double size, and copy old array in newer one. Now keep adding new chars in this array. Repeat the process till you have read all data.You can optimize the process of copying chars from old array to new array by following approach
1)Initialize a variable old_idx to 0
2) When a new char comes (after the old array is full) then create a new array of double size of older one and copy the new char at old_size+1 index. Also copy the data at index old_idx in old array at old_idx in newer array.
3)Increment old_idx
At the end just check that if old_idx < old_array_size then copy rest of old data.
Amortized cost of the whole process is pretty low and this is how ArrayList in java also works.
Advantages of Array over linklist are obvious
1) Less memory footprint
2)Faster linear access (as in array all the memory allocations for data happen in contiguous manner)
scanf, usegetc(orgetchar). Allocate an initial buffer, and read chars into that buffer. When the buffer is full, usereallocto enlarge the buffer. Repeat this process until you've read the entire string.getline...