programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Doubly Linked List - Swaping two sub-parts

Kaspersky Ukshini
Ranch Hand
Posts: 122
Nearly done! I have a couple more (2or3) and I believe I'll be ready to go 8-)

This one is about an Army and a list of warriors... for example 1,2,3,4,5,6,7,9,10 .... and the user inputs points for two sequences, for example 1, 5 and 6,10 .... That means I have to take the aray from the 1st elemenet, up to the 5th one, and swap it with the elements from 6to10....

The nest list should be:

6 7 8 9 10 1 2 3 4 5

Things to keep in mind: The list will always have at least two warriors. The intervals will never interfear, and will at least contain ONE warrior..
It says: be careful when the intervals are next to each other, and when be careful when an interval starts with the first warior, or finishes with the last warrior.

One word: I HAVE NO IDEA what to do lol... Stack I guess???

Knute Snortum
Sheriff
Posts: 4276
127
One possible approach: write a method that swaps two array elements.

Steve Fahlbusch
Bartender
Posts: 612
7
What i would do is just update the pointers (references) in place.

And if it were my assignment i would implement the deque as a circular double linked list.

-steve

Winston Gutkowski
Bartender
Posts: 10575
66
Steve Fahlbusch wrote:What i would do is just update the pointers (references) in place...

@Kaspersky: Or simply swap the values in the two Nodes. Swapping entire Nodes can get quite tricky, especially if you have to worry about concurrency, since you have to re-link 4 complete sets of pointers (8 total).

Winston

Steve Fahlbusch
Bartender
Posts: 612
7
@Winston - given the project definition above there is no way of knowing if the two sub parts are equal in size - meaning that there can be ugly issues when one has to shuffle data that is not part of the move.

And yes this needs to be an atomic operation on the list, but do does adding a new node or removing an existing node.

-steve

Kaspersky Ukshini
Ranch Hand
Posts: 122
Yeah, but the number of sub-sequences is not allways the same guys.
One sub-sequence can contain 3memebrs, the other one 5...

Winston Gutkowski
Bartender
Posts: 10575
66
Steve Fahlbusch wrote:@Winston - given the project definition above there is no way of knowing if the two sub parts are equal in size - meaning that there can be ugly issues when one has to shuffle data that is not part of the move.

You're quite right Steve. I was thinking of a "single node swap".

Winston