fork download
copy 
  1. // Create an iterator for this class
  2. // Implement a begin() method, ++ and -- operators, and dereference operator to retrieve the current value
  3.  
  4. #include <iostream>
  5. #include <stdexcept>
  6.  
  7. class LinkedListIterator {
  8. 	friend class LinkedList;
  9. 	public:
  10. 		void begin(); // sets the pointer to the beginning
  11. 		void operator++(); // Increments
  12. 		void operator--(); // Decrements
  13. 		int operator*(); // Derefernce; gets the value of the current element
  14. };
  15.  
  16. class LinkedList {
  17. 	friend class LinkedListIterator;
  18. 	class Node {
  19. 	public:
  20. 		int value;
  21. 		void setNext(Node* n) {
  22. 			next = n;
  23. 		}
  24. 		void setPrev(Node* n) {
  25. 			prev = n;
  26. 		}
  27. 		Node* next;
  28. 		Node* prev;
  29. 	};
  30. public:
  31. 	LinkedList() { // Initial empty list conditions
  32. 		head = NULL;
  33. 		tail = NULL;
  34. 		length = 0;
  35. 	}
  36. 	~LinkedList() { // Removes each Node
  37. 		while (head != NULL && tail != NULL) pop(); // Pop each value to clear memory
  38. 	}
  39.  
  40. 	unsigned int size() { // Returns the size of the list
  41. 		return length;
  42. 	}
  43.  
  44. 	int &operator[](unsigned int index) { // Returns the value at the given index
  45. 		Node* node = head;
  46. 		for (int i = 0; i < index; ++i) {
  47. 			node = node->next;
  48. 			if (node == NULL) {
  49. 				std::string error("Offset of out of range");
  50. 				throw std::range_error(std::string(error));
  51. 			}
  52. 		}
  53. 		return node->value;
  54. 	}
  55.  
  56. 	void add(int val) { // Adds a value to the beginning of the list
  57. 		Node* newNode = new Node();
  58. 		newNode->value = val;
  59. 		if (head != NULL) {
  60. 			head->setPrev(newNode);
  61. 		}
  62. 		newNode->next = head;
  63. 		newNode->prev =	NULL;
  64. 		head = newNode;
  65. 		if (length == 0) {
  66. 			tail = newNode;
  67. 		}
  68.  
  69. 		length++;
  70. 	}
  71. 	void push(int val) { // Pushes a value to the end of the list
  72. 		Node* newNode = new Node();
  73. 		newNode->value = val;
  74. 		if (tail != NULL) {
  75. 			tail->setNext(newNode);
  76. 		}
  77. 		newNode->prev = tail;
  78. 		newNode->next =	NULL;
  79. 		tail = newNode;
  80. 		if (length == 0) {
  81. 			head = newNode;
  82. 		}
  83.  
  84. 		length++;
  85. 	}
  86. 	void insert(int index, int val) { // Inserts a value at index in the list
  87. 		if (index == length-1) {
  88. 			this->push(val);
  89. 			return;
  90. 		}
  91. 		Node* newNode = new Node();
  92. 		newNode->value = val;
  93. 		Node* before = this->nodeAt(index);
  94. 		Node* after = before->next;
  95.  
  96. 		newNode->next = after;
  97. 		newNode->prev = before;
  98. 		before->next = newNode;
  99. 		after->prev = newNode;
  100. 		length++;
  101. 	}
  102.  
  103. 	int pop() { // Pops a value from the beginning and returns it
  104. 		if (head == NULL || tail == NULL) {
  105. 			std::string error("Cannot pop empty list");
  106. 			throw std::range_error(error);
  107. 		}
  108. 		Node* n = head;
  109. 		int ret = n->value;
  110. 		head = head->next;
  111. 		if (head != NULL) {
  112. 			head->prev = NULL;
  113. 		}
  114. 		delete n;
  115.  
  116. 		length--;
  117. 		return ret;
  118. 	}
  119. 	int shift() { // Shifts a value from the end and returns it
  120. 		if (head == NULL || tail == NULL) {
  121. 			std::string error("Cannot shift empty list");
  122. 			throw std::range_error(error);
  123. 		}
  124. 		Node* n = tail;
  125. 		int ret = n->value;
  126. 		tail = tail->prev;
  127. 		if (tail != NULL) {
  128. 			tail->next = NULL;
  129. 		}
  130. 		delete n;
  131.  
  132. 		length--;
  133. 		return ret;
  134. 	}
  135. 	int remove(int index) {
  136. 		if (index == 0) {
  137. 			return this->pop();
  138. 		}
  139. 		if (index == length-1) {
  140. 			return this->shift();
  141. 		}
  142. 		Node* n = this->nodeAt(index);
  143. 		int ret = n->value;
  144. 		Node* before = n->prev;
  145. 		Node* after = n->next;
  146. 		before->next = after;
  147. 		after->prev = before;
  148. 		delete n;
  149.  
  150. 		length--;
  151. 		return ret;
  152. 	}
  153.  
  154. private:
  155. 	Node* nodeAt(int index) {
  156. 		Node* node = head;
  157. 		for (int i = 0; i < index; ++i) {
  158. 			node = node->next;
  159. 			if (node == NULL) {
  160. 				std::string error("Offset of out of range");
  161. 				throw 1;
  162. 			}
  163. 		}
  164. 		return node;
  165. 	}
  166.  
  167. 	Node* head;
  168. 	Node* tail;
  169. 	int length;
  170. };
  171.  
  172. int main() {
  173. 	LinkedList list;
  174.  
  175. 	list.add(100); // list = [100]
  176. 	list.add(12); // list = [12, 100]
  177. 	list.push(15); // list = [12, 100, 15]
  178. 	list.insert(2,32); // list = [12, 100, 15, 32]
  179. 	list.remove(1); // list = [12, 15, 32]
  180.  
  181. 	while (list.size()) {
  182. 		std::cout << list.pop() << std::endl; // prints elements one by one
  183. 	}
  184.  
  185. 	return 0;
  186. }
  187.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
12
15
32
https://ideone.com/p6z8FQ
language:
C++14 (gcc 8.3)
created:
7 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!