Explanation for Linked List in Python-CodePudding

I have started learning linked list in python and after going through a lot material for leaning linked list. I found out that linked list is made of nodes(each node has two values namely the data and a address) and the first node is called the HEAD node and last node points towards the None value showing it to be the end of linked list. A linked list is formed when the previous node contains the address of the next node. In python to achieve connecting one node to another we simply assign an object to the head variable. The below code is an example

class Node:
    def __init__(self,data):
        self.data = data
        self.link = None
class SingleLinkedList:
    def __init__(self):
        self.head = None
    def display(self):
        if self.head is None:
            print("Its a Empty Linked list")
        else:
            temp = self.head
            while temp:
                print(temp,"-->"end='')
                temp = temp.link
L = SingleLinkedList()
n = Node(10)
L.head = n
n1 = Node(20)
L.head.link = n1
n2 =Node(30)
n1.link = n2
L.display()

My question is that in the linked list the node's link value(also known as reference/address value)should be contain the address of the next node, how is that achieved by the 18th line(L.head = n) of code

My assumption is that when we assign an object to a variable(head) we are actually assigning the address of that object to the variable.

I would like to know whether my assumption is correct or wrong and if its wrong why is it wrong

can someone explain the flow of the code shown in the question.

Thanks in Advance

CodePudding user response：

when we assign an object to a variable(head) we are actually assigning the address of that object to the variable. I would like to know whether my assumption is correct or wrong and if its wrong why is it wrong.

This would be true for other -- pointer-based -- languages, like C, but Python does not actually give you pointers, not even memory addresses. Python has a layer of abstraction whereby all values are objects, and names can refer to them, and several names can refer to the same object. That's all that is really relevant here, although Python has identifiers for objects (see the id function).

can someone explain the flow of the code shown in the question.

The flow can be analysed by using a debugger with which you can step through the code, set breakpoints and inspect values. Here is a rough overview of what happens:

L = SingleLinkedList()

This calls the constructor of the SingleLinkedList class: __init__ gets executed, which initialises the attributes of the new object, and L is a name given to that object:

   ┌────────────┐
L:─┤ head: None │
   └────────────┘

The next statement n = Node(10) will call the constructor of the Node class, with the data parameter as a name for 10. The new object gets its data and link attributes initialised, and n becomes a name for it:

   ┌────────────┐
L:─┤ head: None │
   └────────────┘

   ┌────────────┐
n:─┤ data: 10   │
   │ link: None │
   └────────────┘

The link is made with the assignment: L.head = n

   ┌────────────┐
L:─┤ head: ─┐   │
   └────────│───┘
            │
   ┌────────┴───┐
n:─┤ data: 10   │
   │ link: None │
   └────────────┘

So now both the n name and the L.head attribute reference the same Node object.

The next statement, n2 =Node(30) creates another Node object:

   ┌────────────┐
L:─┤ head: ─┐   │
   └────────│───┘
            │
   ┌────────┴───┐      ┌────────────┐
n:─┤ data: 10   │  n2:─┤ data: 30   │
   │ link: None │      │ link: None │
   └────────────┘      └────────────┘

And n1.link = n2 establishes the link, mutating the n1 object:

   ┌────────────┐
L:─┤ head: ─┐   │
   └────────│───┘
            │
   ┌────────┴───┐      ┌────────────┐
n:─┤ data: 10   │  n2:─┤ data: 30   │
   │ link: ────────────┤ link: None │
   └────────────┘      └────────────┘

The final call of display, will define temp to be what self.head is (with self being L):

   ┌────────────┐
L:─┤ head: ─┐   │
   └────────│───┘
    temp:─┐ │
   ┌──────┴─┴───┐      ┌────────────┐
n:─┤ data: 10   │  n2:─┤ data: 30   │
   │ link: ────────────┤ link: None │
   └────────────┘      └────────────┘

..and in the loop temp = temp.link will make temp reference the second node:

   ┌────────────┐
L:─┤ head: ─┐   │
   └────────│───┘
            │          temp:─┐ 
   ┌────────┴───┐      ┌─────┴──────┐
n:─┤ data: 10   │  n2:─┤ data: 30   │
   │ link: ────────────┤ link: None │
   └────────────┘      └────────────┘

In a final iteration temp will get the value None, finishing the display call. I hope this clarifies it.

CodePudding user response：

So linked list has this concept of Start pointer, commonly referred to as Head. The head points to the first node of the linkedlist. So when you say,

L = SingleLinkedList()

You essentially create a linked list whose head pointer is still set to None.

In the next step you create a node :

n = Node(10)

And then in the next step you make the head pointer of your linked list point to node n1 :

n = Node(10)
L.head = n

Further on you just go on associating n1 to n2 :

n2 =Node(30)
n1.link = n2
L.display()

At the end you have the LinkedList.