JAVA PROJECT This Assignment contains two parts. Part - 1: Implement a singly li
ID: 3890761 • Letter: J
Question
JAVA PROJECT
This Assignment contains two parts.
Part - 1: Implement a singly linked list ADT to store a collection of doubles.
Part - 2: Implement a Double linked List ADT to store a collection of integers.
Your program will include the following member functions:
--- a default constructor linkedList()
-- a custom constructor that takes a value and create a node with that value. Ex: linkedList(Type data)
1. a member function pushFront(data) that inserts a node with data at the front of the list
2. a member function pushBack(data) that appends a node with data at the back of the list
3. a member function popFront() that removes first node of the list.
4. a member function popBack() that removes last node of the list.
5. a member function insert(index, val) that inserts a new node with value "val" at a specific position mentioned by the index argument.
6. a member function deleteDuplicates(val) that deletes a node with that number and all its copies from the list, where these copies can be located anywhere in the list.
7. a member function mtoLastElement(M) that returns Mth to the last element of a list such that when M = 0, the last element of the list is returned.
8. a member function size() that returns the size of the list.
9. a member function reverseList() that reverses a linked list without recreating a temporary copy of this linked list. In other words, your function CAN NOT use the 'new' operator. Here is an example, if a list contains the following data items, 3 -> 5 -> 1 -> 7; this reverse() function will change the list to 7 -> 1 -> 5 -> 3.
10. a MemberFunction mergeLists(linkedList one, linkedList two) which will create a new list that contains the elements of two lists in sorted order(ascending). Assume the two lists are in sorted order for this case
Ex: one: 1 -> 3 -> 7 -> 25 -> 50 (sorted)
two: 5 -> 9 -> 11 - > 12 -> 29 (sorted)
result list : 1 -> 3 -> 5 -> 7 - > 9 -> 11 -> 12 -> 25 -> 29 -> 50 (Sorted)
Submission: submit your all three .java files as a whole zip and Follow the grading, programming rubric while submitting your assignment. Please make sure your programming is interactive with the tests.
EXTEND CODE BELOW
public class linkedList{
public node head;
public int size;
public linkedList(){
head = null;
size = 0;
}
public void appendNode(int data){
node newNode = new node(data);
if(head == null)
head = newNode;
else{
node last = head;
while(last.next != null)
last = last.next;
last.next = newNode;
}
++size;
}
public void insertFront(int data){
node newNode = new node(data);
newNode.next = head;
head = newNode;
++size;
}
public void printList(){
if(head == null)
return;
node walk = head;
while(walk != null){
System.out.print(walk.data+" -> ");
walk = walk.next;
}
System.out.println("null");
}
public void size(){
System.out.println("Size is : "+size);
}
public void removelast(){
if(isEmpty())
return;
if(head.next == null){
head = null;
return;
}
node last = head;
node prev = head;
while(last.next != null){
prev = last;
last = last.next;
}
prev.next = null;
--size;
}
public boolean isEmpty(){
return (size == 0);
}
public void removeFront(){
if(isEmpty())
return;
head = head.next;
--size;
}
public void deleteIndex(int i ){
if(isEmpty())
return;
if(i >= size){
System.out.println("Index out of bound error");
return;
}
if(i == 0){
head = head.next;
--size;
return;
}
node prev = null;
node curr = head;
while(i != 0){
prev = curr;
curr = curr.next;
i--;
}
prev.next = curr.next;
--size;
}
public static void main(String[] args){
linkedList l = new linkedList();
//l.size();
l.appendNode(1);
l.appendNode(2);
l.appendNode(3);
//l.printList();
//l.size();
l.insertFront(4);
l.insertFront(5);
//l.printList();
//l.size();
//l.removelast();
//l.removelast();
//l.printList();
//l.size();
//l.removeFront();
l.printList();
l.size();
l.deleteIndex(1);
l.printList();
l.size();
}
}
public class node{
public int data;
public node next;
public node(){
data = 0;
next = null;
}
public node(int data){
this.data =data;
this.next = null;
}
public static void printList(node start){
if(start == null)
return;
node walk = start;
while(walk != null){
System.out.print(walk.next+" -> ");
walk = walk.next;
}
System.out.print("null ");
}
public static void main(String[] args){
node a = new node(5);
node b = new node(7);
node c = new node(17);
a.next = b;
b.next = c;
c.next = null;
printList(a);
}
}
Explanation / Answer
SINGLE ADT LIST
import java.util.*;
/* Class Node */
class Node
{
protected int data;
protected Node link;
/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}
/* Class linkedStack */
class linkedStack
{
protected Node top ;
protected int size ;
/* Constructor */
public linkedStack()
{
top = null;
size = 0;
}
/* Function to check if stack is empty */
public boolean isEmpty()
{
return top == null;
}
/* Function to get the size of the stack */
public int getSize()
{
return size;
}
/* Function to push an element to the stack */
public void push(int data)
{
Node nptr = new Node (data, null);
if (top == null)
top = nptr;
else
{
nptr.setLink(top);
top = nptr;
}
size++ ;
}
/* Function to pop an element from the stack */
public int pop()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception") ;
Node ptr = top;
top = ptr.getLink();
size-- ;
return ptr.getData();
}
/* Function to check the top element of the stack */
public int peek()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception") ;
return top.getData();
}
/* Function to display the status of the stack */
public void display()
{
System.out.print(" Stack = ");
if (size == 0)
{
System.out.print("Empty ");
return ;
}
Node ptr = top;
while (ptr != null)
{
System.out.print(ptr.getData()+" ");
ptr = ptr.getLink();
}
System.out.println();
}
}
/* Class LinkedStackImplement */
public class LinkedStackImplement
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of class linkedStack */
linkedStack ls = new linkedStack();
/* Perform Stack Operations */
System.out.println("Linked Stack Test ");
char ch;
do
{
System.out.println(" Linked Stack Operations");
System.out.println("1. push");
System.out.println("2. pop");
System.out.println("3. peek");
System.out.println("4. check empty");
System.out.println("5. size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to push");
ls.push( scan.nextInt() );
break;
case 2 :
try
{
System.out.println("Popped Element = "+ ls.pop());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;
case 3 :
try
{
System.out.println("Peek Element = "+ ls.peek());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;
case 4 :
System.out.println("Empty status = "+ ls.isEmpty());
break;
case 5 :
System.out.println("Size = "+ ls.getSize());
break;
case 6 :
System.out.println("Stack = ");
ls.display();
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* display stack */
ls.display();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
DOUBLE LINKED LIST
import java.util.NoSuchElementException;
public class DoublyLinkedListImpl<E> {
private Node head;
private Node tail;
private int size;
public DoublyLinkedListImpl() {
size = 0;
}
/**
* this class keeps track of each element information
* @author java2novice
*
*/
private class Node {
E element;
Node next;
Node prev;
public Node(E element, Node next, Node prev) {
this.element = element;
this.next = next;
this.prev = prev;
}
}
/**
* returns the size of the linked list
* @return
*/
public int size() { return size; }
/**
* return whether the list is empty or not
* @return
*/
public boolean isEmpty() { return size == 0; }
/**
* adds element at the starting of the linked list
* @param element
*/
public void addFirst(E element) {
Node tmp = new Node(element, head, null);
if(head != null ) {head.prev = tmp;}
head = tmp;
if(tail == null) { tail = tmp;}
size++;
System.out.println("adding: "+element);
}
/**
* adds element at the end of the linked list
* @param element
*/
public void addLast(E element) {
Node tmp = new Node(element, null, tail);
if(tail != null) {tail.next = tmp;}
tail = tmp;
if(head == null) { head = tmp;}
size++;
System.out.println("adding: "+element);
}
/**
* this method walks forward through the linked list
*/
public void iterateForward(){
System.out.println("iterating forward..");
Node tmp = head;
while(tmp != null){
System.out.println(tmp.element);
tmp = tmp.next;
}
}
/**
* this method walks backward through the linked list
*/
public void iterateBackward(){
System.out.println("iterating backword..");
Node tmp = tail;
while(tmp != null){
System.out.println(tmp.element);
tmp = tmp.prev;
}
}
/**
* this method removes element from the start of the linked list
* @return
*/
public E removeFirst() {
if (size == 0) throw new NoSuchElementException();
Node tmp = head;
head = head.next;
head.prev = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}
/**
* this method removes element from the end of the linked list
* @return
*/
public E removeLast() {
if (size == 0) throw new NoSuchElementException();
Node tmp = tail;
tail = tail.prev;
tail.next = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}
public static void main(String a[]){
DoublyLinkedListImpl<Integer> dll = new DoublyLinkedListImpl<Integer>();
dll.addFirst(10);
dll.addFirst(34);
dll.addLast(56);
dll.addLast(364);
dll.iterateForward();
dll.removeFirst();
dll.removeLast();
dll.iterateBackward();
}
}
import java.util.NoSuchElementException;
public class DoublyLinkedListImpl<E> {
private Node head;
private Node tail;
private int size;
public DoublyLinkedListImpl() {
size = 0;
}
/**
* this class keeps track of each element information
* @author java2novice
*
*/
private class Node {
E element;
Node next;
Node prev;
public Node(E element, Node next, Node prev) {
this.element = element;
this.next = next;
this.prev = prev;
}
}
/**
* returns the size of the linked list
* @return
*/
public int size() { return size; }
/**
* return whether the list is empty or not
* @return
*/
public boolean isEmpty() { return size == 0; }
/**
* adds element at the starting of the linked list
* @param element
*/
public void addFirst(E element) {
Node tmp = new Node(element, head, null);
if(head != null ) {head.prev = tmp;}
head = tmp;
if(tail == null) { tail = tmp;}
size++;
System.out.println("adding: "+element);
}
/**
* adds element at the end of the linked list
* @param element
*/
public void addLast(E element) {
Node tmp = new Node(element, null, tail);
if(tail != null) {tail.next = tmp;}
tail = tmp;
if(head == null) { head = tmp;}
size++;
System.out.println("adding: "+element);
}
/**
* this method walks forward through the linked list
*/
public void iterateForward(){
System.out.println("iterating forward..");
Node tmp = head;
while(tmp != null){
System.out.println(tmp.element);
tmp = tmp.next;
}
}
/**
* this method walks backward through the linked list
*/
public void iterateBackward(){
System.out.println("iterating backword..");
Node tmp = tail;
while(tmp != null){
System.out.println(tmp.element);
tmp = tmp.prev;
}
}
/**
* this method removes element from the start of the linked list
* @return
*/
public E removeFirst() {
if (size == 0) throw new NoSuchElementException();
Node tmp = head;
head = head.next;
head.prev = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}
/**
* this method removes element from the end of the linked list
* @return
*/
public E removeLast() {
if (size == 0) throw new NoSuchElementException();
Node tmp = tail;
tail = tail.prev;
tail.next = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}
public static void main(String a[]){
DoublyLinkedListImpl<Integer> dll = new DoublyLinkedListImpl<Integer>();
dll.addFirst(10);
dll.addFirst(34);
dll.addLast(56);
dll.addLast(364);
dll.iterateForward();
dll.removeFirst();
dll.removeLast();
dll.iterateBackward();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.