Thread: singly linked list

Another thread successfully high-jacked! Well done, drinks all around!


Quzah.

Originally Posted by Annonymous

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

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.

Originally Posted by Annonymous

Well I thought of one and that was MK27's asynchronous server.

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.

Originally Posted by MK27

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.

It's a memory vs speed trade off. For the cost of one more pointer per node, I can now instantly remove that node or insert before or after that node, without having to loop through the whole list to find myself again.


Quzah.