Jan 31 Friday 2025

package linkedlists;

import javax.swing.text.html.HTMLDocument;
import java.util.Iterator;

public class LinkedList implements Iterable<Node> {
    private Node head, tail;


    public LinkedList() {
       head = null;
       tail = null;
    }


    public void append(int elem) {
       Node newNode = new Node(elem);
       // FILL IN CODE
       if (head == null){
          head = tail = newNode;
       }else{
          tail.setNext(newNode);
          tail = newNode;
       }
    }


    public void insertAtFront(int elem) {
       // FILL IN CODE:
       // Insert a new node with elem in front of the linked list
       Node newNode = new Node(elem);

       if(head == null){
          head  = tail = newNode;
       }
       else{
          newNode.setNext(head);
          head = newNode;
       }
    }

//  public Node find(int i){
//        Node current = head;
//        for(int j=0; current!=null && j<i; j++){
//           current = current.next();
//        }
//        return current;
//  }


//  public void insertAtIndex(int i, int elem) {
//     // FILL IN CODE: insert a new node with the given elem
//     // at "index" i
//     // Example:
//     // If the linked list is 5 -> 7 - > 2 and we call
//     // insertAtIndex(1, 8), the linked list will be
//     // 5 -> 8 -> 7 -> 2  we inserted element 8 at "index" = 1.
//     Node newNode = new Node(elem);
//     if(i==0){
//         insertAtFront(elem);
//         return;
//     }
//
//     if(head == null){
////          head  = tail = newNode;
//
//        System.out.println("List is empty");
//        return;
//     }else{
//        Node prev = find(i-1);
//        if(prev!=null){
//           newNode.setNext(prev.next());
//           prev.setNext(newNode);
//           if(prev == tail){
//              tail = newNode;
//           }
//        }else{
//           System.out.println("couldn't insert");
//        }
//     }
//  }

    public void insertAtIndex(int i, int elem) {
       if(i==0){
          insertAtFront(elem);
          return;
       }

       if(head == null){
          System.out.println("List is empty");
          return;
       }

       Node current = head;
       int count=0;
       while(current!=null && count<i-1){
          current = current.next();
          count++;
       }

       if(current == null){
          System.out.println("Invalid index");
          return;
       }
       Node newNode = new Node(elem);
       newNode.setNext(current.next());
       current.setNext(newNode);
       if(current==tail){
          tail = newNode;
       }
    }



    public void printNodes() {
       Node current = head;
       while (current != null) {
          System.out.print(current.getElem() + " ");
          current = current.next();
       }
       System.out.println();

//     while(head!=null){
//        System.out.println(head.getElem());
//        head = head.next();
//     }

    }





    public Node getMiddleNode() {
     // FILL IN CODE: use slow and fast points to return
     // the node in the middle of the linked list in one pass
       Node fast = head;
       Node slow = head;

       if(head == null){
          System.out.println("LinkedList is empty");
          return null;
       }
       else{
          while(fast!=null && fast.next()!=null){
             slow = slow.next();
             fast = fast.next().next();
          }
       }
        return slow;
    }

    public Node tail(){
       return tail;
    }

    public Node head(){
       return head;
    }




//  public Node getKthFromEnd(int k){
//
//     if(head==null){
//        System.out.println("List is empty");
//        return null;
//     }
//     Node slow = head;
//     Node fast = head;
//
//     for(int i=0; i<k ; i++){
//        if(fast.next()!=null){
//           fast = fast.next();
//        }else{
//           System.out.println("out of bound");
//           return null;
//        }
//     }
//
//     while(fast.next()!=null){
//        fast = fast.next();
//        slow = slow.next();
//     }
//
//     return slow;
//  }

    public Node getKthFromEnd(int k){
       if(head==null){
          System.out.println("List is empty");
          return null;
       }
       Node slow = head;
       Node fast = head;

       int count = 0;
       while(fast != null && count < k){
          fast = fast.next();
          count++;
       }
       if(fast==null){
          System.out.println("Index is invalid");
          return null;
       }
       while (fast != tail) {
          slow = slow.next();
          fast = fast.next();
       }

       return slow;
    }

    public void removeNode(int elem) {
       // FILL IN CODE: remove the first node it finds with the given element



    }

    public Iterator<Node> iterator(){
       return new MyLinkedListIterator();
    }


    public class MyLinkedListIterator implements Iterator<Node> {
       private Node curr;

       public MyLinkedListIterator() {
          curr = head;
       }


       @Override
       public boolean hasNext() {
          return (curr!=null);
       }

       @Override
       public Node next() {
          // I want to return curr
          // I want to advance curr
          Node temp = curr;
          if(hasNext()){
             curr = curr.next();
             return temp;
          }
          return null;

       }
    }
}