Linked List in Pascal

[Olsi009]

Hey guys,

I study computer science (1st year) and I have an exam after tomorrow but there's one exercise with the linked lists that is impossible for me.

Supposing that we have 2 created linked lists, let's create a third one that has the elements of the previous 2, but alternated.

Please help :)

[DimaYasny]

what's a linked list anyway? do you mean two arrays? example please

[Olsi009]

No not arrays, a linked list is a set of elements where one element shows the address of the next one and so on.

When you declare smth like this in TP7

Type 

student = ^pointer
  pointer = record
    name:string;
    age:integer
    next:student;
end;

Var
List1:Student;

You can create this way a linked list ( you need the body, of course).

this is a diagram that shows how nodes are linked.

1stStudent--|__|__|--|__|__|--|__|__|--|__|__|--nil

[DimaYasny]

never used those in TP7 :) sorry mate

it's a wonder they still teach TP anyway

[Duoas]

Geez, DimaYasny, if you have no clue what he's talking about at least Google it, instead of wasting his time with "what?".

Whenever you want to "zip" two lists (whether linked-lists or not) you'll need to keep a finger in each source list, and alternately copy elements to the new list. Something like

function zip( ls1, ls2: student ): student;
  // Zips two lists.
  // Either ls1 or ls2 may be nil.
  // If both are nil, the result will also be nil.
  // The new list is allocated with new().
  var
    results: student;  // the head of the new list
    current: student;  // the current elt of the new list

  function copy( elt: student ): student;
    // Adds a new node to the new list
    // and copies the specified elt to the new node.
    // Returns the node following elt.
    begin
    if current = nil
      then begin
           // create the first node in the new list
           current := new( student );
           results := current
           end
      else begin
           // add a node to the new list
           current^.next := new( student );
           current := current^.next
           end;
    // copy elt to the new node
    current^ := elt^;
    // return the next elt
    copy := elt^.next
    end;

  begin
  // no new nodes yet
  results := nil;
  current := nil;

  // So long as either source list has elements
  // we'll copy them to the new list, alternating
  // if possible
  while (ls1 <> nil) or (ls2 <> nil) do begin

    if ls1 <> nul then ls1 := copy( ls1 );
    if ls2 <> nul then ls2 := copy( ls2 )

    end;

  // There is no need to care about setting
  // current^.next to nil here, since that is
  // done when we copy the last element
  // of the source list(s).

  zip := results
  end;

You may want to take a moment to study this. It is actually a fairly elegant solution to the problem.

Obviously, the interleaving of the source lists is done in the loop in the body of the main function. If one list is longer than the other the remaining elements are not forgotten.

The copy subfunction takes care of all the messy details of allocating a new element in the new list: it deals with the special case of allocating the first element in the new list as well as the general case of just adding elements to the new list, and updates the 'current' node pointer as appropriate.

It also takes care of advancing the current pointer into the source list --whichever one that may be.

Since I don't know whether you are using Delphi or not this code works with standard Pascal (that is, I didn't use anything specific to Delphi or other modern dialects).

Hope this helps.

[DimaYasny]

Geez, DimaYasny, if you have no clue what he's talking about at least Google it, instead of wasting his time with "what?".

before you bash anyone over the head, take some time to consider the circumstance, ok?

I studied Pascal in 1994 and that was back in Israel, all teaching done in Hebrew. Terminologies were VERY different from the English ones. That's why I asked, because I was considering the possibility that the question just used terminology unfamiliar to me.

[Duoas]

Look, I didn't mean it caustically, OK? Consider the circumstances yourself: you are requiring the OP to do finding to answer your own questions about the material. Particularly when just a short moment of googling it yourself would have given you the information you needed. It is not the OP's fault if you are unfamiliar with the terminology. If you can't find his words listed anywhere, then it may be safe to ask for clarification. That's all.

[Olsi009]

Thank you for the solution Douas, I'll just make it fit to my program and run it :)
thanks again

[Duoas]

Wait, I thought you said this was to prepare for an exam?

I didn't post that code just to give you an answer. Your professor will recognize if you turn in homework with an unusually brilliant answer (brilliance comes with time --something new programmers haven't had a lot of).

Make sure you understand exactly what is going on and can justify why it does what it does if you do use it (or some variation of it). Otherwise your professor may mark you as having failed to learn something...

The important point (the non-brilliant, required part) is in the loop: each time through the loop two elements (one from each list) are added to the new list, thus creating the alternating effect. So long as at least one list has elements it continues.

As an exercise, see if you can modify it so that it terminates when either list exhausts (that is, so that it discards extra elements of the longer list). You'll have to change one thing (to know when to stop), and add one thing (to make sure the new list is terminated with a nil pointer).

Hope this helps.