LinkedList class implementation in Python

Question

I was solving this problem for implementing LinkedList and ListNode classes, and Insert and Remove methods for LinkedList. I was wondering if I can get any code review and feedback.

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 these tests:

# ##############  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')

Answer 1

Great job, looks really good! A few minor thoughts, on top of the existing answers:

class LinkedList(object):
    ...

You don't need to explicitly inherit from object if you're writing python3 code that doesn't require to be python2 compatible. This happens implicitly in python3. You've already done this for Node. Check out new style vs. old style classes if you want to learn more about this.

class LinkedList:
    ...

Moreover, you could define a function to add multiple values, such as:

def extend(self, vals):
    for val in vals:
        self.append(val)

You can also use that in your __init__ if initial values are provided.

Additionally, you could define an __iter__ function that implements a generator. This could help you with tasks for which you don't want to use to_list() and allocate the memory for a list.

def __iter__(self):
    curr = self.head
    while curr:
        yield curr
        curr = curr.next

Lastly, I don't like using next as a variable, because it's already built-in, but that's not going to cause any trouble here.

Answer 2

use """ """ instead of multiple """

from

    """Initialize this linked list and append the given items, if any"""
    """Best case Omega(1)"""
    """Worst case O(n)"""

to

    """
    Initialize this linked list and append the given items, if any
    Best case Omega(1)
    Worst case O(n)
    """

as usual the representation can be a bit better from

print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n')

to

print('PASSED: {} / {}'.format(test_count[0], test_count[1]), end='\n\n')

end in print allows you to specify how to end the printed charachters, separating it from your actual data. the .format eliminates the need for str() each time while keeping a focus on your output

+1 for main function usage

else, you can use maybe add a .extend instead of multiple appends or make the append method take multiple parameters

like from

linked_list.append(5)
linked_list.append(10)
linked_list.append(15)

to

linked_list.extend([5, 10, 15])

else, instead of writing your own test functions, use the in-built one, will save you some pains, and is available everywhere (no need to rederive your functions each time)