Pascal Programming Lesson #14 - Linked Lists

A linked list is like an array except that the amount of elements in a linked list can change unlike an array. A linked list uses pointers to point to the next or previous element.

Single linked lists

There are 2 types of single linked lists which are called queues and stacks.

Queues

A queue is like standing in a queue at a shop. The first person that joins a queue is the first person to be served. You must always join at the back of a queue because if you join at the front the other people will be angry. This is called FIFO(First In First Out).

Item 1 --> Item 2 --> Item 3 --> (Until the last item)

Each item of a linked list is a record which has the data and a pointer to the next or previous item. Here is an example of how to declare the record for a queue and a pointer to a queue record as well as the variables needed:




program queue;

type
   pQueue = ^tqueue;
   tQueue = record
      data: integer;
      next: pQueue;
   end;

var
   head, last, cur: pQueue;

begin
end.

We will now make 3 procedures. The first procedure will add items to the list, the second will view the list and the third will free the memory used by the queue. Before we make the procedures lets first take a look at the main program.




begin
   head := nil; {Set head to nil because there are no items in the queue}
   add(1) {Add 1 to the queue using the add procedure};
   add(2);
   add(3);
   view; {View all items in the queue}
   destroy; {Free the memory used by the queue}
end.

The add procedure will take an integer as a parameter and add that integer to the end of the queue.




procedure add(i: integer);
begin
   new(cur); {Create new queue item}
   cur^.data := i; {Set the value of the queue item to i}
   cur^.next := nil; {Set the next item in the queue to nil because it doesn't exist}
   if head = nil then {If there is no head of the queue then}
      head := cur {Current is the new head because it is the first item being added to the list}
   else
      last^.next := cur; {Set the previous last item to current because it is the new last item in the queue}
   last := cur; {Make the current item the last item in the queue}
end;

The view procedure uses a loop to display the data from the first item to the last item of the queue.




procedure view;
begin
   cur := head; {Set current to the beginning of the queue}
   while cur <> nil do {While there is a current item}
      begin
         writeln(cur^.data); {Display current item}
         cur := cur^.next; {Set current to the next item in the queue}
      end;
end;

The destroy procedure will free the memory that was used by the queue.




procedure destroy;
begin
   cur := head; {Set current to the beginning of the queue}
   while cur <> nil do {While there is a item in the queue}
      begin
         cur := cur^.next; {Store the next item in current}
         dispose(head); {Free memory used by head}
         head := cur; {Set the new head of the queue to the current item}
      end;
end;

Stacks

To understand a stack you must think about a stack of plates. You can add a plate to the top of the stack and take one off the top but you can't add or take away a plate from the bottom without all the plates falling. This is called LIFO(Last In First Out).

Item 1 <-- Item 2 <-- Item 3 <-- (Until the last item)

When you declare the record for a stack item you must use previous instead of next. Here is an example.




program stack;

type
   pStack = ^tStack;
   tStack = record
      data: integer;
      prev: pStack;
   end;

var
   last, cur: pStack;

begin
   last := nil;
   add(3);
   add(2);
   add(1);
   view;
   destroy;
end.

You will see that the numbers are added from 3 to 1 with a stack instead of 1 to 3. This is because things must come off the top of the stack instead of from the head of a queue.

The add procedure adds the item after the last item on the stack.




procedure add(i: integer);
begin
   new(cur); {Create new stack item}
   cur^.data := i; {Set item value to the parameter value}
   cur^.prev := last; {Set the previous item to the last item in the stack}
   last := cur; {Make the current item the new last item}
end;

The view and destroy procedures are almost the same as with a queue so they will not need to be explained.




procedure view;
begin
   cur := last;
   while cur <> nil do
      begin
         writeln(cur^.data);
         cur := cur^.prev;
      end;
end;

procedure destroy;
begin
   while last <> nil do
      begin
         cur := last^.prev;
         dispose(last);
         last := cur;
      end;
end;