Linked Lists: Data structure for storing a collection of items:
*Linear collection of elements, each element points to the next element in memory 

[]----[]----[]----[]
*each boxes can be represented as objects
*you can have a int, str, boolean etc...
*insertion and deletion faster than arrays
*accessing elements is slower than arrays because you have to traverse all elements starting from the head

*Each element is called a node, and each NODE has two parts
    1)Data
    2)Memory adress of the next node in the list
[]----[]-----[]----[]--    *as you can see the last node doesnt point to anything so the address is None/Null

*each element of the list is called the node
[]------        *the first node is called the (head) of the list
         ------[] *the last node is called the (tail) of the list
 

the advantage to this is that we store information in memory efficiently and allow for easy insertion and deletion

Linked Lists:
    Advantages
__________________________
1)Dynamic: it can grow and shrink at run time
2) insertion and deletion operations are easier than array. WE DONT have to shift nodes like when we insert in arrays
If we wanted to insert in linked lists we just update the next link of node
3) doesnt waste memory, also uses memory more efficiently

    Disadvantages:
_____________________________
1) accessing a node is time consuming. When looking for a value in a linked list YOU have to start at the head/beginning of the chain and check one element at a time for the value you are looking for.

*If linked list is n elements long it can take up to n time O(n)
2) Takes up more memory than an array because it contains a pointer to the next node, with array you dont have a pointer because it is stored in memory sequence sequentially

______________________________________________________
Double Linked List:
Double Linked List has a link to the NEXT node and the previous node...
The first Node/head has a link to Null <-- and then Next node ----> same with the last element

___________________________________________________________________________
circular Linked List:
same as a regular linked list but the tail doesnt point to null, it points to the beginning of the nodes so the head
[]------[]------[]-----
 |---------------------|

_______________________________________________

double circular linked list: combination of the double and circular
[]--[]--[] each node points to previous and next node, while the tail points to the head, and the head points to

class Node:

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

    


class LinkedList:

    def __init__(self):
        self.head = Node()
        self.tails = self.head

    def append(self, data):   #,[]-[]--[]--
        new_node = Node(data)     #[]
        self.tails.next = new_node
        self.tails = new_node

    def size(self):
        counter = 0
        cur = self.head

        while cur.next!=None:
            counter+=1
            cur = cur.next
        return counter

    def display(self): #[]----[]----[]---
        cur = self.head
        lis = []

        if cur.next == None:
            print('No items inside!')

        while cur.next!= None:
            cur = cur.next
            lis.append(cur.data)
            
        return lis

    def get(self, index):
        if index >= self.size() or index < 0:
            print('index out of range!')
            return
        cur = self.head
        current_index = 0
        
        while True:
            cur = cur.next

            if index == current_index:
                return cur.data
            
            current_index+=1
            
       
    
    def erase(self, index):
        if index >= self.size() or index < 0:
            print('index out of range')
            return
        cur = self.head
        current_index = 0   #[]---[]---[]---[]

        while True:
            last_node = cur
            cur = cur.next

            if current_index == index:
                last_node.next = cur.next
                return
            current_index+=1
    def remove(self, data):
        cur = self.head
        
        if data not in self.display():
            print(f'{data} not in the linked list')
            return
        
        while cur.next!=None:
            last_node = cur
            cur = cur.next
            if cur.data == data: #[]---[]----[]--
                last_node.next = cur.next
                return




    def insert(self, data, index):
         if index >= self.size() or index < 0:
            print('index out of range')
            return
         cur = self.head
         current_index = 0
         new_node = Node(data)

         while True:
            last_node = cur
            cur = cur.next
            if current_index == index: # []---[]---[]--[]--
                last_node.next = new_node  #-[]-|
                new_node.next = cur
                return
            current_index+=1

    def display_last(self):
        return self.tails.data
    
    

            
            

if __name__ == '__main__': 

    word = 'brian'
    l1 = LinkedList()
    l1.append('brian')
    l1.append('rambo')
    l1.append('cena')
    l1.append('cmpunk')
    print(l1.display())
    print(l1.display_last())