Generic linked list

Today I will present my generic linked list, the advantage with them is:

• Insert or delete at any position is linear (compared with arrays that deleting the first element can be painful)
• Dynamic allocation

some cons:

• A bit complex to implement
• No constant time access since the elements are not stored linearly

Having a look at pros/cons I think a good way of using them are FIFO/LIFO queues, let's see the interface (it can be found at BB.Collection.List)

TLinkedList<T> = class(TInterfacedObject, ISorteable, IIterator<T>)
  private
    type
      TNodeList = class
      public
        Item: T;
        Next,
        Prior: TNodeList;
      end;

      TLinkedListEnum = record
      private
        FList: TLinkedList<T>;
        FFirst: boolean;

        function GetCurrent: T;
      public
        constructor Create(aList: TLinkedList<T>);
        function MoveNext: boolean;

        property Current: T read GetCurrent;
      end;

    var
      FIndexed,
      FHead,
      FTail: TNodeList;
      FCount: integer;
      FOwnObjects: boolean;
      FComparer: IComparer<T>;
      FSearchType: TSearchType;

    function GetItem(aIndex: integer): T;
    procedure SetItem(aIndex: integer; const aItem: T);
    procedure CheckIndex(aIndex: Integer);
    procedure TryFreeObject(aItem: T);
    function InternalFind(aItem: T): TNodeList;
  public
    constructor Create;
    destructor Destroy; override;
    procedure Add(aItem: T);
    procedure Insert(aItem, aWhich: T);
    procedure Clear;
    function Count: integer; inline;
    procedure Delete(aItem: T);
    function GetEnumerator: TLinkedListEnum;
    procedure Sort;
    function Find(aItem: T): boolean;
    //IEnumerator
    function GetCurrent: T; inline;
    function First: boolean;
    function Next: boolean;
    function Last: boolean;

    property OwnObjects: boolean read FOwnObjects write FOwnObjects;
    property Items[aIndex: integer]: T read GetItem write SetItem; default; //Slow!!!
    property Comparer: IComparer<T> read FComparer write FComparer;
    property SearchType: TSearchType read FSearchType write FSearchType;
  end;

Nothing special, just maintenance, an enumerator and a property in case T is an object and you need to auto delete the objects and a flag that tells the class is the search starts from the head or from the tail (guess why),

Let's see the implementation:

{ TLinkedList<T> }

procedure TLinkedList<T>.Add(aItem: T);
var
  current: TNodeList;

begin
  //Create new node
  current := TNodeList.Create;
  current.Item := aItem;
  current.Prior := FTail;
  current.Next := nil;

  //Update head
  if FHead = nil then
    FHead := current;

  //Update tail node (previous node)
  if FTail <> nil then
    FTail.Next := current;
  //Tail always point to the last item added
  FTail := current;

  Inc(FCount);
end;

procedure TLinkedList<T>.Clear;
var
  current, tmp: TNodeList;

begin
  current := FHead;
  while current <> nil do
  begin
    TryFreeObject(current.Item);

    tmp := current;
    current := current.Next;
    tmp.Free;
  end;

  FHead := nil;
  FTail := nil;
  FIndexed := nil;
  FCount := 0;
end;

function TLinkedList<T>.Count: integer;
begin
  result := FCount;
end;

constructor TLinkedList<T>.Create;
begin
  FOwnObjects := True;
  FComparer := TComparer<T>.Default;
  FSearchType := stFromFirst;

  Clear;
end;

procedure TLinkedList<T>.Delete(aItem: T);
var
  current, prior, next: TNodeList;

begin
  current := InternalFind(aItem);
  if current = nil then
    raise Exception.Create('Item not found');

  prior := current.Prior;
  next := current.Next;

  TryFreeObject(current.Item);

  //Update head
  if FHead = current then
  begin
    if next <> nil then
      FHead := next
    else
      FHead := nil;
  end;

  //Update tail
  if FTail = current then
  begin
    if prior <> nil then
      FTail := prior
    else
      FTail := nil;
  end;

  //Update sides
  if prior <> nil then
    prior.Next := next;

  if next <> nil then
    next.Prior := prior;

  current.Free;
  Dec(FCount);
end;

destructor TLinkedList<T>.Destroy;
begin
  Clear;

  inherited;
end;

function TLinkedList<T>.Find(aItem: T): boolean;
begin
  result := InternalFind(aItem) <> nil;
end;

function TLinkedList<T>.First: boolean;
begin
  result := FCount > 0;
  if result then
    FIndexed := FHead;
end;

procedure TLinkedList<T>.TryFreeObject(aItem: T);
var
  v: TValue;

begin
  if FOwnObjects then
  begin
    v := TValue.From<T>(aItem);
    if v.IsObject then
      v.AsObject.Free;
  end;
end;

function TLinkedList<T>.GetCurrent: T;
begin
  result := FIndexed.Item;
end;

function TLinkedList<T>.GetEnumerator: TLinkedListEnum;
begin
  result := TLinkedListEnum.Create(self);
end;

function TLinkedList<T>.GetItem(aIndex: integer): T;
var
  i: integer;
  current: TNodeList;

begin
  CheckIndex(aIndex);

  current := FHead;
  for i := 0 to aIndex - 2 do
    current := current.Next;
  Exit(current.Item);
end;

procedure TLinkedList<T>.Insert(aItem, aWhich: T);
var
  NewNode, CurrentNode, prior, next: TNodeList;

begin
  CurrentNode := InternalFind(aWhich);
  if CurrentNode = nil then
    raise Exception.Create('Cannot insert, item does not exists');

  NewNode := TNodeList.Create;
  NewNode.Item := aItem;

  //Update left side
  prior := CurrentNode.Prior;
  if prior <> nil then
  begin
    prior.Next := NewNode;
    NewNode.Prior := prior;
  end else
    NewNode.Prior := nil;

  //Update sides
  NewNode.Next := CurrentNode;
  CurrentNode.Prior := NewNode;

  //Update head?
  if FHead = CurrentNode then
    FHead := NewNode;
end;

function TLinkedList<T>.InternalFind(aItem: T): TNodeList;
var
  current: TNodeList;
  cmp: IComparer<T>;

begin
  result := nil;
  cmp := TComparer<T>.Default;

  if FSearchType = stFromFirst then
    current := FHead
  else
    current := FTail;

  while current <> nil do
  begin
    if cmp.Compare(current.Item, aItem) = 0 then
    begin
      result := current;
      Break;
    end;

    if FSearchType = stFromFirst then
      current := current.Next
    else
      current := current.Prior;
  end;
end;

function TLinkedList<T>.Last: boolean;
begin
  result := FCount > 0;
  if result then
    FIndexed := FTail;
end;

procedure TLinkedList<T>.CheckIndex(aIndex: Integer);
begin
  if aIndex >= FCount then
    raise Exception.Create('Invalid index');
end;

function TLinkedList<T>.Next: boolean;
begin
  result := FIndexed.Next <> nil;
  if result then
    FIndexed := FIndexed.Next;
end;

procedure TLinkedList<T>.SetItem(aIndex: integer; const aItem: T);
var
  i: integer;
  current: TNodeList;

begin
  CheckIndex(aIndex);

  current := FHead;
  for i := 0 to aIndex - 2 do
    current := current.Next;
  current.Item := aItem;
end;

procedure TLinkedList<T>.Sort;
var
  v: TValue;
  list: TList<T>;
  was: boolean;
  i: integer;

begin
  if not First then
    Exit;

  list := TList<T>.Create;
  try
    repeat
      list.Add(GetCurrent);
    until not Next;

    list.Sort(FComparer);

    was := OwnObjects;
    try
      OwnObjects := False;

      Clear;
      for i := 0 to list.Count - 1 do
        Add(list[i]);
    finally
      OwnObjects := was;
    end;

  finally
    list.Free;
  end;
end;

That's it, now I will post the generic queues.