We are running a survey to help us improve the experience for all of our members. If you see the survey appear, please take the time to tell us about your experience if you can.
xdata struct EEPROM {
unsigned int Last_Data; struct EEPROM *Node; };
struct EEPROM xdata * xdata p; p = (struct EEPROM xdata *)0x0FF6; if i will print the following statement printf("Size of p = %d",(unsigned int)sizeof(*p));
then it will shows the 5,but actually it should show the 4 bytes
a link list is an excellent idea if you want your project to come to a crawl.
I have no idea why, somehow, the link list has become a part of C, it has nothing to do with language.
The link list is a very ineffective means of storing stuff and, in addition, require 'unlimited' memory which the '51 definitely does not have.
WHAT IS WRONG WITH arrays and structures?
I would greatly appreciate if someone could tell me a reason for using a link list other than "It is easy". That it is "open ended" is irrelevant, in a '51 it WILL end when you run out of memory
Erik
" it has nothing to do with language."
Correct: it's a fundamental tool in any computing environment - so you'd expect any real language to support it! And any programmer to include it in their "armoury"
"The link list is a very ineffective means of storing stuff"
Not necessarily. Linked lists are particularly useful when your data needs to be easily re-ordered without copying it.
"require 'unlimited' memory"
Completely untrue! As previously discussed, statically-allocated linked lists are perfectly common.
"I would greatly appreciate if someone could tell me a reason for using a link list"
See above. As we're talking EEPROM here, it might be something to do with wear-levelling?
For another example, see 'It is easy'"
Surely that could be an entirely valid reason?
Not necessarily. Linked lists are particularly useful when your data needs to be easily re-ordered without copying it. no more useful than re-ordering pointers in an array
"require 'unlimited' memory" Completely untrue! As previously discussed, statically-allocated linked lists are perfectly common. if open-ended is not a desire, then using a linked list becomes even more silly.
"other than 'It is easy'" Surely that could be an entirely valid reason? 1) easier than what 2) "It is easy'" is thr most often used excuse for writing ineffective code.
Just mentally go through the process of getting to the last entry in a linked list as opposed to getting to the last entry in an array of pointers. Point taken?
a link list is an excellent idea if you want your project to come to a crawl
<rest of silly rant snipped>
It seems that almost every thread on this forum has attracted one of your mindless contributions. I'm sure that most people would prefer it if you could confine your comments to areas in which you have some expertise. These areas clearly do not include the 'C' programming language or standard programming techniques.
Whatever your opinions are regarding which techniques are appropriate or which subset of the 'C' language is suitable for use on an 8051 please try and remember that thse are *your opinions*, not *facts*. Unfortunately I suspect that you consider them to be facts.
standard programming techniques.
these "techniques" may be OK on a PC or some such thing, but when applied to the '51 without any concern for the uniqueness of the processor they become misapplied techniques.
I understand from your rants that you belong to the group that believe that the processor is there for the programmer, I happen to be of the opposite opinion.
Did you even bother to absorb (if you have that ability) "Just mentally go through the process of getting to the last entry in a linked list as opposed to getting to the last entry in an array of pointers. Point taken?"
Erik,
That's hardly a fair mental exercise. A similar statement could be: "Mentally go through the process of inserting an element into an array of pointers to maintain sorting on the elements to which they point."
I suspect you'll find that, gee whiz, the linked list completes that task (on average) far faster than the array (which requires shuffling every value after the insertion point of the item.
The reasons for selecting which of these two extremely fundamental data structures (array / linked list) to use is independent of programming language. To a great extent, it can be independent of the processor if we give up the notion of dynamically allocating said structures.
-Jay D.
the example was a sort and I compared to an array of pointers
so, to switch element 47 with element 16 in a linked list is you have to perform 62 reads of addresses. to to switch element 47 with element 16 in an array of pointers, you need to perform TWO reads. There may be an exception here of you use the very inefficient bubble sort, but that will kill the performance regardless of storage method.
You state I suspect you'll find that, gee whiz, the linked list completes that task (on average) far faster than the array (which requires shuffling every value after the insertion point of the item. Of course if you refer to an "array of arrays" you can very well be right, but since "linked lists" is a pointer thingy the only fair comparison is to an array of pointers. I see no way that 62 reads "(on average)" will be faster than TWO.
Now you switch the comparison to "inserting items" and, in that case if the most frequent operation is "inserting" and the only read is sequential you may have found one obscure case where a linked list would be faster. I agree that if you do an insert in a sorted list and uses other than inserting are irrelevant you may have a case for a linked list.
There is, of course the possibility that the definition of a "linked list" has changed since i was last exposed to it. But to my recollection to find element 47 you read element 1 that has a pointer to element 2 that has a pointers to element 3, that .... Again, as stated above if the ONLY read is sequential, you may have a case.
Many would think of a linked list as "the way" for a '51 based data collection system to sort collected data on the fly and then at a convenient time transfer it to a PC (as the case above "sorted insert, sequential read"). I have seen that one. The problem report was "when it has run a couple of days it hangs up". What was the problem? it was that when it took passing umpteen entries in the linked list to find the insert point the process got too slow and crashed. What was the solution? SIMPLE do not sort on the '51, the PC can easily accept unsorted data and sort it.
Now you switch the comparison to "inserting items" and, in that case if the most frequent operation is "inserting" and the only read is sequential you may have found one obscure case where a linked list would be faster.
I take some offense at your assertion that I somehow muddied up your example to suit my purposes. Here is the summary of what I was trying to say (and what everyone programming in any language on any processor for any reason should know):
Linked-Lists 1. Items can be ACCESSED in LINEAR time. 2. Items can be INSERTED in CONSTANT time. Arrays 1. Items can be ACCESSED in CONSTANT time. 2. Items can be INSERTED in LINEAR time.
These facts help to recommend one data structure or the other for a given task. I don't need to justify an application to say that. If you want to say that arrays are the more typical conclusion, I would even agree with that. The problem with your previous replies is that you were speaking in inappropriate absolutes.
Items can be INSERTED in CONSTANT time.
HUH? You may, of course, know something here that I do not know, but to my knowledge, with a linked list it takes a hell of a lot longet to insert after item 94 than to insert after item2 (if you ineret sorted, which would be the only reason i can see for using a LL). If not inserting sorted, (LL insert before item 1) the time to insert for an array and a LL will be about the same, i.e. constant in both cases. Of course if some imbecile do not save the insert point in an arrat and every time fo through the array to find first empty slot, that is screwed up, but not because of using an array.
If there is something here that I miss, please state so.
I take some offense at your assertion that I somehow muddied up your example to suit my purpose I had no thought this was "to suit my purpose<" just that it was not the same. You do not seem to have any "promotional interest" just another case.
HUH? You may, of course, know something here that I do not know, but to my knowledge, with a linked list it takes a hell of a lot longet to insert after item 94 than to insert after item2 (if you ineret sorted, which would be the only reason i can see for using a LL).
Here, I'm talking about the actual act of inserting an element. There are a number of ways we could find the point we actually need to insert at. Imagine this scenario: We have a sorted list of data that currently contains N items. For any new element that we want to insert in sorted order, whether we use an array or a linked list, we have to do something to search the current data to find the point of insertion. For the array, maybe we use a binary-insertion search to speed things up, while for the list we just walk them linearly. At any rate, we have either an array index at which to insert an element, or a linked-list item after which we wish to insert.
From that point, the number of operations to insert a new item into the linked list is constant: We temporarily store the value currently pointed to as "next" by the found item, change that pointer to point to our new item, and then change our new item's pointer to point back to the stashed "next" value. We say that this takes constant time because the operations from this point out have nothing whatsoever to do with the size of our list. In formal books on algorithm design, you'll see them talk of "big-O" notation to describe the relation of an activity to the size of the dataset. For this case, we'd say that this is O(1) meaning it is based on a constant and not a function of the data size.
For the array, however, we have to create a space to place the new element. This means that we would typically start at the end of the list and shuffle each element over one position and then finally insert. This action for an array, then, is dependent on the size of the list, but in the worst case (inserting a new first element) is the entire size of the list. Since we're only looking at the sort of order-of-magnitude efficiency of the algorithm, we'd say it's O(N) meaning it's based linearly on the size of the dataset. (The bubble-sort you mentioned earlier might be called O(N^2) since we might have to run through the list N*N times to sort it).
So.. to sum up, it DOES NOT take longer to insert an item at position 94 in a linked list. Your argument probably has more to do with how we find the position to insert at, in which case, you are correct to say it will take longer. Assuming we use the same algorithm for either, however, (ie a dumb for(i=0; i<N; i++), it takes the same time to search the array as it does the list and so the list would be overall faster for this operation.
Also, let me just mention that I've never used a linked list on the '51, and don't know that I ever will. I just believe that I'm a good '51 programmer BECAUSE of my ability to judiciously choose from these data structures, and not IN SPITE OF my ability to do so (which is nearly what you imply of the OP and commenters).
No, I didn't bother. Previous attempts to have technical discussion with you have been fruitless because you inevitably try, as Jason has discovered below, to twist the subject round once you realise your position is untenable.
I happen to be of the opposite opinion
Please keep your opinions to yourself. Stick to facts.
Please keep your opinions to yourself. Stick to facts
Jack I suggest you do the same.
That you do nor "even bother" illustrates that you do not even KNOW the facts, so what about practicing what you preach.
For any new element that we want to insert in sorted order I have, already stated that a LL may be the best way to "insert in sorted order" with the caveat that it probably will take too long to do this at the data collection point.
whether we use an array or a linked list, we have to do something to search the current data to find the point of insertion. For the array, maybe we use a binary-insertion search to speed things up, while for the list we just walk them linearly. At any rate, we have either an array index at which to insert an element, or a linked-list item after which we wish to insert.
From that point, the number of operations to insert a new item into the linked list is constant: yes, but the number of operations to get to that point is highly variable.
Again, I have several times stated that "insertion in place" is easier with a LL, but probably eventually will exceed alotted time in a '51 app, not just because of using a LL, but because of attempting a time consuming "insert in place" at the data collection point. This I have actually seen and when told the LL user stated "that should not be a problem" as any PC centric abuser of the '51 would.
Also, let me just mention that I've never used a linked list on the '51
Let me emphasize; I am not discussing LLs in general, I leave that to others, but LLs and the '51 (for which I can see no other app where LLs could be discussed than "insertion in place" of collected data). I am not really discussing LLs here, more am I discussing the seemingly widespread (just see Jacks posts) assumption that "C is C" and the fact that you apply it to a '51 is totally irrelevant.
If you (ab)use a '51 using it in a minicontroller app where time is irrelevant, that would not be discussing C and the '51, but discussing making a mistake which belong in a totally different forum.
yes, but the number of operations to get to that point is highly variable.
Again, I have several times stated that "insertion in place" is easier with a LL, but probably eventually will exceed alotted time in a '51 app,
Your first sentence suggested you've very nearly realized what I'm trying to say, but I must not have driven it home properly. With a list, the number of operations to "get to that point" varies, while with an array, the number of operations AFTER "getting to that point" varies. For instance, you said in a previous post that it takes longer to insert at element 96 in a linked list than it does at element 2, and that is completely correct. The important point that you didn't mention is that it takes the same amount of time to insert at element 96 in a linked-list regardless of the list size. So, if the list of data you're working with is any larger than 2*96, the linked list will be faster (since the array would have to "visit" and shuffle over more than 96 elements at the end of the list).
And I don't find it that hard to imagine perfectly acceptable '51 applications that would be better suited to linked lists. For instance, imagine I'm making some sort of networked I/O device that collects data from sensors switches, etc. and then sends that data serially to a network master node. While the master is polling other nodes for information, the I/O point will have to store up a list of everything that's happened so that when it's queried it can send over that event. If this was the only description, then it suggests just an array be used to stored the data, perhaps treated as a FIFO or circular buffer. Imagine now, however, that we consider certain events to be more important than others. We might well want these to be inserted in the front of the list when they occur. If we expected this to happen regularly, I would naturally think of a linked-list since with an array, insertion at the beginning would become more and more costly as the size of the event buffer was scaled, whereas the linked list would suffer no performance impact whatsoever.
Well, all I've been suggesting is that occasions where inserting is a likely event suggests a linked list. You started the discussion with a blanket statement that one shouldn't use a linked list unless we wanted something about the "application slowing to a crawl." I was just pointing out that in the case of needing frequent insertions, you could make the same statement about arrays.
Also, I know that the "C is C" mentality is one that you rail against quite alot. I also know that you and Jack (or whoever he is) have had a bone to pick for some time. I don't think that's what this conversation is about, however. This is about data structures and the fact that a fundamental one like the linked list shouldn't be ruled out just because you're using a '51. Failure to consider it can lead to sub-optimal code (and overly-lengthy forum posts).
-Jay
Jay, We agree on almost all; the one area where we 'discuss' is about "a blanked satement" "use linked list" or "do not use linked list" is valid.
My contention is that in time critical applications and any REAL '51 app is, there is grave danger that someday in the future when the list grow you will have an 'unexpected" error. I can already hear "that will never happen" - famous last words. Why do I state "do not use linked list"? because the only valid use of a linked list is "sorted insert" and such as no place in the time critical device. It belongs at the final data (not event) processing device i.e. the PC at the end of the chain.
so, once more I have no problem, whatsoever, with linked lists on a microcontroller, but they have no place on a microprocessor. Of course, that assumes that this is not a case of misapplying a controller as a processor.
For your suggested use "more important records" I'd use a tag = no overhead.