Question 2. Linked lists [ 16 marks ]

Given the following definition for a singly-linked list class, and assuming the createNode method has already been implemented, write an implementation for the InsertAtPosition method.

class LinkedList {
   private:
       struct ListNode {
          string key;
          ListNode *next, *prev;
       };

       // pointer to the front node of the list,
       //    null if the list is empty
       ListNode *front;

   public:
       LinkedList();  // initialize an empty list
       ~LinkedList(); // deallocate all ListNodes
       void print();  // print the list contents

       // allocate a ListNode, initialize its key with k
       ListNode* createNode(string k); 

       // insert k in the i'th position of the list,
       //    0 or negative values mean insert at the front,
       //    1 means insert after the first element,
       //    2 means insert after the second element, etc
       // insert at the end of the list if i is greater
       //    than or equal to the current size of the list
       void InsertAtPosition(int i, string k);