Defines a simple doubly linked list.

lazlinkedlist.pas defines a simple doubly linked list (TLinkList). It supports Adding, Deleting, getting First and getting Last in O(1). Finding can be done in time O(n).

This file is part of the LazUtils package.

Authors: Mattias Gaertner, Jeroen van Iddekinge

Implements an item in a doubly linked list.

TLinkListItem is a class which implements an item in a doubly linked list. It represents the traversal nodes used in TLinkList, including the terminal (or sentinel) node. Properties are provided to access and maintain the Prior and Next items in the node traversal order.

Contains a reference to the next item in the doubly linked list.
Contains a reference to the previous item in the doubly linked list.
Removes the references to the previous and next items for the list item.

ResetItem sets the values in the Prior and Next properties to Nil.

Defines a simple doubly linked list class.

TLinkList is a class which defines a navigational interface for a simple doubly linked list.

TLinkList provides properties used to access the First and Last items in the linked list, the number of list items in Count, and the first free item in the linked list. Items in the linked list are represented using the TLinkListItem class, which provides Prior and Next properties for navigation of items in the list.

TLinkList contains an abstract virtual CreateItem method that is used to create new items for the linked list. The method must be implemented in a descendent class to provided implementation details that address storage and ownership of the linked list items. See TGtkMessageQueue for an example of a concrete implementation of the TLinkList class.

First free item in the linked list.
Number of free items in the linked list.
First list item in the linked list.
Last list item in the linked list.
Number of items in the linked list.
Removes the specified item from the linked list, and optionally frees the item instance.
List item updated in the method.
Removes the traversal nodes for the specified linked list item.
Linked list item updated in the method.
Specifies the interface used to create a new linked list item for the class.

CreateItem is an abstract virtual method which specifies the interface used to create a new linked list item for the class. The return value is the TLinkListItem class instance allocated in the method. CreateItem must be be implemented in a descendent class to handle storage and ownership for the items created in the linked list.

CreateItem is used in the implementation of the GetNewItem method.

New link list item allocated in the method.
Gets a new linked list item by reusing a free item or creating a new one.

GetNewItem is a TLinkListItem function used to get a new item for the doubly linked list. GetNewItem checks for an unused item in the linked list, and creates a new TLinkListItem instance when a free item is not found. A reused item is updated to remove the Prior and Next traversal nodes in the linked list item. A new item is retrieved by calling the CreateItem method.

Linked list item reused or created in the method.
Configures and adds the specified item as the terminal node for the doubly linked list.

AddAsLast is a procedure used to make the specified list item the terminal node in the doubly linked list. AddAsLast updates the list item in AnItem by setting its Prior property to the node in Last. The value in its Next property is set to Nil. The updated list item is then assigned as the new value for the Last property. The value in First may be set to the value in AnItem when a prior node in the traversal order is not available.

AddAdLast increments the value in the Count property.

Item saved as the last item in the linked list.
First item in the doubly linked list.

First is a read-only TLinkListItem property which represents the first traversal node in the doubly linked list. The value in First is updated in methods like Unbind and AddAsLast.

Last item in the doubly linked list.

Last is a read-only TLinkListItem property which represents the last (or terminal) traversal node in the doubly linked list. The value in Last is updated in methods like Unbind and AddAsLast.

Total number of items used in the doubly linked list.

Count is a read-only Integer property which contains the number of traversal nodes in the doubly linked list. The value in Count is updated in method like Unbind and AddAsLast.

Removes the specified list item from the doubly linked list.

Delete is a procedure used to remove the specified list item from the traversal nodes in the doubly linked list. No actions are performed in the method when AnItem is unassigned (contains Nil).

Delete calls Unbind to update the traversal node for the affected list items. The Prior and Next nodes in AnItem are set to Nil to remove the item from the node order. Delete decrements the value in the Count property.

Item removed from the traversal nodes in the list.
Relocates the specified list item to the last (or terminal) node for the linked list.

MoveToLast is a procedure used to move the specified list item to the last (or terminal) node in the doubly linked list. No actions are performed in the method when AnItem is unassigned (contains Nil).

MoveToLast calls Unbind to ensure that AnItem is removed from the node traversal order in the linked list. MoveToLast calls AddAsLast to update the values in the Prior and Next properties in AnItem making it the terminal node in the traversal order.

Item moved to the last node in the linked list.
Removes all items in the doubly linked list.

Clear is a procedure used to remove all items in the doubly linked list. Clear uses the class instance in First as the initial TLinkListItem in the node traversal order. While the node is assigned, it calls the Delete method for each of the TLinkListItem instances.

Checks the validity of traversal nodes and node counts in the doubly linked list.
Returns 0 when the traversal nodes and counts are valid, or a negative value an inconsistency is found.
Constructor for the class instance.
Create calls the inherited constructor.
Destructor for the class instance.

Destroy calls Clear, and frees the unused items in the linked list. Destroy calls the inherited destructor prior to exiting from the method.