StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhat is wrong with this linked list?
text
Body
copied!<p>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?</p> <p>I was given a generic node class,</p> <pre><code>public class Node<T> { public T val; public Node<T> next; public Node(T val) { this.val = val; this.next = null; } } </code></pre> <p>I was also given an interface defined as below,</p> <pre><code>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); } </code></pre> <p>and I have my own implementation of this interface as below,</p> <pre><code>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(); } } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload