NPE after tLinkedList.removeFirst()

Issue #22 invalid
Maximilian Ammann created an issue

Example:

        TLinkedList list = new TLinkedList();

        TLinkableAdapter linkable1 = new TLinkableAdapter() {
        };
        TLinkableAdapter linkable2 = new TLinkableAdapter() {
        };
        TLinkableAdapter linkable3 = new TLinkableAdapter() {
        };

        list.add(linkable1);
        list.add(linkable2);
        list.add(linkable3);
        list.add(linkable1);
        list.add(linkable2);
        list.add(linkable3);

        list.removeFirst();
        list.removeFirst();
        list.removeFirst();

        System.out.println(list.get(0));
        System.out.println(list.get(1));
        System.out.println(list.get(2));

        list.toString();

The output is:

net.catharos.engine.core.util.structures.TopologicalSort$1@a62812d
null
net.catharos.engine.core.util.structures.TopologicalSort$3@490eb6ae
Exception in thread "main" java.lang.NullPointerException
    at gnu.trove.list.linked.TLinkedList$IteratorImpl.next(TLinkedList.java:703)
    at gnu.trove.list.linked.TLinkedList$IteratorImpl.next(TLinkedList.java:613)
    at java.util.AbstractCollection.toString(AbstractCollection.java:449)
    at net.catharos.engine.core.util.structures.TopologicalSort.main(TopologicalSort.java:94)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:606)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120)

So after the removeFirst() statements somehow the second entry becomes null.

Comments (10)

  1. Rob Eden

    Oh wait, the problem is that you're adding the same Linkable item twice, which won't work.

    When you add "linkable1" the second time, it's still stored as the head but it's now also added as the tail and its previous entry is now pointing at linkable3. And so on...

    When the first remove is performed, linkable1's "next" pointer is nulled and it's removed as the head, but it still exists in the "next" pointer for linkable3.

    We could potentially prevent this by either:

    1. Crawling through all the elements in the list to ensure the element doesn't already exist (very expensive)
    2. Tracking an extra field with the list the element belongs to (not totally reliable, requires API change and also a slight performance hit)

    None of those are really good options, IMO, so for the moment I think I'd have to leave it with "don't do that".

    If you disagree or have another idea for a solution, please comment on the bug and we'll discuss more.

  2. Maximilian Ammann reporter

    I'll think about a solution tomorrow, but it definitely needs to be fixed. For example if I use the default java LinkedList it works. But this should work, a linked list should be able to contain the same object twice.

  3. Rob Eden

    Sorry, I disagree. This implementation is solving additional problems beyond what java.util.LinkedList is, namely not allocating temporary objects. In addition the limitations are detailed in the class docs:

    • the same object cannot be put into more than one list at the same time.
    • the same object cannot be put into the same list more than once at the same time.
    • objects must only be removed from list they are in. That is, if you have an object A and lists l1 and l2, you must ensure that you invoke List.remove(A) on the correct list.
    • It is also forbidden to invoke List.remove() with an unaffiliated TLinkable (one that belongs to no list): this will destroy the list you invoke it on.
  4. Rob Eden

    I should also note that this doesn't mean you can't stick the same data in the list multiple times. If you are using wrapper nodes for the Linkable implementations, you can point to the same object with different wrappers. Example:

     Linkable1   Linkable2  Linkable3
         |           |          |
         |           v          |
         |        Value2        |
         v                     /
      Value1 <----------------
    
  5. Log in to comment