From the sample code below.Implement the following method in the SinglyLinkedLis

Question

From the sample code below.Implement the following method in the SinglyLinkedList class:

// PRECONDITION: a and b are sorted in ascending order and contain no duplicates
// Returns true if every element of list 'c' also appears in list 'a'

public boolean checkContainsAll(SinglyLinkedList<E> a, SinglyLinkedList<E> c)

Let n = a.size() and m = c.size(). Your implementation should be O(n + m). (Note that without the precondition, this method would have to be O(nm).

SAMPLE CODE:

public class SinglyLinkedList<E extends Comparable<? super E>>
{
private final Node head;
private Node tail;
private int size;

public SinglyLinkedList()
{
head = new Node(null, null);
tail = head;
}

public int size()
{
return size;
}

public boolean add(E item)
{
tail.next = new Node(item, null);
tail = tail.next;
++size;
return true;
}

public E get(int pos)
{
if (pos < 0 || pos >= size) throw new IndexOutOfBoundsException("" + pos);
Node n = findPredecessorByIndex(pos);
return n.next.data;
}

public boolean contains(Object obj)
{
Node current = head;
while (current.next != null)
{
Object data = current.next.data;
if (data == null)
{
// both null
if (obj == null) return true;
}
else
{
// check equality
if (data.equals(obj)) return true;
}
current = current.next;
}
return false;
}

public E remove(int pos)
{
if (pos < 0 || pos >= size) throw new IndexOutOfBoundsException("" + pos);
Node pred = findPredecessorByIndex(pos);
E ret = pred.next.data;
delete(pred);
return ret;
}

// deletes n.next
private void delete(Node n)
{
n.next = n.next.next;
--size;
}

// returns the Node at index pos - 1
private Node findPredecessorByIndex(int pos)
{
// inv: position of current is count
Node current = head;
int count = 0;
while (count < pos)
{
current = current.next;
++count;
}
return current;
}


/**
* Node type for this list.
*/
private class Node
{
public E data;
public Node next;

public Node(E pData, Node pNext)
{
data = pData;
next = pNext;
}
}

// PRECONDITION: a and b are sorted and contain no duplicates
// Returns true if every element of list 'c; also appears in list 'a'
public boolean checkContainsAll(SinglyLinkedList<E> a, SinglyLinkedList<E> c)
{
// TODO
return false;
}
}

Explanation / Answer

public static int[] intersectSortedArrays(int[] a, int[] b){ int[] c = new int[Math.min(a.length, b.length)]; int ai = 0, bi = 0, ci = 0; while (ai

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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