When I change pointers in linked list, does the original still hold or does it get removed automatically?

Question

I have a very basic question about linked list

say I reverse the following linked list:

#1->2->3->4 to become 4->3->2->1

And say I start first with reversing the pointer that points from 1 to 2; so that 2 points to 1. My question is, does the pointer/connection from 1 to 2 still exist when I do this?

Or does this connection get removed when we do 2->1?

A further question if the above is true, is "does the original connection 1->2->3->4 always hold, no matter what we do to the pointers; or does it get removed, if say I changed the pointer at 1 to point at 3; i.e. 1->3 ; then does the connection 1->2 gets removed automatically?

Answer 1

Usually a node in a linked list has a single reference to another node: the next one.

When you have a list with 4 nodes, you can visualise it like this:

 head
  ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next: —————→ │ next: —————→ │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

You ask:

And say I start first with reversing the pointer that points from 1 to 2; so that 2 points to 1. My question is, does the pointer/connection from 1 to 2 still exist when I do this?

"reversing the pointer" is not really the right way to express what happens. The "pointer" that points from 1 to 2 will be set to None, and another reference will be set to point from 2 to 1. It is not the same one!

So first the next reference in the first node is made to refer to the node that precedes it -- but as there is no such node it gets to be None:

 head
  ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│   │ next: —————→ │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

And then the same happens with the second node. Its next reference is made to refer to the first node:

 head
  ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │   │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

A bit more about the typical reversal algorithm

As an additional step the head reference should be made to point to what now has become the start of the part that is already reversed:

                head
                 ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │   │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

At each step in this reversal, there is a disconnection between the node whose next is altered, and the node that originally followed it (in the last visualisation, the node with value 3 cannot be reached any more from the node that is pictured at its left side).

For this reason you need to have a variable to remember what the original next node was, so that you can proceed and also change that node's next attribute. You could call that variable next:

                head           next
                 ↓              ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │   │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

If we proceed with the next step, the following actions are performed:

We copy the reference of next... maybe in a variable called current:

                               current
                head           next
                 ↓              ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │   │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

Then remember what the original next node was, by referring to it with the variable next:

                head           current        next
                 ↓              ↓              ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │   │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

Then change the reference from 3 to 4 to a reference from 3 to 2:

                head           current        next
                 ↓              ↓              ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │ ←———— :next  │   │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

Note that now the right most node is detached. We still need to update the head reference:

                               head
                               current        next
                                ↓              ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │ ←———— :next  │   │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

Now only one cycle remains that starts by setting the current reference... etc.

See also How does this recursive function to reverse a linked list work?