A simple linked-list data type with the following properties:

• Simple macro-powered usage without any overhead.
• Pushing new items in O(1).
• Popping the top item in O(1).
• Removing random item in O(1).
• Implements Haxe Iterable → supports for-loops.
• Supports safely removing any item during iteration. (not a thing with the native Haxe Array)
• Supports both FIFO and LIFO iteration through the list.

Installation

haxelib install linkedlist

Usage

Items that go into linked lists should implement the LinkedListItem interface.

import linkedlist.LinkedListItem;

class MyItem implements LinkedListItem
{
    // nothing to implement, a macro automatically creates the necessary fields
}

Then the usage is also simple.

var list: LinkedList<MyItem> = new LinkedList();

// add items
list.push(new MyItem());

// pop items
var item: MyItem = list.pop();

// iterate
for (item in list)
{

}

// remove specific items
list.remove(someItem);

By the default the iteration is done in FIFO (queue) order. To iterate in LIFO (stack) order instead, either pass it as the first argument to the constructor or use the reverse() method.

var list: LinkedList<MyItem> = new LinkedList(LIFO);

list.reverse(); // switch to FIFO

Limitations and implementation details

• The iterator returned by the iterator() method is reused internally for efficiency, and should not be stored by the user. To assist with this, the @:noCompletion meta has been added to this method. Ideally, iteration should only be done using for-loops.
• The reverse() method will only affect new iterators. So calling it from within a for-loop should not impact that loop.
• Regardless of the iteration order, the list is always built by appending items to the head.