linked_list.py

"""
Node and LinkedList class definitions with encapsulation.
"""

class _Node:
    """Private class: Node for the linked list"""
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedList:
    """
    A singly linked list with properties for safe access.
    Uses private attributes and exposes read-only properties.
    """

    def __init__(self, value):
        new_node = _Node(value)
        self._head = new_node
        self._tail = new_node
        self._length = 1

    @property
    def head(self):
        """Get the head node"""
        return self._head

    @property
    def tail(self):
        """Get the tail node"""
        return self._tail

    @property
    def length(self):
        """Get the length"""
        return self._length

    def print_list(self):
        """Prints the linked list"""
        if not self._head:
            print("empty list")
            return
        values = []
        temp = self._head
        while temp:
            values.append(str(temp.value))
            temp = temp.next
        values.append("None")
        print(" -> ".join(values))

    def make_empty(self):
        """Empties the list"""
        self._head = None
        self._tail = None
        self._length = 0

    def append(self, value):
        """Append node to end"""
        new_node = _Node(value)
        if self._length == 0:
            self._head = new_node
            self._tail = new_node
        else:
            self._tail.next = new_node
            self._tail = new_node
        self._length += 1

    def pop(self):
        """Pop node from end"""
        if self._length == 0:
            return None
        temp = self._head
        pre = self._head
        while temp.next:
            pre = temp
            temp = temp.next
        self._tail = pre
        self._tail.next = None
        self._length -= 1
        if self._length == 0:
            self._head = None
            self._tail = None
        return temp

    def prepend(self, value):
        """Prepend node to start"""
        new_node = _Node(value)
        if self._length == 0:
            self._head = new_node
            self._tail = new_node
        else:
            new_node.next = self._head
            self._head = new_node
        self._length += 1

    def pop_first(self):
        """Pop node from start"""
        if self._length == 0:
            return None
        temp = self._head
        self._head = self._head.next
        temp.next = None
        self._length -= 1
        if self._length == 0:
            self._tail = None
        return temp

    def get(self, index):
        """Get node at index"""
        if index < 0 or index >= self._length:
            return None
        temp = self._head
        for _ in range(index):
            temp = temp.next
        return temp

    def set_value(self, index, value):
        """Set value of node at index"""
        temp = self.get(index)
        if temp:
            temp.value = value
            return True
        return False

    def find_middle_node(self):
        """Find the middle node"""
        fast = slow = self._head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def has_loop(self):
        """Check for loop"""
        fast = slow = self._head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                return True
        return False

    def find_kth_from_end(self, k):
        """Find k-th node from end"""
        slow = fast = self._head
        for _ in range(k):
            if not fast:
                return None
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        return slow

    def remove_duplicates(self):
        """Remove duplicate values"""
        current = self._head
        seen = set()
        prev = None
        while current:
            if current.value in seen:
                prev.next = current.next
            else:
                seen.add(current.value)
                prev = current
            current = current.next

    def binary_to_decimal(self):
        """Convert binary linked list to decimal"""
        decimal = 0
        current = self._head
        while current:
            decimal = decimal * 2 + current.value
            current = current.next
        return decimal

    def partition_list(self, x):
        """Partition list around x"""
        if not self._head:
            return
        dummy1 = _Node(0)
        dummy2 = _Node(0)
        prev1 = dummy1
        prev2 = dummy2
        current = self._head
        while current:
            if current.value < x:
                prev1.next = current
                prev1 = prev1.next
            else:
                prev2.next = current
                prev2 = prev2.next
            current = current.next
        prev1.next = dummy2.next
        prev2.next = None
        self._head = dummy1.next

    def reverse_between(self, left, right):
        """Reverse sublist between left and right"""
        if not self._head or left == right:
            return
        dummy = _Node(0)
        dummy.next = self._head
        prev = dummy
        for _ in range(left):
            prev = prev.next
        current = prev.next
        for _ in range(right - left):
            move = current.next
            current.next = move.next
            move.next = prev.next
            prev.next = move
        self._head = dummy.next

    def swap_pairs(self):
        """Swap nodes in pairs"""
        dummy = _Node(0)
        dummy.next = self._head
        prev = dummy
        while prev.next and prev.next.next:
            first = prev.next
            second = prev.next.next
            prev.next, first.next, second.next = second, second.next, first
            prev = first
        self._head = dummy.next