Applications of linked lists

Question

What are some good examples of an application of a linked list? I know that it's a good idea to implement queues and stacks as linked lists, but is there a practical and direct example of a linked list solving a problem that specifically takes advantage of fast insert time? Not just other data structures based on linked lists.

Hoping for answers similar to this question about priority queues: Priority Queue applications

I have found one myself: A LRU (least recently used) cache implemented with a hash table and a linked list.

There's also the example of the Exception class having an InnerExeption

What else is there?

Solution

I work as a developer at a "large stock market" in the US. Part of what makes us operate at very fast speed is we don't do any heap allocation/de-allocation after initialization (before the start of the day on the market). This technique isn't unique to exchanges, it's also common in most real time systems.

First of all, for us, Linked lists are preferred to array based lists because they do not require heap allocation when the list grows or shrinks. We use linked lists in multiple applications on the exchange.

• One application is to pre-allocate all objects into pools (which are linked lists) during initialization; so whenever we need a new object we can just remove the head of the list.
• Another application is in order processing; every Order object implements a linked list entry interface (has a previous and next reference), so when we receive an order from a customer, we can remove an Order object from the pool and put it into a "to process" list. Since every Order object implements a Linked List entry, adding at any point in the list is as easy as populating a previous and next references.

Example off the top of my head:

Interface IMultiListEntry {

    public IMultiListEntry getPrev(MultiList list);
    public void setPrev(MultiList list, IMultiListEntry entry);

    public IMultiListEntry getNext(MultiList list);
    public void setNext(MultiList list, IMultiListEntry entry);

}

Class MultiListEntry implements IMultiListEntry {

    private MultiListEntry[] prev = new MultiListEntry[MultiList.MAX_LISTS];
    private MultiListEntry[] next = new MultiListEntry[MultiList.MAX_LISTS];

    public MultiListEntry getPrev(MultiList list) {
        return prev[list.number];
    }
    public void setPrev(MultiList list, IMultiListEntry entry) {
        prev[list.number] = entry;
    }

    public IMultiListEntry getNext(MultiList list) {
        return next[list.number];
    }
    public void setNext(MultiList list, IMultiListEntry entry) {
        next[list.number] = entry;
    }

}

Class MultiList {

    private static int MAX_LISTS = 3;
    private static int LISTS = 0;

    public final int number = LISTS++;

    private IMultiListEntry head = null;
    private IMultiListEntry tail = null;

    public IMultiListEntry getHead() {
        return head;
    }

    public void add(IMultiListEntry entry) {
        if (head==null) {
            head = entry;
        } else {
            entry.setPrevious(this, tail);
            tail.setNext(this, entry);
        }
        tail = entry;
    }

    public IMultiListEntry getPrev(IMultiListEntry entry) {
        return entry.getPrev(this);
    }
    public IMultiListEntry getNext(IMultiListEntry entry) {
        return entry.getNext(this);
    }
}

Now all you have to do is either extend MultiListEntry or implement IMultiListEntry and delegate the interface methods to an internal reference to a MultiListEntry object.