I encountered this question as I am preparing for my code interview. I was implementing my linked list implementation.
I would like to ask for the following implementation:
- Replace item with item method
- Size property
- Get item at index
- Method
Insert
item at index method
I wrote the following tests to make sure that my codes works a pretty comprehensive following unit test cases, and it passed against all test cases, so the code seems to be working fine.
def test_items(self):
def test_size(self):
def test_get_at_index(self):
def test_insert_at_index(self):
def test_replace(self):
It includes a total of 13 link test cases to show my code is robust.
Implementation:
class Node(object):
def __init__(self, data):
"""Initialize this node with the given data"""
self.data = data
self.next = None
def __repr__(self):
"""Return a string representation of this node"""
return 'Node({})'.format(repr(self.data))
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
if iterable:
for item in iterable:
self.append(item)
def __repr__(self):
"""Return a string representation of this linked list"""
return 'LinkedList({})'.format(self.as_list())
def items(self):
"""Return a list of all items in this linked list.
Best and worst case running time: Theta(n) for n items in the list
because we always need to loop through all n nodes."""
result = [] # Constant time to create a new list
# Start at the head node
node = self.head # Constant time to assign a variable reference
# Loop until the node is None, which is one node too far past the tail
while node is not None: # Always n iterations because no early exit
# Append this node's data to the results list
result.append(node.data) # Constant time to append to a list
# Skip to the next node
node = node.next # Constant time to reassign a variable
return result # Constant time to return a list
def __getitem__(self, arg):
"""Get the item at the index, or raise KeyError if not an int"""
"""Best case Omega(1)"""
"""Worst case O(n)"""
if type(arg) is not int:
raise TypeError
# If argument is over list size, raise ValueError
if arg >= self.length() or arg < -self.length():
raise IndexError
# Use modulus operator, so index can use negatives
counter = arg % self.length()
currentIndex = 0
if counter == self.length():
return self.last()
current = self.head
while current is not None:
if counter == currentIndex:
return current.data
currentIndex += 1
current = current.next
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.data)
current = current.next
return items
def get_at_index(self, index):
""" Gets data at an index"""
at_index = self._at_index(index)
if at_index is None:
return None
return at_index.data
def is_empty(self):
"""Return True if this linked list is empty, or False otherwise"""
"""Best case Omega(1)"""
"""Worst case O(1)"""
return self.head is None
def length(self):
"""Return the length of this linked list"""
"""Best case Omega(1)"""
"""Worst case O(1)"""
return self.size
def append(self, item):
"""Insert the given item at the tail of this linked list"""
new_node = Node(item)
# Check if list is empty
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 prepend(self, item):
"""Insert the given item at the head of this linked list"""
"""Best case Omega(1)"""
"""Worst case O(1)"""
new_node = Node(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 delete(self, item):
"""Delete the given item from this linked list, or raise ValueError"""
"""Best case Omega(1)"""
"""Worst case O(n)"""
current = self.head
previous = None
found = False
# Find the given item
while not found and current is not None:
if current.data == item:
found = True
else:
previous = current
current = current.next
# Delete if found
if found:
if current is not self.head and current is not self.tail:
previous.next = current.next
current.next = None
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
# Update length
self.size -= 1
else:
# Otherwise raise an error to tell the user that delete has failed
raise ValueError('Item not found: {}'.format(item))
def size(self):
""" Gets the size of the Linked List
AVERAGE: O(1)
"""
return self.count
def delete_at_index(self, index):
"""Delete the item at the given index from this linked list, or raise ValueError"""
if type(index) is not int:
raise TypeError
# If argument is over list size, raise ValueError
if index >= self.length() or index < -self.length():
raise IndexError
# Use modulus operator, so index can use negatives
counter = index % self.length()
currentIndex = 0
current = self.head
previous = None
found = False
# Find the given item
while not found and current is not None:
if currentIndex == counter:
found = True
else:
previous = current
current = current.next
currentIndex += 1
if found:
if current is not self.head and current is not self.tail:
previous.next = current.next
current.next = None
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
# Update length
self.size -= 1
else:
raise ValueError('Item not found: {}'.format(item))
def iterable(self):
data = []
current = self.head
while current is not None:
data.append(current.data)
current = current.next
return data
def find(self, condition):
"""Return an item in this linked list satisfying the given condition"""
current = self.head # Start at the head node
while current is not None:
if condition(current.data):
return current.data
current = current.next # Skip to the next node
return None
def _find_node(self, data):
current = self.head
while current is not None:
if current.data == data:
return current
current = current.next
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.
"""
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.data
def insert(self, index, data):
""" Inserts data at a specific index
BEST: O(1)
WORST: O(n)
"""
if index == 0:
self.prepend(data)
return
at_index = self._at_index(index - 1)
if at_index is None:
raise IndexError
if at_index.next is None:
self.append(data)
return
new_node = Node(data)
new_node.next = at_index.next
at_index.next = new_node
def insert_at_index(self, index, item):
"""Insert the given item at the given index in this linked list, or
raise ValueError if the given index is out of range of the list size.
"""
# Check if the given index is out of range and if so raise an error
if not (0 <= index <= self.size):
raise ValueError('List index out of range: {}'.format(index))
if index == 0:
self.prepend(item)
elif index == self.size:
self.append(item)
else:
new_node = Node(item)
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 replace(self, old_item, new_item):
"""Replace the given old_item in this linked list with given new_item
using the same node, or raise ValueError if old_item is not found."""
if old_item == new_item:
return
node = self.head
while node is not None:
if node.data == old_item:
node.data = new_item
return
node = node.next
raise ValueError('Item not found: {}'.format(old_item))
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('tail: {}'.format(ll.tail))
print('size: {}'.format(ll.size))
print('length: {}'.format(ll.length()))
print('testing: Getting items by index:')
for index in range(ll.size):
item = ll.get_at_index(index)
print('get_at_index({}): {!r}'.format(index, item))
print('Deleting items:')
ll.delete('B')
print(ll)
ll.delete('C')
print(ll)
ll.delete('A')
print(ll)
print('head: {}'.format(ll.head))
print('tail: {}'.format(ll.tail))
print('size: {}'.format(ll.size))
print('length: {}'.format(ll.length()))
print("testing: Linked List replace ___________________")
ll = LinkedList(['A', 'B', 'C'])
ll.replace('A', 'D')
print(ll)
ll = LinkedList(['A', 'B', 'C'])
print(ll)
print("testing: insert_at_index ___________________")
print('size: {}'.format(ll.size))
ll.insert_at_index(0, 'AA')
print(ll)
print("testing: insert_at_index 0, 'AA'___________________")
ll.insert_at_index(2, 'BB')
print("testing: insert_at_index 2, 'BB'___________________")
print(ll)
if __name__ == '__main__':
test_linked_list()