1
\$\begingroup\$

I've just finished implementing a doubly-linked structure with random pointer and I am trying to see can we do better and would also like to address some lingering questions that I have.

Assignment

Suppose you're given a reference to the first node a linked structure described as follows:

private class Node {
   private String item;
   private Node next;
   private Node random;
}

Design a linear-time algorithm to create a copy of the doubly-linked structure. You may modifiy the original linked structure, but you must end up with two copies of the original.

So here's what I've taken from this spec:

  • API is not given (I always strive for smallest usable API that satisfies spec)
  • memory requirements are not given (I'll strive for the best possible result but also for clean and simple code. More precisely, I'd settle for O(n))
  • it doesn't impose any restrictions on how to pick random elements (more precisely, it doesn't forbid possible graph cycles in arbitrary depth from forming)

Post-implementation research found two major approaches:

  1. Create additional identical list during cloning ('hinging' the cloned one off of the original list) and through clever pointer massaging, split the two and return one of these as the cloned list (O(n) in time, O(1) in space)
  2. Use a HashMap and two passes over the list during cloning to first clone the list and then assign the random pointers using the HashMap (O(n) in time and space).

I found both approaches a bit confusing - it feels like clone() is too involved, and especially in 1), prone to nasty pointer-related bugs.

On the other hand, I've strived for clean, compact, fast and easy-to-read add() and clone() operations without pointer mess or two passes over the same data structure - at the expense of extra memory and sacrificing concurrency (I am maintaining a static HashMap). More precisely, add() is O(1) and clone() shoud be exactly O(n).

Discussion

While the implementation runs correctly for lists of about <= 100 elements and while I am reasonably confident the clone operation is indeed linear time, cloning scales really poorly (and varies wildly in execution time) and I am not sure why that is so. After running dozens of experiments and tests, empirical evidence suggests after 115 elements or so, cloning takes upward of 30 seconds (when I usually stop the test). For comparison, cloning 10 elements takes the order of 10-100 ms and cloning 100 elements anywhere from 500-4000 ms.

Unless I am not seeing a glaring super-quadratic algorithm, the only explanation I can think of is that larger element sets tend to form cycles more quickly and randomly, so the recursive clone() gets stuck in loop - but this is just a conjecture which I am not sure how to prove (except brute force).

There are ways to detect cycles in linked lists (e.g. Floyd's algorithm variations) but the assignment doesn't even mention these and I certainly don't think implementing such cycle detection would be in the spirit of this exercise.

I am also aware that my recursive clone() would fail with SOE for large collections with languages without tail-recursion optimisations (i.e. Java) but rewriting the method to iterative approach doesn't seem difficult.

Questions

  1. Is there a lingering quadratic behavior in my implementation?
  2. Is there a better way to test the clone() than relying on String comparison as I have done? I could compute a hash and compare that but that is just a variation on the same theme. I am trying to hide as much implementation details as possible - so any Node leaking, I would dislike.
  3. Is such a data structure ever useful? Save for perhaps cryptography, I can't imagine a use case for it - but surely, there are far better crypto-algorithms available.

Code

Test

public class RandomLinkedListTest {

    @Test
    public void test() {
        RandomLinkedList<Integer> linkedList = new RandomLinkedList<>();
        assertTrue(linkedList.isEmpty());

        for (int i = 0; i < 10; i++) linkedList.add(i);

        assertFalse(linkedList.isEmpty());
        assertEquals(10, linkedList.size());

        String original = stringTraceOf(linkedList);

        RandomLinkedList<Integer> clonedList = linkedList.cloneLinkedList();
        String cloned = stringTraceOf(clonedList);
        assertEquals(original, cloned);
    }

    private String stringTraceOf(RandomLinkedList<Integer> list) {
        return StreamSupport.stream(list.spliterator(), false)
                .collect(Collectors.joining("\n"));
    }
}

Data structure

public class RandomLinkedList<T> implements Iterable<String> {
    private static Map<Integer, Node<?>> cache = new HashMap<>();
    private Node<T> first;

    private int count = 0;
    private Random random = new Random();

    public void add(T item) {
        Node<T> oldFirst = first;
        Node<T> node;

        if (isEmpty())
            node = Node.firstNodeOf(item);
        else
            node = Node.nextNodeOf(item, oldFirst, getRandomNode());

        cache.put(node.index, node);
        first = node;
        count++;
    }

    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public RandomLinkedList<T> cloneLinkedList() {
        Node<T> clone = first.cloneNode();
        RandomLinkedList<T> clonedList = new RandomLinkedList<>();
        clonedList.first = clone;
        clonedList.count = count;
        return clonedList;
    }

    @SuppressWarnings("unchecked")
    private Node<T> getRandomNode() {
        Node<T> randomNode = (Node<T>) cache.get(random.nextInt(count));
        if (randomNode != null) return randomNode;
        throw new IllegalStateException("Cannot find random node.");
    }

    @Override
    // produces test output string
    public Iterator<String> iterator() {
        return new Iterator<String>() {
            private Node<T> current = first;
            private int N = count;

            @Override
            public boolean hasNext() {
                return N > 0;
            }

            @Override
            public String next() {
                if (!hasNext()) throw new IllegalStateException();
                String result = current.toString();
                current = current.next;
                N--;
                return result;
            }
        };
    }

    private static class Node<Item> {
        private int index;
        private Item item;
        private Node<Item> next;
        private Node<Item> random;

        private Node(int idx, Item payload, Node<Item> nextNode, Node<Item> randomNode) {
            index = idx;
            item = payload;
            next = nextNode;
            random = randomNode;
        }

        private static <V> Node<V> firstNodeOf(V item) {
            return new Node<>(0, item, null, null);
        }

        private static <V> Node<V> nextNodeOf(V item, Node<V> nextNode, Node<V> randomNode) {
            return new Node<>(nextNode.index + 1, item, nextNode, randomNode);
        }

        private static <V> Node<V> empty() {
            return new Node<>(-1, null, null, null);
        }

        private Node<Item> cloneNode() {
            if (next == null) return this;
            Node<Item> clone = Node.empty();
            clone.index = index;
            clone.item = item;
            clone.next = next.cloneNode();
            clone.random = random.cloneNode();
            return clone;
        }

        @Override
        public String toString() {
            return String.format("Node (index: %s, item: %s, next item: %s, random item: %s)", index, item, next == null ? "null" : next.item, random == null ? "null" : random.item);
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.