CODEWITHSUNDEEP
singly-linked-list
Poindexter
Poindexter

Reputation: 55

Is there a general set of instructions to swap adjacent and non-adjacent records in a singly-linked list?

With a singly linked list, swapping non-adjacent cells can be described by the following operation, assuming '=>' means 'now links to':

Y => X->next
X => Y->next
BeforeY => X
BeforeX => Y

However, this operation does not work for swapping adjacent records, creating circular links, as X->next (say) will be Y.

Adjacent record swaps, assuming X is before Y, can be described by a separate set of operations:

X => Y->next
Y => X
BeforeX => Y

I can't seem to solve this set of operations as a subset of the previous set or common children of a parent set.

Is there a uniform, unconditional set of operations that describes a swap that works for both adjacent and non-adjacent records?

Upvotes: 1

Views: 69

Answers (1)

Jonathan Leffler
Jonathan Leffler

Reputation: 754570

Here is some ASCII Art for the two scenarios.

Non-adjacent X and Y

X can come before or after Y in the list as long as there is at least one element between X and Y (so Ax and By could identify the same node when X comes before Y). The situation before:

     Bx       X        Ax           By       Y        Ay

   +----+   +----+   +----+       +----+   +----+   +----+   
   |    |   |    |   |    |       |    |   |    |   |    |   
-->|    |-->|    |-->|    |--...->|    |-->|    |-->|    |-->
   |    |   |    |   |    |       |    |   |    |   |    |   
   +----+   +----+   +----+       +----+   +----+   +----+

The situation after:

     Bx       X        Ax           By       Y        Ay
                   +------------------------------+
                   |                              |
          +------------------------------+        |
          |        |                     |        |
   +----+ | +----+ | +----+       +----+ | +----+ | +----+   
   |    |-+ |    |-+ |    |       |    | +>|    | +>|    |
-->|   @|   |   @|   |    |--...->|   @|   |   @|   |    |-->
   |    | +>|    | +>|    |       |    |-+ |    |-+ |    |
   +----+ | +----+ | +----+       +----+ | +----+ | +----+   
          |        |                     |        |
          +------------------------------+        |
                   |                              |
                   +------------------------------+

The 4 'next' pointers marked with @ are changed.

Before:

Bx->next = X
X->next  = Ax
By->next = Y
Y->next  = Ay

After:

Bx->next = Y
Y->next  = Ax
By->next = X
X->next  = Ay

Adjacent X and Y

Assume X immediately precedes Y. The situation before:

     Bx         X          Ax
                By         Y          Ay

   +----+     +----+     +----+     +----+
   |    |     |    |     |    |     |    |
-->|    |---->|    |---->|    |---->|    |-->
   |    |     |    |     |    |     |    |
   +----+     +----+     +----+     +----+

The situation after:

     Bx         X          Ax
                By         Y          Ay
                                   
          +------------+
          |            |
   +----+ |   +----+   | +----+     +----+
   |    |-+   |    |   +>|    |     |    |
-->|   @|     |   @|     |   @|     |    |-->
   |    |   +>|    |-+   |    |-+ +>|    |
   +----+   | +----+ |   +----+ | | +----+
            |        |          | |
            +-------------------+ |
                     |            |
                     +------------+

Before:

Bx->next = X
X->next  = Ax = Y
By->next = Y
Y->next  = Ay

After:

Bx->next = Y
Y->next  = X        # Different
By->next = Ay       # Different
X->next  = Ay

The result values in the pointers are different, as shown. This means that there isn't a single mapping that works for both the "non-adjacent X and Y" and the "adjacent X and Y" cases — the pointer twizzling must be different.

Upvotes: 0

Related Questions