Singly Linked List

unit SinglyLinkedList;

{==============================================================================}

{$mode objfpc}{$H+}

{==============================================================================}

interface

{==============================================================================}

uses
  Classes, SysUtils;

{==============================================================================}

type
  TData = Word;

{------------------------------------------------------------------------------}

const
  ELEMENT_DATA_SIZE = SizeOf(TData);

{------------------------------------------------------------------------------}

type
  PElement = ^TElement;
  TElement = record
    Data : TData;
    Next : PElement;
end;

{------------------------------------------------------------------------------}

type
  TSinglyLinkedList = class
    private
      FFirst    : PElement;
      FLast     : PElement;
      FCount    : LongWord;
    private
      function CreateElement(AData: TData) : PElement;
      procedure GetElementByIndex(AIndex: Cardinal; out APrev, AElement: PElement);
      function GetCapacity : LongWord;
    public
      constructor Create;
      destructor Destroy; override;
    public
      procedure Add(AElement : TData);
      procedure Insert(AElement : TData; AIndex : Word);
      procedure Delete(AIndex : Word);
      procedure Clear;
    public
      function Find(AData : TData) : Integer;
      function Get(AIndex : Word) : TData;
    public
      procedure SaveToFile(AFileName : String);
      procedure LoadFromFile(AFileName : String);
      procedure Print;
    public
      property Count : LongWord read FCount;
      property Capacity : LongWord read GetCapacity;
  end;

{==============================================================================}

implementation

{==============================================================================}

constructor TSinglyLinkedList.Create;
begin
  inherited Create();
  FFirst := nil;
  FLast := nil;
  FCount := 0;
end;

{------------------------------------------------------------------------------}

destructor TSinglyLinkedList.Destroy;
begin
  Clear();
  inherited Destroy();
end;

{------------------------------------------------------------------------------}

function TSinglyLinkedList.CreateElement(AData: TData) : PElement;
begin
  New(Result);
  Result^.Next := nil;
  Result^.Data := AData;
end;

{------------------------------------------------------------------------------}

procedure TSinglyLinkedList.GetElementByIndex(AIndex: Cardinal; out APrev, AElement: PElement);
begin
  AElement := FFirst;
  APrev := nil;

  while AIndex > 0 do
  begin
    APrev := AElement;
    AElement := AElement^.Next;
    Dec(AIndex);
  end;
end;

{------------------------------------------------------------------------------}

function TSinglyLinkedList.GetCapacity : LongWord;
begin
  Result := FCount * ELEMENT_DATA_SIZE;
end;

{------------------------------------------------------------------------------}

procedure TSinglyLinkedList.Add(AElement : TData);
var
  NewOne : PElement;
begin
  NewOne := CreateElement(AElement);

  if FFirst = nil then
  begin
    FFirst := NewOne;
    FLast := FFirst;
  end
  else
  begin
    FLast^.Next := NewOne;
    FLast := NewOne;
  end;

  Inc(FCount);
end;

{------------------------------------------------------------------------------}

procedure TSinglyLinkedList.Insert(AElement : TData; AIndex : Word);
var
  NewOne, Next, Prev : PElement;
begin
  if AIndex = FCount - 1 then
    Add(AElement)
  else
  begin
    NewOne := CreateElement(AElement);

    GetElementByIndex(AIndex, Prev, Next);

    if Next = FFirst then
    begin
      NewOne^.Next := FFirst;
      FFirst := NewOne;
    end
    else
    begin
      Prev^.Next := NewOne;
      NewOne^.Next := Next;
      if NewOne^.Next = nil then
        FLast := NewOne;
    end;

    Inc(FCount);
  end;
end;

{------------------------------------------------------------------------------}

procedure TSinglyLinkedList.Delete(AIndex : Word);
var
  ToDelete, Prev: PElement;
begin
  if AIndex = 0 then
  begin
    ToDelete := FFirst;
    FFirst := FFirst^.Next;

    if FFirst = nil then
      FLast := nil;
  end
  else
  begin
    GetElementByIndex(AIndex, Prev, ToDelete);

    if ToDelete^.Next = nil then
    begin
      FLast := Prev;
      Prev^.Next := nil;
    end
    else
      Prev^.Next := ToDelete^.Next;
  end;

  Dispose(ToDelete);
  Dec(FCount);
end;

{------------------------------------------------------------------------------}

procedure TSinglyLinkedList.Clear;
var
  ToDelete : PElement;
begin
  while FFirst <> nil do
  begin
    ToDelete := FFirst;
    FFirst := FFirst^.Next;
    Dispose(ToDelete);
  end;
  FLast := nil;
  FCount := 0;
end;

{------------------------------------------------------------------------------}

function TSinglyLinkedList.Find(AData : TData) : Integer;
var
  ToFind : PElement;
begin
  Result := 0;
  ToFind := FFirst;

  while ToFind <> nil do
  if ToFind^.Data = AData then
    Exit
  else
  begin
    ToFind := ToFind^.Next;
    Inc(Result);
  end;

  Result := -1;
end;

{------------------------------------------------------------------------------}

function TSinglyLinkedList.Get(AIndex : Word) : TData;
var
  ToGet, Unused : PElement;
begin
  if AIndex = FCount - 1 then
    Result := FLast^.Data
  else
  begin
    GetElementByIndex(AIndex, Unused, ToGet);
    Result := ToGet^.Data;
  end;
end;

{------------------------------------------------------------------------------}

procedure TSinglyLinkedList.SaveToFile(AFileName : String);
var
  SaveFile : TFileStream;
  ToSave   : PElement;
begin
  SaveFile := TFileStream.Create(AFileName, fmCreate);
  ToSave := FFirst;
  try
    while ToSave <> nil do
    begin
      SaveFile.WriteBuffer(ToSave^.Data, ELEMENT_DATA_SIZE);
      ToSave := ToSave^.Next;
    end;
  finally
    FreeAndNil(SaveFile);
  end;
end;

{------------------------------------------------------------------------------}

procedure TSinglyLinkedList.LoadFromFile(AFileName : String);
var
  LoadFile : TFileStream;
  ToLoad   : TData;
begin
  LoadFile := TFileStream.Create(AFileName, fmOpenRead);
  try
    while LoadFile.Position < LoadFile.Size do
    begin
      LoadFile.ReadBuffer(ToLoad, ELEMENT_DATA_SIZE);
      Add(ToLoad);
    end;
  finally
    FreeAndNil(LoadFile);
  end;
end;

{------------------------------------------------------------------------------}

procedure TSinglyLinkedList.Print;
var
  ToPrint : PElement;
  Index   : Word;
begin
  ToPrint := FFirst;
  Index := 0;

  Writeln('Count: ', FCount);
  Writeln('Capacity: ', GetCapacity);
  while ToPrint <> nil do
  begin
    Writeln('Index: ',Index,' Data: ',  ToPrint^.Data);

    ToPrint := ToPrint^.Next;
    Inc(Index);
  end;
end;

{==============================================================================}

end.