Managing linked list as if dynamic array

[egsuh]

Hi,
AFAIK, dynamic array and string type operate in the same way. I do not have to take care of their memory allocation.

I defined a type of dynamic array, to use it as a set of large numbers.

Code: Pascal  [Select][+][-]

1. type
2.      TRange = record
3.           min, max: integer;
4.      end;
5.      
6.      TRangeArray = array of TRange;

So, CONCEPTUALLY following definition is possible (not correct syntactically).

    var
         ARangeArray : TRangeArray = [1..6, 11, 22, 2000..3000];

min and max have the same value if a single digit, e.g. 11, 22, etc.
And followings are syntactically correct as I have defined operator overload.

   var
         Arr1, Arr2, Arr3 : TRangeArray;
   begin 
         Arr3 := Arr1 + Arr2;
         Arr3 := Arr1 - Arr2;
         Arr3 := Arr1 * Arr2;
   end;    
       
But as the array operation copies the whole content whenever there is any operation like insertion or deletion, I'm thinking defining a linked list structure. Would be similar to :

   type
      PRangeLink = ^TRange;
      TRange = record
           PrevNode, NextNode: PRangeLink;
           min, max: integer;
      end;

      TRangeLink = PRangeLink;

     


Is there any way that I can treat this as if dynamic array is treated? The key is I do not care about the memory allocation.
Of course I might have to call  New(TRange), but I do not need to dispose it.

[cdbc]

COM Interfaces 

edit: You could have a look HERE, both to see the differences between array & linked list approach and for a COM collection of interfaces regarding lists, queues & stacks - including a memory-manager...

[Khrys]

But as the array operation copies the whole content whenever there is any operation like insertion or deletion

This smells like an attempt at premature optimization to me.
Have you profiled or otherwise measured the performance impact this has on your code? Could you give a very rough estimate of how many subranges you'd have to deal with per  TRangeArray? If it's a small & limited number I'd consider switching to a fixed-size array and keep everything on the stack.

Also consider the linked list overhead - the two pointers take up twice as much space (16 bytes assuming 64-bit) as the actual data (8 bytes).
For a 10-entry  TRangeArray  the data on the heap would add up to 96 bytes for the array version and 240 bytes for the LL version, and that's not even counting memory manager overhead (which is certainly worse in the fragmented LL case).

[Thaddy]

Dynamic arrays can evolve into ragged arrays so choose another way.
Otherwise you end up with bad design and a lot of problems.

[Nicole]

Please do not combine those both.
Lists work in a different way, they are organized differently.
You have properties in arrays, arrays do not have, eg.:"sorted" or "noduplicate" or similar.
If you have those options set, a value e.g. will not be added, because it is already there in the list.
An array would allow that and there is no way to do such a setting with one line.
The line, where a certain value is located may differ by such a "sorted" setting.

The time will pass by and you will forget about what you thought today.
You will use the properties of lists and enjoy them.
And then the array will crash and it will take you hours and days to find out where and how.

I work a lot with dynamic arrays.
For this I have a small unit, which administrates them:
- sets more fields as a block
- deletes empty "rows" at the end
- sorts them for certain criterias
etc.

In other words: It is up to you.
My style is to think myself for stupid and make all things with my code, I did not expect from myself one year ago.

[egsuh]

I implemented the same structure with linked list first, with Turbo Pascal, creating stack and queue -- my small data structure --- for myself.

Later I implemented it using TList with Delphi 5 or 7. Nothing much to do because other algorithms had been  done already. The reason of moving from the successful linked list to TList was that I do not have to maintain the codes related with linked list (and stack, and queue neither) myself.

With Lazarus, I changed it to TFPGMap<integer, integer>, with TFPGMap.key representing min value and TFPGMap.data representing max. Why? auto-sorting, etc. Something was easier than with TList. TList was too generic, and I had to define some details.

Every method was successful. It's not a big deal implementing a new approach. With Lazarus, I could gain from operator overloading.

Recently I changed it to dynamic array.

The best thing with dynamic array is that it's possible to pass by value -- looks so anyway. But with dynamic array, adding a value, e.g. [4,6,9,10]  + [7] will cause a few times copy of the whole content (do not know exactly). With linked list, only add one more node of 7, set its prevnode to 6 and nextnode to 9, and change the nextnode of 6 to 7 and prevnode of 9 to 7.

In short lists, the gain of linked list would not be large. So, simply wondering there are any way that I can do the similar thing with linked list.

[cdbc]

Hi
Make this:

Code: Pascal  [Select][+][-]

1. type
2.      TRange = record
3.           min, max: integer;
4.      end;

into this:

Code: Pascal  [Select][+][-]

1. type
2.   IRange = interface(IInterface)['jbwlv-S-FFWF544VW']
3.     function GetMin: ptrint;
4.     function GetMax: ptrint;
5.     procedure SetMin(aValue: ptrint);
6.     procedure SetMax(aValue: ptrint);
7.     property Min: ptrint read GetMin write SetMin;    
8.     property Max: ptrint read GetMax write SetMax;
9.   end;
10.   TRange = class(TInterfacedObject,IRange)
11.   private
12.     function GetMin: ptrint;
13.     function GetMax: ptrint;
14.     procedure SetMin(aValue: ptrint);
15.     procedure SetMax(aValue: ptrint);
16.   public
17.     property Min: ptrint read GetMin write SetMin;    
18.     property Max: ptrint read GetMax write SetMax;
19.   end;

That will give you the 'AutoFree' you're after, for starters...
Regards Benny

[marcov]

Note that making the range a class/interface has a dynamic memory alloc/dealloc penalty.

So you might be substituting one penalty (copying) for another (allocation/creating and destroy/deallocate) overhead.

[cdbc]

Hi
Yes Marco, but cures his lazyness towards memory-management, which was his question, to begin with... 
Regards Benny