I am trying to simulate linked lists in python using dictionaries - h (stands for head) and t (stands for tail):

t = {"value": 5, "next": None}
h = t

I add a new node n1 as value of the key "next" in t:

n1 = {"value": 10, "next": None}
t["next"] = n1

print(t)
# {'value': 5, 'next': {'value': 10, 'next': None}}

print(h)
# {'value': 5, 'next': {'value': 10, 'next': None}}

I understand that is because both h and t are referring to the same memory address at this moment.

This is also confirmed by

print(id(h))
# 2429471179008

print(id(t))
# 2429471179008

I now changed the value of t to the node n1:

t = n1
print(t)
# {'value': 10, 'next': None}

print(h)
# {'value': 5, 'next': {'value': 10, 'next': None}}

My understanding is that at this point h and t will start referring to different memory addresses.

This is also confirmed by

print(id(h))
# 2429471179008

print(id(t))
# 2429470939776

Now I add one more new node n2 as value of the key "next" in t:

n2 = {"value": 16, "next": None}
t["next"] = n2

print(t)
# {'value': 10, 'next': {'value': 16, 'next': None}}

print(h)
# {'value': 5, 'next': {'value': 10, 'next': {'value': 16, 'next': None}}}

Why is that so? How did the change to t impact h and that too in this fashion?

I was expecting the output of print(h) to still show up as {'value': 5, 'next': {'value': 10, 'next': None}}.

CodePudding user response：

My understanding is that at this point h and t will start referring to different memory addresses.

True, but h["next"] and t reference the same.

Here is a visualisation of all the actions you performed:

t = {"value": 5, "next": None}
h = t

The resulting state can be pictured like this:

  t     h
  ↓     ↓
┌────────────┐
│ value: 5   │
│ next: None │
└────────────┘

n1 = {"value": 10, "next": None}
t["next"] = n1

The resulting state can be pictured like this:

  t     h          n1
  ↓     ↓          ↓
┌────────────┐   ┌────────────┐
│ value: 5   │   │ value: 10  │
│ next: ────────►│ next: None │
└────────────┘   └────────────┘

Then you prepare a next operation with:

t = n1

        h          n1    t
        ↓          ↓     ↓
┌────────────┐   ┌────────────┐
│ value: 5   │   │ value: 10  │
│ next: ────────►│ next: None │
└────────────┘   └────────────┘

Here you can already see that although h and t reference different nodes, they are not independent. h["next"] references the same node as t.

Then the script continues with:

n2 = {"value": 16, "next": None}

The resulting state can be pictured like this:

        h          n1    t          n2
        ↓          ↓     ↓          ↓
┌────────────┐   ┌────────────┐   ┌────────────┐
│ value: 5   │   │ value: 10  │   │ value: 16  │
│ next: ────────►│ next: None │   │ next: None │
└────────────┘   └────────────┘   └────────────┘

The following statement:

t["next"] = n2

...leads to this:

        h          n1    t          n2
        ↓          ↓     ↓          ↓
┌────────────┐   ┌────────────┐   ┌────────────┐
│ value: 5   │   │ value: 10  │   │ value: 16  │
│ next: ────────►│ next: ────────►│ next: None │
└────────────┘   └────────────┘   └────────────┘

Here we have t still referencing a sublist of h.

I hope this clarifies it.