2

Seems that there is only doubly linked list (but no singly linked list) in the C++ standard library, right? Is there any widely-used C++ libraries with singly linked list?

2
  • 1
    Is there any reason to care what the underlying implementation is as long as it acts like a linked list? Just curious...
    – D.Shawley
    May 10, 2010 at 3:26
  • 1
    @D.Shawley: I only need singly linked list in most cases, so I do not want the overhead imposed by doubly linked list.
    – powerboy
    May 10, 2010 at 3:47

3 Answers 3

8

There is the slist class from Boost that is a singly linked list implementation.

1
  • 2
    It appears that there is an slist in some vendor implementations of the STL, but not in the C++ Standard Library. May 10, 2010 at 2:58
7

Just for reference...

Time has passed and C++11 has brought us the std::forward_list container that is implemented as a singly-linked list and essentially does not have any overhead compared to its implementation in C.

Compared to std::list this container provides more space efficient storage when bidirectional iteration is not needed.

Warning: missing push_back method (std::forward_list and std::forward_list::push_back)

3

There is slist, which is an SGI extension (__gnu_cxx::slist)

#include <iostream>
#include <iterator>
#include <ext/slist>

int main(int argc, char** argv) {
  __gnu_cxx::slist<int> sl;
  sl.push_front(1);
  sl.push_front(2);
  sl.push_front(0);
  std::copy(sl.begin(), sl.end(),  // The output is 0 2 1
            std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
  return 0;
}
1
  • I prefer this answer because I prefer not to importing another library, though Greg Hewgill's answer is also correct. Thx guys!
    – powerboy
    May 10, 2010 at 3:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.