delphi 쌍방향 체인 시계, 단방향 체인 시계, 일반 버전

//    
  TSingleLinkedNode = class
  public
    Value: T;
  private
    m_Next: TSingleLinkedNode;
  end;

  TMYLinkedNode = class
  public
    Value: T;
  private
    m_Prev, m_Next: TMYLinkedNode;
  end;

  //   
  TLinkedNodePool = class
  protected
    m_Nodes: TArray;
    m_Index: Integer;
    m_Capacity: Integer;
    m_Stoped: Boolean;
    function NewNode: TObject; virtual; abstract;
    procedure FreeNode(node: TObject); virtual; abstract;
    function GetNode: TObject;
    procedure RetNode(node: TObject);
    procedure ReSize;
    procedure Clear;
  public
    constructor Create(nCapacity: Integer = 128); virtual;
    destructor Destroy; override;
  end;

  //    
  TSingleLinked = class(TLinkedNodePool)
  protected
    m_Head: TSingleLinkedNode;
    m_CurrNode: TSingleLinkedNode;
    m_Count: Integer;
    function NewNode: TObject; override;
    procedure FreeNode(node: TObject); override;
    class function Equal(value1, value2: T): Boolean; static;
  public
    destructor Destroy; override;
    procedure Clear;
    procedure Add(value: T);
    function Delete(value: T; allItem: Boolean = False): TSingleLinkedNode;
    function First: TSingleLinkedNode;
    function Next: TSingleLinkedNode;
    property Count: Integer read m_Count;
  end;

  //     
  TMYLinkedBase = class(TLinkedNodePool)
  protected
    m_Head, m_Tail: TMYLinkedNode;
    m_CurrNode: TMYLinkedNode;
    m_Count: Integer;
    function NewNode: TObject; override;
    procedure FreeNode(node: TObject); override;
    procedure AddT(value: T);
    function DeleteT(value: T; allItem: Boolean = False): TMYLinkedNode;
  public
    constructor Create(nCapacity: Integer = 128); override;
    destructor Destroy; override;
    procedure Clear;
    function DelNode(node: TMYLinkedNode): TMYLinkedNode;
    function First: TMYLinkedNode;
    function Next: TMYLinkedNode;
    property Count: Integer read m_Count;
  end;

  //   
  TMYLinked = class(TMYLinkedBase)
  public
    procedure Add(value: T);
    function Delete(value: T; allItem: Boolean = False): TMYLinkedNode;
  end;

  //  
  TMYQueue = class(TMYLinkedBase)
  public
    procedure Push(value: T);
    function Pop: T;
  end;

{ TLinkedNodePool }

procedure TLinkedNodePool.Clear;
var
  i: Integer;
begin
  for i := 0 to m_Index do
    FreeNode(m_Nodes[i]);
end;

constructor TLinkedNodePool.Create(nCapacity: Integer);
begin
  SetLength(m_Nodes, nCapacity);
  m_Capacity := nCapacity;
  m_Index := -1;
end;

destructor TLinkedNodePool.Destroy;
begin
  m_Stoped := True;
  Clear;
  SetLength(m_Nodes, 0);
  inherited;
end;

function TLinkedNodePool.GetNode: TObject;
begin
  Result := nil;
  if m_Index < 0 then
    ReSize;

  if m_Index >= 0 then begin
    Result := m_Nodes[m_Index];
    Dec(m_Index);
  end;
end;

procedure TLinkedNodePool.RetNode(node: TObject);
begin
  if (m_Index >= Length(m_Nodes) - 1) or m_Stoped then
    FreeNode(node)
  else begin
    Inc(m_Index);
    m_Nodes[m_Index] := node;
  end;
end;

procedure TLinkedNodePool.ReSize;
var
  i: Integer;
  node: TObject;
begin
  for i := 0 to (m_Capacity div 2) do begin
    if m_Index >= Length(m_Nodes) - 1 then
      m_Index := 0
    else
      Inc(m_Index);

    node := Self.NewNode;
    m_Nodes[m_Index] := node;
  end;
end;

{ TSingleLinked }

procedure TSingleLinked.Clear;
var
  Temp, Temp1: TSingleLinkedNode;
begin
  Temp := m_Head;
  while Temp <> nil do begin
    Temp1 := Temp;
    Temp := Temp.m_Next;
    Self.RetNode(Temp1);
  end;
  m_Head := nil;
  m_Count := 0;
end;

destructor TSingleLinked.Destroy;
begin
  Clear;
  inherited;
end;

class function TSingleLinked.Equal(value1, value2: T): Boolean;
var
  lComparer: IEqualityComparer;
begin
  lComparer := TEqualityComparer.default;
  Result := lComparer.Equals(value1, value2);
end;

procedure TSingleLinked.Add(value: T);
var
  node: TSingleLinkedNode;
begin
  node := TSingleLinkedNode(Self.GetNode);
  node.Value := value;
  node.m_Next := nil;
  if m_Head = nil then
    m_Head := node
  else begin
    node.m_Next := m_Head.m_Next;
    m_Head.m_Next := node;
  end;
  Inc(m_Count);
end;


//allItem               
function TSingleLinked.Delete(value: T; allItem: Boolean): TSingleLinkedNode;
var
  Temp, priNode: TSingleLinkedNode;
begin
  Temp := m_Head;
  priNode := nil;  //      
  Result := nil;
  while Temp <> nil do begin
    if Equal(Temp.Value, value) then begin
      if priNode = nil then begin     //     
        m_Head := Temp.m_Next;
        m_CurrNode := Temp.m_Next;    //  foreach next  
        Result := Temp.m_Next;
        Self.RetNode(Temp);
        Dec(m_Count);
      end
      else begin
        priNode.m_Next := Temp.m_Next;  //    
        Result := Temp.m_Next;
        m_CurrNode := Temp.m_Next;
        Self.RetNode(Temp);
        Dec(m_Count);
      end;

      if not allItem then  //       ，     
        Break;
    end
    else begin
      priNode := Temp;
      Temp := Temp.m_Next;
    end;
  end;
end;

function TSingleLinked.NewNode: TObject;
begin
  Result := TSingleLinkedNode.Create;
end;

procedure TSingleLinked.FreeNode(node: TObject);
begin
  TSingleLinkedNode(node).Free;
end;

function TSingleLinked.First: TSingleLinkedNode;
begin
  m_CurrNode := m_Head;
  Result := m_CurrNode;
end;

function TSingleLinked.Next: TSingleLinkedNode;
begin
  m_CurrNode := m_CurrNode.m_Next;
  Result := m_CurrNode;
end;

{ TMYLinkedBase }

procedure TMYLinkedBase.Clear;
var
  Temp, Temp1: TMYLinkedNode;
begin
  Temp := m_Head.m_Next;
  while Temp <> nil do begin
    Temp1 := Temp;
    Temp := Temp.m_Next;
    Self.RetNode(Temp1);
  end;
  m_Tail := nil;
  m_Head.m_Next := m_Tail;
  m_Count := 0;
end;

constructor TMYLinkedBase.Create(nCapacity: Integer);
begin
  inherited Create(nCapacity);
  m_Head := TMYLinkedNode.Create;
  m_Head.m_Next := m_Tail;
  m_Head.m_Prev := nil;
  m_Head.Value := default(T);
end;

destructor TMYLinkedBase.Destroy;
begin
  m_Head.Free;
  Clear;
  inherited;
end;

procedure TMYLinkedBase.AddT(value: T);
var
  Node: TMYLinkedNode;
begin
  Node := TMYLinkedNode(Self.GetNode);
  Node.Value := value;
  if m_Head.m_Next = nil then begin
    m_Head.m_Next := Node;
    Node.m_Prev := m_Head;
    Node.m_Next := nil;
    m_Tail := Node;
  end
  else begin
    m_Head.m_Next.m_Prev := Node;
    Node.m_Next := m_Head.m_Next;
    Node.m_Prev := m_Head;
    m_Head.m_Next := Node;
  end;
  Inc(m_Count);
end;


//        
function TMYLinkedBase.DeleteT(value: T; allItem: Boolean): TMYLinkedNode;
var
  Temp: TMYLinkedNode;
begin
  Temp := m_Head.m_Next;
  Result := nil;
  while Temp <> nil do begin
    if TSingleLinked.Equal(Temp.Value, value) then begin
      Temp.m_Prev.m_Next := Temp.m_Next;
      Result := Temp.m_Next;
      m_CurrNode := Temp.m_Next;
      if Temp.m_Next <> nil then
        Temp.m_Next.m_Prev := Temp.m_Prev
      else if Temp.m_Prev = m_Head then
        m_Tail := nil
      else
        m_Tail := Temp.m_Prev;

      Self.RetNode(Temp);
      Dec(m_Count);
      if not allItem then
        Break;
    end
    else
      Temp := Temp.m_Next;
  end;
end;


//               ，    
function TMYLinkedBase.DelNode(node: TMYLinkedNode): TMYLinkedNode;
begin
  Result := node.m_Next;
  m_CurrNode := node.m_Next;
  node.m_Prev.m_Next := node.m_Next; //      prev，         
  if node.m_Next <> nil then
    node.m_Next.m_Prev := node.m_Prev
  else if node.m_Prev = m_Head then
    m_Tail := nil
  else
    m_Tail := node.m_Prev;

  Self.RetNode(node);
  Dec(m_Count);
end;

function TMYLinkedBase.First: TMYLinkedNode;
begin
  m_CurrNode := m_Head.m_Next;
  Result := m_CurrNode;
end;

function TMYLinkedBase.Next: TMYLinkedNode;
begin
  Result := m_CurrNode.m_Next;
  m_CurrNode := m_CurrNode.m_Next;
end;

procedure TMYLinkedBase.FreeNode(node: TObject);
begin
  TMYLinkedNode(node).Free;
end;

function TMYLinkedBase.NewNode: TObject;
begin
  Result := TMYLinkedNode.Create;
end;


{ TMYLinked }

procedure TMYLinked.Add(value: T);
begin
  inherited AddT(value);
end;

function TMYLinked.Delete(value: T; allItem: Boolean): TMYLinkedNode;
begin
  inherited DeleteT(value, allItem);
end;

{ TMYQueue }

//   
procedure TMYQueue.Push(value: T);
var
  Node: TMYLinkedNode;
begin
  Node := TMYLinkedNode(Self.GetNode);
  Node.Value := value;
  if m_Tail = nil then begin
    m_Tail := Node;
    m_Tail.m_Next := nil;
    m_Tail.m_Prev := m_Head;
    m_Head.m_Next := m_Tail;
  end
  else begin
    m_Tail.m_Next := Node;
    Node.m_Prev := m_Tail;
    Node.m_Next := nil;
    m_Tail := Node;
  end;
  Inc(m_Count);
end;

function TMYQueue.Pop: T;
var
  Temp: TMYLinkedNode;
begin
  Temp := m_Head.m_Next;
  Result := default(T);
  if Temp <> nil then begin
    Result := Temp.Value;
    m_Head.m_Next := Temp.m_Next;
    Temp.m_Prev := m_Head;
    if m_Head.m_Next = nil then
      m_Tail := nil;
    Self.RetNode(Temp);
    m_CurrNode := m_Head.m_Next;  //     
  end;
  Dec(m_Count);
end;