what does object.next actually means in python

Shekhar lohach 0
Viewed 25

I have started studying linkedlist and I couldnt figure out what does .next does. I understand it is pointing to next object but how it is doing that ? for example below is the code to insert new node to linked list.

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
        
class ll:
    def __init__(self):
        ll.head=None

def insertEnd(value):
    newnode = Node(value)
    currentNode = l.head
    while(currentNode.next):
        currentNode = currentNode.next
    currentNode.next = newnode

if __name__ == '__main__':
    l = ll()
    l.head = Node(6)
    second = Node(2)
    l.head.next = second
    insertEnd(9)

So how is thing happening. Kindly help me to understand.

linked-list python-3.x
1 Answers

It may help to go through the program and visualise the state of the linked list:

When l = ll() is executed, the constructor runs and l gets to reference that data structure:

 l
 ↓
┌────────────┐ 
│ head: None │
└────────────┘

Then l.head = Node(6) will run the Node constructor, and then assign the reference it gets from that to the above pictured head member.

 l
 ↓
┌────────────┐ 
│ head: ─┐   │
└────────│───┘
         │
         ▼
┌────────────┐ 
│ data: 6    │
│ next: None │
└────────────┘

A similar thing happens with second = Node(2), but now the returned reference is assigned to a name, not an attribute:

 l
 ↓
┌────────────┐ 
│ head: ─┐   │
└────────│───┘
         │         second
         ▼          ↓
┌────────────┐    ┌────────────┐ 
│ data: 6    │    │ data: 2    │
│ next: None │    │ next: None │
└────────────┘    └────────────┘

With l.head.next = second the next attribute of the first node gets a reference to the second node:

 l
 ↓
┌────────────┐ 
│ head: ─┐   │
└────────│───┘
         │         second
         ▼          ↓
┌────────────┐    ┌────────────┐ 
│ data: 6    │    │ data: 2    │
│ next: ─────────►│ next: None │
└────────────┘    └────────────┘

Now the more challenging insertEnd(9) call is made. In insertEnd, newnode = Node(value) creates a new node and assigns its reference to a local name:

 l
 ↓
┌────────────┐ 
│ head: ─┐   │
└────────│───┘
         │         second            newNode (local)
         ▼          ↓                 ↓
┌────────────┐    ┌────────────┐    ┌────────────┐ 
│ data: 6    │    │ data: 2    │    │ data: 9    │
│ next: ─────────►│ next: None │    │ next: None │
└────────────┘    └────────────┘    └────────────┘

Another local name gets a reference to the first node that is already in the list: currentNode = l.head:

 l
 ↓
┌────────────┐ 
│ head: ─┐   │
└────────│───┘
         │         second            newNode (local)
         ▼          ↓                 ↓
┌────────────┐    ┌────────────┐    ┌────────────┐ 
│ data: 6    │    │ data: 2    │    │ data: 9    │
│ next: ─────────►│ next: None │    │ next: None │
└────────────┘    └────────────┘    └────────────┘
  ↑
 current (local)

Then the loop starts. It will make one iteration where it updates the local name to get another reference: currentNode = currentNode.next

 l
 ↓
┌────────────┐ 
│ head: ─┐   │
└────────│───┘
         │         second            newNode (local)
         ▼          ↓                 ↓
┌────────────┐    ┌────────────┐    ┌────────────┐ 
│ data: 6    │    │ data: 2    │    │ data: 9    │
│ next: ─────────►│ next: None │    │ next: None │
└────────────┘    └────────────┘    └────────────┘
                    ↑
                   current (local)

At this point the loop condition is no longer true, so the loop exits. At this point we can be sure that current references the tail node in the linked list. Finally, that tail node gets an update to its next attribute, so it links to the new node: currentNode.next = newnode

 l
 ↓
┌────────────┐ 
│ head: ─┐   │
└────────│───┘
         │         second            newNode (local)
         ▼          ↓                 ↓
┌────────────┐    ┌────────────┐    ┌────────────┐ 
│ data: 6    │    │ data: 2    │    │ data: 9    │
│ next: ─────────►│ next: ─────────►│ next: None │
└────────────┘    └────────────┘    └────────────┘
                    ↑
                   current (local)

The insertEnd function returns, so all its local names are discarded, and the main program sees this:

 l
 ↓
┌────────────┐ 
│ head: ─┐   │
└────────│───┘
         │         second
         ▼          ↓
┌────────────┐    ┌────────────┐    ┌────────────┐ 
│ data: 6    │    │ data: 2    │    │ data: 9    │
│ next: ─────────►│ next: ─────────►│ next: None │
└────────────┘    └────────────┘    └────────────┘
trincot0
Related