1  #ifndef LINKEDLIST_H
  2  #define LINKEDLIST_H
  3  #include <stdexcept>
  4  using namespace std;
  5  
  6  template<typename T>
  7  class Node
  8  {
  9  public:
 10    T element;  // Element contained in the node
 11    Node<T>* next; // Pointer to the next node
 12  
 13    Node() // No-arg constructor
 14    {
 15      next = nullptr;
 16    }
 17  
 18    Node(T element) // Constructor
 19    {
 20      this->element = element;
 21      next = nullptr;
 22    }
 23  };
 24  
 25  template<typename T>
 26  class Iterator: public std::iterator<std::forward_iterator_tag, T>
 27  {
 28  public:
 29    Iterator(Node<T>* p)
 30    {
 31      current = p;
 32    }
 33  
 34    Iterator operator++() // Prefix ++
 35    {
 36      current = current->next;
 37      return *this;
 38    }
 39  
 40    Iterator operator++(int dummy) // Postfix ++
 41    {
 42      Iterator temp(current);
 43      current = current->next;
 44      return temp;
 45    }
 46  
 47    T& operator*()
 48    {
 49      return current->element;
 50    }
 51  
 52    bool operator==(const Iterator<T>& iterator)
 53    {
 54      return current == iterator.current;
 55    }
 56  
 57    bool operator!=(const Iterator<T>& iterator)
 58    {
 59      return current != iterator.current;
 60    }
 61  
 62  private:
 63    Node<T>* current;
 64  };
 65  
 66  template<typename T>
 67  class LinkedList
 68  {
 69  public:
 70    LinkedList();
 71    LinkedList(const LinkedList<T>& list);
 72    virtual ~LinkedList();
 73    void addFirst(T element);
 74    void addLast(T element);
 75    T getFirst() const;
 76    T getLast() const;
 77    T removeFirst() throw (runtime_error);
 78    T removeLast();
 79    void add(T element);
 80    void add(int index, T element);
 81    void clear();
 82    bool contains(T element) const;
 83    T get(int index) const;
 84    int indexOf(T element) const;
 85    bool isEmpty() const;
 86    int lastIndexOf(T element) const;
 87    void remove(T element);
 88    int getSize() const;
 89    T removeAt(int index);
 90    T set(int index, T element);
 91  
 92    Iterator<T> begin() const
 93    {
 94      return Iterator<T>(head);
 95    }
 96  
 97    Iterator<T> end() const
 98    {
 99      return Iterator<T>(tail->next);
100    }
101  
102  private:
103    Node<T>* head;
104    Node<T>* tail;
105    int size;
106  };
107  
108  template<typename T>
109  LinkedList<T>::LinkedList()
110  {
111    head = tail = nullptr;
112    size = 0;
113  }
114  
115  template<typename T>
116  LinkedList<T>::LinkedList(const LinkedList<T>& list)
117  {
118    head = tail = nullptr;
119    size = 0;
120  
121    Node<T>* current = list.head;
122    while (current != nullptr)
123    {
124      this->add(current->element);
125      current = current->next;
126    }
127  }
128  
129  template<typename T>
130  LinkedList<T>::~LinkedList()
131  {
132    clear();
133  }
134  
135  template<typename T>
136  void LinkedList<T>::addFirst(T element)
137  {
138    Node<T>* newNode = new Node<T>(element);
139    newNode->next = head;
140    head = newNode;
141    size++;
142  
143    if (tail == nullptr)
144      tail = head;
145  }
146  
147  template<typename T>
148  void LinkedList<T>::addLast(T element)
149  {
150    if (tail == nullptr)
151    {
152      head = tail = new Node<T>(element);
153    }
154    else
155    {
156      tail->next = new Node<T>(element);
157      tail = tail->next;
158    }
159  
160    size++;
161  }
162  
163  template<typename T>
164  T LinkedList<T>::getFirst() const
165  {
166    if (size == 0)
167      throw runtime_error("Index out of range");
168    else
169      return head->element;
170  }
171  
172  template<typename T>
173  T LinkedList<T>::getLast() const
174  {
175    if (size == 0)
176      throw runtime_error("Index out of range");
177    else
178      return tail->element;
179  }
180  
181  template<typename T>
182  T LinkedList<T>::removeFirst() throw (runtime_error)
183  {
184    if (size == 0)
185     throw runtime_error("No elements in the list");
186    else
187    {
188      Node<T>* temp = head;
189      head = head->next;
190      if (head == nullptr) tail = nullptr;
191      size--;
192      T element = temp->element;
193      delete temp;
194      return element;
195    }
196  }
197  
198  template<typename T>
199  T LinkedList<T>::removeLast()
200  {
201    if (size == 0)
202      throw runtime_error("No elements in the list");
203    else if (size == 1)
204    {
205      Node<T>* temp = head;
206      head = tail = nullptr;
207      size = 0;
208      T element = temp->element;
209      delete temp;
210      return element;
211    }
212    else
213    {
214      Node<T>* current = head;
215  
216      for (int i = 0; i < size - 2; i++)
217        current = current->next;
218  
219      Node<T>* temp = tail;
220      tail = current;
221      tail->next = nullptr;
222      size--;
223      T element = temp->element;
224      delete temp;
225      return element;
226    }
227  }
228  
229  template<typename T>
230  void LinkedList<T>::add(T element)
231  {
232    addLast(element);
233  }
234  
235  template<typename T>
236  void LinkedList<T>::add(int index, T element)
237  {
238    if (index == 0)
239      addFirst(element);
240    else if (index >= size)
241      addLast(element);
242    else
243    {
244      Node<T>* current = head;
245      for (int i = 1; i < index; i++)
246        current = current->next;
247      Node<T>* temp = current->next;
248      current->next = new Node<T>(element);
249      (current->next)->next = temp;
250      size++;
251    }
252  }
253  
254  template<typename T>
255  void LinkedList<T>::clear()
256  {
257    while (head != nullptr)
258    {
259      Node<T>* temp = head;
260      head = head->next;
261      delete temp;
262    }
263  
264    tail = nullptr;
265    size = 0;
266  }
267  
268  template<typename T>
269  T LinkedList<T>::get(int index) const
270  {
271    if (index < 0 || index > size - 1)
272      throw runtime_error("Index out of range");
273  
274    Node<T>* current = head;
275    for (int i = 0; i < index; i++)
276      current = current->next;
277  
278    return current->element;
279  }
280  
281  template<typename T>
282  int LinkedList<T>::indexOf(T element) const
283  {
284    // Implement it in this exercise
285    Node<T>* current = head;
286    for (int i = 0; i < size; i++)
287    {
288      if (current->element == element)
289        return i;
290      current = current->next;
291    }
292  
293    return -1;
294  }
295  
296  template<typename T>
297  bool LinkedList<T>::isEmpty() const
298  {
299    return head == nullptr;
300  }
301  
302  template<typename T>
303  int LinkedList<T>::getSize() const
304  {
305    return size;
306  }
307  
308  template<typename T>
309  T LinkedList<T>::removeAt(int index)
310  {
311    if (index < 0 || index >= size)
312      throw runtime_error("Index out of range");
313    else if (index == 0)
314      return removeFirst();
315    else if (index == size - 1)
316      return removeLast();
317    else
318    {
319      Node<T>* previous = head;
320  
321      for (int i = 1; i < index; i++)
322      {
323        previous = previous->next;
324      }
325  
326      Node<T>* current = previous->next;
327      previous->next = current->next;
328      size--;
329      T element = current->element;
330      delete current;
331      return element;
332    }
333  }
334  
335    // The functions remove(T element), lastIndexOf(T element),
336    // contains(T element), and set(int index, T element) are
337    // left as an exercise
338  
339  #endif