Python basic data structure Implementation

Question

I am a C++ coder. Recently started with Python. I was having a look at a simple Linked List implementation in Python. I am bit confused here. Not only here but also in Tree implementation and so on with the same problem.

class Element contains data and pointer to next node. Perfect no problem. However in class LinkedList I can see self.tail.next=e, now next is a variable of Element class even if it is public than also an object of Element class has to access it. Here how can we write something like self.tail.next = e as tail is just a variable of LinkedList class and is not an object of Element class. I am confused.

class Element:
        def __init__(self,x):
                self.data=x
                self.next=None


class LinkedList:
        def __init__(self):
                self.head=None
                self.tail=None

        def append(self,x):
                # create a new Element
                e = Element(x)
                # special case: list is empty
                if self.head==None:
                        self.head=e
                        self.tail=e
                else:
                        # keep head the same
                        self.tail.next=e
                        self.tail=e

Just was curious for learning stuff so that I can move on writing my own custom data structures like Random BST's and so on. So was just getting a feel of how self referential structures are implemented in Python. I can think in terms of pointers in C but am confused here. — avinash shah
– avinash shah, Commented Apr 23, 2012 at 10:29
NB. That implementation looks flawed to me at the point where self.tail.next=e and self.tail=e. That should not be done. Where did you get this? — wholerabbit
– wholerabbit, Commented Apr 23, 2012 at 10:35
@goldilocks: Thanks but I am really not interested in implementation whether it is wrong or right, just had a pythonic problem which I got answer for, below. — avinash shah
– avinash shah, Commented Apr 23, 2012 at 11:28
@avinash shah: Just a side note. There are observations that prove that vectors (arrays) of values are always better than linked lists on contemporary processors. This was actually observed also during Python development. The Python lists are implemented as dynamic arrays of references to the element objects. Because of that lists can be efficiently indexed as if they were arrays. In other words, Python lists are actually arrays with added list-interface methods. — pepr
– pepr, Commented Apr 24, 2012 at 6:35

pepr · Accepted Answer · 2012-04-23 11:06:33Z

4

Python works with references. Everything is always passed by reference, the values are always shared via references (unless explicitly copied).

Assigning an object means assigning the reference to that object. This way self.tail.next = e means: self.tail is expecting to refer to the object of the Element class. The object has the .next attribute. The self.tail.next = e means that the last element of the non-empty list is going to point to the just appended new element. Then the self.tail = e means that the reference to the last element is moved to the just appended last element.

Any variable in Python is just a reference variable with the given name. It is automatically dereferenced. Because of that it may look strangely to those familiar with classical compiled languages, like C++.

I am not sure if you can display the articles at Expert Exchange without creating the account. If yes, have a look at http://www.experts-exchange.com/Programming/Languages/Scripting/Python/A_6589-Python-basics-illustrated-part-2.html and namely the http://www.experts-exchange.com/Programming/Languages/Scripting/Python/A_7109-Python-basics-illustrated-part-3.html for the images that explain the problem.

edited Apr 23, 2012 at 11:06

answered Apr 23, 2012 at 10:50

pepr

21.1k15 gold badges83 silver badges148 bronze badges

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

1 Comment

avinash shah Over a year ago

Absolutely perfect. I got my answer in the first two paragraphs. Thanks.

Ivaylo Strandjev · Accepted Answer · 2012-04-23 10:37:25Z

1

The only place where you initialize self.tail is in append and in there you set it to be equal to e. Just a little bit above you have e = Element(x) and so e is an object of type Element. Please note that in the moment you call self.tail.next=e you know head is not none and thus tail is also not None but an instance of Element.

Hope this helps.

answered Apr 23, 2012 at 10:37

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

Comments

jogojapan · Accepted Answer · 2012-04-23 10:43:00Z

1

You wrote:

now next is a variable of Element class even if it is public than also an object of Element class has to access it.

There is a misunderstanding there. Public members (i.e. all members except those that start with two underscores) are accessible from anywhere, not only from within methods of the same class.

edited Apr 23, 2012 at 10:43

answered Apr 23, 2012 at 10:37

jogojapan

70.5k11 gold badges110 silver badges136 bronze badges

7 Comments

Gareth Latty Over a year ago

That invites people to use name mangled variables as private. This is bad practice. Use one underscore to indicate something is internal.

jogojapan Over a year ago

@Lattyware Nonsense. I did not invite anyone to do anything. It's a reality that name mangling happens, so it would have been wrong to claim that all members are readily accessible from just anywhere.

Douglas Leeder Over a year ago

__ is the standard way to mark a method/instance variable as private in python.

Gareth Latty Over a year ago

@DouglasLeeder That is not true. A single underscore is. A double underscore invokes name mangling and holds a different purpose (namely to avoid name clashes of names with names defined by subclasses).

Gareth Latty Over a year ago

@jogojapan If you are going to argue fine details, so are name-mangled variables, just are just harder to get at. My point is that if you give an answer that explains 'privateness' in Python, you need to explain that it isn't the same as in other languages, and your aim should not be to deny access to your attributes, merely to advise against it.

|

wholerabbit · Accepted Answer · 2012-04-23 10:29:44Z

0

next and tail are Elements, that's why. This would be true for a linked list in any language, including C or C++. A linked list is a list of elements linked together with pointers/references.

When the list is traversed, those links are used to get from node (element) to node. It would not make sense if they referred to other linked lists, would it? The first element in the list is the head, the last element is the tail, the next element pointed to in a node is the element after it in the list, the previous node is the element before it.

answered Apr 23, 2012 at 10:29

wholerabbit

11.6k2 gold badges40 silver badges73 bronze badges

2 Comments

avinash shah Over a year ago

:) Absolutely buddy I am confused with language semantics and not linked list. Please re-read my question (i.e. second paragraph) I am new to Python (absolute beginner)

wholerabbit Over a year ago

I read "Here how can we write something like self.tail.next = e as tail is just a variable of LinkedList class and is not an object of Element class." to mean that you believe tail and next should not be accessible as Elements and should be LinkedLists instead. If you don't mean that maybe you should edit? Otherwise I don't see any other question...

Andreas Florath · Accepted Answer · 2012-04-23 12:20:37Z

In python everything is a reference.

Please: separate the list implementation from your (application) data.

As in C++ it is good style to encapsulate the access methods - nevertheless because there are no access restrictions to instance fields they can be accessed from everywhere.

An idea of a generic double linked list (this is only a skeleton which should be enhanced - but I hope it transports the idea).

class DoubleLinkedList(object):

    class ListNode(object):

        def __init__(self):
            self.__next = None
            self.__prev = None

        def next(self):
            return self.__next

        def prev(self):
            return self.__prev

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

        def set_prev(self, prev_node):
            self.__prev = prev_node

        def is_last(self):
            return self.next()==None

    def __init__(self):
        '''Sets up an empty linked list.'''
        self.__head = DoubleLinkedList.ListNode()
        self.__tail = DoubleLinkedList.ListNode()
        self.__head.set_next(self.__tail)
        self.__tail.set_prev(self.__head)

    def first(self):
        return self.__head.next()

    def last(self):
        return self.__tail.prev()

    def append(self, list_node):
        list_node.set_next(self.__tail)
        list_node.set_prev(self.__tail.prev())
        self.__tail.set_prev(list_node)
        list_node.prev().set_next(list_node)

########################################

class MyData(DoubleLinkedList.ListNode):
    def __init__(self, d):
        DoubleLinkedList.ListNode.__init__(self)
        self.__data = d

    def get_data(self):
        return self.__data

ll = DoubleLinkedList()

md1 = MyData(1)
md2 = MyData(2)
md3 = MyData(3)

ll.append(md1)
ll.append(md2)
ll.append(md3)

node = ll.first()
while not node.is_last():
    print("Data [%s]" % node.get_data())
    node = node.next()

Collectives™ on Stack Overflow

Python basic data structure Implementation

5 Answers 5

1 Comment

Comments

7 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

Comments

7 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related