Single Linked List – 单向链表
我们知道，STL的 List 实现的是一个双向链表。
除此之外呢，其实也有一个单向链表的实现，
Single Linked List 和 List 的主要区别还是在于内部实现，或者说，迭代器。
Single Linked List 提供的是Forward Iterator (单向迭代器)
List 提供的是 Bidirectional Iterator(双向迭代器)
所以 Single Linked List 的功能相比List还是少了许多，不过 Single Linked List 所耗的空间更小，某些操作更快。
Single Linked List 同List一样，插入(insert)、移除(erase)、结合(splice)等操作并不会导致原有的迭代器的失效。
当然，指向移除元素的迭代器肯定是会失效的。
还需要注意的是：STL一般规则插入元素是插入在前面，但是Single List没法快速定位前一个位置，这样会对效率产生很大的影响，所以，Single Linked List 提供的是 insert_after() 和 erase_after() 两个函数。
同样的，Single Linked List 不提供 push_back() 这样的从尾部插入的函数，只提供 push_front() 这样的函数，所以插入次序和元素次序会相反。 – 栈可以用单链表来实现。
Single Linked List 的节点：
相比List , Single Linked List 的节点设计稍复杂一些：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
//单向链表节点基本结构 struct __slist_node_bast { __slist_node_base* next; }; //单向链表节点结构 template<class T> struct __slist_node : public __slist_node_base { T data; }; //全局函数：已知某一节点，插入新节点于其后 inline __slist_node_base* __slist_make_list( __slist_node_base* prev_node, __slist_node_base* new_node) { new_node->next = prev_node->next; prev_node->next = new_node; return new_node; } inline size_t __slist_size(__slist_node_base* node) { size_t result = 0; for(; node != 0; node = node->next) +=result; return result; } |
Single Linked List 的迭代器：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
struct __slist_iterator_base { typedef size_t size_type; typedef ptrdiff_t difference_type; typedef forwad_iterator_tag iterator_category; //注意这里是单向的 __slist_node_base* node; //指向基本结构的指针 __slist_iterator_base(__list_node_base* x) : node(x){} void incr() { node = node->next; } //前进一个结点 bool operator==(const __slist_iterator_base& x) const { return node == x.node; } bool operator!=(const __slist_iterator_base& x) const { return node != x.node; } }; template <class T, class Ref, class Ptr> struct __slist_iterator : public __slist_iterator_base { typedef __slist_iterator<T, T&, T*> iterator; typedef __slist_iterator<T, const T&, const T*> const_iterator; typedef __slist_iterator<T, Ref, Ptr> self; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __slist_node<T> list_node; __slist_iterator(list_node* x) : __slist_iterator_base(x){} __slist_iterator() : __slist_iterator_base(0){} __slist_iterator(const iterator& x) : __slist_iterator_base(x.node) {} reference operator*() const { return ((list_node*)node)->data; } pointer operator->() const { return &(operator*()); } self& operator++() { incr(); return *this; } self operator++(int) { self tmp = *this; incr(); return tmp; } }; |
唯一要注意的就是是一个单向迭代器吧
Single Linked List 的数据结构：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
template <class T, class Alloc = alloc> class slist { public: typedef T value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef __slist_iterator<T, T&, T*> iterator; typedef __slist_iterator<T, const T&, const T*> const_iterator; private: typedef __slist_node<T> list_node; typedef __slist_node_base list_node_base; typedef __slist_iterator_base list_iterator_base; typedef simple_alloc<list_node, Alloc> list_node_allocator; static list_node* create_node(const value_type& x) { list_node* node = list_node_allocator::allocate(); //配置空间 __STL_TRY { construct(&node->data, x); //构造元素 node->next = 0; } __STL_UNWIND(list_node_allocator::deallocate(node)); return node; } static void destroy_node(list_node* node) { destroy(&node->data); //析构元素 list_node_allocator::deallocate(node); //释放空间 } private: list_node_base head; //头部，是一个实体 public: slist(){ head.next = 0; } ~slist() { clear(); } public: iterator begin() { return iterator((list_node*)head.next); } iterator end() { //注意这里返回的迭代器指向NULL return iterator(0); } size_type size() const { return __slist_size(head.next); } bool empty() const { return head.next == NULL; } //互换两个slist void swap(slist &L) { list_node_base *tmp = head.next; head.next = L.head.next; L.head.next = tmp; } public: //取头部元素 reference front() { return ((list_node*)head.next)->data; } void push_front(const value_type &x) { __slist_make_link(&head, create_node(x)); } //从头部取走元素 void pop_front() { list_node* node = (list_node*) head.next; head.next = node->next; destroy_node(node); } //... }; |
关系 Single Linked List：
本想测试元素操作的，但是我的Dev-CPP里面似乎没有 slist这个头文件，VS里面也没有。
于是便放弃了。
这个链表其实就是我们数据结构里面学的单链表。
【STL】SList