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 <[email protected]> wrote: > Anyone ? > > On Jul 26, 10:27 pm, banu <[email protected]> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
