fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <ctime>
  4.  
  5. template<class T>
  6. class DoublyLinkedList
  7. {
  8. private:
  9. 	class Link
  10. 	{
  11. 	public:
  12. 		T data;
  13. 		Link* next;
  14. 		Link* previous;
  15.  
  16. 		Link(T data, Link* next = nullptr, Link* previous = nullptr);
  17. 	};
  18. private:
  19. 	Link* first;
  20. 	Link* last;
  21. public:
  22. 	DoublyLinkedList();
  23. 	~DoublyLinkedList();
  24.  
  25. 	bool isEmpty();
  26. 	void insertFirst(T dd);
  27. 	void insertLast(T dd);
  28. 	void deleteFirst();
  29. 	void deleteLast();
  30. 	bool insertAfter(T key, T dd);
  31. 	void deleteKey(T key);
  32. 	void displayForward();
  33. 	void displayBackward();
  34. 	void BSTinsert(Link*& root, Link* z);
  35. 	void BSTtoDLL(Link* root, DoublyLinkedList<T> &L);
  36. 	void BSTSort();
  37. private:
  38. 	Link* find(T key);
  39. };
  40.  
  41.  
  42. template<class T>
  43. DoublyLinkedList<T>::Link::Link(T data, Link* next, Link* previous)
  44. 	: data(data), next(next), previous(previous)
  45. {
  46. }
  47.  
  48.  
  49. template<class T>
  50. DoublyLinkedList<T>::DoublyLinkedList()
  51. 	: first(nullptr), last(nullptr)
  52. {
  53. }
  54.  
  55. template<class T>
  56. DoublyLinkedList<T>::~DoublyLinkedList()
  57. {
  58. 	while (!isEmpty())
  59. 	{
  60. 		deleteFirst();
  61. 	}
  62. }
  63.  
  64. template<class T>
  65. bool DoublyLinkedList<T>::isEmpty()
  66. {
  67. 	return first == nullptr;
  68. }
  69.  
  70. template<class T>
  71. void DoublyLinkedList<T>::insertFirst(T dd)
  72. {
  73. 	Link* newLink = new Link(dd);
  74. 	if (isEmpty())
  75. 		last = newLink;
  76. 	else
  77. 		first->previous = newLink;
  78. 	newLink->next = first;
  79. 	first = newLink;
  80. }
  81.  
  82. template<class T>
  83. void DoublyLinkedList<T>::insertLast(T dd)
  84. {
  85. 	Link* newLink = new Link(dd);
  86. 	if (isEmpty())
  87. 		first = newLink;
  88. 	else
  89. 		last->next = newLink;
  90. 	newLink->previous = last;
  91. 	last = newLink;
  92. }
  93.  
  94. template<class T>
  95. void DoublyLinkedList<T>::deleteFirst()
  96. {
  97. 	if (isEmpty())
  98. 		return;
  99. 	Link* temp = first;
  100. 	if (first->next == nullptr)
  101. 		last = nullptr;
  102. 	else
  103. 		first->next->previous = nullptr;
  104. 	first = first->next;
  105. 	delete temp;
  106. }
  107.  
  108. template<class T>
  109. void DoublyLinkedList<T>::deleteLast()
  110. {
  111. 	if (isEmpty())
  112. 		return;
  113. 	Link* temp = last;
  114. 	if (first->next == nullptr)
  115. 		first = nullptr;
  116. 	else
  117. 		last->previous->next = nullptr;
  118. 	last = last->previous;
  119. 	delete temp;
  120. }
  121.  
  122. template<class T>
  123. bool DoublyLinkedList<T>::insertAfter(T key, T dd)
  124. {
  125. 	Link* current = find(key);
  126. 	if (current == nullptr)
  127. 		return false;
  128. 	Link* newLink = new Link(dd);
  129. 	if (current->next == nullptr)
  130. 	{
  131. 		newLink->next = nullptr;
  132. 		last = newLink;
  133. 	}
  134. 	else
  135. 	{
  136. 		newLink->next = current->next;
  137. 		current->next->previous = newLink;
  138. 	}
  139. 	newLink->previous = current;
  140. 	current->next = newLink;
  141. 	return true;
  142. }
  143.  
  144. template<class T>
  145. void DoublyLinkedList<T>::deleteKey(T key)
  146. {
  147. 	Link* current = find(key);
  148. 	if (current == nullptr)
  149. 		return;
  150. 	if (current->previous == nullptr)
  151. 		first = current->next;
  152. 	else
  153. 		current->previous->next = current->next;
  154. 	if (current->next == nullptr)
  155. 		last = current->previous;
  156. 	else
  157. 		current->next->previous = current->previous;
  158. 	delete current;
  159. }
  160.  
  161. template<class T>
  162. void DoublyLinkedList<T>::displayForward()
  163. {
  164. 	std::cout << "List (first-->last): ";
  165. 	Link* current = first;
  166. 	while (current != nullptr)
  167. 	{
  168. 		std::cout << current->data << " ";
  169. 		current = current->next;
  170. 	}
  171. 	std::cout << std::endl;
  172. }
  173.  
  174. template<class T>
  175. void DoublyLinkedList<T>::displayBackward()
  176. {
  177. 	std::cout << "List (last-->first): ";
  178. 	Link* current = last;
  179. 	while (current != nullptr)
  180. 	{
  181. 		std::cout << current->data << " ";
  182. 		current = current->previous;
  183. 	}
  184. 	std::cout << std::endl;
  185. }
  186.  
  187. template<class T>
  188. void DoublyLinkedList<T>::BSTinsert(Link* &root, Link* z)
  189. {
  190. 	Link* y = nullptr;
  191. 	Link* x = root;
  192. 	while (x != nullptr)
  193. 	{
  194. 		y = x;
  195. 		if (z->data < x->data)
  196. 			x = x->previous;
  197. 		else
  198. 			x = x->next;
  199. 	}
  200. 	if (y == nullptr)
  201. 		root = z;
  202. 	else if (z->data < y->data)
  203. 		y->previous = z;
  204. 	else
  205. 		y->next = z;
  206. }
  207.  
  208. template<class T>
  209. void DoublyLinkedList<T>::BSTtoDLL(Link* root, DoublyLinkedList<T> &L)
  210. {
  211. 	if (root != nullptr)
  212. 	{
  213. 		BSTtoDLL(root->previous, L);
  214. 		if (L.isEmpty())
  215. 			L.first = root;
  216. 		else
  217. 			L.last->next = root;
  218. 		root->previous = L.last;
  219. 		L.last = root;
  220. 		BSTtoDLL(root->next, L);
  221. 	}
  222. }
  223.  
  224. template<class T>
  225. typename DoublyLinkedList<T>::Link* DoublyLinkedList<T>::find(T key)
  226. {
  227. 	Link* current = first;
  228. 	while (current != nullptr && !(current->data == key))
  229. 		current = current->next;
  230. 	return current;
  231. }
  232.  
  233. template<class T>
  234. void DoublyLinkedList<T>::BSTSort()
  235. {
  236. 	Link* temp;
  237. 	Link* root = nullptr;
  238. 	while (!isEmpty())
  239. 	{
  240. 		temp = first;
  241. 		if (first->next == nullptr)
  242. 			last = nullptr;
  243. 		else
  244. 			first->next->previous = nullptr;
  245. 		first = first->next;
  246. 		temp->previous = nullptr;
  247. 		temp->next = nullptr;
  248. 		BSTinsert(root, temp);
  249. 	}
  250. 	BSTtoDLL(root, *this);
  251. }
  252.  
  253. int main(int argc, char *argv[])
  254. {
  255. 	DoublyLinkedList<int> A;
  256. 	int k, n, m;
  257. 	srand(time(nullptr));
  258. 	std::cin >> n >> m;
  259. 	for (k = 0; k < n; k++)
  260. 		A.insertLast(rand() % m);
  261. 	A.displayForward();
  262. 	A.displayBackward();
  263. 	A.BSTSort();
  264. 	A.displayForward();
  265. 	A.displayBackward();
  266. 	while (!A.isEmpty())
  267. 		A.deleteFirst();
  268. 	return EXIT_SUCCESS;
  269. }
Success #stdin #stdout 0s 4200KB
comments (?)
stdin
copy 
30 1000
stdout
copy 
List (first-->last): 482 284 771 485 125 166 128 351 129 286 110 163 764 315 115 298 543 48 615 962 354 135 47 586 100 62 944 509 774 650 
List (last-->first): 650 774 509 944 62 100 586 47 135 354 962 615 48 543 298 115 315 764 163 110 286 129 351 128 166 125 485 771 284 482 
List (first-->last): 47 48 62 100 110 115 125 128 129 135 163 166 284 286 298 315 351 354 482 485 509 543 586 615 650 764 771 774 944 962 
List (last-->first): 962 944 774 771 764 650 615 586 543 509 485 482 354 351 315 298 286 284 166 163 135 129 128 125 115 110 100 62 48 47
https://ideone.com/QGlHQQ
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!