Node, Link, Node, Link, Node: Linking Nodes into a LinkedList

Question

For practice in Python OOP (first time) and for some relaxation from trying to learn Serialization in Java, I decided to write a LinkedList in Python. Now, this class would be pretty useless, because in Python, instead of:

(Java)

int[] array = new int[size];
// initialization...
// Now add an object to the end
int[] newArray = Arrays.copyOf(array, size + 1);
newArray[size] = value; // Really annoying, is it not?

You can do:

array = [] # And other values
array.append(value)

When you want to add a value. But, since it's for practice, it's not for use.

class LinkedList:
 def __init__(self):
 self.first = None
 self.last = None
 self.size = 0
 def add(self, value):
 '''
 Adds the specified element to the end of the array.
 '''
 if not self.first: # first is None
 self.first = Node(None, None, value)
 self.last = self.first
 else:
 node = Node(self.last, None, value)
 self.last.after = node
 self.last = node
 self.size += 1
 def add_at(self, value, index):
 '''
 Adds the specified element at the specified position.
 If the given index is out of range of the list, the
 element is added to the end.
 '''
 if index >= self.size:
 self.add(value)
 if index == 0:
 new = Node(None, self.first, value)
 self.first.before = new
 self.first = new
 node = self.get_node(index)
 new = Node(node, node.after, value)
 node.after.before = node
 node.after = new
 self.size += 1
 def remove(self, index):
 '''
 Removes the specified element at the specified position.
 If the given index is out of range of the list, an
 IndexError is thrown.
 '''
 node = self.get_node(index)
 node.before.after = node.after
 node.after.before = node.before
 return node.value
 def get(self, index):
 '''
 Returns the specified element at the specified position.
 If the given index is out of range of the list, an
 IndexError is thrown.
 '''
 return self.get_node(index).value
 def get_node(self, index):
 '''
 Returns the specified node at the specified position.
 If the given index is out of range of the list, an
 IndexError is thrown.
 '''
 if index >= self.size:
 raise IndexError()
 node = None
 if index > self.size / 2:
 # From back
 node = self.last
 for i in range(index, self.size - 1):
 node = node.before
 else:
 # From front
 node = self.first
 for i in range(1, index):
 node = node.after
 return node
class Node:
 def __init__(self, before, after, value):
 self.before = before
 self.after = after
 self.value = value

Concerns:

1. I think I can separate Python from Java anc C++ now, so the ; is no longer there. But just in case, is there a stray ;?
2. Is the way this class is constructed Pythonic?
3. Are the docstrings good?

Answer 1

Methods & Naming

You're building a collection so, implicitly, you're building a contract with your user that your class will act like a collection, that you'll stick to a protocol for collections objects.

If you wan't to grasp a little more on what I’m trying to say, you can read this article.

So, even though I agree with @Dair that size would be "saffer" as _size (but hey, we’re all responsible adults around here), I strongly disagree with the size property. You should implement it as a __len__ method and use it like:

stuff = LinkedList()
length = len(stuff)

Some other methods can have more common names too:

• add \$->\$ apppend;

• add_at \$->\$ insert or __setitem__:

  __setitem__ will allow you to do stuff[3] = 'some value' and then insert is just a call to self[index] = value.

  You will need to change the signature to def __setitem__(self, key, value).

• remove \$->\$ pop (or maybe __delitem__); remove is prefered to remove by value instead of by index.
• get \$->\$ __getitem__: it will allow you to do the_value = stuff[3]; you should also remove get_node as there is little to no interest in exposing your internals to the user.

Methods that are missing

You could implement an __iter__ method that will allow you to do:

stuff = LinkedList()
# populate stuff
for elem in stuff: # will use __iter__, or fail back to __len__ + __getitem__ if not available
 do_something(elem)

It will also help you shorten __getitem__. You can use something along the lines of:

def __iter__(self):
 node = self.first
 while node is not None: # No self.size involved, yay
 yield node.value
 node = node.after

You can also implement the __reversed__ iterator using the same logic (and use it in __getitem__ too.

Using a parameter to __init__ that default to None would also be usefull to build a LinkedList out of any iterable:

def __init__(self, other=None):
 self._size = 0
 self.first = None
 self.last = None
 if other is not None:
 for element in other:
 self.append(element)

It is then easy to create stuff = LinkedList([1,2,8,12]).

And finally, you should consider adding a __str__ or __repr__ method so you can print(stuff). Use __iter__ to simplify it.

• Blue: Great answer, I didn't know about all the built-in names. Is there some documentation with a complete list?
• 301_Moved_Permanently: For "magic methods" names, have a look at this section of the docs. For the other ones such as insert or append, help([]) in an interactive session might come in handy.