Created
February 19, 2019 08:32
-
-
Save fattakhov/f78b4e1138e721e13dd336ee279961c6 to your computer and use it in GitHub Desktop.
Реализация односвязного списка
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
class Node: | |
"""Класс элемента односвязного списка | |
Хранит два атрибута: само значение элемента и ссылку на следующий элемент коллекции | |
""" | |
def __init__(self, value, following=None): | |
self._value = value | |
self._following = following | |
def __str__(self): | |
return str(self.value) | |
# region :: Properties | |
@property | |
def following(self): | |
return self._following | |
@following.setter | |
def following(self, following): | |
self._following = following | |
@property | |
def value(self): | |
return self._value | |
@value.setter | |
def value(self, value): | |
self._value = value | |
# endregion | |
class LinkedList: | |
""" Класс односвязного списка | |
""" | |
def __init__(self, iterable=None): | |
self._length = 0 | |
self._root = None | |
self._last = None | |
if iterable: | |
for element in iterable: | |
self.append(element) | |
# region :: Magic methods | |
def __len__(self): | |
return self._length | |
def __getitem__(self, key): | |
if not isinstance(key, int): | |
raise TypeError('list indices must be integers or slices, not ' + key.__class__.__name__) | |
if len(self) < key: | |
raise IndexError('list index out of range') | |
iterator = 0 | |
current = self._root | |
while iterator < key: | |
current = current.following | |
iterator += 1 | |
return current.value | |
def __setitem__(self, key, value): | |
if not isinstance(key, int): | |
raise TypeError('list indices must be integers or slices, not ' + key.__class__.__name__) | |
if len(self) < key + 1: | |
raise IndexError('list assigment index out of range') | |
iterator = 0 | |
parent = self._root | |
current = self._root.following | |
while iterator < key: | |
parent = current | |
current = current.following | |
iterator += 1 | |
parent.value = value | |
def __str__(self): | |
return '[' + ','.join(str(value) for value in self ) + ']' | |
def __iter__(self, over_nodes=False): | |
current = self._root | |
while current: | |
yield current if over_nodes else current.value | |
current = current.following | |
def __eq__(self, other): | |
return list(self) == list(other) | |
# endregion | |
def append(self, x): | |
if self: | |
self._last.following = Node(x) | |
self._last = self._last.following | |
else: | |
self._root = Node(x) | |
self._last = self._root | |
self._length += 1 | |
def extend(self, x): | |
for element in x: | |
self.append(element) | |
def insert(self, x, i): | |
node = Node(x) | |
if i == 0: | |
node.following = self._root | |
self._root = node | |
if not self._last: | |
self._last = self._root | |
elif i >= len(self): | |
if not self: | |
self._root = node | |
self._last = self._root | |
else: | |
self._last.following = node | |
self._last = node | |
else: | |
node.following = self[i] | |
self[i - 1].following = node | |
self._length += 1 | |
def remove(self, x): | |
previous = self._root | |
for node in self.__iter__(over_nodes=True): | |
if node.value == x: | |
if node == self._root: | |
self._root = node.following | |
self._length -= 1 | |
else: | |
if self._last == node: | |
self._last = previous | |
previous.following = node.following | |
self._length -= 1 | |
del node | |
break | |
else: | |
previous = node | |
def pop(self, i=None): | |
if not self: | |
raise IndexError('pop from empty list') | |
popped_value = Node | |
for node in self.__iter__(over_nodes=True): | |
if node.following == self._last: | |
node.following = Node | |
popped_value = self._last.value | |
self._last = node | |
break | |
elif not node.following: | |
self._last = None | |
self._root = None | |
popped_value = node.value | |
break | |
self._length -= 1 | |
return popped_value | |
def copy(self): | |
return LinkedList(self) | |
def count(self, x): | |
counter = 0 | |
for value in self: | |
if value == x: | |
counter += 1 | |
return counter | |
import unittest | |
from functools import partial | |
class TestLinkedListClass(unittest.TestCase): | |
""" TestCase для тестирования класса списка | |
""" | |
def setUp(self): | |
self.empty_list = LinkedList() | |
self.non_empty_list = LinkedList(range(0, 10)) | |
def test_len(self): | |
self.assertEqual(len(self.empty_list), 0) | |
self.assertEqual(len(self.non_empty_list), 10) | |
def test_getitem(self): | |
for i in range(0, 10): | |
self.assertEqual(self.non_empty_list[i], i) | |
def test_setitem(self): | |
self.assertRaises(TypeError, partial(self.non_empty_list.__setitem__, None, None)) | |
self.assertRaises(IndexError, partial(self.non_empty_list.__setitem__, 11, None)) | |
self.assertRaises(IndexError, partial(self.non_empty_list.__setitem__, 10, None)) | |
self.non_empty_list[1] = -1 | |
self.assertEqual(self.non_empty_list[1], -1) | |
self.non_empty_list[0] = -2 | |
self.assertEqual(self.non_empty_list[0], -2) | |
self.non_empty_list[9] = -3 | |
self.assertEqual(self.non_empty_list[9], -3) | |
def test_str(self): | |
self.assertEqual(str(self.empty_list), '[]') | |
self.assertEqual(str(self.non_empty_list), '[0,1,2,3,4,5,6,7,8,9]') | |
def test_eq(self): | |
new_list = LinkedList(self.non_empty_list) | |
self.assertEqual(new_list, self.non_empty_list) | |
new_list[0] = 100 | |
self.assertNotEqual(new_list, self.non_empty_list) | |
def test_extend(self): | |
self.non_empty_list.extend([1,2,3]) | |
self.assertEqual(self.non_empty_list, [0,1,2,3,4,5,6,7,8,9,1,2,3]) | |
self.empty_list.extend(('a', 'b', 'c')) | |
self.assertEqual(self.empty_list, ('a', 'b', 'c')) | |
def test_insert(self): | |
self.non_empty_list.insert(100, 0) | |
self.assertEqual(self.non_empty_list[0], 100) | |
self.assertEqual(len(self.non_empty_list), 11) | |
self.non_empty_list.insert(100, 1000) | |
self.assertEqual(self.non_empty_list[11], 100) | |
self.empty_list.insert(100, 1000) | |
self.assertEqual(self.empty_list[0], 100) | |
self.assertEqual(len(self.empty_list), 1) | |
def test_count(self): | |
self.assertEqual(self.non_empty_list.count(1), 1) | |
self.assertEqual(LinkedList([5,5,5,5,5,5]).count(5), 6) | |
def test_copy(self): | |
copied_list = self.non_empty_list.copy() | |
self.assertEqual(self.non_empty_list, copied_list) | |
self.assertNotEqual(id(self.non_empty_list), id(copied_list)) | |
def test_remove(self): | |
self.non_empty_list.remove(3) | |
self.assertEqual(len(self.non_empty_list), 9) | |
self.non_empty_list.remove(9) | |
self.assertEqual(len(self.non_empty_list), 8) | |
self.assertEqual(self.non_empty_list._last.value, 8) | |
self.non_empty_list.remove(0) | |
self.assertEqual(len(self.non_empty_list), 7) | |
self.assertEqual(self.non_empty_list._root.value, 1) | |
if __name__ == '__main__': | |
unittest.main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment