Linked list and linked array

[stanhebben]

I had to modify the batchfiles to get your example working. (supplied them in the zip)

I also created a test which counts in cycles/operation, to compare our libraries.

However, the way to remove elements in our libraries is different. In your lib, you have pass an index, but that means your library will - internally - have to iterate trough the elements. And, those indexes change if you remove an element, which means the implementing application will have to save the indexes and adjust them, which may be hard.

My implementation simply doesn't know what an index is. You have to do the iteration yourself, and remove elements as you find them. This is much faster if you have to remove many elements with known properties. (for example, removing all multiples of 3)

Note: the files in the attachment have to be joined with those in gabor's zip.

[attachment deleted by admin]

[stanhebben]

In the meantime, I made a linked list to see how the data structures compare to each other. (number are in cycles / operation)

Code Select Expand

LList Add: 26
LList Iterate: 12
LList Iterate + remove: 36
LAList Add: 16
LAList Iterate: 13
LAList Iterate + remove: 39

Linked list has a disadvantage when adding elements. However, the linked list has the ability to remove an element directly if you have a pointer to the node.

Edit: forgot to add the source code.

[attachment deleted by admin]

[farrier]

Linked-List ?

Be careful!

http://rss.slashdot.org/~r/Slashdot/slashdot/~3/53217804/article.pl

[stanhebben]

 :bg patent on double-linked list? As the article stated, linked lists have been in use for much longer than that.

Even if that patent exists, and if it describes the doubly-linked list, it won't be valid in Europe. (you can't patent data structures or algorithms in Europe)

Edit: I read the patent text. It indeed describes a superset of a doubly-linked list (triple-linked, and with more than 3 pointers per node). But, as European, I don't have to care about US patents.

[gabor]

Hello friends!

I finished the newest version.
- There are some painfull bugs removed.
- Nicer, improved test app
- More test:
   For the list there is
   - insert at head/tail/random position
   - insert with random size
   - read through the whole list and write the index into every member (dumy data write test)
   - access random members and check for the data
   - remove every member (unnecessary, because destroying the list also removes every member, this is just for the test)
   For the array there is
   - insert at the tail only
   - insert with specified element and subarray size
   - read through the array and do the dumy data write test
   - random access with check
   - remove every element

It still uses the Heap procedures. The linked array could be perfectly combined with Stan's FastAlloc macros to achieve better performance...

Well, it is not perfectly optimized. For now and for my goals it is quite good.
Please test it, take it apart or use it!

Greets, Gábor

PS: the zip is attached to the first post on page 1. (linked191206.zip)