What is wrong with this linked list?

Question

The purpose was to write a function to replace two nodes in the list. If the function could replace the nodes regardless of the order, 10% was awarded. I think that my implementation is able to exchange 2 elements regardless of the order in the list, but I still have not received bonus points. Is there something I am missing?

I was given a generic class node,

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

I was also provided with the interface defined 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: AB * C -> swap(A,B) will result in the list BAC list: ABC -> swap(B,A) * will not swap. list: ACC -> swap(A, D) will throw a * NoSuchElementException list: ABCB -> swap (A, B) will result in the * list BACB list: ABCABB -> swap (A,B) will result in the list BA * CABB 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 shown 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: you forgot to install the tail.

Here is a little test for this 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 that I added two methods to the list to get the head and tail, but it doesn’t matter - the test will even end without an explicit test for the head and tail. Additional methods for the list are very simple:

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

The problem of not setting the tail occurs when replacing 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 that I did not add lines to your code, instead I wrote the code differently. I think this is more readable, but you can also try installing the tail correctly. But it was too complicated for me, so I reduced the complexity of this code - that’s why I rewrote it.

I would suggest that you use the first and second for the first / second occurrence, and not for the first / second argument. I think this will improve the readability of the method. But this is another point; -)

I hope that helps - so the IMHO order is not a problem, but a tail.