The array is either completely full or it's last index is held in the value
extract.
eg if we had a BLOCKSIZE if 2 and we had currently in the list 8 elements
this would use 4 nodes. Upon inserting a futher element a new node would
have to be created also containing an array of data of size 2. If we
inserted the new element in the first postion of the 1st node then all the
array values would need to be suffle shifteed forward one space. Then newly
created node would then have extract as = 0 this being the forst index
postion of the last node in the list, all other nodes would be completely
full so there index values is already know to be BLOCKSIZE - 1.
Kind Regards
Renato Parletta........
To reply send mail to: [EMAIL PROTECTED]
ICQ No: 13078952
"l can only assume that a "Do Not File" document
is filed in a "Do Not File" file."
Senator Frank Church
Senate Intelligence Subcommittee Hearing, 1975
-----Original Message-----
From: Glynn Clements <[EMAIL PROTECTED]>
To: Renato <[EMAIL PROTECTED]>
Cc: [EMAIL PROTECTED] <[EMAIL PROTECTED]>
Date: Sunday, 15 November 1998 9:15
Subject: Re: Ordered linked list of blocks
>
>Renato wrote:
>
>> > > l am wanting to implement an ordered linked list of blocks
>> > > the declaration that l am using is
>> >
>> > > #define BLOCKSIZE 100
>> > > typdef struct listNode *listNodePtr;
>> > >
>> > > typdef struct data{
>> > > char *key;
>> > > chat *value;
>> > > }Data;
>> > >
>> > > typdef stuct listNode{
>> > > Data ListNodeData[BLOCKSIZE];
>> > > listNodePtr next;
>> > > }ListNode;
>> > >
>> > > typdef struct list{
>> > > listNodePtr head;
>> > > unsigned listSize;
>> > > unsigned extract;
>> > > }List;
>> > >
>> > > l use the extract field to keep the index value last array position
in the
>> > > current node.
>> > > My question is could l please recieve some help implementing the
entry of
>> > > data into this struture for both key and value in an ordered format.
>> >
>> > Linked lists aren't a particularly suitable structure for sorted data,
>> > as the insertion time is proportional to the number of entries.
>> >
>> > Better solutions would be binary or n-ary trees, or a two-level array
>> > (an array of pointers to blocks). All of these have logarithmic time
>> > complexity. The algorithms should be available in any text book.
>>
>> Unfortunately l am not give a choice as the data structure that l am able
to
>> work with. Therefore any help would be greatly appreciated
>
>Then you simply have to scan the list for each insertion.
>
>Also, the above ListNode structure doesn't make sense. It would also
>need to contain a count of how many items are stored in the array.
>
>--
>Glynn Clements <[EMAIL PROTECTED]>
>
