Generic linked lists redux

Do generics and typed pointers mix? Certainly, so long as you use a nested type:

type
  TOuterType<T> = class
  public type
    PInnerType = ^TInnerType;
    TInnerType = record
      Value: T;
    end;
  end;

OK, so the New/Dispose bug still holds, but that’s only a minor irritant. I’m not sure why I didn’t think of the nested type ‘trick’ before, and indeed, I’ve now noticed Alexandru Ciobanu uses this sort of thing in his Collections project (which, by the way, is well worth looking at generally). Better late than never though!

Put to work, here’s a simple generic queue implementation based on a singly-linked list. In use, it works just like the stock TQueue<T>:

unit CCR.LinkedQueue;

interface

type
  TLinkedQueue<T> = class
  strict private type
    PNode = ^TNode;
    TNode = record
      NextNode: PNode;
      Value: T;
    end;
  public type
    TEnumerator = record
    strict private
      FDoneFirst: Boolean;
      FNode: PNode;
      function GetCurrent: T;
    public
      constructor Create(AHeadNode: PNode);
      function MoveNext: Boolean;
      property Current: T read GetCurrent;
    end;
  strict private
    FCount: Integer;
    FHeadNode, FTailNode: PNode;
  public
    destructor Destroy; override;
    function GetEnumerator: TEnumerator;
    procedure Clear;
    procedure Enqueue(const Value: T);
    function Dequeue: T;
    function Peek: T;
    property Count: Integer read FCount;
  end;

implementation

uses RTLConsts, Classes;

constructor TLinkedQueue<T>.TEnumerator.Create(AHeadNode: PNode);
begin
  FDoneFirst := False;
  FNode := AHeadNode;
end;

function TLinkedQueue<T>.TEnumerator.GetCurrent: T;
begin
  Result := FNode.Value;
end;

function TLinkedQueue<T>.TEnumerator.MoveNext: Boolean;
begin
  if FDoneFirst then
    FNode := FNode.NextNode
  else
    FDoneFirst := True;
  Result := (FNode <> nil);
end;

destructor TLinkedQueue<T>.Destroy;
begin
  Clear;
  inherited;
end;

function TLinkedQueue<T>.GetEnumerator: TEnumerator;
begin
  Result := TEnumerator.Create(FHeadNode);
end;

procedure TLinkedQueue<T>.Clear;
var
  Node: PNode;
begin
  while FHeadNode <> nil do
  begin
    Node := FHeadNode.NextNode;
    Finalize(FHeadNode.Value);
    FreeMem(FHeadNode);
    FHeadNode := Node;
  end;
  FCount := 0;
end;

procedure TLinkedQueue<T>.Enqueue(const Value: T);
var
  NewNode: PNode;
begin
  NewNode := AllocMem(SizeOf(TNode));
  NewNode.Value := Value;
  if FHeadNode = nil then
    FHeadNode := NewNode
  else
    FTailNode.NextNode := NewNode;
  FTailNode := NewNode;
  Inc(FCount);
end;

function TLinkedQueue<T>.Dequeue: T;
var
  Node: PNode;
begin
  if Count = 0 then
    raise EListError.CreateRes(@SUnbalancedOperation);
  Node := FHeadNode;
  Result := Node.Value;
  FHeadNode := Node.NextNode;
  Finalize(Node);
  FreeMem(Node);
  Dec(FCount);
end;

function TLinkedQueue<T>.Peek: T;
begin
  if Count = 0 then
    raise EListError.CreateRes(@SUnbalancedOperation);
  Result := FHeadNode.Value;
end;

end.

Pretty straightforward I’d say.

What of a generic linked list in a fuller sense though, where you can insert and remove items in any order? While this could be done using pointers, you would then be caught between exposing the pointer stuff directly (in which case, why bother with a generic container in the first place – just implement the pattern directly) and hiding it under an array list-type shell. I’d say it’s better to avoid both by using a class for the node type instead:

unit CCR.SimpleLinkedList;

interface

type
  TSimpleLinkedList<T> = class
  public type
    TNode = class
    strict private
      FPrevious, FNext: TNode;
      FList: TSimpleLinkedList<T>;
      FValue: T;
    protected
      constructor Create(AList: TSimpleLinkedList<T>; APrevious, ANext: TNode;
        const AValue: T); overload;
    public
      constructor Create; overload; //disallow outside construction by raising an exception
      destructor Destroy; override;
      procedure MoveBefore(ANode: TNode);
      procedure MoveAfter(ANode: TNode);
      property List: TSimpleLinkedList<T> read FList;
      property Next: TNode read FNext write FNext;
      property Previous: TNode read FPrevious write FPrevious;
      property Value: T read FValue write FValue;
    end;

    TValueEnumerator = record
    strict private
      FDoneFirst: Boolean;
      FNode: TNode;
      function GetCurrent: T;
    public
      constructor Create(AHead: TNode);
      function MoveNext: Boolean;
      property Current: T read GetCurrent;
    end;
  private
    FCount: Integer;
    FFirst, FLast: TNode;
    procedure ValidateNode(ANode: TNode);
  public
    destructor Destroy; override;
    function GetEnumerator: TValueEnumerator;
    procedure Clear;
    function Add(const AValue: T): TNode; inline;
    function AddAfter(ANode: TNode; const AValue: T): TNode;
    function Insert(Index: Integer; const AValue: T): TNode;
    function InsertBefore(ANode: TNode; const AValue: T): TNode;
    property Count: Integer read FCount;
    property First: TNode read FFirst;
    property Last: TNode read FLast;
  end;

implementation

uses SysUtils, RTLConsts; //for the standard exception types and error messages

{ TNode }

constructor TSimpleLinkedList<T>.TNode.Create;
begin
  raise ENoConstructException.CreateResFmt(@SNoConstruct, [ClassName]);
end;

constructor TSimpleLinkedList<T>.TNode.Create(AList: TSimpleLinkedList<T>;
  APrevious, ANext: TNode; const AValue: T);
begin
  Assert(AList <> nil);
  inherited Create;
  FPrevious := APrevious;
  FNext := ANext;
  if APrevious <> nil then APrevious.Next := Self;
  if ANext <> nil then ANext.Previous := Self;
  if APrevious = AList.Last then AList.FLast := Self;
  if ANext = AList.First then AList.FFirst := Self;
  FList := AList;
  FValue := AValue;
  Inc(AList.FCount);
end;

destructor TSimpleLinkedList<T>.TNode.Destroy;
begin
  Dec(List.FCount);
  if Self = List.First then List.FFirst := Next;
  if Self = List.Last then List.FLast := Previous;
  if Previous <> nil then Previous.FNext := Next;
  if Next <> nil then Next.FPrevious := Previous;
  inherited Destroy;
end;

procedure TSimpleLinkedList<T>.TNode.MoveBefore(ANode: TNode);
begin
  List.ValidateNode(ANode);
  if ANode = Next then Exit;
  //unlink ourselves from our current neighbours
  if Previous <> nil then Previous.Next := Next;
  if Next <> nil then Next.Previous := Previous;
  //link ourselves to our new neighbours
  Previous := ANode.Previous;
  if Previous <> nil then Previous.Next := Self;
  ANode.Previous := Self;
  Next := ANode;
end;

procedure TSimpleLinkedList<T>.TNode.MoveAfter(ANode: TNode);
begin
  List.ValidateNode(ANode);
  if ANode = Previous then Exit;
  //unlink ourselves from our current neighbours
  if Previous <> nil then Previous.Next := Next;
  if Next <> nil then Next.Previous := Previous;
  //link ourselves to our new neighbours
  Next := ANode.Next;
  if Next <> nil then Next.Previous := Self;
  ANode.Next := Self;
  Previous := ANode;
end;

{ TValueEnumerator }

constructor TSimpleLinkedList<T>.TValueEnumerator.Create(AHead: TNode);
begin
  FDoneFirst := False;
  FNode := AHead;
end;

function TSimpleLinkedList<T>.TValueEnumerator.MoveNext: Boolean;
begin
  if not FDoneFirst then
    FDoneFirst := True
  else
    FNode := FNode.Next;
  Result := (FNode <> nil);
end;

function TSimpleLinkedList<T>.TValueEnumerator.GetCurrent: T;
begin
  Result := FNode.Value;
end;

{ TSimpleLinkedList }

destructor TSimpleLinkedList<T>.Destroy;
begin
  Clear;
  inherited Destroy;
end;

function TSimpleLinkedList<T>.GetEnumerator: TValueEnumerator;
begin
  Result := TValueEnumerator.Create(First);
end;

function TSimpleLinkedList<T>.Add(const AValue: T): TNode;
begin
  Result := TNode.Create(Self, Last, nil, AValue);
end;

function TSimpleLinkedList<T>.AddAfter(ANode: TNode; const AValue: T): TNode;
begin
  ValidateNode(ANode);
  Result := TNode.Create(Self, ANode, ANode.Next, AValue);
end;

procedure TSimpleLinkedList<T>.Clear;
begin
  while Count > 0 do First.Free;
end;

function TSimpleLinkedList<T>.Insert(Index: Integer; const AValue: T): TNode;
var
  I: Integer;
  Node: TNode;
begin
  if (Index < 0) or (Index > Count) then
    raise EArgumentOutOfRangeException.CreateRes(@SArgumentOutOfRange);
  if Index = Count then
    Result := Add(AValue)
  else
  begin
    Node := First;
    for I := 1 to Index do
      Node := Node.Next;
    Result := TNode.Create(Self, Node.Previous, Node, AValue);
  end;
end;

function TSimpleLinkedList<T>.InsertBefore(ANode: TNode; const AValue: T): TNode;
begin
  ValidateNode(ANode);
  Result := TNode.Create(Self, ANode.Previous, ANode, AValue);
end;

procedure TSimpleLinkedList<T>.ValidateNode(ANode: TNode);
begin
  if ANode = nil then
    raise EArgumentNilException.CreateRes(@SArgumentNil);
  if ANode.List <> Self then
    raise EArgumentOutOfRangeException.CreateRes(@SGenericItemNotFound);
end;

end.

Beyond the custom enumerator to support for/in loops, this should be considered a pretty minimal implementation. As with the LinkedList class in the .NET BCL, it deliberately avoids an indexer and instead exposes the node objects directly. To delete an item, you therefore free the node. Here’s it in action:


var
  List: TSimpleLinkedList<string>;
  Fourth, Sixth, Seventh: TSimpleLinkedList<string>.TNode;
  S: string;
begin
  ReportMemoryLeaksOnShutdown := True;
  List := TSimpleLinkedList<string>.Create;
  try
    Fourth := List.Add('Fourth');
    List.InsertBefore(Fourth, 'Second');
    Sixth := List.AddAfter(Fourth, 'Sixth');
    List.InsertBefore(Sixth, 'Fifth');
    Seventh := List.InsertBefore(Fourth, 'Seventh');
    List.Add('Zero');
    List.Insert(0, 'First');
    List.Insert(2, 'Third');
    Seventh.MoveAfter(Sixth);
    List.Last.Free; //this removes the node from the list
    for S in List do
      WriteLn(S);
  finally
    List.Free;
  end;
  ReadLn;
end.

I’ve put up a slightly ‘fuller-fat’ version here if anyone’s interested. Compared to the one presented above, it fits into the framework of Generics.Collections (meaning, it descends from TEnumerable<T> and uses IComparer<T>), adds most of the methods from the stock TList<T>, and implements optional object ownership when instantiated with a class.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s