Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8239066

make LinkedList<T> more generic



    • Enhancement
    • Resolution: Fixed
    • P4
    • 15
    • 15
    • hotspot
    • b12
    • generic
    • generic


      utilities/linkedlist.hpp defines an abstract class and 2 implementations(LinkedListImpl, SortedLinkedList).

      I found it's not easy to reuse those classes. here are the problem I met.
      1. equals() is intrusive in LinkedListImpl::find_node. We can't put any primitive type in the container or any class with equals()

      The following example won't compile.
        LinkedListImpl<int> il;

      I think we should move find & find_node out of LinkedList. linkedlist.hpp can provide template functions find & find_node. comparator is a template argument.

      2. LinkedList doesn't define virtual destructor.
      it will cause undefined behavior if users delete subclasses via base ptr.
      It violates item7: declare destructors virtual in polymorphic base classes in effective c++.

        typedef LinkedListImpl<Integer, ResourceObj::C_HEAP, mtTest> list_t;
        LinkedList<Integer>* list = new(ResourceObj::C_HEAP, mtTest) list_t();
        EXPECT_EQ(list->size(), (size_t)2);
        EXPECT_EQ(list->size(), (size_t)0);

      3. allow wrong behavior copy constructor or assignment operator.
      the following code snippet compile but will get runtime error. it's because nodes are frozen twice.

        typedef LinkedListImpl<Integer, ResourceObj::C_HEAP, mtTest> list_t;
        list_t a;
        list_t b(a);
        EXPECT_EQ(b.size(), (size_t)1);

      NONCOPYABLE solves this problem. LinkedList provides move(), which can safely move nodes from one to another.

      4. LinkedListIterator::is_empty is error-prone.
      it won't update along iterations. The following test is broken.

        // pop 2
        e = it.next();
        // pop 1
        e = it.next();

      5. it's not practical to return const E* only from the iterator.
      the container may store mutable objects.
      one simple approach is drop this const qualifier. or define two versions of next() and mark _p mutable.
        mutable LinkedListNode<E>* _p;
        E* next() {
          if (_p == NULL) return NULL;
          E* e = _p->data();
          _p = _p->next();
          return e;

        const E* next() const {
          if (_p == NULL) return NULL;
          const E* e = _p->peek();
          _p = _p->next();
          return e;




            xliu Xin Liu
            xliu Xin Liu
            1 Vote for this issue
            2 Start watching this issue