Homework Soursejava Describe the algorithm to search for an item with given
java
Describe the algorithm to search for an item with given key, in a has table that uses open addressing with double hashing. Consider a class My List Implementation that keeps a doubly linked list with header and trailer sentinel nodes (referenced by instance variables of the list implementation called header and trailer). Assume that the Node class has the usual getter and setter methods. Suppose n is a Node within the list (not one of the sentinels). Write the sequence of Java statements that would be used within My List implementation, in order to remove the Node n from the list. [You can use assignments to instance variables and you can call methods of the Node class, but do not call methods of the List ADT itself.]Solution
import java.util.Scanner;
class LinearSearch
{
public static void main(String args[])
{
int c, n, search, array[];
Scanner in = new Scanner(System.in);
System.out.println(\"Enter number of elements\");
n = in.nextInt();
array = new int[n];
System.out.println(\"Enter \" + n + \" integers\");
for (c = 0; c < n; c++)
array[c] = in.nextInt();
System.out.println(\"Enter value to find\");
search = in.nextInt();
for (c = 0; c < n; c++)
{
if (array[c] == search) /* Searching element is present */
{
System.out.println(search + \" is present at location \" + (c + 1) + \".\");
break;
}
}
if (c == n) /* Searching element is absent */
System.out.println(search + \" is not present in array.\");
}
}
2)
import java.util.Scanner;
class Node
{
protected int data;
protected Node next, prev;
public Node()
{
next = null;
prev = null;
data = 0;
}
public Node(int d, Node n, Node p)
{
data = d;
next = n;
prev = p;
}
public void setLinkNext(Node n)
{
next = n;
}
public void setLinkPrev(Node p)
{
prev = p;
}
public Node getLinkNext()
{
return next;
}
public Node getLinkPrev()
{
return prev;
}
public void setData(int d)
{
data = d;
}
public int getData()
{
return data;
}
}
class linkedList
{
protected Node start;
protected Node end ;
public int size;
public linkedList()
{
start = null;
end = null;
size = 0;
}
public boolean isEmpty()
{
return start == null;
}
public int getSize()
{
return size;
}
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++;
}
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++;
}
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++ ;
}
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();
}
}
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()+ \"\ \");
}
}
public class DoublyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
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;
}
list.display();
System.out.println(\"\ Do you want to continue (Type y or n) \ \");
ch = scan.next().charAt(0);
} while (ch == \'Y\'|| ch == \'y\');
}
}
