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
