[MarsRocket]

I'm trying to implement a Deque ADT using a doubly linked list. I have two doubly linked lists with equal lengths (this will always be the case). Each list keeps track of the current element that is inserted and stored in a variable key.

I have the following methods

 moveNext() //moves the current element "key" to the next element in the list.
 movePrev() //moves to the previous element in the list.
 moveToIndex() //Moves the current element to the specified index.
 insertAfterCurrent(int a) //inserts element after the current element "key"
 insertBeforeCurrent(int a) //inserts element before the current element "key"
 inserFront() // inserts to the front of the list i.e. index 0.
 insertBack()
 deleteCurrent()
 getCurrent()
 deleteFront()
 deleteBack()

Link A must perform a permutation on Link B. That is,

Doubly A = new Doubly(); //Contains elements {1,1,3,2,1}
Doubly B = new Doubly(); //{1,2,3,4,5}

Now each index in A corresponds to the index in B. List B must be rearranged given the specified elements in A which act as indices to move the current element in B to the specified index in A. Assuming index starting at 1.

For example the first element in A(1) specifies that the first element in B must be in position 1. The next element in A(1) states that the next element in B (2) must be in index 1 as well. So 2 is inserted before 1 and so on. The end result of these operations would leave B in a rearranged state: {5,2,4,1,3}

The rearrangement is done in a function called Shuffle. Now I'm having difficulty trying to come up with an algorithm that would achieve this.

My current shuffle function code

      if (A.getLength() > 0 && B.getLength() >0){
        if (B.getLength() == A.getLength()){
           for (A.moveTo(0); !A.offEnd(); A.moveNext()){
                 B.moveNext();         
           }

Now all this is is traverse the A and B lists but after this I am completely lost on how permute B to get the result {5,2,4,1,3}.

[blackcompe]

In psuedocode, this is the algorithm:

Doubly shuffle(doubly indices, doubly list) {
        c = new Doubly
        listIndex = 0;
        FOR i in indices {
            IF i >= length(c)
                c.append(list[listIndex++])
            ELSE
                c.insertAt(i-1, list[listIndex++])
        }
        return c
}

So, you need to use the methods provided to you to do what's done above. First, place the current pointer to the front of the list for both lists and setup the iterative loop. You've done this already.

for(A.moveTo(0), B.moveTo(0); !A.offEnd(); A.moveNext(), B.moveNext()){}

We replace i >= length( c ) with getCurrent and getLength. Then we replace append with insertBack. Then we need do a little trickery to insert an element at a specific index. So we replace the insertAt with moveToIndex and insertBeforeCurrent. Unfortunately, you have to move current back after the insertion, so I'd kept an index counter to remember where your at in B. Lastly we move the list pointers up one, which is taken care of in the loop.

I think that's the correct algorithm. I only tested it with your example. Anyway, the point was to show you how to translate the algorithm into the Doubly API calls.

Edit:

If you have to modify the list instead of creating a new one, well, that's a little different. Suppose I have:

A = {1, 1, 3, 2, 1}
B = {1, 2, 3, 4, 5}

And suppose I've re-arranged so that the first two elements are in their proper positions - {2, 1, 3, 4, 5}. So I'm about to process the element, 3, in B. Basically, you'd get that element, delete it, and insert it into the specified position. E.g.

int elem = B.getCurrent();
B.deleteCurrent();
B.moveToIndex(A.getCurrent()); //A.current points to the index that the 3 (in B)/> is supposed to reside at
B.insertBeforeCurrent(elem);

This post has been edited by blackcompe: 12 October 2012 - 01:54 PM

[MarsRocket]

Thank you but upon my revision, it is still causing me troubles.

I'm modifying the list instead of creating a new one.

static void shuffle(List B, List A){
           for(A.moveTo(0),B.moveTo(0); !A.offEnd(); A.moveNext(), B.moveNext()){

             int x = B.getCurrent();
             B.deleteCurrent();
             B.moveTo(A.getCurrent()-1);
             B.insertBeforeCurrent(x);

           }
           B.displayList();

        }

When I display the list, it goes in an infinite loop of 1's. I'm wondering if it could be my moveTo() function?

void moveTo(int i){

        if (i >= 0 && i <= getLength() -1){


            current = front;
            for(int count = 0; count < i; count++){
                current = current.next;
            }
        }
        index = i;
    }

[blackcompe]

You just copied my code into the loop. You have to do more work than that. I just gave you something that hopefully made sense to get you on your way. I won't do your homework for you. And nothing is wrong with your moveTo function. You need to make sense of how you're supposed to use the API to permute the data.

[MarsRocket]

Thanks for the help, solve it.