2
\$\begingroup\$

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()
\$\endgroup\$
4
  • \$\begingroup\$ You'll have to post your actual code here! See the help center for more details. \$\endgroup\$ Commented Oct 31, 2017 at 19:09
  • 1
    \$\begingroup\$ thank you for pointing out. I Just insert the actual code below my original post. \$\endgroup\$ Commented Oct 31, 2017 at 19:31
  • \$\begingroup\$ I also include the link to gist so if you need to run the code on your machine. \$\endgroup\$ Commented Oct 31, 2017 at 21:25
  • \$\begingroup\$ i put links to test cases too on my gist \$\endgroup\$ Commented Nov 1, 2017 at 2:47

1 Answer 1

Reset to default
2
\$\begingroup\$

  • 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()
\$\endgroup\$
3
  • \$\begingroup\$ 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? \$\endgroup\$ Commented Nov 4, 2017 at 20:39
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Nov 5, 2017 at 1:57
  • \$\begingroup\$ @NinjaG that's not a bug, please read the text again, which explains that it is intended. \$\endgroup\$ Commented Nov 5, 2017 at 15:36

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.