- 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.
