CODEWITHSUNDEEP
c++pointerslinked-listsingly-linked-list
Duxa
Duxa

Reputation: 1008

C++ Linked List traversal and modification

Linked list:

pointer2 -> [a]
pointer ->[a] -> [b] -> [c] -> [d] -> null    
pointer = b; //makes it point one down so it will be pointer -> [b] ->[c] -> [d] -> null    
pointer = pointer 2; //makes pointer point back to where it was pointing to before, both pointers point to [a]   
pointer2 = pointer->next; //makes pointer 2 point to [b]
pointer2->next = pointer->next; //makes [c] point to [b]

Is my understanding correct? Can nodes point to themselves? like pointer->next = pointer->next ?

Basically:

Is that right?

Upvotes: 3

Views: 1304

Answers (3)

Arthur Tacca
Arthur Tacca

Reputation: 9989

Can nodes point to themselves?

As others have said, it is certainly possible. But perhaps you really meant "is it valid?". The answer to that is, it depends on the code that manipulates the linked list. If you are writing that code, then it's up to you whether it's valid.

For example, you might decide that when a node points to itself, then that denotes the end of the linked list. Then here is how you might code a function that searches an integer linked list for the number 3:

struct ListNode {
    int value;
    ListNode* next;
};

bool containsThree(ListNode* list) {
    for (; list->next != list; list = list->next) {
        if (list->value == 3) {
            return true;
        }
    }
    // Also check final node
    if (list->value == 3) {
        return true;
    }
    return false;
}

Alternatively you could decide that next == nullptr means the end of the list. In that case containsThree would look more like this:

bool containsThree(ListNode* list) {
    for (ListNode* node = list; node; node = node->next) {
        if (node->value == 3) {
            return true;
        }
    }
    return false;
}

With this new function, if any node points at itself then the function would loop forever. You could fix this, and even check for larger loops in the list, like this:

bool containsThree(ListNode* list) {
    std::set<ListNode*> seenNodes;
    for (ListNode* node = list; node; node = node->next) {
        if (seenNodes.count(node)) {
            break;
        }
        seenNodes.insert(node);
        if (node->value == 3) {
            return true;
        }
    }
    return false;
}

There's a problem with this final function: it has a significant performance penalty over the previous one. So it's up to you whether loops in your list are allowed and you'll take the hit of checking for them in your functions, or loops are not allowed. Either one is correct, you just need to make a decision and stick to it.

(Edit: The first example function is a bit messy because the condition that ends the loop does so just before we look for 3 in the final node. It's also impossible to pass in an empty list. Both of these problems are fixed in the nullptr examples, but it's actually possible to fix them even using the "node == node->next means end of list" rule. The key is to add a dummy node to the end of the linked list, and require that this extra node have this property. You don't need to check this node for three-ness, and such a node on its own represents an empty list.)

Upvotes: 1

Griffin
Griffin

Reputation: 766

Linked data structure has one pointer for current data, one for the next one (which is the pointer to the current data of next one) and if doubly linked list then one to the previous one (which is the pointer to the current data of the previous one).

Can nodes point to themselves? like pointer->next = pointer->next ?

Yes. That is same as assigning any pointer to itself. Not very useful.

  • pointer->next = pointer2->next - make link node that pointer points to point to one after link node that pointer2 points to
  • pointer = pointer2->next - make pointer point to the link node one after the one pointer2 points to.

After this however, current data pointer and next data pointer are same and point to same thing. This means if someone wants to traverse along this linked list they may end up in infinite loop if they have no pointer check.

Upvotes: 0

Serge Ballesta
Serge Ballesta

Reputation: 148940

You are right exect for the last pointer assignment:

...
pointer2 = pointer->next; //makes pointer 2 point to [b]: Ok
pointer2->next = pointer->next; //makes [c] point to [b]: Wrong

pointer2 points to [b], and pointer->next points to b. The last pointer assignment make b points to itself leading to:

pointer2 -> b -> b !

and:

pointer -> a -> b -> b

You misunderstanding may come from the fact that your pseudo code is not explicit about what are a, b, c and d, what represents next and where you use addresses. Write all this is C++ and it will be more clear.

Upvotes: 0

Related Questions