I was solving this problem for implementing LinkedList and ListNode classes, and Insert and Remove methods for LinkedList. I was wondering if I can get any code review and feedback.
class ListNode: def __init__(self, value=None): self.value = value self.next = None self.prev = None def __repr__(self): """Return a string representation of this node""" return 'Node({})'.format(repr(self.value)) class LinkedList(object): def __init__(self, iterable=None): """Initialize this linked list and append the given items, if any""" """Best case Omega(1)""" """Worst case O(n)""" self.head = None self.tail = None self.size = 0 self.length = 0 if iterable: for item in iterable: self.append(item) def __repr__(self): """Return a string representation of this linked list""" # this actually helps me to see what's inside linkedList return 'LinkedList({})'.format(self.as_list()) def setHead(self,head): self.head = head def getNext(self): return self.next def setNext(self,next): self.next = next def size(self): """ Gets the size of the Linked List AVERAGE: O(1) """ return self.count def as_list(self): """Return a list of all items in this linked list""" items = [] current = self.head while current is not None: items.append(current.value) current = current.next return items def append(self, item): new_node = ListNode(item) if self.head is None: self.head = new_node # Otherwise insert after tail node else: self.tail.next = new_node # Update tail node self.tail = new_node # Update length self.size += 1 def get_at_index(self, index): """Return the item at the given index in this linked list, or raise ValueError if the given index is out of range of the list size. Best case running time: O(1) if it's head or no value, Worst case running time: O(n) if it's in the tail [TODO]""" if not (0 <= index < self.size): raise ValueError('List index out of range: {}'.format(index)) counter = self.head for i in range(index): counter = counter.next return counter.value def prepend(self, item): """Insert the given item at the head of this linked list""" """Best case Omega(1)""" """Worst case O(1)""" new_node = ListNode(item) # Insert before head node new_node.next = self.head # Update head node self.head = new_node # Check if list was empty if self.tail is None: self.tail = new_node # Update length self.size += 1 def insert(self, value, index): """ Inserts value at a specific index BEST: O(1) WORST: O(i -1) """ if not (0 <= index <= self.size): raise ValueError('List index out of range: {}'.format(index)) node = ListNode(value) prev = self.get_at_index(index) if index == 0: self.append(value) elif index == self.size: self.append(value) else: new_node = ListNode(value) node = self.head previous = None for i in range(index): previous = node node = node.next previous.next = new_node new_node.next = node self.size += 1 def remove(self, index): """Best case Omega(1)""" """Worst case O(n)""" previous = None current = self.head while current is not None: if current.value == self.get_at_index(index): if current is not self.head and current is not self.tail: previous.next = current.next if current is self.head: self.head = current.next if current is self.tail: if previous is not None: previous.next = None self.tail = previous return previous = current current = current.next return -1 def contains(self, value): """Return an item in this linked list if it's found""" """Best case Omega(1)""" """Worst case O(n)""" current = self.head # Start at the head node while current is not None: if value == current.value: return True current = current.next # Skip to the next node return False def test_linked_list(): ll = LinkedList() print(ll) print('Appending items:') ll.append('A') print(ll) ll.append('B') print(ll) ll.append('C') print(ll) print('head: {}'.format(ll.head)) print('testing: Getting items by index:') #ll = LinkedList(['A', 'B', 'C']) print(ll) ll.insert('AA', 0) print(ll) ll.remove(1) print(ll) if __name__ == '__main__': test_linked_list() It also passes all of these tests:
# ############## TESTING ############### # ########################################################### from io import StringIO import sys # custom assert function to handle tests # input: count {List} - keeps track out how many tests pass and how many total # in the form of a two item array i.e., [0, 0] # input: name {String} - describes the test # input: test {Function} - performs a set of operations and returns a boolean # indicating if test passed # output: {None} def expect(count, name, test): if (count is None or not isinstance(count, list) or len(count) != 2): count = [0, 0] else: count[1] += 1 result = 'false' error_msg = None try: if test(): result = ' true' count[0] += 1 except Exception as err: error_msg = str(err) print(' ' + (str(count[1]) + ') ') + result + ' : ' + name) if error_msg is not None: print(' ' + error_msg + '\n') class Capturing(list): def __enter__(self): self._stdout = sys.stdout sys.stdout = self._stringio = StringIO() return self def __exit__(self, *args): self.extend(self._stringio.getvalue().splitlines()) sys.stdout = self._stdout # compare if two flat lists are equal def lists_equal(lst1, lst2): if len(lst1) != len(lst2): return False for i in range(0, len(lst1)): if lst1[i] != lst2[i]: return False return True print('ListNode Class') test_count = [0, 0] def test(): node = ListNode() return isinstance(node, object) expect(test_count, 'able to create an instance', test) def test(): node = ListNode() return hasattr(node, 'value') expect(test_count, 'has value property', test) def test(): node = ListNode() return hasattr(node, 'next') expect(test_count, 'has next property', test) def test(): node = ListNode() return node is not None and node.value is None expect(test_count, 'has default value set to None', test) def test(): node = ListNode(5) return node is not None and node.value == 5 expect(test_count, 'able to assign a value upon instantiation', test) def test(): node = ListNode() node.value = 5 return node is not None and node.value == 5 expect(test_count, 'able to reassign a value', test) def test(): node1 = ListNode(5) node2 = ListNode(10) node1.next = node2 return (node1 is not None and node1.next is not None and node1.next.value == 10) expect(test_count, 'able to point to another node', test) print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n') print('LinkedList Class') test_count = [0, 0] def test(): linked_list = LinkedList() return isinstance(linked_list, object) expect(test_count, 'able to create an instance', test) def test(): linked_list = LinkedList() return hasattr(linked_list, 'head') expect(test_count, 'has head property', test) def test(): linked_list = LinkedList() return hasattr(linked_list, 'tail') expect(test_count, 'has tail property', test) def test(): linked_list = LinkedList() return hasattr(linked_list, 'length') expect(test_count, 'has length property', test) def test(): linked_list = LinkedList() return linked_list is not None and linked_list.head is None expect(test_count, 'default head set to None', test) def test(): linked_list = LinkedList() return linked_list is not None and linked_list.tail is None expect(test_count, 'default tail set to None', test) def test(): linked_list = LinkedList() return linked_list is not None and linked_list.length == 0 expect(test_count, 'default length set to 0', test) print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n') print('LinkedList Contains Method') test_count = [0, 0] def test(): linked_list = LinkedList() return (hasattr(linked_list, 'contains') and callable(getattr(linked_list, 'contains'))) expect(test_count, 'has contains method', test) def test(): linked_list = LinkedList() linked_list.append(5) linked_list.append(10) linked_list.append(15) return linked_list.contains(15) is True expect(test_count, 'returns True if linked list contains value', test) def test(): linked_list = LinkedList() linked_list.append(5) linked_list.append(10) linked_list.append(15) return linked_list.contains(8) is False expect(test_count, 'returns False if linked list contains value', test) print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n') 
