# Design Singly Linked List

Design a Singly Linked List class.

Your LinkedList class should support the following operations:

* LinkedList() will initialize an empty linked list.
* int get(int i) will return the value of the ith node (0-indexed). If the index is out of bounds, return -1.
* void insertHead(int val) will insert a node with val at the head of the list.
* void insertTail(int val) will insert a node with val at the tail of the list.
* int remove(int i) will remove the ith node (0-indexed). If the index is out of bounds, return false, otherwise return true.
* int[] getValues() return an array of all the values in the linked list, ordered from head to tail.

Example 1:
> Input:
> ["insertHead", 1, "insertTail", 2, "insertHead", 0, "remove", 1, "getValues"]
>
> Output:
> [null, null, null, true, [0, 2]]

Example 2:
> Input:
> ["insertHead", 1, "insertHead", 2, "get", 5]
>
> Output:
> [null, null, -1]

**Note:**

* The index int i provided to get(int i) and remove(int i) is guranteed to be greater than or equal to 0.

---

## 1. Create a ListNode

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

## 2. Create a Singly Linked List

Note: initialize the linked list with a **dummy node(sentinel node)** will make edge cases easier

class SinglyLinkedList:
    
    def __init__ (self):
        self.head = ListNode(-1) # sentinel node
        self.tail = self.head

## 3. get i-th node

    def get(self, index: int) -> int:
        curr = self.head.next
        i = 0
        # iteration
        while curr:
            # found
            if i == index:
                return curr.val
            
            # next node and increment i
            i += 1
            curr = curr.next
        
        # not found
        return -1
        

Steps:
1. create a pointer(curr), and points to the head.next
2. initiate variable i = 0
3. iteration through the list (standard start: **while curr:**)
4. if i == index, then the node is found. Return the value of the node.
5. iterate to the next node and increment i by 1
6. return -1 if not found

## 4. insertHead

    def insertHead(self, val: int) -> None:
        new_node = ListNode(val)
        new_node.next = self.head.next
        self.head.next = new_node
        # handle self.tail
        # if list is empty before insertion
        if not new_node.next:
            self.tail = new_node
        

Steps:
1. create a new node
2. point new node's next to the head.next
3. move head to point to new node
4. handle edge case: if the list is empty before insertion, then new node should be tail. Therefore, if new node's next points to null, it means the node is the first node. Then, move the tail to point to the new node.

## 5. insertTail

    def insertTail(self, val: int) -> None:
        self.tail.next = ListNode(val)
        self.tail = self.tail.next

easy, not explanation needed

## 6. remove
**This one is tricky, be careful**

    def remove(self, index: int) -> bool:
        curr = self.head
        i = 0
        
        # start the iteration
        while i < index and curr:
            i += 1
            curr = curr.next
            
        if curr and curr.next:
            # if target(curr.next) is the last node
            if curr.next == self.tail:
                # set tail to curr(previous node)
                self.tail = curr
            
            # remove the node
            curr.next = curr.next.next
            
            return True
        
        return False # list out of bounds

Steps:
1. create a pointer that points to the previous node of every node (i.e. first point at the dummy(head))
2. initiate variable i = 0
3. start iteration. **Condition: i < index and curr exist**. The condition "i < index" will ensure curr pointer stop at the previous node before our target node.
4. execute iteration and increment i by 1
5. **check curr and curr.next exist**
6. **handle tail pointer: if target node is the tail**, then curr(the previous node) should be the new tail
**7. remove the node: curr.next = curr.next.next (should memorize this)**
8. return

## get values

    def getValues(self) -> List[int]:
        result = []
        curr = self.head.next
        while curr:
            result.append(curr.val)
            curr = curr.next
            
        return result

easy, no explanation