Here is the IntegerLinkedList_incomplete class:
public class IntegerLinkedList { static class Node { /** The element stored at this node */ private int element; // reference to the element stored at this node /** A reference to the subsequent node in the list */ private Node next; // reference to the subsequent node in the list /** * Creates a node with the given element and next node. * * @param e the element to be stored * @param n reference to a node that should follow the new node */ public Node(int e, Node n) { element = e; next = n; } // Accessor methods /** * Returns the element stored at the node. * @return the element stored at the node */ public int getElement() { return element; } /** * Returns the node that follows this one (or null if no such node). * @return the following node */ public Node getNext() { return next; } // Modifier methods /** * Sets the node's next reference to point to Node n. * @param n the node that should follow this one */ public void setNext(Node n) { next = n; } } //----------- end of nested Node class ----------- // instance variables of the SinglyLinkedList /** The head node of the list */ private Node head = null; // head node of the list (or null if empty) /** The last node of the list */ private Node tail = null; // last node of the list (or null if empty) /** Number of nodes in the list */ private int size = 0; // number of nodes in the list public Node getHead() { return head; } public Node getTail() { return tail; } public int getSize() { return size; } public void setHead(Node h) { head = h; } public void setTail(Node t) { tail = t; } public void setSize(int s) { size = s; } /** Constructs an initially empty list. */ public IntegerLinkedList() { } // constructs an initially empty list // access methods /** * Returns the number of elements in the linked list. * @return number of elements in the linked list */ public int size() { return size; } /** * Tests whether the linked list is empty. * @return true if the linked list is empty, false otherwise */ public boolean isEmpty() { return size == 0; } /** * Returns (but does not remove) the first element of the list * @return element at the front of the list (or -1000000 if empty) */ public int first() { // returns (but does not remove) the first element if (isEmpty()) return -1000000; return head.getElement(); } /** * Returns (but does not remove) the last element of the list. * @return element at the end of the list (or -1000000 if empty) */ public int last() { // returns (but does not remove) the last element if (isEmpty()) return -1000000; return tail.getElement(); } // update methods /** * Adds an element to the front of the list. * @param e the new element to add */ public void addFirst(int e) { // adds element e to the front of the list head = new Node(e, head); // create and link a new node if (size == 0) tail = head; // special case: new node becomes tail also size++; } /** * Adds an element to the end of the list. * @param e the new element to add */ public void addLast(int e) { // adds element e to the end of the list Node newest = new Node(e, null); // node will eventually be the tail if (isEmpty()) head = newest; // special case: previously empty list else tail.setNext(newest); // new node after existing tail tail = newest; // new node becomes the tail size++; } /** * Removes and returns the first element of the list. * @return the removed element (or -1000000 if empty) */ public int removeFirst() { // removes and returns the first element if (isEmpty()) return -1000000; // nothing to remove int answer = head.getElement(); head = head.getNext(); // will become null if list had only one node size--; if (size == 0) tail = null; // special case as list is now empty return answer; } /** * Removes the node pointed to by r * @param r: pointer to the node to be removed * @return: the int element of the removed node */ public int removeNode(Node r) { if (isEmpty()) return -1000000; Node current = head; Node previous = current; while ((current != null) && (current != r)) { previous = current; current = current.getNext(); } if (current == null) return -1000000; previous.next = current.getNext(); size--; if (size == 0) tail = null; return current.getElement(); } /** * Prints the elements in the given linked list * @param head: head of a linked list */ public static void printList(Node head) { Node current = head; while (current != null) { System.out.print(current.getElement() + " "); current = current.getNext(); } } public IntegerLinkedList copyList() { IntegerLinkedList other = new IntegerLinkedList(); if (size > 0) { // we need independent chain of nodes other.head = new Node(head.getElement(), null); int s = other.getSize(); s++; other.setSize(s); Node walk = head.getNext(); // walk through remainder of original list Node otherTail = other.head; // remember most recently created node while (walk != null) { // make a new node storing same element Node newest = new Node(walk.getElement(), null); otherTail.setNext(newest); // link previous node to this one s = other.getSize(); s++; other.setSize(s); otherTail = newest; walk = walk.getNext(); } } return other; } /** * Reverses the order of first n elements in the give linked list recursively * @param list: IntegerLinkedList * @param n: 1 <= n <= size of the list * @return: a Node type; exactly what should be returned (or nothing is returned) must be determined by students * in the context of their recursive algorithm; refer to the assignment */ public static Node reverseFirstN(IntegerLinkedList list, int n) { // complete this method // this method must be a recursive method } }
Here is the Hw4_Part3 class:
public class Hw4_Part3 { public static void main(String[] args) { IntegerLinkedList intList = new IntegerLinkedList(); for (int i=1; i<=10; i++) { intList.addLast(i*10); } System.out.println("Original list: "); IntegerLinkedList.printList(intList.getHead()); System.out.println(); // make a copy and use it for testing IntegerLinkedList intListCopy = new IntegerLinkedList(); intListCopy = intList.copyList(); int N = 2; IntegerLinkedList.reverseFirstN(intListCopy, N); System.out.println("\nAfter reversing first " + N + " elements: "); IntegerLinkedList.printList(intListCopy.getHead()); System.out.println(); intListCopy = intList.copyList(); N = 4; IntegerLinkedList.reverseFirstN(intListCopy, N); System.out.println("\nAfter reversing first " + N + " elements: "); IntegerLinkedList.printList(intListCopy.getHead()); System.out.println(); intListCopy = intList.copyList(); N = 8; IntegerLinkedList.reverseFirstN(intListCopy, N); System.out.println("\nAfter reversing first " + N + " elements: "); IntegerLinkedList.printList(intListCopy.getHead()); System.out.println(); } }
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Hw4_Part3 {
public static void main(String[] args) {
IntegerLinkedList intList = new IntegerLinkedList();
for (int i=1; i<=10; i++) {
intList.addLast(i*10);
}
System.out.println("Original list: ");
IntegerLinkedList.printList(intList.getHead());
System.out.println();
// make a copy and use it for testing
IntegerLinkedList intListCopy = new IntegerLinkedList();
intListCopy = intList.copyList();
int N = 2;
IntegerLinkedList.reverseFirstN(intListCopy, N);
System.out.println("\nAfter reversing first " + N + " elements: ");
IntegerLinkedList.printList(intListCopy.getHead());
System.out.println();
intListCopy = intList.copyList();
N = 4;
IntegerLinkedList.reverseFirstN(intListCopy, N);
System.out.println("\nAfter reversing first " + N + " elements: ");
IntegerLinkedList.printList(intListCopy.getHead());
System.out.println();
intListCopy = intList.copyList();
N = 8;
IntegerLinkedList.reverseFirstN(intListCopy, N);
System.out.println("\nAfter reversing first " + N + " elements: ");
IntegerLinkedList.printList(intListCopy.getHead());
System.out.println();
}
}
public class IntegerLinkedList {
static class Node {
/** The element stored at this node */
private int element; // reference to the element stored at this node
/** A reference to the subsequent node in the list */
private Node next; // reference to the subsequent node in the list
/**
* Creates a node with the given element and next node.
*
* @param e the element to be stored
* @param n reference to a node that should follow the new node
*/
public Node(int e, Node n) {
element = e;
next = n;
}
// Accessor methods
/**
* Returns the element stored at the node.
* @return the element stored at the node
*/
public int getElement() { return element; }
/**
* Returns the node that follows this one (or null if no such node).
* @return the following node
*/
public Node getNext() { return next; }
// Modifier methods
/**
* Sets the node's next reference to point to Node n.
* @param n the node that should follow this one
*/
public void setNext(Node n) { next = n; }
} //----------- end of nested Node class -----------
// instance variables of the SinglyLinkedList
/** The head node of the list */
private Node head = null; // head node of the list (or null if empty)
/** The last node of the list */
private Node tail = null; // last node of the list (or null if empty)
/** Number of nodes in the list */
private int size = 0; // number of nodes in the list
public Node getHead() { return head; }
public Node getTail() { return tail; }
public int getSize() { return size; }
public void setHead(Node h) { head = h; }
public void setTail(Node t) { tail = t; }
public void setSize(int s) { size = s; }
/** Constructs an initially empty list. */
public IntegerLinkedList() { } // constructs an initially empty list
// access methods
/**
* Returns the number of elements in the linked list.
* @return number of elements in the linked list
*/
public int size() { return size; }
/**
* Tests whether the linked list is empty.
* @return true if the linked list is empty, false otherwise
*/
public boolean isEmpty() { return size == 0; }
/**
* Returns (but does not remove) the first element of the list
* @return element at the front of the list (or -1000000 if empty)
*/
public int first() { // returns (but does not remove) the first element
if (isEmpty()) return -1000000;
return head.getElement();
}
/**
* Returns (but does not remove) the last element of the list.
* @return element at the end of the list (or -1000000 if empty)
*/
public int last() { // returns (but does not remove) the last element
if (isEmpty()) return -1000000;
return tail.getElement();
}
// update methods
/**
* Adds an element to the front of the list.
* @param e the new element to add
*/
public void addFirst(int e) { // adds element e to the front of the list
head = new Node(e, head); // create and link a new node
if (size == 0)
tail = head; // special case: new node becomes tail also
size++;
}
/**
* Adds an element to the end of the list.
* @param e the new element to add
*/
public void addLast(int e) { // adds element e to the end of the list
Node newest = new Node(e, null); // node will eventually be the tail
if (isEmpty())
head = newest; // special case: previously empty list
else
tail.setNext(newest); // new node after existing tail
tail = newest; // new node becomes the tail
size++;
}
/**
* Removes and returns the first element of the list.
* @return the removed element (or -1000000 if empty)
*/
public int removeFirst() { // removes and returns the first element
if (isEmpty()) return -1000000; // nothing to remove
int answer = head.getElement();
head = head.getNext(); // will become null if list had only one node
size--;
if (size == 0)
tail = null; // special case as list is now empty
return answer;
}
/**
* Removes the node pointed to by r
* @param r: pointer to the node to be removed
* @return: the int element of the removed node
*/
public int removeNode(Node r) {
if (isEmpty()) return -1000000;
Node current = head;
Node previous = current;
while ((current != null) && (current != r)) {
previous = current;
current = current.getNext();
}
if (current == null) return -1000000;
previous.next = current.getNext();
size--;
if (size == 0)
tail = null;
return current.getElement();
}
/**
* Prints the elements in the given linked list
* @param head: head of a linked list
*/
public static void printList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.getElement() + " ");
current = current.getNext();
}
}
public IntegerLinkedList copyList() {
IntegerLinkedList other = new IntegerLinkedList();
if (size > 0) { // we need independent chain of nodes
other.head = new Node(head.getElement(), null);
int s = other.getSize();
s++;
other.setSize(s);
Node walk = head.getNext(); // walk through remainder of original list
Node otherTail = other.head; // remember most recently created node
while (walk != null) { // make a new node storing same element
Node newest = new Node(walk.getElement(), null);
otherTail.setNext(newest); // link previous node to this one
s = other.getSize();
s++;
other.setSize(s);
otherTail = newest;
walk = walk.getNext();
}
}
return other;
}
/**
* Reverses the order of first n elements in the give linked list recursively
* @param list: IntegerLinkedList
* @param n: 1 <= n <= size of the list
* @return: a Node type; exactly what should be returned (or nothing is returned) must be determined by students
* in the context of their recursive algorithm; refer to the assignment
*/
public static void reverseFirstN(IntegerLinkedList list, int n) {
// complete this method
// this method must be a recursive method
///first travel till the element n
Node plusone;
reverseFirstNutil(list.getHead(),plusone,n);
}
public static void reverseFirstNutil(Node temp,Node plusone,int n){
if(n==1)
{
plusone=temp.getNext();
Node headf=temp;
return;
}
reverseFirstNutil(temp.getNext(),plusone,n-1);
Node q=temp.getNext();
q.next=temp;
temp.next=plusone;
// return headf;
}
}
//here unable to rename file(.java). plz give correct direction
Here is the IntegerLinkedList_incomplete class: public class IntegerLinkedList { static class Node { /** The element...
Data Structures - Singly Linked Lists You will add a method swapNodes to SinglyLinkedList class (below). This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same node, etc. Write the main method to test the swapNodes method. You may need to traverse the list. package linkedlists; public class SinglyLinkedList<E> implements Cloneable { // ---------------- nested Node class...
Q1: You can find a file that defines the CircularlyLinked List class similar to what we discussed in the class. Download the file and work on it. Your task is to: 1. Complete the missing methods in the file as discussed in the class. Search for the comment/" MISSING / in the file to see the methods that need to be completed. 2. Add the following methods to the class a. public Node getMin 1. Task: find the node with...
could somone please help me to complete this ! public class MyLinkedList<AnyType> { private Node<AnyType> head, tail; private int size; public MyLinkedList() { this.head = null; this.tail = null; this.size = 0; } //1.Insert a node at the end of the list public void insert(AnyType data) { Node<AnyType> newNode = new Node(); newNode.data = data; if (head == null) { head = newNode; tail = newNode; head.next = null; tail.next = null; } else { tail.next = newNode; tail =...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements DoubleEndedList { private Node front; // first node in list private Node rear; // last node in list private int size; // number of elements in list ////////////////////////////////////////////////// // YOU MUST IMPLEMENT THE LOCATE METHOD BELOW // ////////////////////////////////////////////////// /** * Returns the position of the node containing the given value, where * the front node is at position zero and the rear node is...
Given a singly-linked list interface and linked list node class, implement the singly-linked list which has the following methods in Java: 1. Implement 3 add() methods. One will add to the front (must be O(1)), one will add to the back (must be O(1)), and one will add anywhere in the list according to given index (must be O(1) for index 0 and O(n) for all other indices). They are: void addAtIndex(int index, T data), void addToFront(T data), void addToBack(T...
//LinkedList import java.util.Scanner; public class PoD { public static void main( String [] args ) { Scanner in = new Scanner( System.in ); LinkedList teamList = new LinkedList(); final int TEAM_SIZE = Integer.valueOf(in.nextLine()); for (int i=0; i<TEAM_SIZE; i++) { String newTeamMember = in.nextLine(); teamList.append(newTeamMember); } while (in.hasNext()) { String removeMember = in.nextLine(); teamList.remove(removeMember); } System.out.println("FINAL TEAM:"); System.out.println(teamList); in.close(); System.out.print("END OF OUTPUT"); } } =========================================================================================== //PoD import java.util.NoSuchElementException; /** * A listnked list is a sequence of nodes with...
Implement the following in java. 1. An insertAtBeginning(Node newNode) function, that inserts a node at the beginning(root) of the linked list. 2. A removeFromBeginning() function, that removes the node from the beginning of the linked list and assigns the next element as the new beginning(root). 3. A traverse function, that iterates the list and prints the elements in the linked list. For the insertAtBeginning(Node newNode) function: 1. Check if the root is null. If it is, just assign the new...
how do I change my code to generic form *********************************************************************** public class UnboundedStackQueue { //question#3 } class Stack { Node head; int size; Stack() //default constructor { this.head=null; this.size=0; } //Input = data //Output = void (just adds value to list) // method pushes elements on stack // time: O(1) // space: O(1) public void push(int data) { Node node=new Node(data); node.next=head; head=node; size++; } //Input = none //Output = top of stack // method pops value from top of...
In Java You may add any classes or methods to the following as you see fit in order to complete the given tasks. Modify the LinkedList (or DoubleLinkedList) class and add a method append. append should take another LinkedList (DoubleLinkedList) as input and append that list to the end of this list. The append method should work by doing a few "arrow" adjustments on the boxes and it should not loop through the input list to add elements one at...
Complete two of the List methods: SinglyLinkedList::size() and SinglyLinkedList::get(). import java.util.AbstractList; public class SinglyLinkedList<E> extends AbstractList<E> { /** Reference to the first node in our linked list. This will be null if the list is empty. */ private Entry head; /** * Creates an empty list. */ public SinglyLinkedList() { reset(); } /** * This method, which is only used within the SinglyLinkedList class, returns the instance to its initial state. This * call will reset the head to be...