Link List

It would help if you formatted you code legibly - see http://www.keil.com/forum/tips.asp

xdata struct EEPROM
{
   unsigned int Last_Data;  // 2 bytes
   struct EEPROM *Node;     // 3 bytes (Generic pointer)
};

So the toal should be 5!

Why did you think 4?

then it will shows the 5,but actually it should show the 4 bytes

You need to refer to the documentation about generic and memory specific pointers. Your code does show you the correct number of bytes. Your guess is incorrect.

http://www.keil.com/support/man/docs/c51/c51_le_ptrs.htm

Why did you think 4?

Hm ... I can only guess.

I can also guess that the next question will be about some dynamic memory allocation/deallocation issue. Anyone want to bet ?

Here: http://www.keil.com/forum/docs/thread8939.asp

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'"

"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.
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?

Erik

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

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.

Erik

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.

Erik

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.

Erik,

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.

-Jay D.

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.

Erik

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).

Erik,

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).

-Jay D.