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