Linked list for interviews

Question

I'm trying to learn linked lists so I can answer interview questions. Even though I've seen plenty of tutorials to understand how they supposedly work, I don't know if I am doing a good job because I have no one to get feedback from.

class Node(object):

    def __init__(self, data, next_node = None):
        self.data = data
        self.next = next_node

    def __str__(self):
        return str(self.data)


class SinglyLinkedList(object):

    def __init__(self):
        self.head = None

    def prepend(self, data):
        '''
        Creates a new node and inserts it at the front, making it the head
        of the list
        '''
        self.head = Node(data, next_node=self.head)

    def append(self, data):
        '''
        Creates a new node and inserts it at the very end of the list
        '''
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
        else:
            iter_node = self.head
            while iter_node.next:
                iter_node = iter_node.next
            iter_node.next = new_node

    def insert(self, after_node, data):
        '''
        A new node is created containing the passed data, and then inserted
        right after the node called after_node in the list
        '''
        new_node = Node(data)
        new_node.next = after_node.next
        after_node.next = new_node

    def delete(self, node):
        '''
        Removes the given node from the list. If the node is at the tail already,
        it is set to None. Otherwise it is "de facto" removed by having it mirror the next
        node's data, and then link to that mirror's next node.
        '''
        if node.next == None:
            node = None
        else:
            node.data = node.next.data
            node.next = node.next.next

    def reverse(self):
        '''
        Reverses the entire linked list.
        '''
        if self.head:
            prev = None
            current = self.head
            while current:
                future = current.next
                current.next = prev
                prev = current
                current = future
            self.head = prev

    def __iter__(self):
        '''
        Yields each node in the list over a loop
        '''
        iter_node = self.head
        while iter_node:
            yield iter_node
            iter_node = iter_node.next

    def __str__(self):
        return "[" + ", ".join(str(node) for node in self) + "]"

Answer 1

• Bug

  SinglyLinkedList.delete called on the tail node doesn't really delete it: the previous node still holds the reference.

• Interface

  SinglyLinkedList.insert and SinglyLinkedList.delete require a handle to a Node object, which is quite hard to obtain. It seems that the only way is to manually iterate the list breaking on a condition. I recommend prepend, append, insert to return a newly created instance. A find method would also be useful.

Answer 2

A bit more on that bug...

To expand a bit on the bug in delete pointed out by @vnp, the problem is with the node = None statement:

def delete(self, node):
    if node.next == None:
        node = None
    else:
        node.data = node.next.data
        node.next = node.next.next

It seems you misunderstand what that statement does. It doesn't do what you think. It creates a local variable called node, shadowing the parameter variable with the same name.

To delete the tail, you need to get to the previous node, and set previous_node.next = None.

To access to the previous node, you could either add a .prev property (effectively turning your single-linked list implementation to doubly-linked list), or iterate until before the target node to delete.

Coding style

There are several coding style issues that would be good to correct by following PEP8, the Python style guide.

---

Instead of:

    if self.head == None:

The correct way to check for None is this:

    if self.head is None:

---

It's recommended to use triple double-quotes instead of single-quotes for docstrings, so instead of:

    '''
    Creates a new node and inserts it at the very end of the list
    '''

Use this:

    """
    Creates a new node and inserts it at the very end of the list
    """