Write a \"contains\" method for the LinkedList class that searches for a given i

Question

Write a "contains" method for the LinkedList class that searches for a given item by sequentially searching from both ends of the list, alternately stepping from each end, one item at a time, toward the middle of the list. The signature for your method must be:public boolean contains(Object obj). Your implementation must consist of only this method -- do not write any helper methods.

private ListNode getNode(int index)
{
    ListNode p;

    if(index < theSize / 2)
    {
        p = head.next;
  
        for(int i = 0; i < index; i++)
        {
            p = p.next;
        }
    }
    else
    {
        p = tail;
  
        for(int i = theSize; i > index; i--)
        {
            p = p.previous;
        }
    }

    return p;
}

ListNode p;

if(index < theSize / 2)

p = head.next;

int i = 0;

i < index;

i++

p = p.next;

p = tail;

int i = theSize;

i > index;

i--

= p.previous;

return p;

O(0)

O(1)

O(N/2)

O(N/2 - 1)

O(N/2 + 1)

O(N)

O(N + 1)

O(N - 1)

if(index < theSize / 2)

Explanation / Answer

PROGRAM:

import java.io.*;
import java.util.*;
class SubLinkedList extends LinkedList
{
public boolean contains(Object obj)
{
String item=obj.toString();
int i=0,j;
j=this.size();
while(i<j)
{
if(i%2==0)
{
if(this.get(i).toString().equalsIgnoreCase(item))
{
System.out.println(item+" Found at: "+i);
return true;
}
i++;
}
else
{
j--;
if(this.get(j).toString().equalsIgnoreCase(item))
{ System.out.println(item+" Found at: "+j);
return true;
}

}
  
}
return false;
}

}
public class TestLinkedList {
public static void main(String args[]) {
int select=1;
String item;
// create a linked list
SubLinkedList ll = new SubLinkedList();
Scanner scan=new Scanner(System.in);
// add elements to the linked list
while(select==1){
System.out.println("Enter element to add Linked List");
item=scan.next();
ll.add(item);
  
System.out.println("Enter 1 to continue");
select=scan.nextInt();
  
}
/*ll.add("F");
ll.add("B");
ll.add("D");
ll.add("E");
ll.add("C");
ll.addLast("Z");
ll.addFirst("A");
ll.add(1, "A2");*/
select=1;
System.out.println("Original contents of Linked List: " + ll);
while(select==1)
{
System.out.println("Enter searching Element");
item=scan.next();
System.out.println("Element "+item+" is found:"+ll.contains(item));
System.out.println("Enter 1 to continue");
select=scan.nextInt();
}
}
}

OUTPUT:

run:
Enter element to add Linked List
DURGA
Enter 1 to continue
1
Enter element to add Linked List
RAO
Enter 1 to continue
1
Enter element to add Linked List
RAM
Enter 1 to continue
1
Enter element to add Linked List
KRISH
Enter 1 to continue
0
Original contents of Linked List: [DURGA, RAO, RAM, KRISH]
Enter searching Element
RAM
RAM Found at: 2
Element RAM is found:true
Enter 1 to continue
1
Enter searching Element
DURGA
DURGA Found at: 0
Element DURGA is found:true
Enter 1 to continue
1
Enter searching Element
KRISHNA
Element KRISHNA is found:false
Enter 1 to continue
0
BUILD SUCCESSFUL (total time: 2 minutes 18 seconds)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.