# Title: Linked list
# Heading: Python Program to Implement a Linked List
# Level: intermediate
# Tags: linked list, singly linked list, node, reverse a linked list
# Time: O(n)
# Space: O(n)
# About: A singly linked list of Node objects that adds values at the end, deletes a value, reverses itself and prints as 1 -> 2 -> 3.

class Node:
    """A value and a link to the next node."""

    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None  # the first node (None if empty)

    def append(self, value):
        """Add value at the end."""
        node = Node(value)
        if self.head is None:
            self.head = node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = node

    def delete(self, value):
        """Remove the first node holding value."""
        previous, current = None, self.head
        while current and current.value != value:
            previous, current = current, current.next
        if current is None:
            return  # value isn't in the list
        if previous is None:
            self.head = current.next  # it was the head
        else:
            previous.next = current.next  # link round it

    def reverse(self):
        """Point every link the other way."""
        previous, current = None, self.head
        while current:
            following = current.next
            current.next = previous
            previous, current = current, following
        self.head = previous

    def __str__(self):
        values, current = [], self.head
        while current:
            values.append(str(current.value))
            current = current.next
        return " -> ".join(values)


numbers = LinkedList()
for value in [1, 2, 3, 4]:
    numbers.append(value)
print("List:", numbers)
numbers.delete(3)
print("Without 3:", numbers)
numbers.reverse()
print("Reversed:", numbers)