linked_list.py

class Node:
	''' Object to hold node objects. This class is only used by Linked List and
	should not used on its own!
	'''
	
	__slots__ = ('data', 'next')
	'''By default, instances of classes have a dictionary for attribute storage.
	This wastes space for objects having very few instance variables. The space
	consumption can become acute when creating large numbers of instances.
	https://docs.python.org/3/reference/datamodel.html#slots
	'''

	def __init__(self, data=None, next=None):
		''' Called when the instance is created. The arguments are those passed
		to the class constructor expression.
		https://docs.python.org/release/3.1.3/reference/datamodel.html#object.__init__
		'''

		self.data = data # Holds the payload of the Node.
		self.next = next # Holds the Nodes next reference.

	def __repr__(self):
		''' Called by the repr() built-in function to compute the “official”
		string representation of an object. If at all possible, this should
		look like a valid Python expression that could be used to recreate an
		object with the same value (given an appropriate environment).
		https://docs.python.org/release/3.1.3/reference/datamodel.html#object.__repr__
		'''

		return "{class_name}(data={values})".format(
			class_name = self.__class__.__name__,
			values = repr(self.data)
		)

	def __str__(self):
		'''Called by the str() built-in function and by the print() function
		to compute the “informal” string representation of an object.
		https://docs.python.org/release/3.1.3/reference/datamodel.html#object.__str__
		'''

		return str(self.data)


class EndNode:
	''' Object to represent the end node of a Linked List and
	should not used on its own!
	'''

	__slots__ = ('linked_list',)

	def __init__(self, linked_list):
		''' Holds a reference the Link List its "ending"
		'''

		self.linked_list = linked_list # Reference to the list this node ends. 

	def __bool__(self):
		''' Called to implement truth value testing and the built-in operation
		bool(); should return False or True.
		https://docs.python.org/release/3.1.3/reference/datamodel.html#object.__bool__
		
		This object should always be False
		'''

		return False # The end of the list should always be false.

	def __repr__(self):

		return "{class_name}()".format(
			class_name = self.__class__.__name__
		)

	''' Getters and Setters allow us to use functions to get and set the values
	of class attributes
	https://docs.python.org/3/library/functions.html#property
	https://en.wikipedia.org/wiki/Mutator_method
	'''
	@property
	def next(self):
		''' Loop the end of the list to head of the list
		This may not be the right thing to do???
		'''

		return self.linked_list.head

	@next.setter
	def next(self, value):
		''' Hack to allow setting an empty list Next values
		I hate this!!!
		'''

		self.linked_list.head = value


class LinkedList:
	__slots__ = ('head', 'endNode')

	def __init__(self, *items):
		self.endNode = EndNode(self) # Marker for end of list.
		self.head = self.endNode # Reference for first Node in list.

		self.append(*items)

	def __add__(self, item):
		''' Called when the + or += operator is used
		https://docs.python.org/release/3.1.3/reference/datamodel.html#object.__add__
		'''

		if isinstance(item, self.__class__):
			return self.extend(item)
		else:
			return self.append(item)

	def __bool__(self):
		return bool(len(self))
		
	def __getitem__(self, index):
		'''Called to implement evaluation of self[key]. For sequence types,
		the accepted keys should be integers and slice objects. Note that the
		special interpretation of negative indexes (if the class wishes to
		emulate a sequence type) is up to the __getitem__() method.
		https://docs.python.org/3/reference/datamodel.html#object.__getitem__
		'''

		if isinstance(index, int):
			item = self.walk(index=index)['current']
			
			if not item:
				raise IndexError("{} index out of range".format(
					self.__class__.__name__
				))

			item = item.data

		elif isinstance(index, slice):
			step = index.step or 1
			start = index.start or (0 if step > 0 else len(self)-1)
			stop = index.stop or (len(self) if step > 0 else -1)

			item = LinkedList(*(self[i] for i in range(
				start,
				stop,
				step
			)))

		else:
			raise TypeError('{} indices must be integers or slices, not {}'.format(
				self.__class__.__name__,
				type(index).__name__
			))

		return item

	def __setitem__(self, index, data):
		'''Called to implement evaluation of self[key]. For sequence types,
		the accepted keys should be integers and slice objects. Note that the
		special interpretation of negative indexes (if the class wishes to
		emulate a sequence type) is up to the __getitem__() method.
		https://docs.python.org/3/reference/datamodel.html#object.__getitem__
		'''

		if not isinstance(index, int):
			raise TypeError('list indices must be integers')

		item = self.walk(index=index)['current']
		item.data = data

		if not item:
			raise IndexError("list index out of range")

		# return item

	def __iter__(self):
		'''This method is called when an iterator is required for a container.
		This method should return a new iterator object that can iterate over
		all the objects in the container. For mappings, it should iterate over
		the keys of the container.
		https://docs.python.org/3/reference/datamodel.html#object.__getitem__
		'''

		current = self.head
		
		while current:
			yield current.data
			current = current.next

	def __len__(self):
		'''Called to implement the built-in function len().
		Called to implement the built-in function len().
		'''

		return self.walk()['position']

	def __repr__(self):

		return '{class_name}({values})'.format(
			class_name = self.__class__.__name__,
			values = ', '.join(repr(i) for i in self)
		)

	def __str__(self):
		'''Called by the str() built-in function and by the print() function
		to compute the “informal” string representation of an object.
		https://docs.python.org/release/3.1.3/reference/datamodel.html#object.__str__
		'''

		out = "HEAD=>";
		for node in self:
			out += '|{}|=>'.format(node)
		out += "None"

		return out

	def __reversed__(self):
		''' Called (if present) by the reversed() built-in to implement reverse
		iteration. It should return a new iterator object that iterates over
		all the objects in the container in reverse order.
		https://docs.python.org/release/3.1.3/reference/datamodel.html#object.__reversed__
		'''

		def rec(current):
			if current:
				yield from rec(current.next)
				yield current

		yield from rec(self.head)

	def __check_node(self, node):
		''' Will check to see if node is a Node object, if not make
		Node object and return it
		'''
		
		return node if isinstance(node, Node) else Node(node)

	def walk(self, target=None, index=None):
		''' Used to walk the list, returning the target node, the previous node
		and position if found. if nothing is found, last node is returned and a
		full count of the list.
		'''
		
		previous = self.head
		count = 0

		current = self.head
		while current:
			if current.data == target or isinstance(index, int) and index == count:
				break
			count += 1
			previous = current
			current = current.next

		return {
			'current': current,
			'previous': previous,
			'position': count,
		}

	def clear(self):
		self.head = self.endNode

		return self

	def swap(self, *items):
		self.clear()
		self.extend(*items)
		
		return self

	def sort(self, **kwags):
		return self.swap(sorted(self))

	def prepend(self, *items):
		''' Add n amount of items to the begin of the list
		'''

		holder = self.head
		last = self.endNode

		for item in items:
			last.next = self.__check_node(item)
			last = last.next
		last.next = holder

		return self

	def append(self, *items):
		''' Add n amount of items to end of the list
		and return the current list.
		'''

		last = self.walk()['previous']
		endNode = last.next

		for item in items:
			last.next = self.__check_node(item)
			last = last.next
		
		last.next = endNode

		return self

	def extend(self, *items):
		''' Add all of the nodes from another linked list or iterables to this one.
		'''

		item, *items = items

		for item in item:
			self += item

		return self.extend(*items) if items else self

	def insert(self, before, *items, **kwags):
		''' Insert a item before the target node. If the target is not found
		this will append it to the end of the list
		'''
		item, *items = items
		before = before if isinstance(before, Node) else self.walk(before, **kwags)['previous']

		if before:
			item = self.__check_node(item)
			item.next = before.next
			before.next = item

		return self.insert(item, *items, **kwags) if items else self

	def search(self, target):
		''' Finds and returns the target node, if the node is not found, None
		is returned
		'''

		return self.walk(target)['current']

	def delete(self, target):
		''' Deletes and returns the target node. If no node is found, nothing
		will happen.

		Return the deleted node if found, or None not found.
		'''

		node = None
		target = self.walk(target) # find the node

		if target['current']:
			node = target['current']
			target['previous'].next = target['current'].next
			node.next = None

		return node

	def print_right(self):
		out = 'None->'
		for node in reversed(self):
			out += '|{}|->'.format(node)
		out +='HEAD'

		print(out)

if __name__ == '__main__':
	ll = LinkedList(3, 4, 5)
	ll.append(6, 7, 8)
	ll.prepend(1)
	ll.insert(3, 2)
	ll += 9
	
	l2 = LinkedList(10, 11, 12)
	ll += l2

	print(ll)
	ll.print_right()
	me = LinkedList(*'william')

	ll = LinkedList(*range(0,6))