Index



Creating a sorted linked list
Popping items off the stack and
using recursion to destroy a linked list

The following unit demonstrates the creation of a sorted linked list, inserting items onto a sorted link list, popping items off the stack, and destroying a linked list.  integers will be used as the 'key' value for sorting the list, and a string is included as a the second element in the record for the purposes of demonstrating how to fill in a record field once the key value has been properly inserted into the list.  The items to be inserted (or popped) are entered into an edit box and the resulting stack is printed out on a memo.

You can download the unit as a text file by right clicking on the following link ­>unit_sorted_linked_list_insert_pop_dispose.txt

A linked list is a linear data structure consisting of nodes (records) each containing a pointer which points to the next element in the list.  For the purposes of this demo the record (described in the type declaration section has the following structure.

        | c:integer (the sort key) | s:string (a record field) | nextlink:link |

type
   link=^node;
   node=record C:integer; s:string; nextlink:link end;

Two global pointer variables are declared, one a pointer which is the head (or beginning of the linked list structure) and another ('linkpoint')  is used repeatedly to create a new record when a new item is being inserted into the list.

var
 Form1: TForm1;
 head, linkpoint:link;

The list is initialized in the 'FormCreate' section of the code.  (Click on the form, and then choose 'Events' on the property menu, and then double click on the 'FormCreate' event to enter the code into the editor).  Because this is going to be a sorted linked list, the value pointed to by the head must be the lowest value in the linked list.  For this example the head is initialized to ­1 and we then assume that every element on the list will be a valid integer value greater than or equal to zero.  (Note that the code below does not do any error checking for invalid integers.  Enter valid integers to avoid crashing the program.)  

Using the 'New' procedure creates a new record of the type pointed to by a link (as described in the type declaration) and 'head' (a variable of the type 'link') is set to point to this newly created record structure.  The key value is initialized to ­1, the lowest value that can be entered into the sorted linked list.  The pointer 'nextlink' always points to the next element in the sequential list, and when the structure is initialized it is always set to 'nil' (it is pointing at nothing at the moment, until a new record is created and inserted into the list).

procedure TForm1.FormCreate(Sender: TObject);
begin
new(head); head^.C:=­1; head^.nextlink:=nil;
end;

When a valid integer has been typed into Edit1 (and an optional string value into Edit2) and the InsertButton is pressed, the value of the 'head' pointer of the list is passed to a function that inserts the item in the correct position so as to maintain a sorted linked list.  The function returns a pointer of type link that can then be used to correctly fill in the record fields of the newly created element in the link list structure.  As the code moves along the linked list it keeps track of the previous link visited in a variable called 'previous'.  What we are looking for is the first element on the list that is greater than the value of the key we wish to insert (or the end of the list, signalled by a null pointer, whichever comes first.)  When we locate an element greater than the insertion key, the nextlink field of the newly created node will be set equal to the nextlink pointer of the previous node, and then the nextlink pointer of the previous node will be set to point to the newly created record, and the record will have been inserted into the linked list, properly sorted by its key value.

As an example consider a linked list consisting of the following key values into which we want to insert the value '11'.

| ­1 | ­> | 2 | ­> | 10 | ­> | 12 | ­>nil

In this case '11' must be inserted between '10' and '12' for the linked list to be properly sorted at creation time.  The function scans the list until it finds a key value greater than '11', in this case the value of '12'.  'Previous' would in this case be the pointer to the record holding the value '10'.  Now the 'nextlink' pointer of the record holding the '10' key value is pointing to '12', so after using New to create a new record for the '11' key, we then set the nextlink field of the '11' record to be equal to the nextlink field of the '10' record, which is already pointing to '12'.  Having done this swap we have both '10' and '11' pointing to '12' with '11' more or less 'hanging in space' (nothing is yet pointing at '11' in the list).  To complete the insertion we set the nextlink field of the '10' record to point to '11' and '11' is now properly inserted into the sorted linked list.

| ­1 | ­> | 2 | ­> | 10 | ­> | 12 | ­>nil

                  | 11 | ­> | 12 |        (set the nextlink of '11' equal to nextlink of 10)

                                          (both are now pointing at 12)

(set the nextlink pointer of 10 to point to 11 to finish inserting the value 11 into the sorted linked list)

| ­1 | ­> | 2 | ­> | 10 | ­> | 11 | ­> | 12 | ­>nil

The code to accomplish this is shown below.  Note that in this implementation a boolean variable 'found' is used as a control in the loop (it becomes true when a value greater than the key is located, in the example above, where we inserted 11, when 12 is encountered on the linked list, found becomes true, for 'cnew=11' is less than 12).  Intuitively I understood that the code could be implemented simply by using a boolean (true or false) variable, but at the same time I believe that the same thing could be accomplished without the use of this control variable.  Consider the following code to be just one way of implementing an insertion into a linked list.  If the value in the list is still less than the value of the insertion key then we crawl along the linked list by setting the 'head' variable equal to the 'nextlink' pointer of the record.  Note that 'head' in this code is a separate head variable from the global variable declared previously (we would not want to be changing the value of our global head pointer or we would lose track of the beginning of the linked list.)  This 'head' variable is declared in the function heading (and does not use the 'var' keyword, which would indicate that we were referencing the global head variable, and not a new variable local in scope to the routine also called head) and so a  variable named 'head' will be temporarily created while the function is active, and it is this temporary head variable that will be changed as we crawl along the list, and not the permanent global head variable.  (If this is confusing, give the variable head in the insert code a different name­but as I mentioned, it makes no real difference.)  If the <= statement is included in the comparison, duplicate key insertion will not generate an error (otherwise it will). If the insertion of duplicate keys is going to be a problem then a function returning a boolean variable could be written that crawls along the list until it reaches a value greater than the insertion key, returning true only if the insertion key is already found, and raising an error message rejecting the input.


function TForm1.SortedLinkedListInsert(cnew:integer; head:link):link;
var Previous:link;  found:boolean;
begin
    found:=false;   Previous:=nil;
    repeat
          If cnew <= head^.C then found:=true;  { <= allows insertion of duplicate keys}
          If (cnew > head^.C)  then begin
             Previous:=Head;
             head:=head^.nextlink;
          end;
    until (found) or (head=nil);
    new(linkpoint); {create a new record}
    linkpoint^.C := cnew;  {insert new key value, '11' in example above}
    Linkpoint^.nextlink:=Previous^.nextlink;  {set '11' to nextlink of '10' which is ­> 12}
    Previous^.nextlink:=linkpoint;  {now set '10' to point to '11'}
    Result:=Linkpoint;  {return the pointer to '11'}
end;

You can also implement the code to reject duplicates as demonstrated in the following text file ... sorted_linked_list_insert_no_duplicates.txt

If you run the code with the memo included you can watch the elements being added into the linked list in properly sorted form.

A linked list can be thought of as a type of 'stack', and we may wish to remove an item from the list (or 'pop' it off the stack).  When the pop button is clicked the integer value of the key of the record to be popped off the stack is passed to the procedure PopSortedStack.  Two temporary pointers of type link are declared, and one of them 'temp' is initialized to head so that is pointing to the bottom of the linked list (note that this time 'head' is not declared in the procedure header and we are referencing the global permanent, unchangeable 'head' pointer of the linked list).  Each record has a pointer 'nextlink' which is set to point to the next record in the list.  Let us assume that we have the following linked list and we wish to pop the value 10 and remove it from the list.

| ­1 | ­> | 2 | ­> | 10 | ­> | 12 | ­>nil

Now what we want in the end is to have 10 removed (popped) from the list, and we want the nextlink pointer of the '2' record to be pointing to 12.  Now we begin by pointing to '­1' which is the value of the head pointer.  Now the 'nextlink' pointer of the '­1' record is pointing to a record holding the value '2'.  So while we are pointing at the '­1' record we can look ahead to see if the next record holds the value '10', the key value of the record we want to pop.  The syntax for 'peeking ahead' would look like this (temp is set equal to the head pointer in this procedure).  temp^.nextlink^.c   In plain English we can translate this code as the record the temp pointer is pointing to (­1) has a 'nextlink' field which is pointing to a record which has a key integer (c) which in the first case contains the value '2'.  This is not equal to 'cpop', the value we want to remove, which in this example is '10' so we crawl up the list one node by setting temp equal to the value of the nextlink pointer of the '­1' record it is pointing to, so that in the next repeat of the loop, we are now pointing at the '2' record.  The code to crawl up a node would be temp:=temp^.nextlink  which means that we set temp equal to value of the nextlink field of the record that temp itself is pointing to.  We are now pointing at the '2' record and we want to peek ahead and see if 'cpop' (10) is the next record (temp^.nextlink^.c) which in this example it is, so we are pointing at the two record, and the nextlink record of the '2' record is pointing at '10', which is equal to 'cpop' making this record the one to remove from the list.

To remove '10' we need to set the '2' record to point to '12' and then we can use the 'Dispose' procedure to destroy the 10 record, and it has then been removed and popped off the list.  To do this we need to use a second temporary pointer (temp2) to hold the value of the '10' records nextlink pointer which is pointing to 12.  We can then use the 'nextlink' pointer of the '2' record to destroy the '10' record, and then set the value of the nextlink pointer of the '2' record equal to 'temp2' so that '2' now points to '12', and the '10' record has been properly disposed of, freeing its memory in the process.  

So then temp is pointing to the '2' record and '10' is pointing to '12' so '2' needs to be pointing to '12' after '10' has been popped.  To set temp2 to point to '12' we use the code temp2:=temp^.nextlink^.nextlink  ...  In plain English this means that temp is pointing to the '2' record which has a nextlink field which is pointing to the '10' record and this record also has a next link field and we will set temp2 equal to the pointer value in this field (so that temp2 points to 12, the value following 10).  We dispose of '10' by using dispose(temp^.nextlink) (the nextlink of the two record points to 10).  Finally we finish the pop by setting the nextlink of the '2' record to point to the twelve record (which is temporarily pointed at by temp2, as described above) temp^.nextlink:=temp2.

This all might seem a little confusing the first time you look at it, but if you understand pointer syntax, it is pretty straightforward...

cpop=10 ­ remove (or pop) the '10' record

| ­1 | ­> | 2 | ­> | 10 | ­> | 12 | ­>nil    (temp=nextlink pointer of '­1')

     temp^.nextlink^.c=10  (the nextlink pointer of '­1' points to '2'

                                and the nextlink pointer of '2' points to c=10)

| ­1 | ­> | 2 | ­> | 10 | ­> | 12 | ­>nil

      temp2:=temp^.nextlink^.nextlink  (the nextlink pointer of '­1' points to '2'

                                        and the nextlink pointer of 2 points to 10

                                        and the pointer value of the 10 record is pointing

                                        to '12')

        dispose(temp^.nextlink)         (temp=nextlink pointer of '­1' which is

                                        pointing to '2' and the nextlink pointer of

                                        '2' points to 10 which is the record we want to

                                        dispose of (or pop)

and finally '­1' is pointing to 2 which has a nextlink pointer which is still pointing to 10, which no longer exists, and must now point to 12, the value of the pointer being stored previously in temp2 so  temp:=temp^.nextlink

The code follows...

Procedure TForm1.PopSortedStack(cpop:integer);
var temp, temp2:link;
begin
temp:=head;
if temp^.nextlink<>nil then begin
  while temp^.nextlink^.C<>cpop do temp:=temp^.nextlink;
  temp2:=temp^.nextlink^.nextlink;
  dispose(temp^.nextlink); temp^.nextlink:=temp2;
end;

{the following code is for visual testing of the code above}

temp2:=head;  Memo1.clear;
while temp2<>nil do begin
Memo1.Lines.Append(InttoStr(temp2^.C));
temp2:=temp2^.nextlink;
end;
end;

Rather than popping a single value off the stack we might want to destroy the entire linked list (except for the head).   Destroying a linked list lends itself well to a recursive procedural call (a procedure that calls itself over and over again).

When a procedure or function call returns the code always jumps to the next line to resume execution.  For example consider the following code...

Dumpit(variable);

x:=x+1;

The code calls a procedure 'Dumpit' passing it some variable and the program execution jumps to the Dumpit code.  On return execution drops to the next line and 'x' is incremented by 1.  This is pretty straightforward.  Now let us suppose that Dumpit is a recursive procedure.  The code within the Dumpit procedure would include a line calling itself  ­ Dumpit(variable) ­ wrapped around some kind of conditional statement (an if or while not nil for example) so the program would not forever be locked into a Dumpit procedure that called itself forever (or until your computer ran out of memory and crashed).  While everyone is familiar with procedures that call other procedures, procedures can also call themselves, and thus are recursive.  Destroying a linked list works very well as a recursive procedure.  The code is as follows.  (Note that the first line 'if ptr<>nil' is only used so that if nothing is on the stack and someone presses the destroy button, the program will not crash on a pointer error in the next line of code, since in that case no 'nextlink' field would exist since ptr is nil and is not pointing to a record, after all.)


procedure TForm1.DestroyStack(ptr:link);
begin
if ptr<>nil then begin
  if ptr^.nextlink<>nil then DestroyStack(ptr^.nextlink);
  dispose(ptr);
end;
end;

The procedure crawls up the linked list, passing as a value the nextlink field of the pointer (ptr).  When the destroy button is clicked the DestroyStack procedure is called for the first time, being passed the pointer value head^.nextlink  (so in the example above we are passing it the pointer pointing to '2' and not head itself which is pointing to '­1', for we want to destroy the stack, but not the head itself, which will remain intact).  As long as the 'nextlink' field pointed to by the pointer is not 'nil' (the end of the list) the Procedure calls itself again and again.  Consider the following list.

| ­1 | ­> | 2 | ­> | 10 | ­> | 12 | ­>nil

We enter DestroyStack pointing to '2'.  Now the nextpointer of '12' is pointing to nil so when the code is passed the next pointer of the '10' record (which points to 12) the 'if' statement is no longer true for the nextlink field of the '12' record is nil.  This last statement does not execute, the procedure calls itself no more, and instead execution drops to the next line.  We are pointing at '12' (the value of the 'c' field pointed at by the nextlink pointer of the '10' record) so when we call dispose(ptr) we destroy the twelve record and all associated fields.  The procedure exits.  However we have a bunch of recursive procedure calls stacked up that have not yet returned, so they begin to return.  The nextlink pointer of the '2' record was the one that called up the procedure for the '10' record which destroyed the '12'.  Now it returns from its recursive function call, drops down to the dispose(ptr) line and destroys the '10' record.  Finally the initial value (the nextlink pointer of the ­1, or head record) returns from its recursive call and drops down to the nextline of code and destoys the '2' record.  This was the initial call to DestroyStack so it now exits and returns to the DestroyButton code and to tidy things up we now set head^.nextlink:=nil (remember that it is still pointing to '2' which has been destroyed and no longer exists).

The code for the complete unit is in the following text file : unit_sorted_linked_list_insert_pop_dispose.txt

Related pages:

Disposing of a linked list (recursive) ... using an iterative procedure might be a better idea for really large lists.

Implementing a LIFO stack using a linked list

Using an array to index and quickly search large linked lists - using the divide and conquer strategy that people use when looking up things in phone books. Even very large lists can be quickly searched using this type of strategy.
Index       Home




A Unified Field Theory

 failed_gravity_theory.gif - 10361 Bytes



The Unified Field Theory
is also available as a zip file -> unified.zip

Introduction :The Pioneer Effect and the New Physics. A brief description of the new physics required to explain the 'Pioneer Effect', which is the constant deceleration of space craft as they fly through space.




Principles of Evolution: A Study in the Evolution of Bedbugs


A couple of years ago my bedroom was invaded by bedbugs. There were two variant genetic lines. One type of bedbug was an enlongated, thin, tubular insect, and the second genetic line was a flat, perfectly circular insect. The result of the cross breeding of these two genetically distinct variants was the production of a bedbug with charcteristics of both, an enlongated, flat bedbug with a central bulge (such that the shape of the bedbug was somewhere between 'long' and 'circular'). The long skinny bedbugs were such strange and unfamiliar looking insects that at first I did not recognize them as being bedbugs, and considered them to be a seperate species of insect. However, as the photographs of bedbugs above indicate, enlongated and skinny bedbugs are not uncommon, and the photographs also show the variants that are produced by genetic combinations that result in an insect somewhere in between 'circular' and 'enlongated'.

Therefore it is my hypothesis that evolution occurs by means of the transfer of dominate genes, with the production of such dominant genes being the product of 'biological algorithms', a genetic software program that brings physical characteristics into harmony with behavior, such that when behavior changes, and a conflict then exists, this acts as a trigger and causes the release of dominant genes. The result is rapid evolution of species. The bedbug is a relatively new insect, not the product of millions of years of evolution but rather an insect that is evolving in real time. The newly emerging dominant form of the insect is the flat, round ciruclar insect, well adapted to living in human bedrooms (it is flat, rather than tubular, thus allowing it to hide in the smallest cracks, living a stealthy lifestyle, and it is round, which gives the insect a maximum storage capacity such that it must endanger itself only a few times a month by emerging to feed.

Other examples of rapid evolution include the development of long legs in an invasive species of toad in Australia. As the toads move into the mountainous regions of Australia, and their behvaior changes, making them 'climbing toads', over the course of just a couple of decades the toads in the highlands have grown long legs specially adapted to climbing. It is worth noting here that the toads are poisonous, and are a successful invasive species because they have no natural predators in Australia, and so it would not be the case that the toads with long legs were 'the fittest survivors', because all the toads are survivors, and therefore predation does not explain the rapid emergence and spread of such well adapted, long legged toads. Once again we see evidence for the existence of biological algorithms and the rapid spread of dominant genes through a population, which once introduced proceed to overwhelm the older genes which are being replaced (making toad long legged and a bed bug round and flat).


A Theological Experiment

My interest in pursuing the Unified Field Theory is spurred on by my need to discover the theoretical explanation of a new form of propulsion (as explained on this page: Why the Unified Field Theory?). The experiment involving the bedbugs came out of nowhere.

I also believe that it is possible to justify theological propositions using experimental methods. If a thing is an objective truth then it can be verified and proven true by means of experimentation. Such a theological proposition is of more value than a ‘divine revelation’, since such revelations depend upon nothing more than establishing authority figures which requires the creation of artificial hierarchies, for the only reason why I might be encouraged to believe an authority figure who orders me to believe unsubstantiated opinions is if I could somehow be convinced that this authority possessed a mind that was somehow superior to mine, and thus was fit to express opinions as though opinions were unquestionable facts and thus worthy of being elevated to the status of absolute dogma.

There is a self evident human inequality which is visibly apparent. Some people are ‘beautiful’ and thus are the true elite on this planet, and some people are not. It is this sexual inequality and the degeneration that follows upon beauty that is the true driving force behind all the evil that happens on earth. The need for ruthless oppression and the pursuit of wealth and the consequent creation of suffering and poverty which must follow upon this practice is for the purpose of creating an artificial alpha elite.

The true elites are the young and the beautiful. The artificial elite are the rich and the wealthy. The elite aging rich artificial alpha male has no good looks, for he is physically degenerate, but he will be found escorting beauty because he has a beautiful wallet. If he loses his wallet he will be found at home with all the other unattractive aged beta males sitting in a rocking chair watching reruns of Bonanza. No money, no sex. It is for this reason that the alpha males are found to be so ruthless and so violent in pursuit of their goal. The alpha male has fallen. The beta male has arisen and now the whole planet is full of ruinous destruction for it.

We see in religion a confused and contradictory reaction to this reality. On the one hand religion preaches a sexless heaven where castration and the clitorectomy create ‘pure spirits’. Muslims throw women under sacks. On the other hand religion supports hierarchy and is the prop of the elite alpha male. It is for this reason that religion is incoherent when it comes to speaking about sex.

Now we see this same principle at work in all of nature. Guppies dance and show off their colorful tails and the guppy who dances with the most colorful tail is the sexually successful guppy. Therefore it is the doctrine of the ruthless oppressor which teaches that the solution to human sexual violence is to be found in castration and the creation of pure ghosts. This would be equivalent to damning an aardvark for having the ‘sinful aardvark nature’ or prosecuting an anteater for the high crime of ‘ant genocide’.

Therefore it was my theological hypothesis that the correct solution to this problem is to give every guppy a beautiful colorful tail. I compare this solution to the classic religious solution which is to cut off every tail since having a tail is ‘sinful’. If having a tail is sinful then God must be sinful for no human being has any choice in deciding whether or not they would be born with a colorful tail, or whether they would not.

When I was young I was a beautiful guppy with a lovely tail. So everyone seemed to think. I am older now. My nose became very badly sunburned and destroyed. It seemed good to me to test my hypothesis by using these ‘biological algorithms’ to correct this problem. I healed half my nose as you can see by the line separating the still very dark patch on the side in the photograph below.





I documented my experiment on these pages. one two t hree four fi ve six


I have confirmed to my own satisfaction that my theological proposition is correct and that religious dogma is erroneous, being based as it was upon nothing more than ‘divine revelation’ which is just a form of opinionated speculation. For the time being I am not continuing this experiment, for I must wait until the weather on this planet improves, and the dark clouds of ruthless oppression break letting a little sun shine come through so that I can show the world the truth about God, by showing people how God goes about giving an old guppy back his beautiful colorful tail.


Until then I will have to sit on the sidelines, while all my scientific breakthroughs are deliberately ignored, while I wonder to myself what ever in the world could be wrong with the human race, because what this all will prove at the end of it all is that there definitely was something wrong with the people on this planet.