1 // Copyright (c) 2009 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef BASE_LINKED_LIST_H_ 6 #define BASE_LINKED_LIST_H_ 7 8 // Simple LinkedList type. (See the Q&A section to understand how this 9 // differs from std::list). 10 // 11 // To use, start by declaring the class which will be contained in the linked 12 // list, as extending LinkNode (this gives it next/previous pointers). 13 // 14 // class MyNodeType : public LinkNode<MyNodeType> { 15 // ... 16 // }; 17 // 18 // Next, to keep track of the list's head/tail, use a LinkedList instance: 19 // 20 // LinkedList<MyNodeType> list; 21 // 22 // To add elements to the list, use any of LinkedList::Append, 23 // LinkNode::InsertBefore, or LinkNode::InsertAfter: 24 // 25 // LinkNode<MyNodeType>* n1 = ...; 26 // LinkNode<MyNodeType>* n2 = ...; 27 // LinkNode<MyNodeType>* n3 = ...; 28 // 29 // list.Append(n1); 30 // list.Append(n3); 31 // n3->InsertBefore(n3); 32 // 33 // Lastly, to iterate through the linked list forwards: 34 // 35 // for (LinkNode<MyNodeType>* node = list.head(); 36 // node != list.end(); 37 // node = node->next()) { 38 // MyNodeType* value = node->value(); 39 // ... 40 // } 41 // 42 // Or to iterate the linked list backwards: 43 // 44 // for (LinkNode<MyNodeType>* node = list.tail(); 45 // node != list.end(); 46 // node = node->previous()) { 47 // MyNodeType* value = node->value(); 48 // ... 49 // } 50 // 51 // Questions and Answers: 52 // 53 // Q. Should I use std::list or base::LinkedList? 54 // 55 // A. The main reason to use base::LinkedList over std::list is 56 // performance. If you don't care about the performance differences 57 // then use an STL container, as it makes for better code readability. 58 // 59 // Comparing the performance of base::LinkedList<T> to std::list<T*>: 60 // 61 // * Erasing an element of type T* from base::LinkedList<T> is 62 // an O(1) operation. Whereas for std::list<T*> it is O(n). 63 // That is because with std::list<T*> you must obtain an 64 // iterator to the T* element before you can call erase(iterator). 65 // 66 // * Insertion operations with base::LinkedList<T> never require 67 // heap allocations. 68 // 69 // Q. How does base::LinkedList implementation differ from std::list? 70 // 71 // A. Doubly-linked lists are made up of nodes that contain "next" and 72 // "previous" pointers that reference other nodes in the list. 73 // 74 // With base::LinkedList<T>, the type being inserted already reserves 75 // space for the "next" and "previous" pointers (base::LinkNode<T>*). 76 // Whereas with std::list<T> the type can be anything, so the implementation 77 // needs to glue on the "next" and "previous" pointers using 78 // some internal node type. 79 80 namespace base { 81 82 template <typename T> 83 class LinkNode { 84 public: LinkNode()85 LinkNode() : previous_(0), next_(0) {} LinkNode(LinkNode<T> * previous,LinkNode<T> * next)86 LinkNode(LinkNode<T>* previous, LinkNode<T>* next) 87 : previous_(previous), next_(next) {} 88 89 // Insert |this| into the linked list, before |e|. InsertBefore(LinkNode<T> * e)90 void InsertBefore(LinkNode<T>* e) { 91 this->next_ = e; 92 this->previous_ = e->previous_; 93 e->previous_->next_ = this; 94 e->previous_ = this; 95 } 96 97 // Insert |this| into the linked list, after |e|. InsertAfter(LinkNode<T> * e)98 void InsertAfter(LinkNode<T>* e) { 99 this->next_ = e->next_; 100 this->previous_ = e; 101 e->next_->previous_ = this; 102 e->next_ = this; 103 } 104 105 // Remove |this| from the linked list. RemoveFromList()106 void RemoveFromList() { 107 this->previous_->next_ = this->next_; 108 this->next_->previous_ = this->previous_; 109 } 110 previous()111 LinkNode<T>* previous() const { 112 return previous_; 113 } 114 next()115 LinkNode<T>* next() const { 116 return next_; 117 } 118 119 // Cast from the node-type to the value type. value()120 const T* value() const { 121 return static_cast<const T*>(this); 122 } 123 value()124 T* value() { 125 return static_cast<T*>(this); 126 } 127 128 private: 129 LinkNode<T>* previous_; 130 LinkNode<T>* next_; 131 }; 132 133 template <typename T> 134 class LinkedList { 135 public: 136 // The "root" node is self-referential, and forms the basis of a circular 137 // list (root_.next() will point back to the start of the list, 138 // and root_->previous() wraps around to the end of the list). LinkedList()139 LinkedList() : root_(&root_, &root_) {} 140 141 // Appends |e| to the end of the linked list. Append(LinkNode<T> * e)142 void Append(LinkNode<T>* e) { 143 e->InsertBefore(&root_); 144 } 145 head()146 LinkNode<T>* head() const { 147 return root_.next(); 148 } 149 tail()150 LinkNode<T>* tail() const { 151 return root_.previous(); 152 } 153 end()154 const LinkNode<T>* end() const { 155 return &root_; 156 } 157 158 private: 159 LinkNode<T> root_; 160 }; 161 162 } // namespace base 163 164 #endif // BASE_LINKED_LIST_H_ 165