Re: Singly Linked List in C

arnuld wrote:
On Fri, 08 May 2009 10:51:05 +0000, James Kuyper wrote:
arnuld wrote:

A queue - see <http://en.wikipedia.org/wiki/Queue_(data_structure)>. While a linked list is certainly one way to implement a queue, a circular buffer (see links on that same page) could be a better approach, if you can accept a fixed upper limit to the number of elements in the queue. It avoids the space overhead of having each node contain a pointer to the next element in the queue, and it avoids the time overhead associated with allocating and deallocating each node.

Well, it can't happen as I have no idea how many elements in the list
will be, that could be 2 or 100 or 9,222.


BTW, even if the upper size is fixed (say 10,000), then if there only 100
elements then it wouldn't it cause the space overhead for extra 9900
elements (in case of circular buffer) ?

Sure, it's a trade-off. A fixed sized circular buffer has advantages an disadvantages; a linked list has different advantages and disadvantages. The only way to be sure which structure is more appropriate is to compare those advantages and disadvantages. If you have a small node size and a relatively stable queue length, a circular buffer can be the best option. If you have a large node size and a highly variable queue length, the linked list may be a better option. That's why I was very careful, in my initial statement on the issue, to say "... a list MIGHT not be the appropriate data structure..." (emphasis added).

Declaring a parameter to be const can make sense for exactly the same reasons that declaring any other local variable const might make sense. I would not consider it objectionable, but I would want to make sure that you understand that making 'sp' const has nothing to do with protecting the argument of the function from modification.

Now I understand, that 2nd const will be useful only in case I am passing
the address of the original pointer which is not the case here.

Right: you could pass the address of the pointer to the function, using a parameter declared as "const struct my_struct * const * sp"; in that case, the second const would serve to protect the original pointer from change. The first const would protect the thing that the pointer points at from change. In this case, there's room for a third 'const', after the second '*'; that third const would protect sp from being changed.
.

Relevant Pages

  • Re: Singly Linked List in C
    ... circular buffer could be a better ... elements in the queue. ... It avoids the space overhead of having each node ... reasons that declaring any other local variable const might make sense. ...
    (comp.lang.c)
  • Re: [RFC] Hard disk protection revisited
    ... disk drivers with 'protect' helper functions ... > queue structure. ... > 'unprotect' helper function, and the plugging timer is restored. ...
    (Linux-Kernel)
  • Re: Thread safe queue in C
    ... within linux with C and i need a thread safe queue.How can i obtain a ... Anyway, creating a queue with POSIX Threads is rather trivial, I don't see why you can't quickly create one: ... typedef struct queue_s queue; ... queue* const _this, ...
    (comp.programming.threads)
  • [RFC] Hard disk protection revisited
    ... disk drivers with 'protect' helper functions ... queue structure. ... 'unprotect' helper function, and the plugging timer is restored. ...
    (Linux-Kernel)
  • Re: [PATCH 4/4] disk-protect: Add a generic block layer queue freezing facility
    ... * When reading the 'protect' attribute, ... * before the unfreeze timeout expires. ... * seconds to freeze the queue for. ...
    (Linux-Kernel)