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

• Wooble: Why would you need to implement a linked list in Python?
• avinash shah: 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.
• wholerabbit: 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?
• avinash shah: @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.
• pepr: @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.

Answer 1

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.

• avinash shah: Absolutely perfect. I got my answer in the first two paragraphs. Thanks.

Answer 2

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.

Answer 3

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.

• Gareth Latty: That invites people to use name mangled variables as private. This is bad practice. Use one underscore to indicate something is internal.
• jogojapan: @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: __ is the standard way to mark a method/instance variable as private in python.
• Gareth Latty: @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: @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.

Answer 4

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.

• avinash shah: :) 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: 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...

Answer 5

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