Python implementation as single linked list class `replace item` with item

Question

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:

1. Replace item with item method
2. Size property
3. Get item at index
4. 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()

• Daniel: You'll have to post your actual code here! See the help center for more details.
• NinjaG: thank you for pointing out. I Just insert the actual code below my original post.
• NinjaG: I also include the link to gist so if you need to run the code on your machine.
• NinjaG: i put links to test cases too on my gist

Answer 1

• Multi-line doc strings don't need to start and end with """ on each line.

  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)
  

• It'd be nice to know how to use your function in your docstrings.

• You should rely more on Pythons standard interfaces as_list, should probably be more list(linked_list).
• If you create an _internal_iter method, then your could return Nodes, and simplify a lot of your code.
• You could default this.head to a Node, this would allow for you to remove the edge cases with it.
• You should make an _get_index, which returns the item you want, with the input checks.
• You should work with the previous node on the most part. This is as it's easier to work down the list, rather than up the list.
• You should remove all your duplicate functions.
• You should make your class work the same way as list. You should possibly remove replace, rename your functions to the normal names, insert_at_index to insert, and use special methods.
• append and prepend are special cases of insert. Don't duplicate your code by inverting this relationship.
• Most of your functions if given a previous node, should be \$O(1)\$. The biggest exceptions to these are _internal_iter and _get_index.

• while not found and current is not None: would be better as a for-else loop.

  for item in self._internal_iter():
   if item.data == wanted:
   ...
   break
  else:
   raise ValueError('...')
  

• Your unit tests aren't automated, look into unittest.

In all I'd drastically change your code:

from itertools import islice, tee
def pairwise(iterable):
 "s -> (s0,s1), (s1,s2), (s2, s3), ..."
 a, b = tee(iterable)
 next(b, None)
 return zip(a, b)
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):
 self._tail = self._head = Node(None)
 self._size = 0
 if iterable:
 for item in iterable:
 self.append(item)
 def __repr__(self):
 return 'LinkedList({})'.format(list(self))
 def _internal_iter(self):
 node = self._head
 while node is not None:
 yield node
 node = node.next
 def __len__(self):
 return self._size
 def _get_index(self, index):
 if type(index) is not int:
 raise TypeError
 length = len(self) + 1
 if not (-length <= index < length):
 raise IndexError('')
 index %= length
 if index == (length - 1):
 return self._tail
 return next(islice(self._internal_iter(), index, None))
 def __iter__(self):
 it = (node.data for node in self._internal_iter())
 head = next(it)
 return it
 def __getitem__(self, index):
 return self._get_index(index).next.data
 def __setitem__(self, index, item):
 self._get_index(index).next.data = item
 def __delitem__(self, index, item):
 prev = self._get_index(index)
 curr = prev.next
 prev.next = curr.next
 self._size -=1
 if prev.next is None:
 self._tail = prev
 return curr.data
 def insert(self, index, item):
 node = Node(item)
 prev = self._get_index(index)
 node.next = prev.next
 prev.next = node
 if node.next is None:
 self._tail = node
 self._size += 1
 def append(self, item):
 self.insert(len(self), item)
 def prepend(self, item):
 self.insert(0, item)
 def remove(self, value):
 for prev, curr in pairwise(self._internal_iter()):
 if curr.data == value:
 prev.next = curr.next
 self._size -=1
 if prev.next is None:
 self._tail = prev
 return
 raise ValueError('Item not found: {}'.format(value))
 def replace(self, value, item):
 for node in islice(self._internal_iter(), 1, None):
 if node.data == value:
 node.data = item
 return
 raise ValueError('Item not found: {}'.format(value))
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('len: {}'.format(len(ll)))
 print('testing: Getting items by index:')
 for index in range(len(ll)):
 print('index [{}] {!r}'.format(index, ll[index]))
 print('Deleting items:')
 ll.remove('B')
 print(ll)
 ll.remove('C')
 print(ll)
 ll.remove('A')
 print(ll)
 print('head: {}'.format(ll._head))
 print('tail: {}'.format(ll._tail))
 print('len: {}'.format(len(ll)))
 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(len(ll)))
 ll.insert(0, 'AA')
 print(ll)
 print("testing: insert_at_index 0, 'AA'___________________")
 ll.insert(2, 'BB')
 print("testing: insert_at_index 2, 'BB'___________________")
 print(ll)
if __name__ == '__main__':
 test_linked_list()

• NinjaG: Thank you for your feedback and suggestion. I agree with you on most of the cases. But after running the new code, I think I found an issue on your code and when I run the code at terminal. It shows that there's a bug when run the test_linked_list(). For example, it prints that LinkedList(['A', 'B', 'C']), But output shows that head: Node(None), instead of showing head: Node('"'). this is a bug. Can we fix that bug?
• NinjaG: I think it will be a great improvement if we can identify why we got different output when we run the file test_linked_list(). Thansk.
• Peilonrayz: @NinjaG that's not a bug, please read the text again, which explains that it is intended.