Thanks a lot for your inputs Sunny. Your solution seems correct to me. Is
this the only method ? Can you think of any other methods which could be
more efficient. I heard merge sort or quick sort are also used for linked
lists. Do you see their applicability in this case?
What about duplicate avoidance ? Do I perform binary search on each node
during the list construction to check for duplicates? Or you can think of a
more efficient way?
Thanks a lot
Varun
On Thu, Jul 28, 2011 at 11:02 AM, sunny agrawal <sunny816.i...@gmail.com>wrote:
> Nice Problem :)
>
> i think taking care of duplicates is very simple.......but main point is
> sorted insertion
> that has to very carefully done
> there are many cases that need to be taken care of
> 1. if the value to be inserted is between two nodes and both nodes are
> full....then a new node will be inserted in the link list and value to be
> inserted will be the first element in the new node....
> case: (1,2)->(4,5) and 3 need to be inserted
> after insertion list will be
> (1,2)->(3,x)->(4,5)->NULL
>
> 2. else the value that need to be inserted will be inside some node.......
> if there is empty space in the node....simply insert using insertion sort
> (1,2)->(4,x) and 3 is to be inserted, insertion sort in node 2 will suffice
> (1,2)->(3,4)->NULL
> 3. but if the node in which the value need to inserted is full then last
> number from that node will be shifted to a new node and then insert the
> value in the node.
> if array_sz is large the one instead of shifting the last element u can
> split into two halves and put first half in first and second in 2nd
> (1,2)->(3,5) 4 to be inserted
> (1,2)->(1,4) ->(5,x) ->NULL
> i think considering these 3 cases would suffice.......although first case
> can be merged with 3rd if programmed carefully
>
>
>
> On Thu, Jul 28, 2011 at 3:35 AM, banu <varun.nagp...@gmail.com> wrote:
>
>> Anyone ?
>>
>> On Jul 26, 10:27 pm, banu <varun.nagp...@gmail.com> wrote:
>> > Hi,
>> > Basically I am trying to create a blocked linked list(unrolled linked
>> > list) with following properties
>> > - Configurable number of elements in each node
>> > - No duplicate elements in the unrolled linked list
>> > - Linked list is sorted either during insertion or after creating the
>> > linked list
>> > - In place
>> >
>> > Assuming I need to create a sorted unrolled linked list with no
>> > duplicate elements with block size say 2
>> >
>> > Example: 10,2,4,2,5,7,9.11,11,5
>> >
>> > Final blocked linked list: (2,4)->(5,7)->(9,10)->(11,x) or in reverse
>> > order
>> >
>> > Note: x means unutilized location in the array wihtin the node. In
>> > case there are not enough elements to insert in a node, some memory
>> > allocated for a node is unutilized
>> >
>> > // Following is node structure
>> > #define ARRAY_SZ 2
>> > typedef struct node
>> > {
>> > struct node* next;
>> > long long int elements[ARRAY_SZ];
>> > long long int elemIndex;
>> >
>> > }NODE, *NODE_PTR;
>> >
>> > Can you suggest me a way to do this correctly and efficiently? It
>> > could be an pseudo text or C-code.
>> >
>> > Thanks
>> > Varun
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
