Need help understanding python simple linked list program

Question

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..

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?
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.

There is a lot to be said. Study Python, there are many good resources available. — Pynchia
– Pynchia, Commented Jun 29, 2015 at 5:11

James · Accepted Answer · 2015-06-29 05:02:21Z

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).
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.

answered Jun 29, 2015 at 5:02

James

1,2488 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Siddarth Over a year ago

How is next_node an instance of class Node? Is'nt it a variable in class Node, I know that new_node is instance of Node because of new_node = Node(d,self.root).

James Over a year ago

When you have a LinkedList with at least one node, and you add() a new node, you construct this new node with a reference to the root. Notice in Node's __init__(), the old root (which points to some node) becomes the next of a new node, and the new root then is set to this new node.

shaktimaan · Accepted Answer · 2015-06-29 05:16:44Z

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.

Collectives™ on Stack Overflow

Need help understanding python simple linked list program

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related