JAVA PROJECT This Assignment contains two parts. Part - 1: Implement a singly li
ID: 3870115 • 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);
}
}
Expert Answer
Was this answer helpful?
0
0
63 answers
Given below is the code for singly linked list of doubles. Output is shown by executing the main in linkedList. Request you to post Part 2 as a separate question.
Hope the answer helped. If it helped, please do rate the answer. Thank you.
node.java
public class node{
public double data;
public node next;
public node(){
data = 0;
next = null;
}
public node(double 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);
}
}
linkedList.java
public class linkedList {
public node head;
public int size;
public linkedList() {
head = null;
size = 0;
}
public void pushBack(double 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 pushFront(double data) {
node newNode = new node(data);
newNode.next = head;
head = newNode;
++size;
}
public void popBack() {
if (isEmpty())
return;
if (head.next == null) { // single element in list
head = null;
return;
}
node last = head;
node prev = head;
while (last.next != null) {
prev = last;
last = last.next;
}
prev.next = null;
--size;
}
public void popFront() {
if (isEmpty())
return;
head = head.next;
--size;
}
public int size() {
return size;
}
public boolean isEmpty() {
return (size == 0);
}
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 insert(int index, double val)
{
if(index <= 0)
pushFront(val);
else if (index >= size())
pushBack(val);
else
{
node prev = null;
node curr = head;
for(int i = 0; i < index; i++)
{
prev = curr;
curr = curr.next;
}
node n = new node(val);
n.next = curr;
prev.next = n;
}
}
public void deleteDuplicates(double val)
{
if(isEmpty())
return;
node prev = null;
node curr = head;
while(curr != null)
{
if(curr.data == val) //matching node
{
if(curr == head) //deleting head
head = head.next;
else
prev.next = curr.next;
curr = prev.next; //set the updated curr node
}
else
{
prev = curr;
curr = curr.next;
}
}
}
//returns the value in the mth node to the last node, if no such node, then returns 0
public double mtoLastElement(int m)
{
if(m >= size())
return 0;
int index = size() - m - 1; //calcuate the index of the element from begining of list
node curr = head;
for(int i = 0; i < index; i++)
curr = curr.next;
return curr.data;
}
public void reverseList()
{
if(size() <= 1)// nothing to reverse for an empty list or a list with 1 element
return;
//so the list has atleast 2 elements if it reaches this part of code
node first = head;
node second = first.next;
node savedNext;
first.next = null; //set hte next to null since the first node will become the last after reversing
while(second != null)
{
savedNext = second.next; //save the actual next node before overwirting it
second.next = first; //overwrite the next value to point to previous node
first = second;
second = savedNext;
}
head = first; //update the head to last node processed
}
//assuming one and two are already sorted, the merged list also is sorted
public static linkedList mergeLists(linkedList one, linkedList two)
{
node p1 = one.head;
node p2 = two.head;
linkedList three = new linkedList();
while(p1 != null || p2 != null)
{
if(p1 == null) //already reached end of list one
{
three.pushBack(p2.data);
p2 = p2.next;
}
else if(p2 == null) //not end of list one , but end of list two
{
three.pushBack(p1.data);
p1 = p1.next;
}
else //there are elements in list one and two to be merged
{
if(p1.data < p2.data)
{
three.pushBack(p1.data);
p1 = p1.next;
}
else
{
three.pushBack(p2.data);
p2 = p2.next;
}
}
}
return three;
}
public static void main(String[] args) {
linkedList linkedList();
linkedList two = new linkedList();
//push odd numbers using pushBack
for(int i = 1; i < 10; i+=2)
one.pushBack(i);
//push even numbers using pushFront
for(int i = 10; i >= 0; i -= 2)
two.pushFront(i);
System.out.println("list one: size = " + one.size());
one.printList();
System.out.println("list two: size = " + two.size());
two.printList();
System.out.println("on list two, popFront() and popBack()");
two.popFront();
two.popBack();
System.out.println("list two: size = " + two.size());
two.printList();
two.insert(4, 6);
System.out.println("after two.insert(2, 6): ");
System.out.println("list two: size = " + two.size());
two.printList();
two.deleteDuplicates(6);
System.out.println("after two.deleteDuplicates( 6): ");
System.out.println("list two: size = " + two.size());
two.printList();
linkedList three = linkedList.mergeLists(one, two);
System.out.println("merging one and two into three");
System.out.println("list three: size = " + three.size());
three.printList();
System.out.println("three.mtolastElement(5) = " + three.mtoLastElement(5));
three.reverseList();
System.out.println("after three.reverseList()");
System.out.println("list three: size = " + three.size());
three.printList();
}
}
output
list one: size = 5
1.0 -> 3.0 -> 5.0 -> 7.0 -> 9.0 -> null
list two: size = 6
0.0 -> 2.0 -> 4.0 -> 6.0 -> 8.0 -> 10.0 -> null
on list two, popFront() and popBack()
list two: size = 4
2.0 -> 4.0 -> 6.0 -> 8.0 -> null
after two.insert(2, 6):
list two: size = 5
2.0 -> 4.0 -> 6.0 -> 8.0 -> 6.0 -> null
after two.deleteDuplicates( 6):
list two: size = 5
2.0 -> 4.0 -> 8.0 -> null
merging one and two into three
list three: size = 8
1.0 -> 2.0 -> 3.0 -> 4.0 -> 5.0 -> 7.0 -> 8.0 -> 9.0 -> null
three.mtolastElement(5) = 3.0
after three.reverseList()
list three: size = 8
9.0 -> 8.0 -> 7.0 -> 5.0 -> 4.0 -> 3.0 -> 2.0 -> 1.0 -> null
Explanation / Answer
Part-2
import java.util.Scanner;
/* Class Node */
class Node
{
protected int data;
protected Node next, prev;
/* Constructor */
public Node()
{
next = null;
prev = null;
data = 0;
}
/* Constructor */
public Node(int d, Node n, Node p)
{
data = d;
next = n;
prev = p;
}
/* Function to set link to next node */
public void setLinkNext(Node n)
{
next = n;
}
/* Function to set link to previous node */
public void setLinkPrev(Node p)
{
prev = p;
}
/* Funtion to get link to next node */
public Node getLinkNext()
{
return next;
}
/* Function to get link to previous node */
public Node getLinkPrev()
{
return prev;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
}
/* Class linkedList */
class linkedList
{
protected Node start;
protected Node end ;
public int size;
/* Constructor */
public linkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert element at begining */
public void pushFront(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
start = nptr;
}
size++;
}
/* Function to insert element at end */
public void pushBack(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
end = nptr;
}
size++;
}
/* Function to insert element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null, null);
if (pos == 1)
{
pushFront(val);
return;
}
Node ptr = start;
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();
}
size++ ;
}
* this method removes element from the start of the linked list
* @return
*/
public void popFront() {
if (size == 0) throw new NoSuchElementException();
Node tmp = start;
start = start.next;
start.prev = null;
size--;
start = tmp;
}
/**
* this method removes element from the end of the linked list
* @return
*/
public void popBack() {
if (size == 0) throw new NoSuchElementException();
Node tmp = end;
end = end.prev;
end.next = null;
size--;
}
/* function to reverse the list*/
Node nptr=head; //create a node and point to head
while(nptr!=null)
{
temp=nptr.next;
nptr.next=nptr.prev;
nptr.prev=temp;
nptr=nptr.next;
}
/* Class DoublyLinkedList */
public class DoublyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of linkedList */
linkedList list = new linkedList();
System.out.println("Doubly Linked List Test ");
char ch;
/* Perform list operations */
do
{
System.out.println(" Doubly Linked List Operations ");
System.out.println("1. Push front");
System.out.println("2. Push Back");
System.out.println("3. insert at position");
System.out.println("4. PopFront");
System.out.println("5. PopBack");
System.out.println("6. Reverse the list");)
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.pushFront( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.pushBack( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter position");
int pos = scan.nextInt() ;
if (pos < 1 || pos > list.getSize() )
System.out.println("Invalid position ");
else
list.insertAtPos(num, pos);
break;
case 4 :
list.popFront();
break;
case 5 :
list.popFront();
break;
case 6 :
list.reverse(start);
break;
default :
System.out.println("Wrong Entry ");
break;
}
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.