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()

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()