blob: 41461ff365e66fdbd568e2dcd3a96b7d212378ae [file] [log] [blame]
James Robinson646469d2014-10-03 15:33:28 -07001// 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_