[Back to POINTERS SWAG index] [Back to Main SWAG index] [Original]

    unit Lists;

    {--------------------------------------------------------------------------}
    { Abstract Data Type for dynamically sized list                            }
    { By Michael Dales 30th May 1996                                           }
    {                                                                          }
    { Here is a simple list unit, that has the advantage of being dynamically  }
    { sized, unlike normal arrays. To use the list you only need to know the   }
    { data type names and the methods declared in the interface of this unit   }
    { are used to manipulate them without the need to know the underlying      }
    { representation.                                                          }
    {                                                                          }
    { Deaclare your list variable to be of type TList, and remeber to use      }
    { CreateList on it before you carry out any operations using it. Data is   }
    { stored in nodes as pointers, just so you can have a list which isn't     }
    { tied to just one kind of data type. Remeber though that because of this  }
    { you'll need to typecast your pointers when you retrieve them from the    }
    { list. Each node is has a type called PListNode, and an invalid node has  }
    { the value null.                                                          }
    {                                                                          }
    { Email comments to: 9402198d@udcf.gla.ac.uk                               }
    { URL: http://www.gla.ac.uk/Clubs/WebSoc/~9402198d/index.html              }
    {--------------------------------------------------------------------------}

    interface

    const null = nil;        {Non specific terminator}

    type PListNode = ^TListNode;             {Pointer to node}
         TListNode = record                  {Node record}
                   Item      : Pointer;      {Pointer to node data}
                   Next      : PListNode;    {Next node}
                   Previous  : PListNode;    {Previous node}
         end;

         TList = record                   {Holder for list}
               First : PListNode;         {Pointer to start of list}
               Rear  : PListNode;         {Pointer to end of list}
               Size  : integer;           {Size of list}
         end;

    {CreateList - Initiates a new list}
    procedure CreateList(var L : TList);

    {DestroyList - Frees up all memory used by list and sets list to nil}
    procedure DestroyList(var L : TList);

    {AddNewNode - Adds new node to list L, filling it with the data
                  supplied. Returns true is new node sucessfully
                  added, otherwise returns false.}
    procedure AddNewNode(var L : TList; Data : Pointer);

    {DeleteListElement - Deletes an element passed.}
    procedure DeleteNode(var L : TList; ANode : PListNode);

    {GetFirstNode - Returns the first node in a given list}
    function GetFirstNode(L:TList):PListNode;

    {GetNextNode - Returns the successor of the given node}
    function GetNextNode(Node:PListNode):PListNode;

    {GetNodeData - Returns the data in a specific node}
    procedure GetNodeData(Node:PListNode; var Data:Pointer);

    {UpdateNode - Replaces a nodes details with new ones}
    procedure UpdateNode(Node:PListNode; Data:Pointer);

    {--------------------------------------------------------------------------}
    implementation
    {--------------------------------------------------------------------------}

        {CreateList - Initiates a new list}

    procedure CreateList(var L : TList);
    begin
         L.First := nil;      {No list yet}
         L.Rear := nil;
         L.Size := 0;         {No length yet}
    end;

        {RemoveLastNode - Deletes last node on the list}

    procedure RemoveLastNode(var L : TList);
    begin
         with L do                                  {With the list}
         begin
              if Size > 0 then                        {If nodes in list}
              begin
                   if Size = 1 then                   {If just one node}
                   begin
                        if First^.Item <> nil then  {If data in node then}
                           Dispose(First^.Item);        {Dispose of it}
                        Dispose(First);             {Dispose of first node}
                        First := nil;
                        Rear := nil;                  {Set rear to nil}
                   end else
                   begin                            {If more than one node}
                        Rear := Rear^.Previous;       {Set rear to second last}
                        Dispose(Rear^.Next);        {Remove last node}
                   end;
                   Size := Size-1;                    {Decrement list size}
              end;
         end;
    end;

        {DestroyList - Frees up all memory used by list and sets list to nil}

    procedure DestroyList(var L : TList);
    begin
         while L.First <> nil do              {While still nodes left}
               RemoveLastNode(L);             {Remove last node}
         CreateList(L);
    end;

        {GetFirstNode - Returns the first node in a given list}

    function GetFirstNode(L : TList) : PListNode;
    begin
         GetFirstNode := L.First;
    end;

        {GetNextNode - Returns the successor of the given node}

    function GetNextNode(Node : PListNode) : PListNode;
    begin
         if Node <> nil then
            GetNextNode := Node^.Next
         else
             GetNextNode := nil;
    end;

        {GetNodeData - Returns the data in a specific node}

    procedure GetNodeData(Node : PListNode; var Data : Pointer);
    begin
         if Node <> nil then
            Data := Node^.Item
         else
             Data := nil;
    end;

        {AddNewNode - Adds new node to list L, filling it with the data
                      supplied. Returns true is new node sucessfully
                      added, otherwise returns false.}

    procedure AddNewNode(var L:TList; Data:Pointer);
    var temp    : PListNode;
    begin
         new(temp);                 {Create new node}
         with temp^ do              {Fill node}
         begin
              Item := Data;
              Next := nil;
              Previous := L.Rear;
         end;
         If (L.Size = 0) then         {If empty list...}
         begin
              L.First := temp;        {Add as first node}
              L.Rear := temp;
         end else                       {else add at end}
         begin
              L.Rear^.Next := temp;  {Make old rear of list point to new}
              L.Rear := temp;        {Make rear point to new node}
         end;
         L.Size := L.Size + 1;          {Increment list length}
    end;

        {UpdateNode - Replaces a nodes details with new ones}

    procedure UpdateNode(Node : PListNode; Data : Pointer);
    begin
         if Node <> nil then
         begin
              Node^.Item := Data;
         end;
    end;

        {DeleteListElement - Deletes an element passed.}

    procedure DeleteNode(var L : TList; ANode : PListNode);
    begin
         if (L.Size = 1) or (ANode^.Next = nil) then    {If we're deeling with}
            RemoveLastNode(L)            {last node then that's easy}
         else                            {otherwise...}
         begin
              if (ANode = L.First) then      {if we're deleting the first node}
              begin
                   L.First := L.First^.Next;    {Start list from second node}
                   L.First^.Previous := nil;    {Set new starts previous link}
                   Dispose(ANode);              {Dispose of old first}
              end else
              begin
                   ANode^.Previous^.Next := ANode^.next;     {Move pointers...}
                   ANode^.Next^.Previous := ANode^.Previous;
                   Dispose(ANode);          {Dispose of node}
              end;
              L.Size := L.Size-1;           {Note new list size}
         end;
    end;

    end.

[Back to POINTERS SWAG index] [Back to Main SWAG index] [Original]