Linked Lists vs. Arrays

[Dim A]

I have a data structure that order is very important in and I'm debating between linked lists or arrays. The number of elements will never exceed 100, so I could get by with an array of 100, but it's so much easier to move items in linked lists.

What do you guys think?

[kedaman]

That depends what you mean with lists? Listboxes?
Well Listboxes are controls and a totally different thing.

Arrays are much faster too operate and handle than putting items in a listbox, but under runtime you won't be able to view them without having some kind of list.

[PaulLewis]

Do you mean you plan to write a class which contains an element which holds another instance of the same class and so on?

Or is there something VB can do that I haven't seen or heard of before?

I am not much for knowing what's fastest in compiled code etc, but I have found the Collection object to be useful when order is not important, and the array syntax useful when order is important.

If you plan to have an array of objects (i.e. your own classes) and if you plan on moving them about alot (sorting etc) then I would hope that linked list (class) ideas would work best.

Finally, kedaman mentioned the default property of a class you create which would seem to be the best way to implement your comparison plans. I don't know C++, but in Java, there are so many ways of customising classes and so many "standard" interfaces you can choose to implement that there is simply no comparison with VB. It will be a valiant effort I think to make VB work more like C++, but in the end, you will probably have to wait for VB7 like everyone else

When I switch languages after a prolonged period in another, I find it takes a couple of days to "remember" the rules. How many times I've typed Dim lResult as Long = 0 in VB I cannot count I hear it will be in VB7 which is cool

Sorry if I was too opinionated in my reply - I hope I am not normally that way

Cheers
Paul Lewis

[Dim A]

I mean by having a class item that has a pointer to another class item of the same type...

In C++ it's relatively simple, the class would have a class pointer called something like NextItem, that would point to the next Item in the list.

This allows you to do easy insertion of things into the list, unlike arrays, such as:

TempPointer=MyItem->NextItem
MyItem->NextItem=NewItem
NewItem->NextItem=TempPointer

This is much more efficient, (I believe), then using an array and shifting upto 100 elements in the array to move an item from the end to the beginning.

To traverse the linked list more effectively, A doubly linked list could be created. So that, the class would also have a pointer to the previous item. Knowing of one item, you could then traverse to the beginning or end of the linked list by use of the NextItem and PrevItem pointers.

Basically it has the same functionaility of having an array of MyClass plus it has the added feature of being dynamically expandable/contractable, and it takes a little more work to access the 10th item. To find the 10th item you'd have to start at the beginning of the list, and count out 10 traversals.

I'm hoping that something like this would be possible in VB, but I'm not sure if it's worth all of the added effort and a full linked list would actually take up more space then a full array because of the pointers, but an empty linked list would be a lot smaller then an empty array.

Let me know what you guys think. I might be totally off base trying to do this in VB, and it might be more trouble then it's worth.

[PaulLewis]

HEhe,

I was just checking on how you planned to implement the list. I am glad there wasn't a feature of VB I was totally oblivious of giving us that flexibility.

I think it would take you only a few minutes to test your idea out. You should let us know if there are major differences in speed between the two (or major differences in memory allocation or anything).

The understanding is that the array would be an array of your class right?

For only 100 items, I think it will be hard to detect a noticeable difference in speed since you no doubt develop on a fast machine.

Another point to consider: You said that the order is very important in your app, but in fact, what you really mean is that the retrieval order is very important. A linked list stores the items in an arbitary order whereas the array stores them in a fixed order. This is a subtle but important point which you no doubt know.

Therefor, if the order they are stored in is of no importance, then I prefer 'keeping it VB' and using a collection. Assign each item in the collection a key which has to be a string. It's not going to be as fast as an array but like I said, I suspect there will be a very small difference in speed if we are only talking about 100 items.

I would be interested to learn of any differences in performance between sorting an array of 100 instances of a class vs sorting the class as a linked list, vs sorting a collection (mind you, collections aren't designed or optimised for sorting).

Anyhow, if I had to read code of someone elses employing any of these methods, I'd hope that I could fathom it out so I don't think it will matter which way you do it. I always like to keep it clean and keep it simple. By clean, I mean don't go adding programming complexities if they serve no real purpose. Of course, the purpose may only be to allow you to use a particular programming paradigm that you like, but usually, you will find it easier to compromise to a certain degree...

Darn it - I've been too wordy again.

Sorry

Paul Lewis

[Sam Finch]

VB Has a linked list facility, It's called a collection. you declare one with

Dim collMyCollection As New Collection

and you can add, remove and read Items using the Add and Remove Methods and the Item Property. You can also Give your items a Key, which is a string to Identify them by use

collMyCollection.Add 10, "MyKey"

and then you can access it with

Msgbox collMycolection.Item("MyKey")

If the sortorder is the main issue, go for the linked list, there is nothing bad in using your own data structures. if you need more details, have a look in 1 of the last 3 issues of VBPJ, where you find a decent article, maybe there is even source code on their homepage.

best regards

Sascha

[Gen-X]

Sam

Well done! I was waiting for someone to mention the Collection as I read down this post... I am surprised people don't realise what they are


Perhaps something that wasn't highlighted was that the "Key" is very important if you want to be able to search for a particular item based "roughly" on what we would call an index value.

In this way you can get at the contents either by referencing the element directly (ie cMyCol(12)) or you could reference it by using a unique key (ie cMyCol("fred"))

There is an inherant problem however in which referencing by the key makes it impossible to find out what element number it is. While you can reference an element and look at its key you can't actually look at its element directly from the key.

If you want a way around that just let me know and I will go through the code.

[PaulLewis]

Sam mentioned that a Collection is VB's form of a linked list which is something I did not know. I don't know how the classes / types VB makes available work internally.

If the Collection is actually an implementation of a linked list, then they have certainly expanded the definition of a linked list

I would say that Collection looks more like a Hashtable (er, thats my Java bias coming through).

Also, I think that in a linked list implementation you should be able to at least forward scroll through each element without providing an index or key (i.e. use a method like "next").

As far as I know, one item in a Collection has no knowledge of any of the other items so the exposed interface to us mere mortals is not that of a linked list.

I don't doubt Sam's info at all since I really do not know how it's implemented under the hood. It's just that if VB's intention was to provide us a linked list, why not make it scrollable? Or is my ignorance showing through yet again?


Regards
Paul Lewis

P.S. Obviously I have nothing to do this morning hence my posts

[Sam Finch]

Gen-X

I don't Really use the Key Functionality with Collections, Mainly for that reason but also because I don't really see any Particular advantage in it, The Only Time I used it was for Storing object Refenences when Subclassing UserControlls So I could Get an object Reference From an hWnd by using the hWnd as a Key, But I don't like to use Them while Subclassing because they're one of the first things to go when a project terminates, I just Use Modified Versions of Get/Set WindowLong to Save the Object Reference in the UserInfo Window Long.


Paul If you Have a Collection which you Want to loop Trough Try this

Dim collMyCollection as Collection
Dim i as Variant

Set collMyCollection = FillCollection 'This is a Made up Function that Returns a New Collection With Stuff in it

For Each i In CollMyCollection

    MsgBox I

Next i

That loops through every Item in the Collection.

[PaulLewis]

Thanks Sam,

Who would have thought of that syntax? Obviously my background is not VB so I didn't even bother to look into that syntax in VB.

I take it all back! By offering the "for each" syntax, which gives forward scrolling, Collections do resemble a Linked List. The key/index feature makes them equally useable as a hashtable which I guess is how I usually visualise my collections.

The power of Forums like this one is that it helps readers and contributors alike in furthering their understanding...

In this case, I have been enlightened and I appreciate it

regards
Paul Lewis

[Gen-X]

Firstly, A collection is implemented "using" linked lists...

That doesn't mean it has all the functionality that they provide (such as forward scrolling) but it does mean that its the core of their contruction.

There are 2 factors that prove this :

1. Dynamically increased size

2. Ability to delete "intermediate" nodes without disturbing structure (element numbers are "shuffled")


As for the use of Collections with key references the best part is if you wish to store information regarding ComboBoxes, you wish to display a fanciful "text" as the dropdown but you want to return a CODE as the actual answer.

Unlike Access which has the wonderful ability to produce a multi-column dropdown and to provide which one is "bound" as far as the value being set... VB doesn't provide this (well none that I could find when I looked).

If you create the collection where each item is in fact the instance of a class with 3 fields (Code, Contents [Default] and Element) you can actually get it to reference BOTH ways.

---- MyNewClass ----
Public Code as string
Public Contents as variant
Public Element as long
---- MyNewClass ----

Dim reItem as New MyNewClass

reItem.Code = "AM"
reItem.Contents = "America"
reItem.Element = cMyCol.Count

cMyCol.Add reItem, reItem.Code

With this above structure I can at any time find out either way what I am looking at.

For i = 1 to cMyCol.Count
  Msgbox cMyCol(i).Code
Next I

MsgBox cMyCol("AM").Element

Of course the Element number has to be adjusted if you remove items from the collection but you set the collection up as a class and provide all the functionality required within that class.

The whole thing then works together to provide you with a duel referencing system that allows you to load ComboBoxes, ListBoxes, collections or anything else while being able to reference it either by element or by Key and still being able to find the back-reference.

[Dim A]

Collections may just be what I'm looking for...
It seems to mimic a listbox functionality without the display and with expanded storage types.

Kinda odd that it starts from subscript 1 instead of 0 though.

I think I may have a few problems yet with this, but I'll bring them up as they come along

[Crazyrange]

VB Has a linked list facility, It's called a collection. you declare one with

Dim collMyCollection As New Collection

and you can add, remove and read Items using the Add and Remove Methods and the Item Property. You can also Give your items a Key, which is a string to Identify them by use

collMyCollection.Add 10, "MyKey"

and then you can access it with

Msgbox collMycolection.Item("MyKey")

Thank you so much! It is posts like these that spare the blushes of ignoramuses like me who don't read through the whole book before starting something! This is exactly what I am looking for!