1

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?

hippietrail
  • 14,735
  • 16
  • 96
  • 147
powerboy
  • 9,823
  • 17
  • 58
  • 92
  • 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 '10 at 03: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 '10 at 03:47

3 Answers3

8

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

Greg Hewgill
  • 890,778
  • 177
  • 1,125
  • 1,260
  • 2
    It appears that there is an `slist` in some vendor implementations of the STL, but not in the C++ Standard Library. – Greg Hewgill May 10 '10 at 02:58
5

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)

Community
  • 1
  • 1
manlio
  • 17,446
  • 14
  • 72
  • 116
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;
}
Stephen
  • 45,698
  • 7
  • 58
  • 67
  • 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 '10 at 03:10