INDEX


Using an array to index a linked list
Using a divide and conquer strategy
to do quick searches on long linked lists


     An array is a static structure, while linked lists are dynamic. If you have fewer items than the size of an array the array is wasting space, and you cannot put more items on an array than the size of the array. If you use a dynamic array you are not supposed to deference any elements in the array (pointers are out). A linked list consists of the items on the list plus a pointer to the next element on the list. Linked lists are dynamic and shrink and grow as the number of items on the list changes. These two data structures one inherently static and the other dynamic can be combined to do speedy searches of large numbers of elements.

     This example uses a sorted linked list which rejects duplicate entries. Follow the links at the bottom of the page for more pages on this site dealing with linked lists. The code has been recycled with the only difference being that in this example strings are the sort key rather than integers. The linked list is sorted as it is created, and is maintained in alphabetical order as new items are inserted, eliminating the need to create a linked list and then sort it later. The array is an array of pointers to elements on the linked list, and contains 702 pointers. Each letter of the alphabet has 27 entries on the array such as 'a aa ab ... az'. When a search is done it is a simple matter to look up the first two letters of the word and calculate the array position which contains a pointer to the element on the sorted linked list that begins with those two letters. A search can then be done from this point. This emulates the way people look up things in a phone book. First they jump to the letter and then to position of the second letter and start searching from there. This is a kind of divide and conquer strategy and allows humans to do speedy searches even in something as large as a phone book.

aindex.gif - 5882 Bytes


     The screen shot above shows the debugging and test interface for the code. The program is first loaded with lots of words to sort by reading plain text files and parsing the words in the file and inserting them onto a sorted linked list. This is just a way to get lots of words quickly onto a linked list. When button one is pushed an OpenDialog appears and when a text file is selected it is read in and parsed. The words are appended to a memo, partly as a debugging tool for the text parsing code, and also as some visual feedback that something is going on. As the words are read in they are sorted on the list and the alphabetical array index is updated.

debug.gif - 9744 Bytes


     When the list has been created and the index array has been updated the button at the bottom of the screen (Button3) prints out two debug text files, one of the array index and one of the sorted linked list contents. As you can see above the array index for 'ac' points to 'accept' and on the sorted linked list 'accept' is the first entry under 'ac'. Index position 12on the array corresponds to the two letters 'al' and 'Align' is the first word under 'al' followed by 'alive, all, along' etc. In order to find the first word under 'al' we need to get a pointer in the array of pointers that points to the first word starting with 'al' on the linked list for the search code to function properly, and by debugging based on these two text files it can be confirmed that both the sort code on the linked list is sorted properly, the words have been parsed correctly and the indexing code is working properly.

      This unit demos a way to use an indexing array to quickly find things on sorted linked list. When a search must be made a quick calculation is made based on the first two letters of the search word (don't use the search code (Button2) to search for one letter) and the result of this quick calculation is the position in the array of the pointer pointing to that particular section of the linked list (the array would point to 'be' if we were looking for Ben).

      Note that the read text procedure ignores punctuation so the word "wasn't" becomes two words - "wasn" and then the letter "t" is also recognized as a word - the code thinks that words start with a letter and end with anything other than a letter and has not been taught to recognize punctuation.

      At the same time each word is put onto a sorted linked list the array index is updated if Ben was pointed by the 'be' pointer of the array and Bean was input then Bean would become the new pointer in 'be' replacing Ben because Bean is less than Ben (when you do a search for 'be' entries you want to start at the lowest 'be' entry on the list).

      You can do a quick telephone book like look up for a word on the linked list by typing it into the edit box and hitting the search button (Button2). The search function calculates which page to flip to in the 'telephone book' (a pointer located at a certain numbered position on the static array) and then sends the pointer and the following pointer (the place to stop) to a quick search function. The search function would search from 'be' to 'bf' for any 'be' entry rather than starting from the beginning of the linked list or going right to the end of the sorted list and quickly either find the pointer to the entry and report back that it didn't exist.

      A second field is included in the record where a random number is inserted. When "Ben" is found on the list his 'number' is also reported. This is just a demo of how records can have an indexing field and then corresponding fields of data in the record (the index field in this example is the string and the additional data field is the random number).

     With a few modifications this code could also be adapted to quickly insert items on the linked list. This has not been implemented at the moment (it just occurred to me). For example to insert 'Ben' on the list we could begin a search for the insertion point at 'Be'. If the pointer to 'Be' on the array is 'nil' then we step back on the array until we find a pointer that is not nil (let's say there was an entry for 'ba'). We then pass this pointer to 'ba' to the insertion routine (currently it starts right at the bottom of the list with the head). If a pointer to 'Be' exists and the current entry is less than the entry we want to insert then we can pass the 'Be' pointer to the insertion function. For example if 'Bean' was the lowest 'Be' entry and we were inserting 'Ben' we could pass the 'Be' pointer (the pointer to Bean) in order to insert 'Ben'. However if 'Ben' was the lowest 'be' entry and we wanted to insert 'Bean' (which is less than Ben) then we could not use the 'be' pointer, but rather we would have to scan to the next lowest non nil entry on the array index (perhaps 'ba'). The reason for this is that in order to insert a link into a sorted linked list we need a previous pointer, and the previous pointer in this case would not be found by starting at 'be', since we are inserting a value less than the current entry, but rather we would have to start scanning at 'ba' for example, and then 'Bean' would be inserted at the end of the 'ba' entries and at the beginning of the 'be' entries (the last 'ba' entry providing the 'previous' pointer needed to insert the 'Bean' entry before the 'Ben' entry in this example). Time could then be saved both on the searching and on the insertion into the sorted list by using the array.

You can download the Delphi 3 / Delphi 5 project as a zip file ... indexed_list.zip 18 KB or as a textfile ... array_indexed_sorted_linked_list.txt.


Related pages:

Inserting, sorting, and disposing of elements on linked list

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
Delphi INDEX




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.