#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    75
    Rep Power
    2

    Python and pointers


    I am trying to make a simple linked list program in python as we make in c with a node and pointer to next node.
    I am having considerable difficulty getting it right. I made an exact copy of the c code with works in python. It does not work.

    Here is the python code for a simple linked list: -
    Code:
    class Node:
        def __init__ (self, key):
            self.key = key
            self.next = None
    
    def insert (head, key):
        if head is None:
            head = Node(key)
        else:
            cur = head
            while cur.next is not None:
                cur = cur.next
            cur.next = Node(key)
    
    head = None
    insert (head, 1)
    insert (head, 2)
    This does not work. Why is this? I made an almost similar code in c and it works there.

    Thank You!
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2009
    Posts
    491
    Rep Power
    33
    To start you off there are errors that should show up when you try to run the code. You do not keep track of the class instances anywhere, All variables from the function "insert" are garbage collected, therefore do not remain after the function returns, so there is no linked list anywhere. See the code below with print statements and comments added. Also you have to decide and code how you want the records linked; by color, by type, etc. Right now you link the first record to the second to the third which is just a sequential file which can be read sequentially just as easily, easier in fact. There are many examples of this in Python on the web as it is a common homework question.
    Code:
    head = None
    insert (head, 1) 
    print head
    insert (head, 2)     ## head still equals None
    print head
    Last edited by dwblas; August 11th, 2013 at 01:03 PM.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    75
    Rep Power
    2
    Originally Posted by dwblas
    To start you off there are errors that should show up when you try to run the code. You do not keep track of the class instances anywhere, All variables from the function "insert" are garbage collected, therefore do not remain after the function returns, so there is no linked list anywhere. See the code below with print statements and comments added. Also you have to decide and code how you want the records linked; by color, by type, etc. Right now you link the first record to the second to the third which is just a sequential file which can be read sequentially just as easily, easier in fact. There are many examples of this in Python on the web as it is a common homework question.
    Code:
        else:
            cur = head
            while cur.next is not None:
    
    head = None
    insert (head, 1) 
    print head
    insert (head, 2)     ## head still equals None
    print head
    I changed my code to head = insert(head, 1) and it worked. It was passing by value so no changes were being made.
    Is there a way to pass by reference in python?
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    75
    Rep Power
    2
    There is another big problem I am facing here.
    When I write head.next = Node(key), will python store the whole Node class in head.next or will it store the pointer to the Node class in head.next?
  8. #5
  9. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,625
    Rep Power
    4247
    Originally Posted by Avichal
    I changed my code to head = insert(head, 1) and it worked. It was passing by value so no changes were being made.
    Is there a way to pass by reference in python?
    Python actually passes everything by reference, but you need to understand how it works. For one thing, variables and constants are treated a bit differently than other languages:
    Code:
    >>> x = 20     # Creates an object for '20' in the memory and another for x and points x as a reference to the 20 object
    >>> y = 20     # '20' is already created, so create y and point it to the '20' object
    >>> print(id(x))
    44192896
    >>> print(id(y))    
    44192896       # As you can see, both x and y are pointing to the same '20' object in memory
    >>> y += 1    # Now create a new '21' object and point y to it
    >>> print(id(y))
    44192928       # Note that y is now referring to a different object
    # Now if you create another variable and set its value to 21
    # the id(variable) will be the same as id(y))
    Takes a little while to get used to it if you're coming from a different programming language background, but it becomes very logical after a little while, especially if you think in terms of implementing a simple object-oriented interpreter yourself.

    For people coming from C-like languages, the main reason they ask for passing by reference is because they want the function to return more than one value back to the caller. Python solves this issue in a different manner by allowing multiple return values:
    Code:
    def somefunc(x, y):
        return 7, 8, 9
    
    a, b, c = somefunc(x, 42)
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  10. #6
  11. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,625
    Rep Power
    4247
    Originally Posted by Avichal
    There is another big problem I am facing here.
    When I write head.next = Node(key), will python store the whole Node class in head.next or will it store the pointer to the Node class in head.next?
    Python will store the reference to a Node object in head.next.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    75
    Rep Power
    2
    If everything is passed by reference in python, then why didn't my original code work?
    When I switched to head = insert(head, 1), it worked. So it is passed by value, right?
    I don't understand how it's passed by reference and still value of head remains unchanged.
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2009
    Posts
    491
    Rep Power
    33
    Some objects are defined as mutable and some are immutable, which is something you have to learn in Python, and has nothing to do with how they are passed. From the python docs
    for instance, numbers, strings and tuples are immutable, while dictionaries and lists are mutable.
    The example code below, not the same as yours, uses a list which is mutable so does not have to be returned.
    Code:
    class Node:
        def __init__ (self, key):
            self.key = key
            self.next = None
    
    def insert (head, key):
        cur.append(Node(key))
        if len(cur) > 1:
            previous = cur[-2]
            previous.next = key
    
    cur = []
    head = None
    for rec in [1, 2, 3]:
        insert(head, rec)
        for node in cur:
            print node.key, node.next
        print "----------" 
    ##
    ##
    ## an immutable object like strings are __not__ changeable anywhere
    ## it should be obvious that a class instance is also immutable
    x = "abc"
    print x, id(x)
    x += "def"
    ## different id because x was not changed, now is a new address/variable
    print x, id(x)  
    
    ## list
    x = [1, 2]
    print x, id(x)
    x += [3]
    print  x, id(x)  ## same address
    Last edited by dwblas; August 12th, 2013 at 02:29 PM.
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    75
    Rep Power
    2
    I don't understand how your answer answers my question. I must be missing something.
    I asked how was head not being changed in my code even if it is passed by reference?
  18. #10
  19. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2009
    Posts
    491
    Rep Power
    33
    This is as simple as I can put it. If you don't understand this then you are on your own. Note that all id's, memory address in CPython, below are the same until the string is modified, and since strings are immutable, the same variable name now points to a new block of memory.
    Code:
    def change_str(x_str):
        print "     in function id = ", id(x_str), "by reference = same as original"
        x_str += "def"
        print "     after change id =", id(x_str)
     
    
    x_str= "abc"
    print "id =", id(x_str)
    change_str(x_str)
    print "id = original", id(x_str)
    Last edited by dwblas; August 13th, 2013 at 01:07 PM.

IMN logo majestic logo threadwatch logo seochat tools logo