How to deserialize a JSON array to a singly linked list by using Jackson

[Frank Dai]

I want to deserialize a JSON array to a singly linked list in Java.

The definition of singly linked list is as the following:

public class SinglyLinkedListNode<T> {
    public T value;
    public SinglyLinkedListNode next;
    public SinglyLinkedListNode(final T value) {
        this.value = value;
    }
}

How to deserialize a JSON string such as [1,2,3,4,5] in to a singly linked list?

public void typeReferenceTest() throws IOException {
    ObjectMapper objectMapper = new ObjectMapper();

    final ArrayList<Integer> intArray = objectMapper.readValue("[1,2,3,4,5]",
        new TypeReference<ArrayList<Integer>>() {});
    System.out.println(intArray);

    // How to achieve this?
    final ArrayList<Integer> intList = objectMapper.readValue("[1,2,3,4,5]",
        new TypeReference<SinglyLinkedListNode<Integer>>() {});
    System.out.println(intList);
}

[Tatu Saloranta]

Probably by a custom deserializer. There just isn't anything similar, structurally, between an Array of numbers, and a POJO like one you have.

-+ Tatu +-

--
You received this message because you are subscribed to the Google Groups "jackson-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jackson-user...@googlegroups.com.
To post to this group, send email to jackso...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Frank Dai]

A deserializer extending JsonDeserializer may help, but not enough.

For example, what happens if I want to deserialize [[1,2,3], [4,5,6]] into a ArrayList<SinglyLinkedListNode<Integer>> ?

In one word, I want that the SinglyLinkedList can be used in all kinds of combinations with map and list, just like ArrayList.

[Frank Dai]

When I read the source code I found a class com.fasterxml.jackson.databind.deser.std.ArrayBlockingQueueDeserializer, maybe this is a  clue

[Tatu Saloranta]

What you are trying to do is basically structural transformation, at least from Jackson's perspective.

Jackson tries to stay away from just 2 things:

1. (Schema) Validation

2. Structural transformations

partly because these are both quicksand style traps, as amount of variation is infinite.

Now: structurally what JSON has is an array. What you are asking is to bind that to a POJO.

These are not compatible by default. That logically what you represent is a List is irrelevant unless you actually implement java.util.Collection, in which case Jackson knows how to do the mapping.

To add to the problem, however, you are using a generically typed class. Jackson has no way of knowing meaning of your type parameter, and it will be ignored.

If you register a custom deserializer, however, you get access to type definition, and you can figure out type parameter to use for deserialization (via TypeFactory.findTypeParametersFor(...), or whatever the name of the method is).

Without generic type parameter, you could perhaps use a static factory method in node class itself, to let Jackson first bind contents as, say, Collection<Integer> or int[], and then construct nodes. But that type parameterization makes this a very much custom case.

-+ Tatu +-

[Frank Dai]

But Since Jackson can deserialize an JSON array(e.g., [1,2,3,4,5]) to an ArrayList:

final ArrayList<Integer> intArray = objectMapper.readValue("[1,2,3,4,5]", new TypeReference<ArrayList<Integer>>() {});

I think there must be a way to deserialize an JSON array to an user defined singly linked list:

final ArrayList<Integer> intList = objectMapper.readValue("[1,2,3,4,5]", new TypeReference<SinglyLinkedListNode<Integer>>() {});

[Tatu Saloranta]

What you are asking is a Java class named `SinglyLinkedListNode` which does not implement `java.util.List` or `java.util.Collection`. That does not look like a List or Collection to Jackson; it just a POJO with getters, setters and fields.

If it did implement one of those interfaces and had a no-arguments constructor, yes, it could be deserialized automatically.

-+ Tatu +-

[Frank Dai]

@Tatu You’re right, after I make the SinglyLinkedListNode implement java.util.List, Jackson can automatically deserialize a JSON array into a singly linked list. The code of SinglyLinkedListNode is as the following:

import java.util.*;
import java.util.function.Consumer;

/**
 * Singly Linked List.
 *
 * <p>As to singly linked list, a node can be viewed as a single node,
 * and it can be viewed as a list too.</p>
 *
 * @param <E> the type of elements held in this collection
 * @see java.util.LinkedList
 */
public class SinglyLinkedListNode<E>
    extends AbstractSequentialList<E>
    implements Cloneable, java.io.Serializable {
    public E value;
    public SinglyLinkedListNode<E> next;

    /**
     * Constructs an empty list.
     */
    public SinglyLinkedListNode() {
        value = null;
        next = null;
    }

    /**
     * Constructs an list with one elment.
     */
    public SinglyLinkedListNode(final E value) {
        this.value = value;
        next = null;
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public SinglyLinkedListNode(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final SinglyLinkedListNode<E> l = last();
        final SinglyLinkedListNode<E> newNode = new SinglyLinkedListNode<>(e);
        if (l == null)
            this.value = e;
        else
            l.next = newNode;
        modCount++;
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, SinglyLinkedListNode<E> succ) {
        assert succ != null;
        final SinglyLinkedListNode<E> prev = this.previous(succ);
        final SinglyLinkedListNode<E> newNode = new SinglyLinkedListNode<>(e);
        if (prev == null)
            this.value = e;
        else
            prev.next = newNode;
        modCount++;
    }

    /**
     * Return the node before x.
     *
     * @param x current node
     * @return the node before x
     */
    private SinglyLinkedListNode<E> previous(final SinglyLinkedListNode<E> x) {
        assert (x != null);
        if (size() < 2)  return null;
        if (this == x) return null;

        SinglyLinkedListNode<E> prev = new SinglyLinkedListNode<>();
        prev.next = this;
        SinglyLinkedListNode<E> cur = this;
        while (cur != x) {
            prev = prev.next;
            cur = cur.next;
        }
        return prev;
    }

    /**
     * Return the last node.
     * @return the last node.
     */
    private SinglyLinkedListNode<E> last() {
        if (size() == 0) return null;
        if (size() == 1) return this;

        SinglyLinkedListNode<E> prev = new SinglyLinkedListNode<>();
        prev.next = this;
        SinglyLinkedListNode<E> cur = this;
        while (cur != null) {
            prev = prev.next;
            cur = cur.next;
        }
        return prev;
    }

    /**
     * Unlinks non-null node x.
     */
    E unlink(SinglyLinkedListNode<E> x) {
        assert x != null;
        final E element = x.value;
        final SinglyLinkedListNode<E> next = x.next;
        final SinglyLinkedListNode<E> prev = previous(x);

        if (prev == null) {
            this.value = next.value;
            this.next = next.next;
        } else {
            prev.next = next;
        }

        x.next = null;

        modCount++;
        return element;
    }

    /**
     * @inheritDoc
     */
    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }


    private class ListItr implements ListIterator<E> {
        private SinglyLinkedListNode<E> lastReturned;
        private SinglyLinkedListNode<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            assert isPositionIndex(index);
            next = (index == size()) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size();
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.value;
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        public E previous() {
            throw new UnsupportedOperationException();
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }

        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            unlink(lastReturned);

            nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.value = e;
        }

        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size()) {
                action.accept(next.value);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    /**
     * @inheritDoc
     */
    public int size() {
        int size = 0;
        if (value == null) return size;

        SinglyLinkedListNode<E> cur = this;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        return size;
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * Returns the (non-null) Node at the specified element index.
     */
    SinglyLinkedListNode<E> node(int index) {
        assert isElementIndex(index);

        SinglyLinkedListNode<E> x = this;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    }

    /**
     * Tells if the argument is the index of an existing element.
     */
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size();
    }

    /**
     * Tells if the argument is the index of a valid position for an
     * iterator or an add operation.
     */
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size();
    }

    /**
     * Constructs an IndexOutOfBoundsException detail message.
     * Of the many possible refactorings of the error handling code,
     * this "outlining" performs best with both server and client VMs.
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: " + size();
    }
}

Here is the unit test code:

@Test public void typeReferenceTest() throws IOException {
    ObjectMapper objectMapper = new ObjectMapper();

    final SinglyLinkedListNode<Integer> intList = objectMapper.readValue("[1,2,3,4,5]",
        new TypeReference<SinglyLinkedListNode<Integer>>() {});
    System.out.println(intList);

    final ArrayList<SinglyLinkedListNode<Integer>> arrayOfList = objectMapper.readValue("[[1,2,3], [4,5,6]]",
        new TypeReference<ArrayList<SinglyLinkedListNode<Integer>>>() {});
    System.out.println(arrayOfList);
}

[Tatu Saloranta]

Ok good. Yes, that works.

-+ Tatu +-

[Frank Dai]

One more question, can I implement a subclass of StdDeserializer to deserialize a String to a SinglyLinkedListNode<E> ?

...

[Tatu Saloranta]

Yes, if the goal is to allow deserialization from JSON String into SinglyLinkedListNode<E>.

That would need to be registered for type `SinglyLinkedListNode`, however, and may get problematic if you want to allow deserialization both from a JSON Array (default), and from a String.

-+ Tatu +-

--