Created
November 6, 2014 23:01
-
-
Save caetanus/c03acd35b2fea49b24a7 to your computer and use it in GitHub Desktop.
single linked list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # -*- coding: utf-8 -*- | |
| import sys | |
| class _ListNode(object): | |
| def __init__(self, obj): | |
| self._obj = obj | |
| self._next = None | |
| def _append(self, obj): | |
| self._next = obj | |
| def __eq__(self, obj): | |
| return self._obj == obj | |
| def __repr__(self): | |
| return repr(self._obj) | |
| class LinkedList(object): | |
| def __init__(self, sequence=None): | |
| self._len = 0 | |
| self._last = None | |
| self._first = None | |
| if sequence: | |
| self.extend(sequence) | |
| def append(self, obj): | |
| item = _ListNode(obj) | |
| if not self._first: | |
| self._first = item | |
| self._last = item | |
| self._len += 1 | |
| return | |
| self._last._append(item) | |
| self._last = item | |
| self._len += 1 | |
| def _getnode_and_prev(self, index): | |
| if index < 0: # inverse index list[-1] gets the last item | |
| item = self._len + index | |
| if index > self._len: | |
| raise IndexError("list index out of range") | |
| prev = None | |
| node = self._first | |
| i = 0 | |
| while i < index: | |
| prev = node | |
| node = node._next | |
| i += 1 | |
| return (prev, node) | |
| def _getnode(self, index): | |
| if index < 0: # inverse index list[-1] gets the last item | |
| item = self._len + index | |
| if index == self._len - 1: | |
| return last | |
| if index > self._len: | |
| raise IndexError("list index out of range") | |
| node = self._first | |
| i = 0 | |
| while i < index: | |
| node = node._next | |
| i += 1 | |
| return node | |
| def __getitem__(self, index): | |
| return self._getnode(index)._obj | |
| def __setitem__(self, index, item): | |
| self._getnode(index)._obj = item | |
| def insert(self, index, value): | |
| node = _ListNode(obj) | |
| if index == 0: | |
| old_first = self._first | |
| self._first = node | |
| node._append(old_first) | |
| self._len += 1 | |
| return | |
| if index == self._len: | |
| self.append(value) | |
| previous_node = self[index-1] | |
| next_node = previous_node._next | |
| previous_node._append(node) | |
| node._append(next_node) | |
| def extend(self, sequence): | |
| for item in sequence: | |
| self.append(item) | |
| def __iadd__(self, iterable): | |
| self.extend(iterable) | |
| def index(self, obj): | |
| for i in self: | |
| if i == obj: | |
| return i._obj | |
| raise ValueError("{} is not in list".format(obj)) | |
| def __delitem__(self, index): | |
| self.pop(index) | |
| def pop(self, index=-1): | |
| prev, node = self._getnode_and_prev(index) | |
| self._len -= 1 | |
| if prev and node is not self._last: | |
| prev._next = node._next | |
| return node._obj | |
| if node is self._last: | |
| self._last = prev | |
| return node._obj | |
| if node is self._first: | |
| self._first = node._next | |
| return node._obj | |
| def __iter__(self): | |
| node = self._first | |
| yield node._obj | |
| while node._next: | |
| node = node._next | |
| yield node._obj | |
| def __len__(self): | |
| return self._len | |
| def __repr__(self): | |
| return repr([i for i in self]) | |
| def _index(self, value, start=0, stop=sys.maxint): | |
| if stop is not None: | |
| if stop < 0: | |
| stop = self._len - stop | |
| elif stop > self._len: | |
| self.stop = self._len | |
| i = 0 | |
| prev = None | |
| node = self._first | |
| while i < stop: | |
| prev = node | |
| node = node._next | |
| if i < start: | |
| i += 1 | |
| continue | |
| if node._obj == value: | |
| return (i, prev, node) | |
| raise ValueError("{} is not i in list".format(repr(obj))) | |
| def index(self, value, start=0, stop=sys.maxint): | |
| i, node, prev = self._index(value, start, stop) | |
| return i | |
| def remove(self, value): | |
| i, node, prev = self._index(value) | |
| if prev is None: | |
| self._first = node._next | |
| return | |
| if node is self._last: | |
| self._last = prev | |
| return | |
| self.prev = self.node._next | |
| def __getslice__(self, start=0, end=sys.maxint, step=1): | |
| # list[i:j] | |
| if step < 0: | |
| raise AttributeError("single linked list cannot iterate backwards.") | |
| if end > self._len: | |
| end = self._len | |
| node = self._getnode(start) | |
| new_list = self.__class__() | |
| new_list.append(node._obj) | |
| while start <= end: | |
| start += step | |
| if node._next == None: | |
| break | |
| for i in range(step): | |
| node = node._next | |
| new_list.append(node._obj) | |
| return new_list | |
| def sort(self): | |
| raise NotImplementedError("cannot sort a single linked list.") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment