Let's move on to the Insert() operation for the LinkedList class. There are four cases for this operation, and they are:
- The new item is inserted at the beginning of the linked list, which is index = 0, so that it becomes the new Head.
- The new item is added to an empty linked list. If the linked list has only one element, both Head and Tail will point to the only element.
- The new item is inserted into the last of the linked list, which is index = N, so it becomes the new Tail.
- The new item is inserted in the other position of the linked list, where index = 1 to N-1.
Now, let's create the implementation for inserting an operation. For cases 1 and 2, we can solve these problems by creating an InsertHead() ...