Singly Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212

class SllNode:
    """A single node in the singly linked list."""

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


class SllList:
    """
    Singly Linked List implementation.

    Provides operations for adding, removing, searching, and
    traversing elements in a one-directional linked structure.
    """

    def __init__(self, val=None):
        """Initialize the list, optionally with a starting value."""
        if val is not None:
            self.head = SllNode(val)
            self.len = 1
        else:
            self.head = None
            self.len = 0

    def __len__(self):
        """Return the number of nodes in the list."""
        return self.len

    def __str__(self):
        """String representation: head -> ... -> tail."""
        values = [str(el) for el in self]
        return " -> ".join(values)

    def __repr__(self):
        return str(self)

    def __iter__(self):
        """Iterate over all values in the list."""
        cur = self.head
        while cur:
            yield cur.val
            cur = cur.next

    def __bool__(self):
        """Return True if the list is not empty."""
        return self.len > 0

    def get_at(self, position) -> SllNode:
        """
        Get the node at the specified position.
        Raises IndexError if position is invalid.
        """
        if position >= self.len or position < 0:
            raise IndexError("Position is invalid.")
        node = self.head
        for _ in range(position):
            node = node.next
        return node

    def add_left(self, val):
        """Add a new node with the given value at the head."""
        new_head = SllNode(val)
        new_head.next = self.head
        self.head = new_head
        self.len += 1

    def add_right(self, val):
        """Add a new node with the given value at the tail."""
        if not self:
            self.head = SllNode(val)
        else:
            tail = self.get_at(self.len - 1)
            tail.next = SllNode(val)
        self.len += 1

    def add_at(self, val, position):
        """
        Insert a new node at the specified position.
        Raises IndexError if position is out of bounds.
        """
        if position > len(self) or position < 0:
            raise IndexError("Invalid position to insert a value at.")
        if position == 0:
            return self.add_left(val)
        if position == len(self):
            return self.add_right(val)
        before = self.get_at(position - 1)
        after = before.next
        before.next = SllNode(val)
        before.next.next = after
        self.len += 1

    def remove_left(self):
        """
        Remove and discard the head node.
        Raises IndexError if list is empty.
        """
        if not self:
            raise IndexError("List is empty.")
        self.head = self.head.next
        self.len -= 1

    def remove_right(self):
        """
        Remove and discard the tail node.
        Raises IndexError if list is empty.
        """
        if not self:
            raise IndexError("List is empty.")
        if self.len == 1:
            self.head = None
        else:
            before_tail = self.get_at(self.len - 2)
            before_tail.next = None
        self.len -= 1

    def remove_at(self, position):
        """
        Remove the node at the specified position.
        Raises IndexError if list is empty or position is invalid.
        """
        if not self:
            raise IndexError("List is empty.")
        if position < 0 or position >= self.len:
            raise IndexError("Position is invalid.")
        if position == 0:
            return self.remove_left()
        before = self.get_at(position - 1)
        to_remove = before.next
        before.next = before.next.next
        to_remove.next = None
        self.len -= 1

    def traverse(self):
        """Return a list of all values in the list."""
        cur = self.head
        arr = []
        while cur:
            arr.append(cur.val)
            cur = cur.next
        return arr

    def search_for(self, val):
        """
        Search for a value in the list.
        Returns the position if found, -1 otherwise.
        """
        cur = self.head
        pos = 0
        while cur:
            if cur.val == val:
                return pos
            pos += 1
            cur = cur.next
        return -1

    def reverse_list(self):
        """Reverse the linked list in place."""
        prev = None
        cur = self.head
        while cur:
            # This one-liner only works in Python! - tuple unpacking evaluates all vars on right first
            # cur.next, prev, cur = prev, cur, cur.next

            # Standard approach - store 3 variables
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next

        self.head = prev


# Example usage:
if __name__ == "__main__":
    # Create a new list
    sll = SllList()

    # Add elements
    sll.add_right(10)
    sll.add_right(20)
    sll.add_right(30)
    print(sll)  # 10 -> 20 -> 30

    # Add to head
    sll.add_left(5)
    print(sll)  # 5 -> 10 -> 20 -> 30

    # Add at position
    sll.add_at(15, 2)
    print(sll)  # 5 -> 10 -> 15 -> 20 -> 30

    # Search for a value
    pos = sll.search_for(20)
    print(f"Found 20 at position: {pos}")  # Found 20 at position: 3

    # Get value at position
    node = sll.get_at(2)
    print(f"Value at position 2: {node.val}")  # Value at position 2: 15

    # Remove elements
    sll.remove_left()
    print(sll)  # 10 -> 15 -> 20 -> 30

    sll.remove_right()
    print(sll)  # 10 -> 15 -> 20

    # Reverse the list
    sll.reverse_list()
    print(sll)  # 20 -> 15 -> 10