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

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

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.

StackExchange Code Review Q#114817, answer score: 2