Singly Linked List in Python

Question

A school student here. Hope you are having a nice day.

So, I implemented a Singly Linked List in Python and of course also a Node. I tried to make it have the best Big O time complexity I could. Here it is, please tell me what do you think can be improved, changed, etc.

class LinkedList():
 """
 A basic class implementing a Singly Linked List.
 LinkedList() - new empty linked list
 LinkedList(iterable) - new linked list with items of iterable:
 head - iterable[0] tail - iterable[-1]
 """
 class Node():
 """A class for a singly linked list node."""
 def __init__(self, value):
 """Initialize default values."""
 self.value = value
 self.link = None # by default a node is linked to nothing
 def __init__(self, seq=()):
 """Initialize default values."""
 self.size = 0
 # While instantiated there are no elements in list
 # but None, to which will be linked the first element
 self.head = None
 node = self.head
 for i in seq: # iterate through and copy contents
 new_node = self.Node(i)
 if node:
 node.link = new_node
 node = node.link
 else:
 # runs only once, at the first item,
 # when the list is empty(head is None)
 self.head = new_node
 node = self.head
 self.size += 1
 def __len__(self):
 """Implement len(self). Return the number of items in list."""
 return self.size
 def __iter__(self):
 """Implement iter(self)."""
 node = self.head
 while node:
 yield node.value
 node = node.link
 def __repr__(self):
 """Return repr(self)."""
 return self.__str__()
 def __str__(self):
 """Define string casting for the list."""
 node = self.head
 s = ''
 while node:
 s += str(node.value) + ' => '
 node = node.link
 return s + 'None'
 def __getitem__(self, index):
 """Implement indexing access: a[b]."""
 # change index if negative
 index = self.size + index if index < 0 else index
 if 0 <= index < self.size:
 i = 0
 node = self.head
 while i < index:
 node = node.link
 i += 1
 return node.value
 else:
 raise IndexError('list index out of range')
 def __setitem__(self, index, item):
 """Implement indexed assignment."""
 # change index if negative
 index = self.size + index if index < 0 else index
 if 0 <= index < self.size:
 i = 0
 node = self.head
 while i < index:
 node = node.link
 i += 1
 node.value = item
 else:
 raise IndexError('list assignment index out of range')
 def __delitem__(self, index):
 """Implement indexed deletion."""
 # change index if negative
 index = self.size + index if index < 0 else index
 # check .remove() method for explanation
 if 0 < index < self.size:
 i = 0
 node = self.head
 while i < index - 1:
 node = node.link
 i += 1
 node.link = node.link.link
 self.size -= 1
 elif index == 0:
 self.head = self.head.link
 self.size -= 1
 else:
 raise IndexError('list deletion index out of range')
 def __contains__(self, item):
 """Implement 'in' access: if item in..."""
 i = 0
 node = self.head
 while i < self.size:
 if node.value == item:
 return True
 node = node.link
 i += 1
 return False
 def insertStart(self, item):
 """Insert an item to the head of the link."""
 self.size += 1
 new_node = self.Node(item)
 if not self.head: # check in the list has a head
 self.head = new_node
 else:
 new_node.link = self.head # link the node to the head
 self.head = new_node # make it the head
 def insertEnd(self, item):
 """Insert an item at the tail."""
 new_node = self.Node(item)
 if self.head: # check if list is empty
 node = self.head
 while node.link: # iterate through the list to get to the tail
 node = node.link
 node.link = new_node
 else:
 self.head = new_node # create a head
 self.size += 1
 def insert(self, index, item):
 """Insert given item before specified index."""
 t = type(index)
 if t is not int:
 raise TypeError('{} cannot be interpreted as an integer'.format(t))
 else:
 # change index if negative
 index = self.size + index if index < 0 else index
 if index > self.size - 1: # check for special cases
 self.insertEnd(item)
 elif index <= 0:
 self.insertStart(item)
 else: # iterate through and insert item
 i = 0
 node = self.head
 while i < index - 1:
 node = node.link
 i += 1
 new_node = self.Node(item)
 new_node.link = node.link
 node.link = new_node
 self.size += 1
 def remove(self, value=None):
 """
 Remove the first occurence of the value(default head).
 Raises a ValueError if the is not present.
 Raises an IndexError if the list is empty.
 """
 if not self.head:
 raise IndexError("remove from an empty list")
 else:
 if value: # check if value is provided
 if self.head.value == value:
 self.head = self.head.link
 else:
 node = self.head
 try:
 # iterate through the list while checking for
 # given value and being one step behind to be
 # able to efficiently remove it
 while node.link.value != value:
 node = node.link
 node.link = node.link.link
 except AttributeError: # mute the original error
 raise ValueError('value not present in list') from None
 else:
 self.head = self.head.link # value not present. remove head
 self.size -= 1
 def index(self, item):
 """Return index of first occurence of specified item. -1 if absent."""
 i = 0
 node = self.head
 while i < self.size:
 if node.value == item:
 return i
 node = node.link
 i += 1
 return -1
 def reverse(self):
 """Reverse list in place."""
 current_node = self.head
 prev_node = None
 next_node = None
 while current_node:
 next_node = current_node.link
 current_node.link = prev_node
 prev_node, current_node = current_node, next_node
 self.head = prev_node

Answer 1

Your code is good because you implemented many __methods__ that allow natural use of the class with for and print built-ins.

A great way to make it easier to improve the code is to add automatic tests, for example with doctest.

Let me show you a practical example:

I note that __str__ repeats logic already inside __iter__, so first thing I write a test to see how it works now:

import doctest
class LinkedList():
 def __str__(self):
 """
 Define string casting for the list.
 >>> str(LinkedList([1, 2, 3]))
 '1 => 2 => 3 => None'
 """
 # old code
if __name__ == "__main__":
 doctest.testmod()

Than I write the new implementation that uses __iter__ through the for keyword:

def __str__(self):
 """
 Define string casting for the list.
 >>> str(LinkedList([1, 2, 3]))
 '1 => 2 => 3 => None'
 """
 return ' => '.join((str(x) for x in self)) + ' => None'

Just executing the code runs the test and I know that the new implementation works the same as the old one at least in this case. More tests can be added for example for empty list or different data types inside the list but this is the basic idea.

The same can be said for index, you can reuse the __iter__ logic once again:

def index(self, item):
 """
 Return index of first occurence of specified item. -1 if absent.
 >>> LinkedList(['a', 'b', 'c', 'd']).index('b')
 1
 """
 for index, x in enumerate(self):
 if x == item:
 return index
 return -1

In general when you write a collection the __iter__ method is very useful for implementing other methods.

• Nick: Thanks for telling me that I could use __iter__ method inside class definition. I didn't know that it could be used inside definition so I went for more manual solutions. I will definitely keep that in mind.
• Solomon Ucko: What about map(str, self) instead of (str(x) for x in self)?
• Caridorc: @Solomon Ucko Yes It is the same, you can use It no problem