What is wrong with this linked list?

Question

The assignment was to write a function to swap 2 nodes in the list. If the function could swap the nodes regardless of the order, a 10% was awarded. I think my implementation is able to swap 2 elements regardless of the order in the list but I still did not received the bonus marks. Is there anything that I am missing?

I was given a generic node class,

public class Node<T> {
    public T val;
    public Node<T> next;

    public Node(T val) {
        this.val = val;
        this.next = null;
    }
}

I was also given an interface defined as below,

public interface SwapList<T> {

    public void add(T val);

    /**
     * Swaps two elements in the list, but only if @param val1 comes BEFORE @param
     * val2. Solve the problem regardless of the order, for 10% extra. list: A B
     * C -> swap(A,B) will result in the list B A C list: A B C -> swap(B,A)
     * will not swap. list: A C C -> swap(A, D) will throw a
     * NoSuchElementException list: A B C B -> swap (A, B) will result in the
     * list B A C B list: A B C A B B -> swap (A,B) will result in the list B A
     * C A B B a list with one or zero elements cannot do a swap
     */
    public void swap(T val1, T val2);

    public T get(int i);
}

and I have my own implementation of this interface as below,

import java.util.NoSuchElementException;
public class SwapListImpl<T> implements SwapList<T> {

    private Node<T> head;
    private Node<T> tail;
    private int counter;

    public SwapListImpl() {
        head = null;
        tail = null;
        counter = 0;
    }

    @Override
    public void add(T val) {
        Node<T> node = new Node<T>(val);
        if (head == null) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = node;
        }

        counter++;
    }

    @Override
    public void swap(T val1, T val2) {

        if (counter < 2 || val1.equals(val2))
            return;

        Node<T> current = head;
        Node<T> currentPrev = null;

        Node<T> first = head;
        Node<T> firstPrev = null;
        Node<T> firstNext = first.next;

        Node<T> second = head;
        Node<T> secondPrev = null;
        Node<T> secondNext = second.next;

        boolean foundFirst = false;
        boolean foundSecond = false;
        boolean inOrder = false;

        while (current != null) {
            if (!foundFirst && current.val.equals(val1)) {

                firstPrev = currentPrev;
                first = current;
                firstNext = current.next;

                if (!foundSecond)
                    inOrder = true;

                foundFirst = true;

            }

            if (!foundSecond && current.val.equals(val2)) {

                secondPrev = currentPrev;
                second = current;
                secondNext = current.next;

                if (foundFirst)
                    inOrder = true;

                foundSecond = true;
            }

            if (foundFirst && foundSecond) {

                if (!inOrder) {
                    Node<T> temp = first;
                    first = second;
                    second = temp;

                    temp = firstPrev;
                    firstPrev = secondPrev;
                    secondPrev = temp;

                    temp = firstNext;
                    firstNext = secondNext;
                    secondNext = temp;
                }

                if (firstPrev == null) {

                    head = second;

                    if (first == secondPrev) {
                        second.next = first;
                        first.next = secondNext;
                    } else {
                        second.next = firstNext;
                        secondPrev.next = first;
                        first.next = secondNext;
                    }
                } else {

                    firstPrev.next = second;
                    first.next = secondNext;

                    if (first == secondPrev) {
                        second.next = first;
                    } else {
                        second.next = firstNext;
                        secondPrev.next = first;
                    }
                }

                break;
            }

            currentPrev = current;
            current = current.next;
        }

        if (!foundFirst || !foundSecond) {
            throw new NoSuchElementException();
        }
    }

    @Override
    public T get(int i) {
        if (i < counter) {
            Node<T> node = head;
            for (int n = 0; n < i; n++) {
                node = node.next;
            }
            return node.val;
        } else {
            throw new IndexOutOfBoundsException();
        }
    }
 }   

Answer 1

I think the problem is the swap itself: you forgot to set the tail.

Here is a small test for exactly that problem:

@Test
public void test() {
  SwapListImpl<String> list = new SwapListImpl<String>();
  list.add("A");
  list.add("B");
  list.add("C");

  list.swap("A", "C");

  assertEquals("C", list.get(0));
  assertEquals("C", list.getHead().val);
  assertEquals("B", list.get(1));
  assertEquals("A", list.get(2));
  assertEquals("A", list.getTail().val);

  list.add("D");

  assertEquals("C", list.get(0));
  assertEquals("C", list.getHead().val);
  assertEquals("B", list.get(1));
  assertEquals("A", list.get(2));
  assertEquals("D", list.get(3));
  assertEquals("D", list.getTail().val);

  list.swap("A", "C");

  assertEquals("A", list.get(0));
  assertEquals("A", list.getHead().val);
  assertEquals("B", list.get(1));
  assertEquals("C", list.get(2));
  assertEquals("D", list.get(3));
  assertEquals("D", list.getTail().val);

  list.swap("C", "B");

  assertEquals("A", list.get(0));
  assertEquals("A", list.getHead().val);
  assertEquals("C", list.get(1));
  assertEquals("B", list.get(2));
  assertEquals("D", list.get(3));
  assertEquals("D", list.getTail().val);
}

You see I added two methods to the list, for getting the head and tail, but that's not important - the test would even fail without the explicit test for head and tail. The extra methods for the list are really simple:

  public Node<T> getTail() {
      return this.tail;
    }

    public Node<T> getHead() {
      return this.head;
    }

The problem of not setting tail occurs when swapping the last element of the list and then adding another element.

Here is a fixed version of the actual swap:

  if (foundFirst && foundSecond) {

    if (second == this.tail) {
      this.tail = first;
    } else if (first == this.tail) {
      this.tail = second;
    }

    if (first == this.head) {
      this.head = second;
    } else if (second == this.head) {
      this.head = first;
    }

    if (firstPrev == second) {
      first.next = second;
    } else {
      if (firstPrev != null) {
        firstPrev.next = second;
      }
      first.next = secondNext;
    }
    if (secondPrev == first) {
      second.next = first;
    } else {
      if (secondPrev != first && secondPrev != null) {
        secondPrev.next = first;
      }
      second.next = firstNext;
    }
    break;
  }

You see I didn't add lines to your code - instead I wrote the code in another way. I think it's more readable, but you also can try just to set the tail in the correct way. But it was too complex for me, so I reduced the complexity of that code - that's the reason why I rewrote it.

I would suggest, that you use first and second for the first/second occurence and not for the first/second argument. I think that would improve the readability of the method. But that's another point ;-)

Hope that helps - so the order IMHO is not the problem, but the tail.