CODEWITHSUNDEEP
c#
Xphile1973
Xphile1973

Reputation: 1

swapping nodes in doubly linked list

Trying to swap the second and third nodes from a doubly linked list in c# with the following method:-

public static void swapNodes(List dblLinkList)
{
    Node tempnodeTwo = dblLinkList.firstNode.next;          //node two in list
    Node tempnodeThree = dblLinkList.firstNode.next.next;   //node three in list

    Node tempnodeFive = tempnodeTwo.previous;
    Node tempnodeSix = tempnodeThree.next;

    tempnodeThree.previous = tempnodeFive;
    tempnodeThree.next = tempnodeThree;
    tempnodeTwo.previous = tempnodeTwo;
    tempnodeTwo.next = tempnodeSix;
}

The following shows the output: The first is the original list and the second is the result of the method.

N:19:16 19:16:9 16:9:15 9:15:15 15:15:N
N:19:16 16:16:15 9:15:15 15:15:N

Where am I going wrong?? I have already studied previous questions about this topic which gave me the idea for the code but now stuck!

Upvotes: 0

Views: 370

Answers (3)

Hogan
Hogan

Reputation: 70523

well here in these lines

  tempnodeThree.next = tempnodeThree;
  tempnodeTwo.previous = tempnodeTwo;

you are setting the next of a node to itself and the previous of another to itself.

don't you mean

  tempnodeThree.next = tempnodeTwo;
  tempnodeTwo.previous = tempnodeThree;

I think you would have an easier time if you used better names.

I also would not implement this function like this -- I'd make the function suit it's name like this:

public static void swapNodes(Node a, Node b)
{
  if (a == null) return;
  if (b == null) return;

  Node afterA = a.next;
  Node beforeA = a.previous;

  a.previous = b.previous;
  if (b.previous != null) b.previous.next = a;
  a.next = b.next;
  if (b.next != null) b.next.previous = a;

  b.next = afterA;
  if (afterA != null) afterA.previous = b;
  b.previous = beforeA;
  if (beforeA != null) beforeA.next = b;
}

// call it like this
swapNodes(dblLinkList.firstNode.next, dblLinkList.firstNode.next.next);

Upvotes: 1

CSDev
CSDev

Reputation: 3235

Are you sure it's c#? Looks like java. C# has LinkedListNode<T> class, not Node. And LinkedListNode<T> has Next and Previous properties. With capitals. And they are read only.

Any way c# implementation looks like this:

using System;
using System.Collections.Generic;

namespace LinkedListSwap
{
    class Program
    {
        static void Main(string[] args)
        {
            var list = new LinkedList<string>(new[] { "1st", "2nd", "3rd", "4th", "5th", "6th", "7th" });
            Console.WriteLine(list.ToDisplayString());
            list.Swap(2, 3);
            Console.WriteLine(list.ToDisplayString());
        }
    }

    static class LinkedListExtensions
    {
        public static void Swap<T>(this LinkedList<T> list, int firstIndex, int secondIndex)
        {
            if (firstIndex < 1 || firstIndex > list.Count)
                throw new IndexOutOfRangeException($"Index out of range: {nameof(firstIndex)}");

            if (secondIndex < 1 || secondIndex > list.Count)
                throw new IndexOutOfRangeException($"Index out of range: {nameof(secondIndex)}");

            if (firstIndex == secondIndex)
                return;

            if (firstIndex > secondIndex)
                (firstIndex, secondIndex) = (secondIndex, firstIndex);

            int i = 0;

            var leftNode = list.First;
            while (++i < firstIndex)
                leftNode = leftNode.Next;

            var rightNode = leftNode.Next;
            while (++i < secondIndex)
                rightNode = rightNode.Next;

            list.Replace(leftNode, rightNode);
            list.Replace(rightNode, leftNode);
        }

        public static void Replace<T>(this LinkedList<T> list, LinkedListNode<T> oldNode, LinkedListNode<T> newNode)
        {
            list.AddAfter(oldNode, new LinkedListNode<T>(newNode.Value));
            list.Remove(oldNode);
        }

        public static string ToDisplayString<T>(this LinkedList<T> list) => string.Join(" ", list);
    }
}

Output is:

1st 2nd 3rd 4th 5th 6th 7th
1st 3rd 2nd 4th 5th 6th 7th

Upvotes: 0

heuristican
heuristican

Reputation: 294

It seems that you assume tempnodeThree is the third and tempnodeTwo is the second node of the linked list regardless of the changes you make but this is not the case.

After the initializations what you get is:

tempnodeFive <--> tempnodeTwo <--> tempnodeThree <--> tempnodeSix

And you need is:

tempnodeFive <--> tempnodeThree <--> tempnodeTwo <--> tempnodeSix

So what you have to change from left to right are:

tempNodeFive.next, tempNodeTwo.previous, tempNodeTwo.next, tempNodeThree.previous, tempNodeThree.next, tempNodeSix.previous

Let's go over them following the 2nd linked list representation:

tempNodeFive.next = tempNodeThree;
tempNodeTwo.previous = tempnodeThree;
tempNodeTwo.next = tempnodeSix;
tempNodeThree.previous = tempnodeFive;
tempNodeThree.next = tempnodeTwo;
tempNodeSix.previous = tempnodeTwo;

These six lines are what you need.

PS: You can reconsider variable names for a readable and maintainable code, esp. tempNodeFive and tempnodeSix because five and six does not make any sense as an index and it arises confusion while reading the code.

Upvotes: 1

Related Questions