Like Tree6Likes

singly linked list

This is a discussion on singly linked list within the C Programming forums, part of the General Programming Boards category; Another thread successfully high-jacked! Well done, drinks all around! Quzah....

  1. #16
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Another thread successfully high-jacked! Well done, drinks all around!


    Quzah.
    CommonTater likes this.
    Hope is the first step on the road to disappointment.

  2. #17
    Registered User Annonymous's Avatar
    Join Date
    Apr 2011
    Location
    Jackson, New Jersey, United States
    Posts
    302
    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?..

  3. #18
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    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.

  4. #19
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Annonymous View Post
    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.
    Last edited by MK27; 09-10-2011 at 08:22 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #20
    Registered User Annonymous's Avatar
    Join Date
    Apr 2011
    Location
    Jackson, New Jersey, United States
    Posts
    302
    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.

  6. #21
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Again. In what kind of program are they frequently used in?
    Not programs so much as functions within programs...

    Stacks, Queues, unknown file sizes, deferred tasks, windows controls, lists, ... the cursed things are all over the place.

  7. #22
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Annonymous View Post
    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.
    Last edited by MK27; 09-10-2011 at 08:58 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  8. #23
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by MK27 View Post
    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.
    Hope is the first step on the road to disappointment.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. singly linked list
    By aextine in forum C Programming
    Replies: 2
    Last Post: 06-08-2010, 02:20 PM
  2. singly linked list
    By right2001 in forum C Programming
    Replies: 3
    Last Post: 08-20-2009, 10:21 AM
  3. Singly Linked List
    By devarishi in forum C Programming
    Replies: 4
    Last Post: 12-23-2008, 11:00 PM
  4. need help with singly linked-list
    By vearns in forum C++ Programming
    Replies: 20
    Last Post: 04-09-2008, 09:48 AM
  5. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 05:37 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21