CODES IN JAVA

1.Implement Singly Linked List detect Loopwhich check whetherthe linked list containsa loop.-Its an instance method that takes no parameter. It returns true if the linked list contains a loop that goes on forever if tracing the list from head. It returns false if it does not contain a loop.This method should be O(n), n as the number of nodes in the linked list.

2.Complete Doubly Linked Listgetmethod whichbehaves like the operator[] of array.-Its an instance method that takes a position and an element, and then returns the element fromthis specific position. It throws an exception if the position is out of bound. It traverses the list from header if the position is closer to the header and traverses the list from trailer otherwise.Part of the method is given.

Given code: FILL UP THE MISSING CODES BELOW

/** * * Student: * */ public class A1LinkedList{ public static void main(String argc[]){ LinkedList sl = new LinkedList<>(); DLinkedList dl = new DLinkedList<>(); PolynomialLinkedList sum = new PolynomialLinkedList(); PolynomialLinkedList prod = new PolynomialLinkedList(); for (int i = 40; i >= -40; i-=2) { sl.add(i*i); dl.add(i); } try { sl.insert(111, sl.getNode(38), sl.getNode(40)); if (sl.detectLoop()) System.out.println("Loop! Wrong"); else System.out.println("No loop."); sl.insert(123, sl.getNode(38), sl.getNode(36)); if (sl.detectLoop()) System.out.println("Loop!"); else System.out.println("No loop. Wrong"); sl.insert(321, sl.getNode(38), sl.getNode(37)); if (sl.detectLoop()) System.out.println("Loop!"); else System.out.println("No loop. Wrong"); dl.print(); System.out.println("Index 20, has 0? " + dl.get(20)); System.out.println("Index 21, has -2? " + dl.get(21)); } catch(Exception e){ e.printStackTrace(); } PolynomialLinkedList p1, p2, p3, p4; p1 = new PolynomialLinkedList(2,3); p2 = new PolynomialLinkedList(3,2); p3 = p1.add(p2); p1 = new PolynomialLinkedList(1,0); p4 = p2.add(p1); sum = p3.add(p4); // extra credit //prod = p3.multiply(p4); p3.print(); p4.print(); sum.print(); //prod.print(); } } class LinkedList{ private static class Node{ private E element; private Node next; public Node(E e, Node n){ element = e; next = n; } public E getElement(){ return element; } public Node getNext(){ return next; } public void setElement(E e){ element = e; } public void setNext(Node n){ next = n; } } private Node head; public LinkedList(){ head = null; } public void add(E e){ Node temp = new Node<>(e, head); head = temp; } public void insert(E e, Node p, Node n){ p.setNext(new Node<>(e, n)); } public Node getNode(int i) throws Exception{ Node temp = head; while (i > 0){ if (temp == null) throw new Exception("Out of bound"); temp = temp.getNext(); i--; } return temp; } public boolean detectLoop(){ //implement this method *******************MISSING CODE***********HERE************************************ return true; } } class DLinkedList{ private static class DNode{ private E element; private DNode prev; private DNode next; public DNode(E e){ this(e, null, null); } public DNode(E e, DNode p, DNode n){ element = e; prev = p; next = n; } public E getE(){ return element; } public DNode getPrev(){ return prev; } public DNode getNext(){ return next; } public void setE(E e){ element = e; } public void setPrev(DNode p){ prev = p; } public void setNext(DNode n){ next = n; } } private DNode header; private DNode trailer; private int size; public DLinkedList(){ header = new DNode(null); trailer = new DNode(null, header, null); header.setNext(trailer); size = 0; } public void add(E e){ DNode oLast = trailer.getPrev(); DNode temp = new DNode<>(e, oLast, trailer); oLast.setNext(temp); trailer.setPrev(temp); size++; } public E get(int i) throws Exception{ if (i < 0 || i >= size) throw new Exception("Bad Index"); DNode ansNode; if (i < size / 2){//lower end ansNode = header.getNext(); //loop - traversal from header while (i > 0){ ansNode = ansNode.getNext(); i--; } } //complete this method****************************MISSING CODE*******HERE************* return null; } public void print(){ DNode temp = header.getNext(); while (temp != trailer){ System.out.print(temp.getE().toString() + ", "); temp = temp.getNext(); } System.out.println(); } } class PolynomialLinkedList{ private static class PNode{ private int coe; private int exp; private PNode next; public PNode(int c, int e){ this(c, e, null); } public PNode(int c, int e, PNode n){ coe = c; exp = e; next = n; } public void setCoe(int c){ coe = c;} public void setExp(int e){ exp = e;} public void setNext(PNode n){ next = n;} public int getCoe(){ return coe;} public int getExp(){ return exp;} public PNode getNext(){ return next;} } private PNode first; private PNode last; public PolynomialLinkedList(){ first = last = null; } public PolynomialLinkedList(int c, int e){ PNode tempn = new PNode(c, e); first = last = tempn; } public void print(){ if (first == null){ System.out.println(); return; } PNode temp = first; String ans = ""; while (temp != null){ if (temp.getCoe() > 0) { if (temp != first) ans = ans + " + "; ans = ans + temp.getCoe(); } else if (temp.getCoe() < 0) ans = ans + " - " + temp.getCoe() * -1; if (temp.getExp() != 0){ ans = ans + "X^" + temp.getExp(); } temp = temp.getNext(); } System.out.println(ans); } public PolynomialLinkedList add(PolynomialLinkedList s){ PolynomialLinkedList sum = new PolynomialLinkedList(); //implement this method return sum; } public PolynomialLinkedList multiply(PolynomialLinkedList s){ PolynomialLinkedList product = new PolynomialLinkedList(); //implement this method for extra credit return product; } }