python linklist pointer and size

Question

I am a rookie python programmer. I see the leetcode's definition of a linked list below. I got 2 questions for this concept, any help would be appreciated. Thanks in advance

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

Q1 Just wonder what is the type of the "self.next", I know in C++, it should be a pointer that represents the address of the next node. But python does not have that type, so I am confused what type "next" is.

Q2 Some tell me next is just a name. If that is the case, I run the code below,

head =ListNode(1)
print sys.getsizeof(head)
head.next = ListNode(2)
print sys.getsizeof(head)

first the head.next is 'None', and then it is assigned to another ListNode type, but I get the same size of head before and after this change, which I think the size of head should be larger since one of its member (next) is changed from None type to ListNode type. I am just confused about this, thank you so much!

PS. In my understanding, if I keep adding new nodes to the linklist, the head will be larger and larger since there are more and more 'nested' member 'next', just point out where I get wrong, thanks.

Its python you can assign pretty much anything to it, but it would need to be a `Node` type which has a `next` parameter for the list to work. You'd do better to create an `add` method to the list class, rather than explicitly adding to `.next`. You could put a type check in there or in python 3.5+ there is a notion of types. The size will remain the same no matter what as an actual node is just a value and a reference to the next node. If you wanted to know how many nodes there are you need to walk the list to count the nodes or else maintain a count when you add nodes. — Paul Rooney, Sep 11 '16 at 23:24
thanks for the clarification, and one more question about the reference, if the size of the reference does not change, why we would have different size for reference of a int and the reference of list, since in this case they are both reference just that the object they refer are different. — Muhe Xie, Sep 11 '16 at 23:47
I'm not 100% certain to be honest. But I know that although everything in python is a reference. An int value is an immutable reference and so is copied when its assigned to (akin to pass by value in c++) but the `ListNode` like built-in lists, dicts etc is a mutable reference and so changeable by a function its passed into (akin to non-const reference in c++). This semantic difference may account for a difference in size. [This](http://stackoverflow.com/questions/6158907/what-does-python-treat-as-reference-types) question might be of interest. — Paul Rooney, Sep 11 '16 at 23:56

score 0 · Answer 1 · edited May 23 '17 at 10:33

Question 1:

Python variables are dynamically typed. (i.e. a variable could hold an int, and then hold a list, and then any other arbitrary object, etc).

In your case, Head.next starts by referencing, None a NoneType object.

After you assign it a different value (ListNode(2)), the Head.next now references the newly created ListNode object.

Question 2:

Why doesn't the size change. I'm not an expert on how python's sys.getsizeof works, but from what I can gather, is that List.next in both cases is a reference variable (i.e. a variable that references some other object). The size doesn't change because sys.getsizeof finds the size of the object's variables. Where Head.next is just a reference to some other object in both cases.

See, How do I determine the size of an object in Python?, for more complete answers on how sys.getsizeof works.

Thank you so much! So did you mean when I when we talk about a reference variable, the function sizeof(Var1) get the size of the reference variable it self rather then the size of the object it points to? — Muhe Xie, Sep 11 '16 at 23:51
@MuheXie Yes, that's what I understood from reading about it. — Timothy Murphy, Sep 12 '16 at 01:21

score 0 · Answer 2 · answered Sep 11 '16 at 23:27

My interpretation of a linked list.

class LinkedList(object):
    class Node(object):
        def __init__(self, val=None, next=None, previous=None):
            self.val = val
            self.next = next
            self.last = previous

    def __init__(self):
        self.length = 0
        self.start = None
        self.end = None

    def append(self, value):
        self.length += 1
        if not self.start:
            self.start = self.Node(value)
        else:
            if not self.end:
                self.end = self.Node(value)
                self.end.previous = self.start
                self.end.next = self.start
                self.start.next = self.end
            else:
                end = self.Node(value)
                self.end.next = end
                end.previous = self.end
                self.end = end
                self.end.next = self.start

    def prepend(self, value):
        self.length += 1
        if not self.start:
            self.start = self.Node(value)
        else:
            n = self.Node(value, self.start, self.end)
            self.start.previous = n
            self.start = n

    def __len__(self):
        return self.length

    def __iter__(self):
        self.position = 0
        return self

    def next(self):
        self.position += 1
        if self.position-1 >= len(self):
            raise StopIteration
        if self.position-1 == 0:
            return self.start
        cnt = 0
        n = self.start
        while cnt<self.position-1:
            n = n.next
            cnt += 1
        return n


    def __getitem__(self, index):
        if index == 0:
            return self.start

        if index == -1:
            return self.end

        cnt = 0
        n = self.start
        while cnt<index+1:
            n = n.next
            cnt += 1
        return n.val

    def __repr__(self):
        return repr(tuple(x.val for x in self))

l = LinkedList()
l.append(4)
l.append(5)
l.append(3)
l.prepend(0)
print l
print l[1]

python linklist pointer and size

2 Answers2