linked_list.h revision c7f5f8508d98d5952d42ed7648c2a8f30a4da156 
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
80namespace base {
81
82template <typename T>
83class LinkNode {
84 public:
85  LinkNode() : previous_(0), next_(0) {}
86  LinkNode(LinkNode<T>* previous, LinkNode<T>* next)
87      : previous_(previous), next_(next) {}
88
89  // Insert |this| into the linked list, before |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|.
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.
106  void RemoveFromList() {
107    this->previous_->next_ = this->next_;
108    this->next_->previous_ = this->previous_;
109  }
110
111  LinkNode<T>* previous() const {
112    return previous_;
113  }
114
115  LinkNode<T>* next() const {
116    return next_;
117  }
118
119  // Cast from the node-type to the value type.
120  const T* value() const {
121    return static_cast<const T*>(this);
122  }
123
124  T* value() {
125    return static_cast<T*>(this);
126  }
127
128 private:
129  LinkNode<T>* previous_;
130  LinkNode<T>* next_;
131};
132
133template <typename T>
134class 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).
139  LinkedList() : root_(&root_, &root_) {}
140
141  // Appends |e| to the end of the linked list.
142  void Append(LinkNode<T>* e) {
143    e->InsertBefore(&root_);
144  }
145
146  LinkNode<T>* head() const {
147    return root_.next();
148  }
149
150  LinkNode<T>* tail() const {
151    return root_.previous();
152  }
153
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