Siddarth
Siddarth

Reputation: 1020

Need help understanding python simple linked list program

Below is a simple linked list program, I know how a linked list works conceptually ( adding, removing, etc) but I am finding it hard to understand how it works from an object oriented design perspective.

Code:

class Node():

    def __init__(self,d,n=None):
        self.data = d
        self.next_node = n   

    def get_next(self):
        return self.next_node

    def set_next(self,n):
        self.next_node = n

    def get_data(self):
        return self.data

    def set_data(self,d):
        self.data = d

class LinkedList():

    def __init__(self,r = None):
        self.root = r
        self.size = 0 

    def get_size(self):
        return self.size

    def add(self,d):
        new_node = Node(d,self.root)
        self.root = new_node
        self.size += 1

    def get_list(self):
        new_pointer = self.root
        while new_pointer:
            print new_pointer.get_data()
            new_pointer = new_pointer.get_next()

    def remove(self,d):
        this_node = self.root
        prev_node = None
        while this_node:
            if this_node.get_data() == d:
                if prev_node:
                    prev_node.set_next(this_node.get_next())
                else:
                    self.root = this_node
                self.size -= 1
                return True
            else:
                prev_node = this_node
                this_node = this_node.get_next()
        return False

    def find(self,d):
        this_node = self.root
        while this_node:
            if this_node.get_data() == d:
                return d
            else:
                this_node = this_node.get_next()
        return None

myList = LinkedList()
myList.add(5)
myList.add(8)
myList.add(12)
myList.get_list() 

I have couple questions here..

  1. How is it storing the values. As far as I understand each variable can hold one value. So how does data / next_node hold multiple values. And does next_node hold the memory location of the next node?

  2. new_pointer.get_data() How is new_pointer able to access get_data()? Don't we need to have an instance to access methods of Node?

This question may be silly, but I am quiet new to object oriented programming. If someone can answer these questions or post an external link addressing these questions it would be really helpful.

Thanks in advance.

Upvotes: 1

Views: 353

Answers (2)

shaktimaan
shaktimaan

Reputation: 1857

myList.root is storing one value only that is the root of the list. See initially when you do:

myList = LinkedList()

in memory myList.root = None (according to __init__ of LinkedList). Now:

myList.add(1)

Then this statement is called:

new_node = Node(d,self.root)        #Note here self.root = None

and then: def init(self,d,n=None): self.data = d self.next_node = n
So our list is : 1--> None.Now:

myList.add(2)

then again this statement is called:

new_node = Node(d,self.root)        #Note here self.root has some value

now a new node object is created and its next is assigned to myList.root. So our list becomes : 2-->1--> None Going in similar fashion whole list is assigned. Key thing to note here is that myList.root is always storing the top most node which in turn holds the next node and so on.

For your second question, it is quite clear from above explaination that always the object of class node is available to myList.root which in turn has next_node which is again an object of 'node'. So they all have access to 'get_data()' method.

Upvotes: 0

James
James

Reputation: 1238

  1. next_node is an instance of Node and so it has its own data field. next_node is a reference to the node object, which is some memory address (however it is not a C-like pointer, as you don't need to dereference it or anything).

  2. I'm assuming you are talking about get_list(). new_pointer is an instance of Node. (unless it is None, in which case you would never get into the get_data() call). When you do an add, you create this instance of Node and set root to it. Then in get_list you set new_pointer to root.

Upvotes: 1

Related Questions