JAVA PROJECT This Assignment contains two parts. Part - 1: Implement a singly li
ID: 3870155 • 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
public class linkedList{
static 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 void insert_specific(int data,int i)
{
if(isEmpty())
return;
if(i>=size+1){
System.out.println("Index out of bound error");
return;
}
if(i == 0){
insertFront(data);
}
else if(i==size)
{
appendNode(data);
}
else{
node newNode = new node(data);
node prev = null;
node curr = head;
while(i != 0){
prev = curr;
curr = curr.next;
i--;
}
prev.next = newNode;
newNode.next = curr;
size++;
}
}
public node removeDuplicateElements(node n) {
if (n == null || n.next == null) {
return null;
}
if (n.data == n.next.data) {
node next_next = n.next.next;
n.next = null;
n.next = next_next;
removeDuplicateElements(n);
} else {
removeDuplicateElements(n.next);
}
return n;
}
public node Node_reverse(node n) {
node prev = null;
node current = n;
node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
n = prev;
return n;
}
public node mergeTwoLists(node l1, node l2) {
node head = new ListNode(0);
node p = head;
while(l1!=null||l2!=null){
if(l1!=null&&l2!=null){
if(l1.val < l2.val){
p.next = l1;
l1=l1.next;
}else{
p.next=l2;
l2=l2.next;
}
p = p.next;
}else if(l1==null){
p.next = l2;
break;
}else if(l2==null){
p.next = l1;
break;
}
}
return head.next;
}
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(1);
l.insertFront(5);
l.printList();
//l.size();
//l.removelast();
//l.removelast();
//l.printList();
//l.size();
//l.removeFront();
//l.printList();
l.size();
head = l.removeDuplicateElements(head);
l.printList();
head = l.Node_reverse(head);
//l.deleteIndex(1);
//l.insert_specific(10,5);
l.printList();
l.size();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.