Re: Linked list allocation

On Mon, 17 Dec 2007 19:51:32 +0100 (CET), Jeff Bown
<nospam@xxxxxxxxxxxxxx> wrote:

Consider implementing a (doubly) linked list.

The simplest strategy is to provide functions
item_t add_item(item_t predecessor);
void delete_item(item_t item);
where add_item allocates memory for a new list item and returns it (or
NULL), and delete_item frees that memory.

However, if at startup the program immediately adds a large number of
items to a list, then all those calls to malloc() become expensive.

An alternative I thought of was that add_item should allocate a block,
say of size (100 * size-needed-by-an-item), then use pointers inside
this block until the time comes to allocate a new block for 100 items.

The problem with this is that deleting items becomes a mess - you can
only free a block when all 100 items in it have been deleted, so in the
worst case (where the programmer allocates 101 items, frees 99, adds
101, ...) you end up with for all intents and purposes a memory leak.

Is there a better solution?

Your description is a little confusing - to me anyway, and
perhaps to others judging from the variety of answers you got.

Ordinarily a linked list (single, or double) consists of nodes,
where a node (doubly linked) looks something like this:

struct node {
node * prev; /* Link to previous node */
node * next; /* Link to next node */
void * data; /* generic pointer to data */
};

and the prototypes look something like this:

node * add_item(node * predecessor, void * datum);
void delete_item(node * item);

Usually you would have a few more routines but set that aside for
the moment. The point I am after is that you seem to be mixing
up nodes and data.

Now, supposing these are your prototypes, how do you go about
implementing them? I will suppose that you can write the code
for inserting and deleting nodes from linked lists. The question
at hand is: what about storage allocation and deallocation? It
is important to recognize that there are two different kinds of
things being allocated and freed, nodes and data.

A generic linked list package shouldn't be responsible for
allocating or freeing data, though there are standard techniques
that can be used.

For nodes a common technique is to (a) use a free list, and (b)
allocate blocks of nodes, link them together, and add them to the
free list. When adding items nodes are popped off the free list;
when deleting items nodes are pushed onto the free list.

HTH. HAND.



.

Relevant Pages

  • Re: Pointer To A Vector Elements While Still Adding
    ... As I understand it, when you add an element to the end of a list, memory is ... there is sufficient capacity. ... elements to 10,000 lists. ... better to allocate them statically). ...
    (comp.lang.cpp)
  • Re: race on multi-processor solaris
    ... > Use a lock-free garbage collector. ... So what does protect the memory attached to the node? ... >>such linked lists, ...
    (comp.unix.solaris)
  • Re: garbage collection problem in large linked lists
    ... Instead all buckets are allocated at once in an array. ... VG.net, which must be very scalable, but only for lists which would normally ... Linked lists require pointer dereferencing in order to traverse. ... When you run out of space, you allocate a new smaller array. ...
    (microsoft.public.dotnet.framework.performance)
  • Re: reuse memory and unset seems slo
    ... > so to reuse memory, do I have to reassign new data to original name ... Nope - tcl lists are not implemented as linked lists, ...
    (comp.lang.tcl)
  • Re: Process arbitrary #lists (continued)
    ... Subject: Process arbitrary #lists (continued) ... allocate ) ... so simple to manipulate the indexable data structure with averages, ... Probably not, but why bother, todays CPU comes with HUMONGUOUS memory ...
    (comp.lang.pl1)