0

I am trying to insert a node at a both given index in a linked list and just at the end, but I don't understand the syntax or even conceptually what I am doing.

I have an insertTail function and an insertAfter function for both of these problems, but I'm not sure I am implementing them correctly. 

void insertTail(T value) {
        if (head == NULL) {
            insertHead(value);
        }
        else {
            T tailNode = Node(value);
            Node* tempPtr = head;
            while (tempPtr != NULL) {
                tempPtr = tempPtr->next;
            }
            next = tailNode->data;
        }

    };


void insertAfter(T value, T insertionNode) {
        Node* tempPtr = head;
        while (tempPtr->data != insertionNode) {
            tempPtr = tempPtr->next;
        }
        Node* afterNode = new Node(value);
        afterNode->next = tempPtr->next;
        tempPtr->next = afterNode;
    };

My code won't even compile with what I have currently. It gives an error for the first line in the else statement in the insertTail function that reads

'initializing': cannot convert from 'LinkedList<std::string>::Node' to 'std::basic_string<char,std::char_traits<char>,std::allocator<char>>'

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Simple
  • 11
  • 1
  • 1
    Please provide [mcve]. You are definitely trying to use templates where the type `T` is hidden for us. I would advise you to try a non-template version first. – Dmitry Kuzminov Jun 10 '19 at 23:59
  • 3
    "*I don't understand the syntax or even conceptually what I am doing*" - draw it out on paper first, work out the steps involved to perform the tasks, and then write code for each step. – Remy Lebeau Jun 11 '19 at 00:05

1 Answers1

1

Both of your functions are implemented all wrong. They need to look more like this instead (assuming a single-linked list is being used):

void insertTail(T value) {
    if (!head) {
        insertHead(value);
    }
    else {
        Node* tailNode = head;
        while (tailNode->next) {
            tailNode = tailNode->next;
        }
        tailNode->next = new Node(value);
    }
}


void insertAfter(T value, Node *insertionNode) {
    if (!insertionNode) {
        insertTail(value);
    }
    else {
        Node* newNode = new Node(value);
        newNode->next = insertionNode->next;
        insertionNode->next = newNode;
    }
}
Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
  • Addendum: When you get to the part where you are removing nodes (and make absolutely certain you have the insert routines fully debugged before you start working on removal) give [this answer , particularly the community add-on, a read](https://stackoverflow.com/a/22122095/4581301). There are some good tricks that can save you a lot of time. – user4581301 Jun 11 '19 at 00:11
  • @user4581301 the double-pointer trick is handy for insertions, too. `insertTail()` above could be implemented in a way that avoids the `if` to call `insertHead()`. – Remy Lebeau Jun 11 '19 at 05:20