program LinkedList;

uses crt;

type
  itemtype = char;   {Contents of List-the items}

  nodePtr = ^listnode;  {a pointer to a node of the list}

  listnode = record     {List Node Structure}
    itemData: itemtype; {the data part within the node}
    next: nodePtr;      {a pointer to point to the next item}
  end;

  list = record         {List Structure}
    frontPtr : nodePtr; {a pointer to point at the first node}
    num : integer;      {the number of items in the list}
    backPtr : nodePtr;  {a pointer to point at the last node}
  end;


{*****************************************
Procedure to Initialise a List
Pre: List not initialised
Post:List initialised with first position
     ready to accept the first item.
******************************************}
procedure init(var l:list);
  begin
    l.frontPtr:= nil;   {points at nothing}
    l.backPtr := nil;   {points at nothing}
    l.num:=0;           {no items in the list}
  end;










{*****************************************
Function to return True/False if list is full
Pre: List initialised
Post:List unchanged
******************************************}
function isFull(l:list): boolean;
begin
isFull:=false;  {can never be full}
end;












{*****************************************
Function to return True/False if list is empty
Pre: List initialised
Post:List unchanged
******************************************}
function isEmpty(l:list): boolean;
begin
if l.num=0
   then isEmpty:=TRUE
   else isEmpty:=FALSE;

   {isEmpty:=l.num=0;       {if the number of items is 0}
end;













{*****************************************
Function to return number of items in List
Pre: List initialised
Post:List unchanged
******************************************}
function itemNo(l:list): integer;
begin
itemNo:=l.num;  {that part of the list which stores number of items}
end;










{*****************************************
Procedure to Insert an item in the List
Pre: List initialised
Post:List has item inserted
******************************************}
procedure insert(var l:list;i:itemtype);
  var
     tempPtr : nodePtr;

  begin
    new(tempPtr);               {}
    tempPtr^.itemData:=i;       {}
    tempPtr^.next:=nil;         {}
    if (l.num=0)                        {if it is the first item}
       then l.frontPtr:=tempPtr         {then set the front pointer}
       else l.backPtr^.next:=tempPtr;   {else set the last node to at new node}
    l.backPtr:=tempPtr;         {move the back pointer to point at new node}
    l.num:=l.num+1;             {increment the number of items}
  end;




{*****************************************
Procedure to Insert an item at a specific position
Pre: List initialised
Post:List has item inserted at a specific position
******************************************}
procedure insertPosn(var l:list;i:itemtype;p:integer);
  var
     tempPtr : nodePtr;
     floatPtr: nodePtr;
     counter:integer;

  begin
  if ( (p>0) and (p<l.num+2) )
    then
        begin
            new(tempPtr);               {}
            tempPtr^.itemData:=i;       {}
            if (p>1)
               then
               begin
               counter:=1;            {counter to keep track of jumps}
               floatPtr:=l.frontPtr;  {scanning pointer to get to the previous node}
               while (counter+1 <> p) do
                begin
                 counter:=counter+1;
                 floatPtr:=floatPtr^.next;
                end;
               tempPtr^.next:=floatPtr^.next;{line4}
               floatPtr^.next:=tempPtr;      {line5}
               end
               else tempPtr^.next:=l.frontPtr;{pointer of new node -> front}

            l.num:=l.num+1;             {increment the number of items}
            if (p=1) then l.frontPtr:=tempPtr;
            if (p=l.num) then l.backPtr:=tempPtr;
        end;
    end;

{*****************************************
Procedure to Display contents of list
Pre: List initialised
Post:List unchanged
******************************************}
procedure displayList(l:list);
  var
     tempPtr : nodePtr;
  begin
  clrscr;
  tempPtr:=l.frontPtr;  {scanning pointer to get to the previous node}
  while (tempPtr <> nil) do
      begin
           writeln(tempPtr^.itemdata);
           tempPtr:=tempPtr^.next;
      end;
  end;










{*****************************************
               MAIN PROGRAM
******************************************}
Var
  TestList:list;

BEGIN
  init(TestList);

  insertPosn(TestList,'z',1);
  displayList(TestList);
  


  insert(TestList,'b');
  insert(TestList,'d');
  insert(TestList,'f');

  displayList(TestList);

  insertPosn(TestList,'a',1);
  displayList(TestList);
  insertPosn(TestList,'c',3);
  displayList(TestList);
  insertPosn(TestList,'e',5);
  displayList(TestList);
  insertPosn(TestList,'g',7);
  displayList(TestList);

  writeln('Number of items in list: ',itemNo(TestList));
END.