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

    {
    ³ I'm trying to understand the rudiments of linked lists

    ³ 4) What are common uses for linked lists?  Is any one particular form
    ³    (oneway, circular etc ) preferred or used over any other form?

    One use is to maintain queues.  New people, requests, or jobs come in at
    the end of the line (or break in with priority), but once the head of
    the line has been serviced, there is no need to maintain its location in
    the queue.  I wrote the following last semester:
    ---------------------------------------------------------------
    Purpose:
      Maintains a queue of jobs and priorities of those jobs in a linked list.
      The user will be prompted for job number and priority and can list the
      queue, remove a job from the front of the queue (as if it ran), and stop
      the program.  A count of jobs outstanding at the end will be displayed. }

    type
      PriRange = 0 .. 9;
      JobPnt   = ^JobNode;
      Jobnode  = RECORD
        Numb     : integer;
        Priority : PriRange;
        Link     : JobPnt
      END;

    procedure addrec(var Start : JobPnt; comprec : Jobnode);
    var
      curr,
      next,
      this  : JobPnt;
      found : boolean;
    begin
      new(this);
      this^.Numb := comprec.Numb;
      this^.Priority := comprec.Priority;
      if Start = NIL then
      begin
        Start := this;   {Points to node just built}
        Start^.Link := NIL; {Is end of list}
      end
      else    {Chain exists, find a place to insert it}
      if comprec.Priority > Start^.Priority then
      begin
        this^.Link := Start;     {Prep for a new beg of chain}
        Start := this
      end {Condition for insert at beg of chain}
      else
      begin {Begin loop to insert after beg of chain}
        found := false;  {To initialize}
        curr  := start;
        while not found do
        begin
          next := curr^.link;
          if (next = NIL) or (comprec.Priority > next^.Priority) then
            found := true;
            if not found then
              curr:= next  {another iteration needed}
        end;
        {Have found this^ goes after curr^ and before next^}
        this^.Link := next; {Chain to end (even if NIL)}
        curr^.Link := this;  {Insertion complete}
      end;
    end;

    procedure remove(Var Start : JobPnt);
    var
      hold : JobPnt;
    begin
      if Start = NIL then
        Writeln('Cannot remove from empty queue', chr(7))
      else
      begin
        hold := Start^.Link; {Save 1st node of new chain}
        dispose(Start);     {Delete org from chain}
        Start := hold;       {Reset to new next job}
      end;
    end;

    procedure list(Start : JobPnt); {List all jobs in queue. "var" omitted}
    begin
      if Start = NIL then
        Writeln('No jobs in queue')
      else
      begin
        Writeln('Job No     Priority');
        Writeln;
        while Start <> NIL do
        begin
          Writeln('  ',Start^.Numb : 3, '          ', Start^.Priority);
          Start:=Start^.Link
        end;
        Writeln;
        Writeln('End of List');
      end;
    end;

    {Main Procedure starts here}
    var
      cntr  : integer;
      build : JobNode;
      work,
      Start : JobPnt;
      Achar : char;

    begin
      Start := NIL; {Empty at first}
      cntr  := 0;
      REPEAT
        Write('Enter (S)top, (R)emove, (L)ist, or A jobnumb priority to');
        Writeln(' add to queue');
        Read(Achar);

        CASE Achar of
          'A', 'a' :
          begin
            Read(build.Numb);
            REPEAT
              Readln(build.Priority);
              if (build.Priority < 0) or (build.priority > 9) then
                Write(chr(7), 'Priority between 0 and 9, try again ');
            UNTIL (build.Priority >= 0) and (build.Priority <= 9);
            addrec(Start, build);
          end;

          'R', 'r' :
          begin
            Readln;
            remove(Start);
          end;

          'L', 'l' :
          begin
            Readln;
            list(Start);
          end;

          'S', 's' : Readln; {Will wait until out of CASE loop}

          else
          begin
            Readln;
            Writeln('Invalid option',chr(7))
          end;
        end;

      UNTIL (Achar = 's') or (Achar = 'S');
      work := start;
      while work <> NIL do
      begin
        cntr := cntr + 1;
        work := work^.link
      end;
      Writeln('Number of jobs remaining in queue: ', cntr);
    end.

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