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);