fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3.  
  4. template<typename> struct List;
  5.  
  6. template<class T>
  7. struct Node {
  8. 	using value_type = T;
  9. 	using self_type = Node<value_type>;
  10. 	using list_type = struct List<value_type>;
  11.  
  12. 	friend struct List<T>;
  13.  
  14. 	// Nodes come initialized pointing to themselves.
  15. 	Node(T* data_) : _data(data_), _next(this) {}
  16.  
  17. 	// Not copyable or moveable
  18. 	Node(self_type&) = delete;
  19. 	Node(self_type&&) = delete;
  20.  
  21. 	value_type* data() noexcept { return _data; }
  22. 	const value_type* data() const noexcept { return _data; }
  23. 	self_type* next() noexcept { return _next; }
  24. 	const self_type* next() const noexcept { return _next; }
  25.  
  26. private:
  27. 	value_type*	_data;
  28. 	self_type*	_next;
  29. };
  30.  
  31. template<class T>
  32. struct List
  33. {
  34. 	using value_type = T;
  35. 	using self_type = List<value_type>;
  36. 	using node_type = struct Node<value_type>;
  37.  
  38. 	List() : _head(nullptr) {}
  39.  
  40. 	void free() {
  41. 		node_type* ptr;
  42. 		while ((ptr = _head)) {
  43. 			std::swap(_head, _head->_next);
  44. 			delete ptr;
  45. 		}
  46. 	}
  47.  
  48. 	~List()
  49. 	{
  50. 		this->free();
  51. 	}
  52.  
  53. 	node_type* push_front(value_type* data_)
  54. 	{
  55. 		node_type* insertion = new node_type(data_);
  56. 		std::swap(insertion->_next, _head);
  57. 		return insertion;
  58. 	}
  59.  
  60. 	node_type* insert_after(node_type* node_, value_type* data_)
  61. 	{
  62. 		node_type* insertion = new node_type(data_);
  63. 		std::swap(insertion->_next, node_->_next);
  64. 		return insertion;
  65. 	}
  66.  
  67. 	node_type* insert_before(node_type* node_, value_type* data_)
  68. 	{
  69. 		if (_head == node_)
  70. 			return push_front(data_);
  71. 		for (node_type* previous = _head; previous; previous = previous->_next) {
  72. 			if (previous->_next == node_)
  73. 				return insert_after(previous, data_);
  74. 		}
  75. 		return nullptr;
  76. 	}
  77.  
  78. 	value_type* pop_front() {
  79. 		auto* node = _head;
  80. 		if (!_head)
  81. 			return nullptr;
  82. 		_head = node->_next;
  83. 		auto* data = node->_data;
  84. 		delete node;
  85. 		return data;
  86. 	}
  87.  
  88. 	value_type* remove(node_type* node_)
  89. 	{
  90. 		node_type* previous = _head;
  91. 		if (previous == node_)
  92. 			return pop_front();
  93. 		while (previous) {
  94. 			auto next = previous->_next;
  95. 			if (next == node_) {
  96. 				auto* data = node_->_data;
  97. 				std::swap(previous->_next, node_->_next);
  98. 				delete node_;
  99. 				return data;
  100. 			}
  101. 			previous = next;
  102. 		}
  103. 	}
  104.  
  105. 	bool empty() const noexcept { return _head == nullptr; }
  106. 	node_type* head() noexcept { return _head; }
  107. 	const node_type* head() const noexcept { return _head; }
  108. 	value_type* front() noexcept { return _head->data(); }
  109. 	const value_type* front() const noexcept { return _head->data(); }
  110.  
  111. 	node_type* tail() const noexcept {
  112. 		node_type* node = _head;
  113. 		if (node != nullptr) {
  114. 			while (node->_next) {
  115. 				node = node->_next;
  116. 			}
  117. 		}
  118. 		return node;
  119. 	}
  120.  
  121. 	void dump() {
  122. 		if (empty()) {
  123. 			std::cout << "list is empty\n";
  124. 		} else {
  125. 			for (auto* node = head(); node; node = node->next()) {
  126. 				std::cout << "\"" << *node->data() << "\", ";
  127. 			}
  128. 			std::cout << "(end)\n";
  129. 		}
  130. 	}
  131.  
  132. private:
  133. 	node_type* _head;
  134. };
  135.  
  136. int main() {
  137. 	List<std::string> strings;
  138.  
  139. 	strings.push_front(new std::string("hello"));
  140. 	strings.dump();
  141. 	strings.push_front(new std::string("mumble"));
  142. 	strings.dump();
  143. 	strings.push_front(new std::string("world"));
  144. 	strings.dump();
  145.  
  146. 	auto* node = strings.head()->next();
  147. 	std::cout << "front->next = " << *(node->data()) << "\n";
  148.  
  149. 	auto* removed = strings.remove(node);
  150. 	std::cout << "removed " << *removed << "\n";
  151. 	delete removed;
  152.  
  153. 	strings.dump();
  154.  
  155. 	node = strings.insert_before(strings.head()->next(), new std::string("mumble"));
  156. 	strings.dump();
  157. 	node = strings.insert_before(strings.head(), new std::string("wibble"));
  158. 	strings.dump();
  159. 	delete strings.pop_front();
  160. 	strings.dump();
  161. 	node = strings.tail();
  162. 	std::cout << "strings.tail() = " << *strings.tail()->data() << "\n";
  163. 	node = strings.insert_after(node, new std::string("*cough*"));
  164. 	strings.dump();
  165. 	delete strings.remove(node);
  166. 	strings.dump();
  167.  
  168. 	return 0;
  169. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
"hello", (end)
"mumble", "hello", (end)
"world", "mumble", "hello", (end)
front->next = mumble
removed mumble
"world", "hello", (end)
"world", "mumble", "hello", (end)
"wibble", "world", "mumble", "hello", (end)
"world", "mumble", "hello", (end)
strings.tail() = hello
"world", "mumble", "hello", "*cough*", (end)
"world", "mumble", "hello", (end)
https://ideone.com/2RUWgj
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!