Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
2.6k views
in Technique[技术] by (71.8m points)

list - Not sure how a node is passed as parameter in LinkedList instance method in python

I have started implementing linked list in python , I was able to create a traverse method and how to insert in the beginning of list method but while implementing this method of insertion of a node after a specific node , I have observed a code online that uses prev_node as one of the parameters including data , my question here is , all this time I thought only a single value parameters can be passed as param but not something that could be bundled with other attributes , for instance , data here is single value parameter but when it comes to prev_node it has prev_node.pointer in it and since it's a parameter we are passing , not sure how does this have a property of node which is pointer in this scenario? could someone please help on how is this working ? Here is the code

class Node():
    def __init__(self,data):
        self.data=data
        self.pointer=None
        
class LinkedList():
    def __init__(self):
        self.head=None
           
    
    def add_beg(self,data):
        """ add data in the beginning """
        new_node=Node(data)
        new_node.pointer=self.head
        self.head=new_node
        
    def traverse(self):
        if self.head is None:
            print('no value found ')
            return
        else:
            current=self.head
            while current is not None:
                print(current.data,'')
                current=current.pointer
                
                
    def add_after(self,prev_node,data):
        """ add data after the specific node  """
        new_node=Node(data)
        new_node.pointer=prev_node.pointer   #Here is the part I do not understand
        prev_node.pointer=new_node

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

I will try to explain with a simple example. Given a list of data elements ['B', 'D', 'E] let's create a Linked List consisting of Nodes each Node will be defined by 3 pieces of info as follows:

  • id - just a number representing the sequence of node instantiation
  • data - the data contained within the node
  • prev_node - the node id of the previous node

Given this data let's build a linked list using your add method:

LL = LinkedList() -> LL.self.head = None    
LL.add_beg('B') -> Node(1, 'B', None), LL.self.head = 1  

When we execute LL.add_beg('B') we create a Node instance and set LL.self.head = node Id
When we add a second data value

LL.add_beg('D') -> Node(2, 'D', 1), LL.self.head = 2  

At this point we have the following:

LL.self.head = 2  
Node(2, 'D', 1)
Node(1, 'B', None)

Now let's add a Node between 2 & 1, as folows:

LL.add_after(2, 'E')
  new_node = Node('E') -> Node(3,'E', None)
  new_node.pointer= prev_node.pointer -> Node(3, 'E', 1)  From the prev_pointer of Node #2
  prev_node.pointer=new_node  -> Node(2, 'D', 3)  update Node #2 with new_node ID  

The end result is a linkedList that lookslike the following:

LL.self.head = 2  
Node(2, 'D', 3)
Node(3, 'E', 1
Node(1, 'B', None)

And the new node is successfully inserted between Nodes 1 & 2.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...