JAVA (I use Eclipse): Implement the search(int k), insert(int x), delete() funct
ID: 3589861 • Letter: J
Question
JAVA (I use Eclipse):
Implement the search(int k), insert(int x), delete() function in LinkedList.java.
I already have Stack.java and Queue.java completed. I included the code for reference.
Please do not modify the original code. Only include additional missing code in the provided structure. Please make sure the program works.
-----------------------------------
Below are the prepared codes to fill in:
package ds;
public class Stack {
public int size;
public int top;
public int[] array;
public Stack () {
size = 0;
top = -1;
array = null;
}
public Stack (int _size) {
size = _size;
top = -1;
array = new int[size];
}
/*
* Implement the Stack-Empty(S) function
*/
public boolean empty () {
return top == -1;
}
/*
* Implement the Push(S, x) function
*/
public void push (int x) {
if(top < size-1){
top++;
array[top] = x;
}
}
/*
* Implement the Pop(S) function
* Return -1 if the stack is empty
*/
public int pop () {
if(empty())
return -1;
int x = array[top];
top--;
return x;
}
/*
* Convert stack to string in the format of #size, [#elements]
*/
public String toString () {
String str;
str = size + ", [";
for (int i = 0; i <= top; i++)
str += array[i] + ", ";
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack s;
s = new Stack(10);
for (int i = 0; i < 5; i++)
s.push(i);
System.out.println(s.toString());
for (int i = 0; i < 2; i++)
s.pop();
System.out.println(s.toString());
}
}
-----------------------------------
package ds;
public class Queue {
public int size;
public int[] array;
public int head;
public int tail;
public Queue () {
size = 0;
array = null;
head = -1;
tail = 0;
}
public Queue (int _size) {
size = _size;
array = new int[size];
head = 0;
tail = 0;
}
/*
* Implement the ENQUEUE(Q, x) function
*/
public void enqueue (int x) {
if(array.length==0)
return;
if(head==0 && tail==array.length){
System.out.println("Queue Overflow");
return;
}
array[tail++]=x;
}
/*
* Implement the DEQUEUE(Q) function
*/
public int dequeue () {
if(head<0 || head>tail){
System.out.println("Queue is empty");
return 0;
}
return array[head++];
}
/*
* Convert queue to string in the format of #size, head, tail, [#elements]
*/
public String toString () {
String str;
str = size + ", " + head + ", " + tail + ", [";
for (int i = head+1; i%size < tail; i++)
str += array[i] + ",";
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Queue q;
q = new Queue(10);
for (int i = 0; i < 5; i++)
q.enqueue(i);
System.out.println(q.toString());
for (int i = 0; i < 2; i++)
q.dequeue();
System.out.println(q.toString());
}
}
-------------------------------------------------
package ds;
public class LinkedList {
public ListNode head;
public LinkedList () {
head = null;
}
/*
* Implement the LIST-SEARCH(L, k) function
*/
public ListNode search (int k) {
}
/*
* Implement the LIST-INSERT(L, x) function
* Note that x is a integer value, not a ListNode
*/
public void insert (int x) {
}
/*
* Implement the LIST-DELETE(L, x) function
*/
public void delete (ListNode x) {
}
/*
* Convert a LinkedList to a string in the format of [#elements]
*/
public String toString () {
String str;
ListNode n;
str = "[";
n = this.head;
while (n != null) {
str += n.key + ",";
n = n.next;
}
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList l;
l = new LinkedList();
for (int i = 0; i < 5; i++)
l.insert(i);
System.out.println(l.toString());
for (int i = 0; i < 2; i++)
l.delete(l.head.next);
System.out.println(l.toString());
}
}
-----------------------------------------------------
package ds;
public class ListNode {
public int key;
public ListNode prev;
public ListNode next;
public ListNode () {
prev = next = null;
}
public ListNode (int _key) {
key = _key;
prev = next = null;
}
}
Explanation / Answer
/**
where required i added comment and i checked missing functions are now completed and works properly.
*/
package ds;
public class Stack {
public int size;
public int top;
public int[] array;
public Stack () {
size = 0;
top = -1;
array = null;
}
public Stack (int _size) {
size = _size;
top = -1;
array = new int[size];
}
/*
* Implement the Stack-Empty(S) function
*/
public boolean empty () {
return top == -1;
}
/*
* Implement the Push(S, x) function
*/
public void push (int x) {
if(top < size-1){
top++;
array[top] = x;
}
}
/*
* Implement the Pop(S) function
* Return -1 if the stack is empty
*/
public int pop () {
if(empty())
return -1;
int x = array[top];
top--;
return x;
}
/*
* Convert stack to string in the format of #size, [#elements]
*/
public String toString () {
String str;
str = size + ", [";
for (int i = 0; i <= top; i++)
str += array[i] + ", ";
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack s;
s = new Stack(10);
for (int i = 0; i < 5; i++)
s.push(i);
System.out.println(s.toString());
for (int i = 0; i < 2; i++)
s.pop();
System.out.println(s.toString());
}
}
-----------------------------------
package ds;
public class Queue {
public int size;
public int[] array;
public int head;
public int tail;
public Queue () {
size = 0;
array = null;
head = -1;
tail = 0;
}
public Queue (int _size) {
size = _size;
array = new int[size];
head = 0;
tail = 0;
}
/*
* Implement the ENQUEUE(Q, x) function
*/
public void enqueue (int x) {
if(array.length==0)
return;
if(head==0 && tail==array.length){
System.out.println("Queue Overflow");
return;
}
array[tail++]=x;
}
/*
* Implement the DEQUEUE(Q) function
*/
public int dequeue () {
if(head<0 || head>tail){
System.out.println("Queue is empty");
return 0;
}
return array[head++];
}
/*
* Convert queue to string in the format of #size, head, tail, [#elements]
*/
public String toString () {
String str;
str = size + ", " + head + ", " + tail + ", [";
for (int i = head+1; i%size < tail; i++)
str += array[i] + ",";
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Queue q;
q = new Queue(10);
for (int i = 0; i < 5; i++)
q.enqueue(i);
System.out.println(q.toString());
for (int i = 0; i < 2; i++)
q.dequeue();
System.out.println(q.toString());
}
}
-------------------------------------------------
package ds;
public class LinkedList {
public ListNode head;
public LinkedList () {
head = null;
}
/*
* Implement the LIST-SEARCH(L, k) function
*/
public ListNode search (int k) {
ListNode temp=head;
//return first ListNode from the head which key value is x
while(temp!=null)
{
if(temp.key==k)
{
return temp;
}
temp=temp.next;
}
return null; //key k not found in link list
}
/*
* Implement the LIST-INSERT(L, x) function
* Note that x is a integer value, not a ListNode
*/
public void insert (int x) {
ListNode temp=new ListNode (x);
// insert node at front of link list
if(head==null)
{
head=temp;
}
else{
head.prev=temp;
temp.next=head;
head=temp;
}
}
/*
* Implement the LIST-DELETE(L, x) function
*/
public void delete (ListNode x) {
ListNode temp =head;
while(temp!=x)
{
temp=temp.next;
}
if(temp!=null) //ListNode x is present so now delete this node
{
if(temp==head)
{
head=head.next;
if(head!=null)
{
head.prev=null;
}
}else{
ListNode before=temp.prev;
ListNode after=temp.next;
if(before!=null)
{
before.next=after;
}
if(after!=null)
{
after.prev=before;
}
}
}
}
/*
* Convert a LinkedList to a string in the format of [#elements]
*/
public String toString () {
String str;
ListNode n;
str = "[";
n = this.head;
while (n != null) {
str += n.key + ",";
n = n.next;
}
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList l;
l = new LinkedList();
for (int i = 0; i < 5; i++)
l.insert(i);
System.out.println(l.toString());
for (int i = 0; i < 2; i++)
l.delete(l.head.next);
System.out.println(l.toString());
}
}
-----------------------------------------------------
package ds;
public class ListNode {
public int key;
public ListNode prev;
public ListNode next;
public ListNode () {
prev = next = null;
}
public ListNode (int _key) {
key = _key;
prev = next = null;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.