• Post Reply Bookmark Topic Watch Topic
  • New Topic

Doubly Linked List - Swaping two sub-parts  RSS feed

 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One possible approach: write a method that swaps two array elements.
 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@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
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!