Hello everyone, I am studying link list in c I have a project in which I have lookup table of rpm (clocks used to load the timer used for motor). This rpm table, I am taking in an array Now I want to implement a link list which will access the rpm from table and load it to timer of clock used for running the motor Is it possible Because as I am studying the link list, in that it is mentioned that link list is used instead of array Is it possible to access an array elements using link list ? If yes, then pls suggest me some link for it Correct me if I am wrong Thank u all
But what does "if you want to totally ignore efficiency" mean?
To me it does mean: "Anyone using linked lists are stupid."
People don't have to ignore efficiency just because they use lists. A list is the most efficient way of being able to add a new entry in the middle.
Also remember that lists need not represent pointers.
typedef struct { unsigned char next_idx; unsigned char prev_idx; unsigned char up_idx; unsigned char first_idx; unsigned char* *cmd; unsigned char flags; } entry_t; entry_t entries[] = {...}
The above can be seen as an array. The above can be seen as a single-linked list (from leaf to root, or from root down through left-most branch) The above can be seen as a double-linked list between elements on the same level.
Can you suggest any more efficient way of navigating such information?
The reason we learn all these container object types in school is just that every problem isn't identical. Because of this, the word efficient isn't really meaningful unless specifically qualified. Efficient for what? Efficient to implement in few lines of code? Efficient for finding random data? Efficient for finding spatially related data? Efficient for inserting data? Efficient for removing data? Efficient memory usage? Efficient to sort? Efficient to debug? Efficient to extend?
You are ignoring efficiency if you do not consider the cases where a linked list (indexed or with pointers) spanks an ordered or unordered array. An array is extremely inefficient for some jobs. Ever thought about the old flat databases? Relational databsaes or object-oriented databases has almost killed off all flat databases except for storing your contact information in Outlook. Why? Because they where not efficient...
In this specific case, it seems that the OP is working with a project where a table would be the best - or at least a very good - solution. But that is not a general case. A table, queue, hash, tree, trie, list, ringbiffer - All different concepts, sometimes being more efficient and sometimes less efficient.
Ever thought about flash file systems? Often done as tree-branching lists. Why? Because it is efficient, and you want to keep down on number of writes when performing an update.
How many RTOS do you think uses linked lists for keeping track of pending and waiting tasks? Why? Because the low cost of inserting and removing! They didn't ignore efficiency. They selected an efficient structure.
Erik, I DON'T want to annoy you, but a while ago I have posted this in response to one of your post (here: http://www.keil.com/forum/docs/thread12822.asp):
with all due respect, if that does not fit into your perception of efficiency - then you must have a great time rewriting just about anything to win a pico-second here and there. no thanks...
hell, if this guy wants to do it with lists, lets wish him all the best. I just finished a control program for a machine that uses polling only (I deliberately excluded interrupts for the control part) based on a C167CS processor, where the response time error doesn't matter that much (as long as it is plus minus 250 milliseconds). It's not like a GPS system - all it needs to do is control a couple of hydraulic valves and read position sensors. The real challenge was dealing with the trashy legacy software and to make it comply with safety standards. If it had not required rather extensive communication (interrupt based CAN, serial...) I think it could have been done with an 8 bitter as well. This is a typical non time-critical embedded application. It needs to work, be safe and comply with the requirements - not fight to squeeze every CPU cycle (unless they are included in the requirements, of course!).
But what does "if you want to totally ignore efficiency" mean? exatclly what it says. If I make a one off I will want to ignore anything that will increase developement costs. If I make something that is to be produced in huge numbers (my 'record' is 680,000) I will want to ignore anything that will increase unit cost. If I make something where throughput is critical I will want to ignore anything that is not the fastest possible code in areas where it matters. The reason we learn all these container object types in school is just that every problem isn't identical. Because of this, the word efficient isn't really meaningful unless specifically qualified. Efficient for what? Efficient to implement in few lines of code? Efficient for finding random data? Efficient for finding spatially related data? Efficient for inserting data? Efficient for removing data? Efficient memory usage? Efficient to sort? Efficient to debug? Efficient to extend? none of the above, but efficient for the processor (i.e. throughput). There would be no other reason to have 'architecture' in the title.
Erik
I DON'T want to annoy you you are absolutely not, different opinions is the very purpose of a forum. I state my opinion, you state yours. There is, in your post, NOTHING that even reading it 10 times (I did not) could be construed as a personal attack.
The very point that has been totally missed in this whole discourse is that nobody knows if the OPs project is time critical (i.e. requiring 'efficiency') or not, and if you read my post that started this whole shebang you will see that I specifically say "if you do not care about efficiency, go ahead and use the linked list"
Neither you nor I can know if the OP cares about efficiency, but because of my post he is warned if he does.
By the way, this brings up a different issue, where so many posts fail to state "what for". The best solution for a rocket is not necessarily the best soultion for a toy (expression 'stolen' from Patryk www.cygnal.org/.../002723.html )
"none of the above, but efficient for the processor (i.e. throughput). There would be no other reason to have 'architecture' in the title."
But my point: "Efficient for finding random data" does mean efficient for the processor.
But my point: "Efficient for finding spatially related data" does mean efficient for the processor.
But my point: "Efficient for inserting data" does mean efficient for the processor.
But my point: "Efficient for removing data" does mean efficient for the processor.
But my point: "Efficient memory usage" does mean efficient for the processor.
But my point: "Efficient to sort" does mean efficient for the processor.
It is all about architecture. For some situations, lists are the #1 champ. They are 100% perfect for some operations. A ring-buffer allows perfect inserts in one end and perfect removals in the other end. But try inserting or removing in the middle.
A dual-linked list can be spliced in constant time. Suggest any alternative that can beat a list for splicing in the middle!
They are marvelous for sorted priority queues.
A trie - a special form of tree/linked list - is a champ at allowing log-n search (the best you can get with the exception of a direct lookup) while at the same time supporting optimum forward and backward iteration. A hash can do constant-time searches, but try to iterate a hash table in sorted order...
Maybe you call lists inefficient because you apply your concept of a list on some virtual (for us unknown) problem that may not be suitable for a list. But for a large class of problems, there are no other solution that can do better, i.e. be more efficient for your little processor, than a list.
All CS programs has at least one course where abstract data types are covered, and where they are compared when it comes memory usage and how fast they are for different operations. A sequential scan of a list is O(N) - the worst - but an insert directly after a known element is O(1) - the best. But the O(N) to locate an item in a list may directly become O(log N) if the list is formed as a trie. That is the best you can manage in a sorted vector too. Except that a sorted vector takes O(N) amortized time to insert a random element. The trie does it in O(log N), totally spanking a vector.
Small processor or supercomputer doesn't matter. O(N), O(log N) or O(1) does matter, and it takes a problem description and design work to figure out if a list will be the perfect choice or not. But never call it inefficient unless you specify a usage where it really is inefficient compared to another data structure. That is the same as saying a 8051 is inefficient! Or an ARM is inefficient. Or an Opteron is inefficient. Or English is inefficient. They all are, depending on criteria.
all correct IF a linked list is the right choice to what the OP is doing". What you mention can, when using the '51 architecture in many cases be done much more effcient with an array of pointers. Since we do not know what the OP is dealing with, I include a part of my previous post By the way, this brings up a different issue, where so many posts fail to state "what for".
so, we are discussing different approaches - which is fine - however which is the best depend on the (OPs) application.