Question

Please solve this problem in java. (simple linked list)

public class MyLinkedList implements MiniList{
/* Private member variables that you need to declare:
** The head pointer
** The tail pointer
*/
   private Node head;
   private Node tail;
  

  
public class Node {
// declare member variables (data and next)
   Integer data;
   Node next;

// finish these constructors
   public Node(int data, Node next) {
      
       this.data=data;
       this.next=next;
   }
public Node(int data) {
   this.data = data;
   this.next = null;
} // HINT: use this() with next = null
}

// Initialize the linked list (set head and tail pointers)
public MyLinkedList() {
head = null;
tail = null;
}

@Override
public boolean add(Integer item) {
Node newNode = new Node(item);
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
return true;
}

@Override
public void add(int index, Integer element) {
   Node newNode = new Node(element);
if(index == 0) {

newNode.next = head;
head=newNode;
} else {
Node curr = head;
for(int i=0;i curr = curr.next;
}
if(curr.next!=null) {
  
newNode.next = curr.next;
curr.next = newNode;
  
} else {
tail.next = newNode;
  
tail = newNode;
}
}
}

@Override
public Integer remove() {
Node current = head;
Integer ele = null;
ele = head.data;
head = head.next;

return ele;
}

@Override
public Integer remove(int index) {
Node current = head;
Integer ele = null;
int count = 0;
if (head == null) {
return null;
}
while (current != null) {
if (index - 1 == count && current.next != null) {

ele = current.next.data;
if (current.next.next == null) {
// t.next = current.next;
tail = current;
}
current.next = current.next.next;
//current.next.next = null;
break;
}
current = current.next;
count++;
}
return ele;
}

@Override
public boolean remove(Integer item) {
Node current = head;

if (head == null) {
return false;
}
if (current.data == item) {
head = current.next;
return true;
}
while (current != null) {
if (current.next != null && current.next.data == item) {
if (current.next.next == null) {
// t.next = current.next;
tail = current;
}
current.next = current.next.next;
//current.next.next = null;
break;
}
current = current.next;
}
return true;
}

@Override
public void clear() {
head = null;
}

@Override
public boolean contains(Integer item) {

Node current = head;

if (head == null) {
return false;
}
while (current != null) {
if (current.data == item) {
return true;
}
current = current.next;
}
return false;
}

@Override
public Integer get(int index) {
Node current = head;
int count = 0;
if (head == null) {
return null;
}
while (current != null) {
if (index == count) {
return current.data;
}
current = current.next;
count++;

}
return null;
}

@Override
public int indexOf(Integer item) {
Node current = head;
int count = 0;
if (head == null) {
return -1;
}
while (current != null) {
if (current.data == item) {
return count;
}
current = current.next;
count++;
}
return -1;
}

@Override
public boolean isEmpty() {
if (head == null) {
return true;
}
return false;
}

@Override
public int size() {
Node current = head;
int count = 0;
if (head == null) {
return 0;
}
while (current != null) {
current = current.next;
count++;
}
return count;
}
  
// Uncomment when ready to test
@Override
public String toString() {
String ret = "";
Node curr = head;
while (curr != null) {
ret += curr.data + " ";
curr = curr.next;
}
return ret;
}

}
------------------------------------------------------------------------------------------------------------

public class LLTest {
public static void main(String args[]) {
MyLinkedList ll = new MyLinkedList();

// Testing add methods
System.out.println("Testing Add");
ll.add(40);
ll.add(10);
ll.add(20);
ll.add(1, 30);
ll.add(3, 100);
ll.add(65);
ll.add(2);
System.out.println("Expected: 40 30 10 100 20 65 2");
System.out.println("Actual: " + ll);
System.out.println();

// Testing remove methods
System.out.println("Testing Remove");
ll.remove();
ll.remove(2);
ll.remove(3);
ll.remove((Integer)2);
System.out.println("Expected: 30 10 20");
System.out.println("Actual: " + ll);
System.out.println("Size should be 3 -> " + ll.size());
System.out.println();

// Testing Contains
System.out.println("Testing Contains");
ll.add(2); // to make it a little bigger
System.out.println("Should be true -> " + ll.contains(2));
System.out.println("Should be false -> " + ll.contains(65));
System.out.println("Should be true -> " + ll.contains(30));
System.out.println();

// Testing Get
System.out.println("Testing Get");
System.out.println("Actual list: " + ll);
System.out.print("List using get: ");
for (int i = 0; i < ll.size(); i++) {
System.out.print(ll.get(i) + " ");
}
System.out.println("\n");

// Testing indexOf
System.out.println("Testing indexOf");
System.out.println("Should be 2 -> " + ll.indexOf(20));
System.out.println("Should be 3 -> " + ll.indexOf(2));
System.out.println("Should be -1 -> " + ll.indexOf(65));

// You can write more tests (these are not all encompassing)
// When should these methods fail/throw exceptions?
// Have all of the edge cases been tested?
// Not quite all of the methods have been tested here (e.g. clear())

}
}
------------------------------------------------------------------------------------------------------------

public interface MiniList {
public boolean add(E item);
public void add(int index, E element);

public E remove();
public E remove(int index);
public boolean remove(E item);

public void clear();

public boolean contains(E item);

public boolean equals(Object o);

public E get(int index);
public int indexOf(E item);

public boolean isEmpty();

public int size();
}

Answer 1

Working code implemented in Java and appropriate comments provided for better understanding.

Here I am attaching code for all files:

MyLinkedList.java:

public class MyLinkedList implements MiniList<Integer>{
/* Private member variables that you need to declare:
** The head pointer
** The tail pointer
*/
   Node m_pHead;
   Node m_pTail;
   int m_iSize;

public class Node {
// declare member variables (data and next)
   int data;
   Node pNext;

// finish these constructors
public Node(int data, Node pNext) {
   this.data = data;
   this.pNext = pNext;
}
public Node(int data) {
   this.data = data;
   this.pNext = null;
} // HINT: use this() with next = null
}

// Initialize the linked list (set head and tail pointers)
public MyLinkedList() {
   m_pHead = null;
   m_pTail = null;
   m_iSize = 0;
}

@Override
public boolean add(Integer item) {
   Node newNode = new Node(item);
  
   if (null == m_pHead)
       m_pHead = newNode;
   else
       m_pTail.pNext = newNode;
      
m_pTail = newNode;
  
m_iSize++;
return true;
}

@Override
public void add(int index, Integer element) {
   Node pCur = m_pHead;
   Node newNode = new Node(element);
  
   if (index == 0) {
       newNode.pNext = pCur.pNext;
       pCur.pNext = null;
       m_pHead = newNode;
   }
  
   for (int i = 1; i < index; i++) {
       pCur = pCur.pNext;
   }
  
   newNode.pNext = pCur.pNext;
   pCur.pNext = newNode;
  
   m_iSize++;
}

@Override
public Integer remove() {
Node pCur = m_pHead;
m_pHead = pCur.pNext;
pCur.pNext = null;
  
m_iSize--;
return pCur.data;
}

@Override
public Integer remove(int index) {
   Node pPrev = m_pHead;
   Node pCur = m_pHead.pNext;
  
   if (null == m_pHead)
       return null;
   // head case
   else if (index == 0) {
   m_pHead = m_pHead.pNext;
   pPrev.pNext = null;
  
   m_iSize--;
   return pCur.data;
}
  
   // inside case
if (index > 0 && index < m_iSize - 1) {
   for (int i = 1; i < index; i++) {
       pPrev = pCur;
       pCur = pCur.pNext;
   }
  
   pPrev.pNext = pCur.pNext;
   pCur.pNext = null;
  
   m_iSize--;
   return pCur.data;
}
  
// tail case
if (index == m_iSize - 1) {
   pPrev.pNext = null;
  
   m_iSize--;
   return pCur.data;
}
  
return null;
}

@Override
public boolean remove(Integer item) {
   Node pPrev = m_pHead;
Node pCur = m_pHead.pNext;
  
if (m_pHead.data == item) {
   m_pHead = m_pHead.pNext;
   pPrev.pNext = null;
   m_iSize--;
   return true;
}
  
while (null != pCur) {
   if (pCur.data == item) {
       pPrev.pNext = pCur.pNext;
       pCur.pNext = null;
      
if (null == pPrev.pNext)
   m_pTail = pPrev;

       m_iSize--;
       return true;
   }

   pPrev = pCur;
   pCur = pCur.pNext;
}
  
return false;
}

@Override
public void clear() {
   m_pHead = null;
   m_pTail = null;
}

@Override
public boolean contains(Integer item) {
Node pCur = m_pHead;
  
while (null != pCur) {
   if (pCur.data == item) {
       return true;
   }
  
   pCur = pCur.pNext;
}
  
return false;
}

@Override
public Integer get(int index) {
   Node pCur = m_pHead;
  
if (index < 0 || index >= m_iSize)
   return null;
  
for (int i = 0; i < index; i++)
   pCur = pCur.pNext;
  
return pCur.data;
}

@Override
public int indexOf(Integer item) {
Node pCur = m_pHead;
int index = 0;
  
while (null != pCur.pNext) {
   if (pCur.data == item) {
       return index;
   }
  
   index++;
   pCur = pCur.pNext;
}
  
return (pCur.data == item) ? index : -1;
}

@Override
public boolean isEmpty() {
   return (m_pHead == null) ? true : false;
}

@Override
public int size() {
return m_iSize;
}

// Uncomment when ready to test
@Override
public String toString() {
String ret = "";
Node curr = m_pHead;
while (curr != null) {
ret += curr.data + " ";
curr = curr.pNext;
}
return ret;
}

}

MiniList.java:

public interface MiniList<E> {
public boolean add(E item);
public void add(int index, E element);

public E remove();
public E remove(int index);
public boolean remove(E item);

public void clear();

public boolean contains(E item);

public boolean equals(Object o);

public E get(int index);
public int indexOf(E item);

public boolean isEmpty();

public int size();
}

LLTest.java:

public class LLTest {
public static void main(String args[]) {
MyLinkedList ll = new MyLinkedList();

// Testing add methods
System.out.println("Testing Add");
ll.add(40);
ll.add(10);
ll.add(20);
ll.add(1, 30);
ll.add(3, 100);
ll.add(65);
ll.add(2);
System.out.println("Expected: 40 30 10 100 20 65 2");
System.out.println("Actual: " + ll);
System.out.println("Size should be 7 -> " + ll.size());
System.out.println();

// Testing remove methods
System.out.println("Testing Remove");
ll.remove();
ll.remove(2);
ll.remove(3);
ll.remove((Integer)2);
ll.remove(100);
System.out.println("Expected: 30 10 20");
System.out.println("Actual: " + ll);
System.out.println("Size should be 3 -> " + ll.size());
System.out.println();

// Testing Contains
System.out.println("Testing Contains");
ll.add(2); // to make it a little bigger
System.out.println("Should be true -> " + ll.contains(2));
System.out.println("Should be false -> " + ll.contains(65));
System.out.println("Should be true -> " + ll.contains(30));
System.out.println();

// Testing Get
System.out.println("Testing Get");
System.out.println("Actual list: " + ll);
System.out.print("List using get: ");
for (int i = 0; i < ll.size(); i++) {
System.out.print(ll.get(i) + " ");
}
System.out.println("\n");

// Testing indexOf
System.out.println("Testing indexOf");
System.out.println("Should be 2 -> " + ll.indexOf(20));
System.out.println("Should be 3 -> " + ll.indexOf(2));
System.out.println("Should be -1 -> " + ll.indexOf(65));
System.out.println();
  
// You can write more tests (these are not all encompassing)
// When should these methods fail/throw exceptions?
// Have all of the edge cases been tested?
// Not quite all of the methods have been tested here (e.g. clear())
  
System.out.println("Testing isEmpty and clear.");
System.out.println("Should be false -> " + ll.isEmpty());
ll.clear();
System.out.println("Should be true -> " + ll.isEmpty());
}
}

Sample Output Screenshots: