Can you show an example of linked list data structure without pointers?

lmm · on May 10, 2018

My C++ is rusty but you'd do it exactly like you do in ML. Something like:

    template<typename T> class List<T> {
      protected:
        List();
      template<typename U> class Visitor<U> {
        public:
          U visitNil();
          U visitCons(T current, U accumulator);
      }
      public:
        virtual <U> U visit(Vistor<U> visitor);
    }
    template<typename T> class Nil<T> extends List<T> {
      U visit(Visitor<U> visitor) = visitor.visitNil();
    }
    template<typename T> class Cons<T> extends List<T> {
      private:
        T head;
        List<T> &tail;
      public:
        Cons(T head, List<T> &tail) {
          this.head = head;
          this.tail = tail;
        }
      U visit(Visitor<U> visitor) = visitor.visitCons(head, tail.visit(visitor));
    }

vbezhenar · on May 11, 2018

Thanks, that neat. But how would you build a list of arbitrary length and free it later? You'll use pointers, one way or another. The only way to avoid pointers I could imagine is to use stack with recursion, but that's completely crazy and limited programming style.

jcelerier · on May 10, 2018

In more than ten years of programming in C++ I never had once to implement a linked list. That's 100% irrelevant to programming practice. The only reason to implement one is whether it's for academic purposes, else just use `std::{s,}list`.

vbezhenar · on May 11, 2018

Using std::list which uses pointers is using pointers.

jcelerier · on May 11, 2018

... no it's not. Else by that logic you'd be using pointers through any programming language.