Can someone help me please inmplement the following in my JAVA PROGRAM that I\'v
ID: 3563749 • Letter: C
Question
Can someone help me please inmplement the following in my JAVA PROGRAM that I've created?
a. Add
b. Delete
c. Search
d. Insert
This is what I created.
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.io.*;
public class DoublyLinkedList implements Iterable
{
private int N;
private Node pre;
private Node post;
public DoublyLinkedList()
{
pre=new Node();
post=new Node();
pre.next=post;
post.prev=pre;
}
private class Node
{
private Item item;
private Node next;
private Node prev;
}
public boolean isEmpty()
{
return N==0;
}
public int size()
{
return N;
}
public void add (Item item)
{
Node last=post.prev;
Node x= new Node();
x.item=item;
x.next= post;
x.prev= last;
post.prev= x;
last.next=x;
N++;
}
public ListIterator iterator()
{
return new DoublyLinkedListIterator();
}
private class DoublyLinkedListIterator implements ListIterator
{
private Node current=pre.next;
private Node lastAccessed=null;
private int index=0;
public boolean hasNext()
{
return index }
public boolean hasPrevious()
{
return index>0;
}
public int previousIndex()
{
return index-1;
}
public int nextIndex()
{
return index;
}
public Item next()
{
if (!hasNext()) throw new NoSuchElementException();
lastAccessed=current;
Item item=current.item;
current=current.next;
index++;
return item;
}
public Item previous()
{
if(!hasPrevious())throw new NoSuchElementException();
current=current.prev;
index--;
lastAccessed=current;
return current.item;
}
public void set(Item item)
{
if(lastAccessed==null) throw new IllegalStateException();
lastAccessed.item=item;
}
public void remove()
{
if (lastAccessed==null)throw new IllegalStateException();
Node x= lastAccessed.prev;
Node y= lastAccessed.next;
x.next=y;
y.prev=x;
N--;
if (current==lastAccessed)
current=y;
else
index--;
lastAccessed=null;
}
public void add(Item item)
{
Node x=current.prev;
Node y=new Node();
Node z= current;
y.item=item;
x.next=y;
y.next=z;
z.prev=y;
y.prev=x;
N++;
index++;
lastAccessed=null;
}
}
public String toString()
{
StringBuilder s=new StringBuilder();
for (Item item: this)
s.append(item+ " ");
return s.toString();
}
public static void main(String[]args)
{
int N=10;
System.out.println(N+ " random integers between 0 and 99");
DoublyLinkedList list=new DoublyLinkedList();
for(int i=0; i list.add((int)(Math.random()*100));
System.out.println(list);
System.out.println();
ListIteratoriterator=list.iterator();
System.out.println("add 1 to each element via next(0 and set()");
while (iterator.hasNext())
{
int x=iterator.next();
iterator.set(x+1);
}
System.out.println(list);
System.out.println();
System.out.println("multiply each element by 3 via previous() and set()");
while(iterator.hasPrevious())
{
int x=iterator.previous();
iterator.set(x+x+x);
}
System.out.println(list);
System.out.println();
System.out.println("remove elements that are a multiple of 4 via next(0 and remove()");
while(iterator.hasNext())
{
int x=iterator.next();
if(x%4==0) iterator.remove();
}
System.out.println(list);
System.out.println();
System.out.println("remove elements that are even via previous() and remove()");
while(iterator.hasPrevious())
{
int x=iterator.previous();
if(x%2==0) iterator.remove();
}
System.out.println(list);
System.out.println();
System.out.println("add elements via next() and add()");
while(iterator.hasNext())
{
int x=iterator.next();
iterator.add(x+1);
}
System.out.println(list);
System.out.println();
System.out.println("add elements via previous() and add()");
while(iterator.hasPrevious())
{
int x=iterator.previous();
iterator.add(x*10);
iterator.previous();
}
System.out.println(list);
System.out.println();
}
}
Explanation / Answer
/*
* Java Program to Implement Doubly Linked List
*/
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 insertAtStart(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 insertAtEnd(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)
{
insertAtStart(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++ ;
}
/* Function to delete node at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
if (size == 1)
{
start = null;
end = null;
size = 0;
return;
}
start = start.getLinkNext();
start.setLinkPrev(null);
size--;
return ;
}
if (pos == size)
{
end = end.getLinkPrev();
end.setLinkNext(null);
size-- ;
}
Node ptr = start.getLinkNext();
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node p = ptr.getLinkPrev();
Node n = ptr.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size-- ;
return;
}
ptr = ptr.getLinkNext();
}
}
/* Function to display status of list */
public void display()
{
System.out.print(" Doubly Linked List = ");
if (size == 0)
{
System.out.print("empty ");
return;
}
if (start.getLinkNext() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ " <-> ");
ptr = start.getLinkNext();
while (ptr.getLinkNext() != null)
{
System.out.print(ptr.getData()+ " <-> ");
ptr = ptr.getLinkNext();
}
System.out.print(ptr.getData()+ " ");
}
}
/* 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. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.insertAtEnd( 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 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position ");
else
list.deleteAtPos(p);
break;
case 5 :
System.out.println("Empty status = "+ list.isEmpty());
break;
case 6 :
System.out.println("Size = "+ list.getSize() +" ");
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display List */
list.display();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.