I was solving this problem for implementing linkedList class and ListNode class, and Insert method, Remove Method for Linked List. and I was wondering if I can get any code review and feedback. You can find this problem below.
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 the test below:
# ############## 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')