Inserting into a particular position in a double linked list

Question

I have made a post here on code review which can be found here. I was told that my insertPosition function does not update head or tail. When I asked how some questions about this claim, my questions fell on deaf ears.

Here is the function:

template <class T>
void DoubleLinkedLists<T>::insertPosition(int pos, const T& theData) {
    Node* current = head;
    int i = 0;
    while (current != nullptr) {
        if (i++ == pos) {
            Node* newNode = new Node;
            newNode->data = theData;
            // Let's do the wiring
            newNode->previous = current->previous;
            newNode->next = current;
            if (newNode->previous != nullptr) {  // If the node is inserted at the end
                newNode->previous->next = newNode;
            }
            current->previous = newNode;
            return;
        }
        current = current->next;
    }
}

Does the latter function not update head or tail? If so, how should I change it?

If `head` is initially `nullptr`, where in your code do you expect it to change to no longer be `nullptr`? — jxh, Jun 19 '18 at 22:37
When I create the node using my createNode function (essentially it is a push_back function or append) — , Jun 19 '18 at 22:38
I think the point is this `insertPosition()` function can not add a new head. — drescherjm, Jun 19 '18 at 22:39
Yes, it doe shave a tail. I already have a function for insertHead as well. — , Jun 19 '18 at 22:40
I see your point so should I create some conditional statements where if the user wants to insert at the beginning or end then I call on the insertHead or insertTail functions? — , Jun 19 '18 at 22:43
Do you have a reason to not want `pos == 0` to mean *insert at the head*? — jxh, Jun 19 '18 at 23:05
Do you have a reason that`insertPosition(0, data)` should be different from `insertHead(data)` in all cases, including when `head` is `nullptr`? — jxh, Jun 19 '18 at 23:21

score 1 · Accepted Answer · answered Jun 19 '18 at 23:32

1

Does the function not update head or tail?

No, it does not. Look at it for yourself. There is no mention of head or tail anywhere in its code, and it doesn't call any class methods that might refer to those members, either.

The code should look something like this:

template <class T>
void DoubleLinkedLists<T>::insertPosition(int pos, const T& theData)
{
    if (pos < 0)
        throw std::invalid_argument("pos is not a valid index");

    Node *current = head, *previous = nullptr;
    while (pos-- > 0) {
    {
        if (!current)
            throw std::invalid_argument("pos is not a valid index");

        previous = current;
        current = current->next;
    }

    Node* newNode = new Node;
    newNode->data = theData;

    // Let's do the wiring
    newNode->previous = previous;
    newNode->next = current;

    if (newNode->previous)
        newNode->previous->next = newNode;
    else
        head = newNode;

    if (newNode->next)
        newNode->next->previous = newNode;
    else
        tail = newNode;
}

answered Jun 19 '18 at 23:32

Remy Lebeau

555,201
31
458
770

I understand most of this code but not the if(newNode->previous) I am not sure whats going on there, could you explain? – Jun 22 '18 at 00:11
@Snorrlaxxx The code is checking if the new node is being inserted at the very front and/or very back of the list. If `previous` is pointing at an earlier node, the new node CAN'T be a new `head` node, so `head` is untouched and `previous->next` is updated to point at the new node. Otherwise, the new node MUST be a new `head` node, so `head` is updated to point at the new node. – Remy Lebeau Jun 22 '18 at 00:44
@Snorrlaxxx Likewise, if `current` is pointing at a later node, the new node CAN'T be a new `tail` node, so `tail` is untouched and `current->previous` is updated to point at the new node. Otherwise, the new node MUST be a new `tail` node, so `tail` is updated to point at the new node. – Remy Lebeau Jun 22 '18 at 00:44
I sort of understand what you saying so if(newNode->previous) states "hey newNode, are you point to an earlier node?" If it is then we say okay newNode cannot be a new head so lets update and make previous->next point to the newNode? – Jun 22 '18 at 00:45
@Snorrlaxxx that is correct. When it comes to understanding linked lists, it helps to draw the nodes on paper and follow the code logic step by step, erasing/drawing links between nodes as the code performs them. – Remy Lebeau Jun 22 '18 at 00:46
Thanks for answering my question. You seem very advanced and I hope one day to be as good as you, do you have any advice or books I should read? – Jun 22 '18 at 00:57
@Snorrlaxxx see [The Definitive C++ Book Guide and List](https://stackoverflow.com/questions/388242/). But I'm a self-taught programmer and haven't read very many programming books (most of my learning is from reading other people's code), so I can't advise which ones are better than others. – Remy Lebeau Jun 22 '18 at 01:08
I am on the same boat, I am a mathematician my education but instead of being in theory land I need to learn to code well to get a good job :). – Jun 22 '18 at 01:15

Inserting into a particular position in a double linked list

1 Answers1