ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng)/ProfitPress-MegaCDROM2.B6I/PROG/PASCAL/PNL002.ZIP/LINKLIST.PAS

Pascal/Delphi Source File | 1990-05-17 | 7.2 KB | 226 lines

unit LinkList;

{ This is the linked list unit accompanying The Pascal NewsLetter, Issue #2.
  This unit is copyrighted by Peter Davis.
  It may be freely distributed in un-modified form, or modified for use in
  your own programs. Programs using any modified or unmodified form of this
  unit must include a run-time and source visible recognition of the author,
  Peter Davis.
}

{ The DataType used is integer, but may be changed to whatever data type
  that you want.
}

interface


type
  DataType = integer;    { Change this data-type to whatever you want  }

  Data_Ptr = ^Data_Rec;  { Pointer to our data records                 }

  Data_Rec = record      { Our Data Record format                      }
    OurData  : DataType;
    Next_Rec : Data_Ptr;
  end;


procedure Init_List(var Head : Data_Ptr);
procedure Insert_Begin(var Head : Data_Ptr; Data_Value : DataType);
procedure Insert_End(var Head : Data_Ptr; Data_Value : DataType);
procedure Insert_In_Order(var Head : Data_Ptr; Data_Value : DataType);
function Pop_First(var Head : Data_Ptr) : DataType;
function Pop_Last(var Head : Data_Ptr) : DataType;
procedure Delete_Here(var Head : Data_Ptr; Our_Rec : Data_Ptr);



implementation

procedure Init_List(var Head : Data_Ptr);

begin
  Head := nil;
end;

procedure Insert_Begin(var Head : Data_Ptr; Data_Value : DataType);

{ This procedure will insert a link and value into the
  beginning of a linked list.                             }

var
  Temp : Data_Ptr;                { Temporary  Pointer.            }

begin
  new(Temp);                      { Allocate our space in memory.  }
  Temp^.Next_Rec := Head;         { Point to existing list.        }
  Head:= Temp;                    { Move head to new data item.    }
  Head^.OurData := Data_Value;    { Insert Data_Value.             }
end;

procedure Insert_End(var Head : Data_Ptr; Data_Value : DataType);

{ This procedure will insert a link and value into the
  end of the linked list.                                 }

var
  Temp1,             { This is where we're going to put new data }
  Temp2 : Data_Ptr;  { This is to move through the list.         }

begin
  new(Temp1);
  Temp2 := Head;
  if Head=nil then
    begin
      Head := Temp1;                  { If list is empty, insert first   }
      Head^.OurData := Data_Value;    { and only record. Add value and   }
      Head^.Next_Rec := nil;          { Then put nil in Next_Rec pointer }
    end
  else
    begin
      { Go to the end of the list. Since Head is a variable parameter,
        we can't move it through the list without losing pointer to the
        beginning of the list. To fix this, we use a third variable:
        Temp2.
      }
      while Temp2^.Next_Rec <> nil do    { Find the end of the list. }
        Temp2 := Temp2^.Next_Rec;

      Temp2^.Next_Rec := Temp1;          { Insert as last record.    }
      Temp1^.Next_Rec := nil;            { Put in nil to signify end }
      Temp1^.OurData := Data_Value;      { And, insert the data      }
    end;
end;

procedure Insert_In_Order(var Head : Data_Ptr; Data_Value : DataType);

{ This procedure will search through an ordered linked list, find
  out where the data belongs, and insert it into the list.        }

var
  Current,              { Where we are in the list               }
  Next     : Data_Ptr;  { This is what we insert our data into.  }

begin
  New(Next);
  Current := Head;      { Start at the top of the list.          }

  if Head = Nil then
    begin
      Head:= Next;
      Head^.OurData := Data_Value;
      Head^.Next_Rec := Nil;
    end
  else
  { Check to see if it comes before the first item in the list   }
  if Data_Value < Current^.OurData then
    begin
      Next^.Next_Rec := Head;      { Make the current first come after Next }
      Head := Next;                { This is our new head of the list       }
      Head^.OurData := Data_Value; { And insert our data value.             }
    end
  else
    begin
      { Here we need to go through the list, but always looking one step
        ahead of where we are, so we can maintain the links. The method
        we'll use here is: looking at Current^.Next_Rec^.OurData
        A way to explain that in english is "what is the data pointed to
        by pointer Next_Rec, in the record pointed to by pointer
        current." You may need to run that through your head a few times
        before it clicks, but hearing it in English might make it a bit
        easier for some people to understand.                            }

      while (Data_Value >= Current^.Next_Rec^.OurData) and
            (Current^.Next_Rec <> nil) do
        Current := Current^.Next_Rec;
      Next^.OurData := Data_Value;
      Next^.Next_Rec := Current^.Next_Rec;
      Current^.Next_Rec := Next;
    end;
end;

function Pop_First(var Head : Data_Ptr) : DataType;

{ Pops the first item off the list and returns the value to the caller. }

var
  Old_Head : Data_Ptr;

begin
  If Head <> nil then   { Is list empty? }
    begin
      Old_Head := Head;
      Pop_First := Head^.OurData;  { Nope, so Return the value }
      Head := Head^.Next_Rec;      { And increment head.       }
      Dispose(Old_Head);           { Get rid of the old head.  }
    end
  else
    begin
      writeln('Error: Tried to pop an empty stack!');
      halt(1);
    end;
end;


function Pop_Last(var Head : Data_Ptr) : DataType;

{ This function pops the last item off the list and returns the
  value of DataType to the caller.                              }

var
  Temp : Data_Ptr;

begin
  Temp := Head;       { Start at the beginning of the list. }
  if head = nil then  { Is the list empty? }
    begin
      writeln('Error: Tried to pop an empty stack!');
      halt(1);
    end
  else
  if head^.Next_Rec = Nil then { If there is only one item in list, }
    begin
      Pop_Last := Head^.OurData;  { Return the value               }
      Dispose(Head);              { Return the memory to the heap. }
      Head := Nil;                { And make list empty.           }
    end
  else
    begin
      while Temp^.Next_Rec^.Next_Rec <> nil do  { Otherwise, find the end }
        Temp := Temp^.Next_rec;
      Pop_Last := Temp^.Next_Rec^.OurData;  { Return the value          }
      Dispose(Temp^.Next_Rec);              { Return the memory to heap }
      Temp^.Next_Rec := nil;                { And make new end of list. }
    end;
end;


procedure Delete_Here(var Head : Data_Ptr; Our_Rec : Data_Ptr);


{ Deletes the node Our_Rec from the list starting at Head. The procedure
  does check for an empty list, but it assumes that Our_Rec IS in the list.
}

var
  Current : Data_Ptr;  { Used to move through the list. }

begin
  Current := Head;
  if Current = nil then   { Is the list empty? }
    begin
      writeln('Error: Cant delete from an empty stack.');
      halt(1);
    end
  else
    begin   { Go through list until we find the one to delete. }
      while Current^.Next_Rec <> Our_Rec do
        Current := Current^.Next_Rec;
      Current ^.Next_Rec := Our_Rec^.Next_Rec; { Point around old link. }
      Dispose(Our_Rec);                        { Get rid of the link..  }
    end;
end;


end.