DoublyLinkedList

    // let doublylinkedList = {
//     head:{
//         value:10,
//         next{
//             value:5,
                // previous: previous{
                //     value: 10,
                // }
//             next:  next{
//             value:6,
//             next:null
//         }
//         }
//     }
// }



class DoublyLinkedList{
   late Map head;
   late var tail;
   late int length;
    DoublyLinkedList(value){
        this.head = {
            'value': value,
            'next': null,
             'prev': null
        };
        
        this.tail = this.head;
        this.length = 1;
    }
    
    
    // let linkedList = {
//     head:{
//         value:10,
//         next{
//             value:5,
//             next:  next{
//             value:6,
//             next:null
//         }
//         }
//     }
// }

// add at the back 
    append(value){
       var newNode = {
           'value': value,
           'next': null,
           'prev': null,
       };
       newNode['prev'] = tail;
       tail['next'] = newNode;
       tail = newNode;
       length++;
       
        
        
    }
    // add to front 
    prepend(value){
        var newNode = {
            'value': value,
            'next':  null,
            
        };
        newNode['next'] = head;
        head['prev'] = newNode;
        head = newNode;
        length++;
    }
    
    // add at any position and increment length
    
    prinlnt(index){
         if(index != 0){
            dynamic array = [];
            dynamic currentNode = head;
           while(currentNode != null){
               array.add(currentNode['value']);
               currentNode = currentNode['next'];
           }
           
           print(array);
        }
    }
    insert(index, value){
        var newNode = {
            'value': value,
            'next': null,
        };
        
        if(index == 0){
              this.prepend(value);
    
        }else if(index >= length){
            this.append(value);
        }else{
        dynamic previousNode = traverseList(index -1);
        dynamic folllower =  previousNode['next'] ;
        
        previousNode['next'] = newNode;
        newNode['next'] =  folllower;
        newNode['prev'] =  previousNode;
        folllower['prev'] = newNode;
        
   
        
        // newNode['next'] =  currentNode;
        length++;
        
        }
        
       
    }
    
    remove(index){
        if(index == 0){
          dynamic  pointer = head['next'];
            // head = null;
            head = pointer; 
            head['prev'] = null;
            length--;
    
        }else if(index == length-1){
            dynamic previousNode = traverseList(index -1);
            dynamic pointer = tail['next'];
        
            previousNode['next'] = pointer;
            tail = previousNode;
           
           
            length--;
        }else{
         dynamic previousNode = traverseList(index -1);
           dynamic unwantedNode = previousNode['next'];
           dynamic follower = unwantedNode['next'];
            previousNode['next'] = unwantedNode['next'];
            follower['prev'] = previousNode;
            
            length--;
        
        }
        
    }
    
    
    
    traverseList(index){
        dynamic currentNode = head;
        int counter = 0;
        while(counter != index){
            currentNode = currentNode['next'];
            counter++;
        }
        
        return currentNode;
    }
    
    @override
    String toString (){
        return 'Head: ${head}  Tail: $tail length: $length';
    }
}


void main() {
    DoublyLinkedList linkedList = new DoublyLinkedList(10);
    linkedList.append(5);
    linkedList.prepend(6);
    linkedList.insert(1,4);
    //  linkedList.insert(20,90);
    //   print(linkedList);
    //     linkedList.prinlnt(7);
      linkedList.remove(2);
      print(linkedList);
       linkedList.prinlnt(7);
    
}