Inserting an element into a linked list

Question

This program adds an element to the end of a linked list of integers, which is previously keyed in by the user. This works fine on my computer, but I am wondering:

1. If there is a simpler way to do this (three procedures seems a lot for this)
2. If any of the code could potentially become problematic during future usage

program InserElement(input, output);
{Has the user type in integers and forms a linked list out of them,
then inserts an element at the end of that linked list and prints the
linked list with the added new element}

{$mode objfpc}{$H+}

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes;

type
  tRefList = ^tList;
  tList = record
             info : integer;
             next : tRefList
            end;
var
 RefBeginning: tRefList;
 RefEnd : tRefList;
 Number : integer;



   procedure CreateList(var outRefBeginning: tRefList; var OutRefEnd: tRefList);
   { Creates a linear list through user input }
  var
   RefNew : tRefList;

  begin
   writeln('Please key in natural numbers. Key in 0 once you are done. ');
   readln(Number);
   while Number <> 0 do
   begin
     new (RefNew);
     RefNew^.info := Number;
     RefNew^.next := nil;
     if outRefBeginning = nil then
      begin
      outRefBeginning := RefNew;
      OutRefEnd := RefNew;
      end
     else
     begin
       outRefEnd^.next := RefNew;
       outRefEnd := RefNew
     end;
     readln (Number)
   end; { while-loop }
  end; {CreateList}

procedure InsertElement(inNumber : integer; var outRefBeginning : tRefList; var outRefEnd : tRefList);
  { Inserts a new element at the end of the list. outRefBeginning points to the first
  element of that list, outRefEnd points to the last element of it. The Value of inNumber is
  assigned to the record component info of the new element}

  var
   RefNew : tRefList;

  begin
  { Create and initialise new element }
  new(RefNew);
  RefNew^.info := inNumber;
  RefNew^.next := nil;
  { Insert element at the end of the linear list }
  if outRefBeginning = nil then
     begin
     outRefBeginning := RefNew;
     outRefEnd := RefNew
     end
     else
         begin
           outRefEnd^.next := RefNew;
           outRefEnd := RefNew;
         end;
  end;{ InsertElement }

  procedure PrintList;
  { Prints all elements of the linked list }

  var
   RefNew : tRefList;

  begin
   RefNew := RefBeginning;
   while RefNew <>  nil do
   begin
     writeln (RefNew^.info);
     RefNew := RefNew^.next
   end;
  end;

begin
  RefBeginning := nil;
  RefEnd := nil;
  CreateList(RefBeginning, RefEnd);
  InsertElement(5,RefBeginning,RefEnd);
  PrintList;
  readln;
end.

Answer 1

Overall, this is a great start. It's easy to read and understand. Personally, I don't think that 3 procedures is a lot. You have 3 things you need to do: create the initial list, add an element to it, and print out the results. If you didn't have at least 3 procedures, I'd say you were doing something wrong. Anyway, here are some things that could be improved.

Naming

I found the naming a little confusing. Why is it a "ref" list? To what does it refer? (Or what does ref mean in this context if not "reference"?) I think that I would name the list node type a tNode instead of a tList, and I would name the thing that points to it a tList.

I notice also that some of your variable and argument names begin with lowercase letters and some with uppercase. While Pascal is not typically a case-sensitive language, it's generally considered good practice to be consistent. Often variable names start with a lowercase letter, and types start with an uppercase letter, but it's up to you. It just makes it easier to read when it's consistent.

Types

Better yet, if you're going to keep track of the head and tail separately, I would make another record type, like this:

type
    tNodePtr = ^tNode;
    tNode = record
        info : integer;
        next : tNodePtr;
    end;

    tList = record
        head : tNodePtr;
        tail : tNodePtr;
    end;

Now you can pass a single variable around instead of passing both the head and tail to each procedure. This makes it easier to read the code and less likely that a caller of one of the procedures will accidentally pass the wrong thing for one of the arguments.

Check Your Allocations

There are 2 places where you call new(). You don't ever check the result, though, to see if the allocation succeeded. You need to make sure that the memory was actually allocated before you start writing to it. Otherwise, you'll end up writing over some other data causing a hard-to-find bug, or writing to data you don't have access to and causing a crash.

Delete Stuff When You're Done With It

The other thing you need to do with memory that you allocate from the heap is delete it when you're no longer using it. In this case, that would be at the end of the program. I would write a procedure to delete the nodes in the list. Something like this (and I'm assuming you're using the types I recommended above):

procedure DeleteList(var list : tList)
    var
        nextNode : tNodePtr;
        currNode : tNodePtr;
    begin
        nextNode = list.head;
        currNode = list.head;
        while nextNode <> nil do
        begin
            nextNode = currNode^.next;
            delete(currNode);
            currNode = nextNode;
        end;
        list.head = nil;
        list.tail = nil;
    end;

(Note: It's been a few years since I've written Pascal, so forgive me if I've made any obvious mistakes here!)

Formatting

While this won't affect the running of your program, the formatting of the code can affect how easy it is to read and understand. I would suggest adopting a consistent indentation amount. I see that you sometimes use 1 space, sometimes 2. I would recommend always using 2 or more (my preference is 4, personally), as a single space is not as easy to distinguish as 2 or more.

Also, it looks like in CreateList() the if class has one type of indenting, and the else clause has a different one. I would be consistent about what level of indentation you use for the begin and end keywords.