Re: [algogeeks] Re: Blocked/Unrolled linked list with no duplicates and sorted
Hi all,
I wrote a pseudo code for a blocked/unrolled single linked list which does
global insertion sort(decreasing order) during insertion of elements in the
list.
Can someone look at pseudocode and let me know if it works correctly? I
think it does! Or do you see any corner cases which might create problems?
I think there might be also be some redundant logic...but I am not able to
figure out? I basically want to make it correct and more legible with
minimum amount of code.
There is also another issue of avoiding wastage due to partially filled
nodes which requires redistributing data between nodes. I am thinking about
some heuristic for this.
*BTW, first here are some test cases and expected results (Note: the sort
order in these test cases is in increasing order, but I wrote the algorithm
for decreasing order)*
eg1: insert 14 in (1,7)-(8,11)-(13,15)-NULL
result: (1,7)-(8,11)-(13,14)-(15,x)-NULL
eg2: insert 14 in (1,7)-(8,11)-(13,15)-(19,x)-NULL
result: (1,7)-(8,11)-(13,14)-(15,19)-NULL
eg3: (1,2)-(4,5)-NULL and 3 need to be inserted
result: (1,2)-(3,x)-(4,5)-NULL (NO redistribution)
eg4: insert 3 in (1,2)-(4,x)-NULL
result: (1,2)-(3,4)
eg5: (0,7,11,20,40)-(42,71,90,93,100)-NULL and 39 needs to be
inserted *[Assuming
ARRAY_SZ = 5]*
result: (0,7,11,20,39)-(40,x,x,x,x)-(42,71,90,93,100)-NULL (NO ReDIST)
(lot of space wasted in new Node N as chances of filling it are low and so
redistribution is required)
*And here is the pseudocode for the algorithm*
*--Data structure--*
#define ARRAY_SZ 2
typedef struct node
{
struct node* next;
int Array[ARRAY_SZ];
int last_elem;
}NODE, *NODE_PTR;
*// isNotFull(node) function returns false when node=null or node.Array is
full. true otherwise*
*// Function that inserts element in a blocked linked list and maintains a
global decreasing sort order*
*
*
*Function insert(int elem, NODE_PTR* list): NODE_PTR*
*begin*
NODE_PTR currentNode = *list, startNode = NULL, oldNode = NULL
if(!currentNode)
{
create newNode
newNode.next = null
newNode.last_index=0
newNode.Array[newNode.last_index] = elem
return newNode
}
startNode = currentNode
while(currentNode)
{
if (isNotfull(currentNode))
{
// we can certainly insert elem in this non-full currentNode if either
next node is null(i.e. currentNode is last node in the list)
// or elem currentNode.next.Array[0]
if(null == currentNode.next or elem currentNode.next.Array[0])
{
currentNode.last_index++
insertionsort(elem, currentNode.Array)
return startNode
}
else
{
// even though currentNode is non-full we cannot insert in it, so we
move to next node
// TODO: redistribution
oldNode = currentNode
currentNode = currentNode.next
}
}
else
{
// currentNode is full
// case : elem should be inserted before currentNode
if(elem currentNode.Array[0])
{
if(!oldNode)
{
// currentNode is the first node of list, so insert a newNode before this
and insert elem in this newNode
create newNode
newNode.Array[newNode.last_index] = elem
newNode.next = currentNode
return newNode
}
else
{
// currentNode is not the first node of the list because a previous node
i.e. oldNode exists
if(isNotfull(oldNode))
{
insertionsort(elem,oldNode)
return startNode
}
else
{
// previous node i.e. oldNode is full, so a newNode must be inserted
between currentNode and oldNode. insert elem in this newNode
create newNode
newNode.Array[newNode.last_index] = elem
oldNode.next = newNode
newNode.next = currentNode
return startNode
}
}
}
// case: elem should be inserted after currentNode. if next node is
null, create new node and insert elem in this new node. else,goto next
node.
else if (elem currentNode.Array[currentNode.last_index])
{
if(null == currentNode.next)
{
// currentNode is last node of the list and is full
create newNode
newNode.Array[newNode.last_index] = elem
newNode.next = null
currentNode.next = newNode
return startNode
}
else
{
// nextNode is not null
if(elem currentNode.next.Array[0] or isNotfull(currentNode.next))
{
// element cannot be in-between currentNode and nextNode. it must be
inserted in nextNode or ahead
oldNode = currentNode
currentNode = currentNode.next
}
else
{
// = elem currentNode.next.Array[0] and nextNode is full
// elem must be inserted between currentNode and nextNode
// TODO: redistribution
create newNode
newNode.Array[newNode.last_index] = elem
newNode.next = currentNode.next
currentNode.next = newNode
return startNode
}
}
}
}
// case: elem needs to be inserted inside full currentNode
else
{
if(isNotfull(currentNode.next))
{
// there is some space in nextNode
insertionsort(currentNode.Array[last_index], currentNode.next)
insertionsort(elem, currentNode)
return startNode;
}
else
{
// nextNode doesnt exist i.e. null or nextNode
[algogeeks] Re: Blocked/Unrolled linked list with no duplicates and sorted
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.
Re: [algogeeks] Re: Blocked/Unrolled linked list with no duplicates and sorted
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
fullthen 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 nodesimply 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.
Re: [algogeeks] Re: Blocked/Unrolled linked list with no duplicates and sorted
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.comwrote:
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
fullthen 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 nodesimply 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.
