#!/usr/bin/env python3
"""Linked List -> Extended Linked List Implementation: Homework

The goal of this homework is to implement a singly linked list data structure with additional functionalities. 
In previous tutorials you have learned how a node and a linked list data structure in its basic form can be created.
However, a LinkedList class can have more methods to perform additional operations on a linked list,
such as: insertion (begin, end, or after a specific element), deletion, traversal, and sorting.

Your task is to:
    * locate the TODOs in this file
    * complete the missing part from the code 
    * run the test of this homework located in same folder.

To test run LinkedList_t.py in your command line'

Notes:
    * do not change class structure or method signature to not break unit tests
    * visit this url for more information on linked list:
    https://realpython.com/linked-lists-python/
"""

# Teuntje van Leeuwe 1007734
# Ryan Bakkes 1001519
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    #TODO 1:Insert at the beginning of the list
    def insertBeg(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
    
    #TODO 2: Insert at the end
    def insertEnd(self, new_data):
        new_node = Node(new_data)
        if self.head == None:
            self.head = new_node
            return
        current = self.head
        while current.next != None:
            current = current.next
        current.next = new_node

    #TODO 3: Insert after a specific node
    def insertAfter(self, data, new_data):
        # Insert after a specific node
        new_node = Node(new_data)
        current = self.head
        while current != None:
            if current.data == data:
                new_node.next = current.next
                current.next = new_node
                return
            current = current.next

    #TODO 4: Deleting a node at a specific index
    def deleteIndex(self, index):
        current = self.head
        x = 0

        if x == index:
            self.head = current.next
            return

        while current != None:
            if x == index - 1:
                current.next = current.next.next
                return
            current = current.next
            x += 1 

    #TODO 5: Search an element
    def find(self, key):
        current = self.head
        x = 0
        while current != None:
            if current.data == key:
                return x
            current = current.next
            x += 1
        return -1

    #TODO 6: Sort the linked list
    def sort(self, head):
        current = head
        index = None

        while current != None:
            index = current.next
            while index != None:
                if current.data > index.data:
                    temp = current.data
                    current.data = index.data
                    index.data = temp
                index = index.next
            current = current.next

    #TODO 7: Print the linked list
    def printList(self):
        current = self.head
        while current != None:
            print(current.data)
            current = current.next