Linked Lists, Dictionaries and in-memory Databases

[REDEBOLT]

There has been some interest lately in linked lists.  I have been experimenting with linked lists and comparing them to database capabilities.  Many thanks to Parker for his contribution of double linked lists.  This first program contribution involves building and printing a list of city names as a part of a zip code database.  It is a simple application used to illustrate the concept of linked lists.  For future programs, I intend to experiment with the concept of sorting using lists.  Eventually, I intend to discuss dictionaries and sqlite.  Concepts of using indexes and updating of lists will be discussed.

I hope that Parker will forgive me for making some minor changes to his code, such as changing the class name.

Below is a zip file containing the source codes and executable program.

[Parker]

I don't have any problems with you modifying my code.

[REDEBOLT]

' ZIPLIST02.EBA
'
' This example program will read the zipcode records from a text file and build
' a linked list and then print them out.

Below is a zip file containing the source codes and executable program.

[REDEBOLT]

' ZIPLIST03.EBA
'
' This example program will read 42702 zipcode records from a text file and builds
' a linked list.

Warning! This zipcode file is not up-to-date and should not be relied upon for current
information.  It should be used for testing only.

To Parker:

At line 82, there is this statement:
''ZipList.removeAll( )                    ' Remove all list nodes.

If I uncomment this line, the program abends
when I close the console.

I don't understand why.

Below is a zip file containing the source codes and executable program.

Edit: 05/06/2007 5:00 pm.

I discovered the error i made.  The destructor does a removeAll( ).
I should not have called removeAll( ) before my program ended.
My apologies to Parker for my error.

Below is a zip file containing the updated source codes and executable program.

[Parker]

Hmm

There's no problem for me, whether or not the line is commented out. However, try adding a line inside the while statement, which changes your removeAll to this:

Code Select Expand

sub CLinkedList::removeAll( )
pointer node : node = *<p_listnode>head._next
pointer temp

while node <> tail
if node = 0 then return
temp = *<p_listnode>node._next
delete node
node = temp
wend
end sub

If that doesn't work, please describe the problem in detail, and maybe I or someone else can duplicate it and solve it.

[REDEBOLT]

Thanks very much Parker!
The program now ends normally.

[REDEBOLT]

' ZIPLIST04.EBA
'
' This example program will read 42702 zipcode records from a text file and builds
' a linked list sorted by city-state and a list sorted by state-city.  You have to
' wait several minutes for the program to finish.  The lists are written to files
' for examination.

The program ran in 25 mins on my 366mhz machine and in 10 mins on my 1ghz machine.  It's about as interesting to watch as watching paint dry. The lesson to gain from this exercise is that an insertion sort using lists is very slow due to the fact that much of the time spent is for searching the lists.

Now that I am learning how lists work, I will be investigating the use of B-tree lists.

Below is a zip file containing the source codes and executable program along with the input/output files.

[Allan]

thanks for sharing your work on linked list

B-Tree will be of great interest to me in ebasic.

[LarryMc]

The technique I use to sort information like that is:
1. Write the information to a text file.
2. Use ShellExecuteExA to invoke the equivalent of the old DOS sort command.
3. Read the result file back in.


Works pretty fast.

[Allan]

The Heapsort.eba in the Projects folder is also very fast for sorting and easily loaded/saved to file.