Dprogramming.com - The D Programming Language [archived content]

Entice Designer
DCode editor
    D irclib IRC
    ini files
    list linked list
    Splat sockets

list.d 2.1.2

Circularly-linked list module, containing a portable linked list template mixin.
Documentation is now available online.

Download Software

Download list.


Q. Why another linked list implementation?
A. This one uses a different concept from many of the existing linked list implementations. The next and previous pointers are added directly to your data structure (struct or class) using a mixin so that no extra memory allocations are needed to add items to the list. In fact, there are no heap allocations whatsoever in this template.
Q. What is a circular linked list, and why does this module use this type of list?
A. A circular linked list is a linked list that links items in a continuous circle. This allows the full list to be traversed by starting at any item in the list; a fixed head or tail is not required.
Q. Where can I find the documentation and some example usage?
A. The documentation and a simple example are found on the list documentation page. More complete and advanced examples are found in the unittest found at the bottom of the list.d source file. Another example is below about removing and deleting items.
Q. Why do many of the functions in the template start with list?
A. Because the list code is mixed-into your data structure (struct or class), I chose to prepend list to many functions to avoid name mishaps. If you prefer to have shorter names without the list prefix, you may add aliases to your struct or class; a mixin ListNames is provided for this purpose:
mixin ListNames;
Q. Is it possible to have more than one linked list per data structure?
A. Update: this is actually not possible; I am not aware of a way to get this to work.
Q. How can I loop over list items and remove certain ones?
A. Note: foreach must not be used for this; this is a limitation specified by the D programming language to allow possible optimizations. Instead, the filter() function can be used; it takes a callback delegate that is called back for each item in the list, allowing that item to be removed from the list.
Q. The list documentation says that I cannot delete list items during filter(), so how am I supposed to free the memory?
A. You can just rely on the garbage collector. However, if you are asking this question, you probably do not wish to rely on the GC. One solution is to add removed items to another "removed items" list, and then loop over them, deleting after filter(). Or, with this removed items list, you could save the list and use it as a free list; instead of allocating new list items in the future, grab from the free list. Here is some example code.
Q. Why is there a ListHead struct with pretty much the same functions?
A. ListHead is an implementation of a common use of List where an item is designated as the list head (first item). It is not "another way of doing the same thing", it is merely boilerplate code so that it does not need to be reimplemented over and over. Note that if using ListHead, you will probably want to use ListHead.remove() instead of List's remove/unlist functions so that the head item can be kept track of properly.
Q. How can I make sure the list is only modified through a ListHead?
A. You could mix in the list with a protection attribute, but I'm not sure if this is reliable:
private mixin List;
Non-modifying functions of List are marked as public in the template. In the future, D may change how mixin protection attributes are handled and this may no longer work. It is not exactly clear in the D specification if this is how it should always work.
Q. Can I use this list in my closed-source or commercial application? What is the license?
A. Yes, you may freely use list.d. The license is zlib/libpng. See list.d for the copyright and license.

Copyright © 2004-2008 Christopher E. Miller