title: C++ Creating an ordered linked list
body: <p>So I am attemping to create an Ordered Linked List to store them in an array to be able to organize a library of books and authors. However, I am finding it extremely difficult to create an ordered linked list. I managed to find the code to create a linked list online, however, I have no idea how I would begin making a Ordered linked list. I am relatively new to the language am finding the creation of this very stressful. </p>
  
  <p>Any suggestions as to how I would go about its creation using the Linked List structure below?</p>
  
  <p>I'm rather new to C++ and this is one of the first data structures i've every worked with, so sorry for the rather vague question. </p>
  
  <p>If I were to phrase this into a solidified question, it would be this: how do I go about creating an ordered linked list using this code as a general base?</p>
  
  <pre><code> #ifndef LINKEDLIST_H
  #define LINKEDLIST_H
  #include &lt;stdexcept&gt;
  using namespace std;
  
  template&lt;typename T&gt;
  class Node
  {
  public:
      T element;  // Element contained in the node
      Node&lt;T&gt;* next; // Pointer to the next node
  
      Node() // No-arg constructor
      {
          next = nullptr;
      }
  
      Node(T element) // Constructor
      {
          this-&gt;element = element;
          next = nullptr;
      }
  };
  
  template&lt;typename T&gt;
  class Iterator : public std::iterator&lt;std::forward_iterator_tag, T&gt;
  {
  public:
      Iterator(Node&lt;T&gt;* p)
      {
          current = p;
      }
  
      Iterator operator++() // Prefix ++
      {
          current = current-&gt;next;
          return *this;
      }
  
      Iterator operator++(int dummy) // Postfix ++
      {
          Iterator temp(current);
          current = current-&gt;next;
          return temp;
      }
  
      T&amp; operator*()
      {
          return current-&gt;element;
      }
  
      bool operator==(const Iterator&lt;T&gt;&amp; iterator)
      {
          return current == iterator.current;
      }
  
      bool operator!=(const Iterator&lt;T&gt;&amp; iterator)
      {
          return current != iterator.current;
      }
  
  private:
      Node&lt;T&gt;* current;
  };
  
  template&lt;typename T&gt;
  
  class LinkedList
  {
  public:
      LinkedList();
      LinkedList(const LinkedList&lt;T&gt;&amp; list);
      virtual ~LinkedList();
      void addFirst(T element);
      void addLast(T element);
      T getFirst() const;
      T getLast() const;
      T removeFirst() throw (runtime_error);
      T removeLast();
      void add(T element);
      void add(int index, T element);
      void clear();
      bool contains(T element) const;
      T get(int index) const;
      int indexOf(T element) const;
      bool isEmpty() const;
      int lastIndexOf(T element) const;
      void remove(T element);
      int getSize() const;
      T removeAt(int index);
      T set(int index, T element);
  
      Iterator&lt;T&gt; begin() const
      {
          return Iterator&lt;T&gt;(head);
      }
  
      Iterator&lt;T&gt; end() const
      {
          return Iterator&lt;T&gt;(tail-&gt;next);
      }
  
  private:
      Node&lt;T&gt;* head;
      Node&lt;T&gt;* tail;
      int size;
  };
  
  template&lt;typename T&gt;
  LinkedList&lt;T&gt;::LinkedList()
  {
      head = tail = nullptr;
      size = 0;
  }
  
  template&lt;typename T&gt;
  LinkedList&lt;T&gt;::LinkedList(const LinkedList&lt;T&gt;&amp; list)
  {
      head = tail = nullptr;
      size = 0;
  
      Node&lt;T&gt;* current = list.head;
      while (current != nullptr)
      {
          this-&gt;add(current-&gt;element);
          current = current-&gt;next;
      }
  }
  
  template&lt;typename T&gt;
  LinkedList&lt;T&gt;::~LinkedList()
  {
      clear();
  }
  
  template&lt;typename T&gt;
  void LinkedList&lt;T&gt;::addFirst(T element)
  {
      Node&lt;T&gt;* newNode = new Node&lt;T&gt;(element);
      newNode-&gt;next = head;
      head = newNode;
      size++;
  
      if (tail == nullptr)
          tail = head;
  }
  
  template&lt;typename T&gt;
  void LinkedList&lt;T&gt;::addLast(T element)
  {
      if (tail == nullptr)
      {
          head = tail = new Node&lt;T&gt;(element);
      }
      else
      {
          tail-&gt;next = new Node&lt;T&gt;(element);
          tail = tail-&gt;next;
      }
  
      size++;
  }
  
  template&lt;typename T&gt;
  T LinkedList&lt;T&gt;::getFirst() const
  {
      if (size == 0)
          throw runtime_error("Index out of range");
      else
          return head-&gt;element;
  }
  
  template&lt;typename T&gt;
  T LinkedList&lt;T&gt;::getLast() const
  {
      if (size == 0)
          throw runtime_error("Index out of range");
      else
          return tail-&gt;element;
  }
  
  template&lt;typename T&gt;
  T LinkedList&lt;T&gt;::removeFirst() throw (runtime_error)
  {
      if (size == 0)
          throw runtime_error("No elements in the list");
      else
      {
          Node&lt;T&gt;* temp = head;
          head = head-&gt;next;
          if (head == nullptr) tail = nullptr;
          size--;
          T element = temp-&gt;element;
          delete temp;
          return element;
      }
  }
  
  template&lt;typename T&gt;
  T LinkedList&lt;T&gt;::removeLast()
  {
      if (size == 0)
          throw runtime_error("No elements in the list");
      else if (size == 1)
      {
          Node&lt;T&gt;* temp = head;
          head = tail = nullptr;
          size = 0;
          T element = temp-&gt;element;
          delete temp;
          return element;
      }
      else
      {
          Node&lt;T&gt;* current = head;
  
          for (int i = 0; i &lt; size - 2; i++)
              current = current-&gt;next;
  
          Node&lt;T&gt;* temp = tail;
          tail = current;
          tail-&gt;next = nullptr;
          size--;
          T element = temp-&gt;element;
          delete temp;
          return element;
      }
  }
  
  template&lt;typename T&gt;
  void LinkedList&lt;T&gt;::add(T element)
  {
      addLast(element);
  }
  
  template&lt;typename T&gt;
  void LinkedList&lt;T&gt;::add(int index, T element)
  {
      if (index == 0)
          addFirst(element);
      else if (index &gt;= size)
          addLast(element);
      else
      {
          Node&lt;T&gt;* current = head;
          for (int i = 1; i &lt; index; i++)
              current = current-&gt;next;
          Node&lt;T&gt;* temp = current-&gt;next;
          current-&gt;next = new Node&lt;T&gt;(element);
          (current-&gt;next)-&gt;next = temp;
          size++;
      }
  }
  
  template&lt;typename T&gt;
  void LinkedList&lt;T&gt;::clear()
  {
      while (head != nullptr)
      {
          Node&lt;T&gt;* temp = head;
          head = head-&gt;next;
          delete temp;
      }
  
      tail = nullptr;
      size = 0;
  }
  
  template&lt;typename T&gt;
  T LinkedList&lt;T&gt;::get(int index) const
  {
      if (index &lt; 0 || index &gt; size - 1)
          throw runtime_error("Index out of range");
  
      Node&lt;T&gt;* current = head;
      for (int i = 0; i &lt; index; i++)
          current = current-&gt;next;
  
      return current-&gt;element;
  }
  
  template&lt;typename T&gt;
  int LinkedList&lt;T&gt;::indexOf(T element) const
  {
      // Implement it in this exercise
      Node&lt;T&gt;* current = head;
      for (int i = 0; i &lt; size; i++)
      {
          if (current-&gt;element == element)
              return i;
          current = current-&gt;next;
      }
  
      return -1;
  }
  
  template&lt;typename T&gt;
  bool LinkedList&lt;T&gt;::isEmpty() const
  {
      return head == nullptr;
  }
  
  template&lt;typename T&gt;
  int LinkedList&lt;T&gt;::getSize() const
  {
      return size;
  }
  
  template&lt;typename T&gt;
  T LinkedList&lt;T&gt;::removeAt(int index)
  {
      if (index &lt; 0 || index &gt;= size)
          throw runtime_error("Index out of range");
      else if (index == 0)
          return removeFirst();
      else if (index == size - 1)
          return removeLast();
      else
      {
          Node&lt;T&gt;* previous = head;
  
          for (int i = 1; i &lt; index; i++)
          {
              previous = previous-&gt;next;
          }
  
          Node&lt;T&gt;* current = previous-&gt;next;
          previous-&gt;next = current-&gt;next;
          size--;
          T element = current-&gt;element;
          delete current;
          return element;
      }
  }
  
  // The functions remove(T element), lastIndexOf(T element),
  // contains(T element), and set(int index, T element) are
  // left as an exercise
  
  #endif
  </code></pre>