Another thread successfully high-jacked! Well done, drinks all around!
Quzah.
Printable View
Another thread successfully high-jacked! Well done, drinks all around!
Quzah.
So when would I find myself using a linked list? Besides when i am tight on memory. More specifically, when would it be most suitable to use/implemented one?..
First... how is it that you are tight on memory... is this for a microcontroller or something?
The broadest division between using arrays and linked lists is that you use an array when you know how many items you will have and a linked list when you don't. Linked lists can grow and shrink dynamically, arrays tend to be fixed sizes.
I'm skipping the first few pages here based on quzah's comment, lol.
Anyway, I end up using singly linked lists more than double linked lists because that's all I need. Generally, simplicity saves resources too. So eg, the linked list from that inet server I showed you:
llist.h
llist.c
is singly linked and only implements a minimal set of methods (createList, addToList, removeFromList, freeList -- it's really a queue with random access removal and no "pop"). I think there are a couple of places in the code which uses the list where I iterate thru it to find something -- removeFromList does too -- which that might more properly be done with a findInList() function. On the other hand, if the iteration(s) involve some other unique element, maybe it is not necessary.
If you are writing a list in order to learn how to do it, do it according to some fairly complete spec from a book or tutorial (eg, double-linked, insert function, find function). Then in practice you only need to implement what you really need.
Not the kind of response I expected. But let's have another crack at it. I undestand the concept behind them. Coding them is really easy! But I just couldn't think of a situation where I would use them. Well I thought of one and that was MK27's asynchronous server. I know that arrays are a set size and linked list are not. I will say one more time, I could not think of a situation where i would need to use one in. And here is my question; Again. In what kind of program are they frequently used in? Are they best suitable in servers? BTW I am not strapped for memory. I just read somewhere on google that if you were strapped for men then linked list would be of use.
Not programs so much as functions within programs...Quote:
Again. In what kind of program are they frequently used in?
Stacks, Queues, unknown file sizes, deferred tasks, windows controls, lists, ... the cursed things are all over the place.
That one isn't really async, but if it were the same style of queue might be feasible, yeah. The async one I'm working on has a perl interface, so the C parts use perl "hash" functions. Those use a hash table, but the table itself is a linked list (as opposed to an array). I don't know whether it is singly or doubly linked as that is not relevant to using the API. Considering it is a hash table, I'd assume the former.
To be honest, IMO double-linked lists need a pretty specific justification. If the purpose of the "previous" pointer is just to simplify insertions and deletions, the list should not be a double linked list.
Which is to say, the default for a linked list in practice is a singly linked list. You do not need any reason to use a singly linked list instead of a double one. You need a reason to use a double one. Ie, when you see the need for a "linked list" referred to, assume it means a singly linked list unless it specifically says "double linked".
Like Tater says, linked lists are everywhere in one form or another. They can be very simple or very complex. What they have in common is the concept of linking elements together with pointers.* This is different from an array, in which elements are literally sequential in memory. Arrays are faster for certain things, but much more limited. Linked-lists are the foundation of "non standard"/"not built in" complex types in C. They serve no purpose in higher level languages like C++ or perl, because those languages have built-in types that do the same thing (often implemented with linked lists).
* in a sequential chain, one after the other. So each element needs only one (single) or two (double) pointers. Structures with more than two links are trees or graphs, not lists, but they all use that pointer linking concept.