CODEWITHSUNDEEP
javac++calgorithmjosephus
venkysmarty
venkysmarty

Reputation: 11431

Regarding representation of Josephus puzzle using arrays

Algorithms by Robert Sedwick, It was mentioned that linked list can be represented using Arrays, at following link

http://flylib.com/books/en/3.55.1.34/1/

Fig 3.8, here if 5 is removed from my understanding next 4 should be changed to index 6 as val 5 is removed, as we go thourgh the figure at item 4 is removed next of val 3 is chaned. I am not following the logic of the figure. can aany one please help me.

Thanks!

Upvotes: 1

Views: 570

Answers (2)

Bill the Lizard
Bill the Lizard

Reputation: 405745

The values in the next array are the index of the next value in the chain. If you want to remove the value 5, which sits at index 4, you have to change next[3] from 4 to 5, so that the value at index 4 is effectively removed from the circle and will be skipped on later traversals.

Josephus array implementation

After the update highlighted, the "node" with a value of 4 points to the "node" with a value of 6.

Upvotes: 0

user85421
user85421

Reputation: 29680

the index is zero-based as opposed to the value itself (letters would be better values).
Example of removing the value 5: before removing, next index of the node with value 4 is 4, which points to value 5; after removing, next index is changed to 5, pointing to value 6 (next changed from 4 to 5).

Or, using the prefix v to indicate values:

before 

    index ...  3  4  5 ...
    ----------------------
    value     v4 v5 v6
    next       4  5  6

after 

    index ...  3  4  5 ...
    ----------------------
    value     v4 v5 v6
    next       5  5  6

as you can see the node v4 is followed by v6 (index 5) practically removing v5 from the chain.

Upvotes: 1

Related Questions