implement lazy deletion on the doubled linked list (make sure the remove() method performs lazy deletion, and that all other methods honor the deleted nodes correctly, include the process for actually deleting items after half the items in the structure are considered deleted)

public class MyDoubleLinkedList {

private MyNode start, end;

private int size;

public MyDoubleLinkedList()

{

start = null;

size = 0;

}

public String printList()

{

MyNode current = start;

String output = "[";

while(current != null)

{

output += current.toString() + ", ";

current = current.next;

}

output += "]";

return output;

}

public String printListRev()

{

MyNode current = end;

String output = "[";

while(current != null)

{

output += current.toString() + ", ";

current = current.prev;

}

output += "]";

return output;

}

public void insert(E obj, int index)

{

MyNode temp = new MyNode(obj);

if(index <= 0 || size == 0)//insert at start

{

if(start == null)

{

start = temp;

end = temp;

}

else

{

temp.next = start;

start.prev = temp;

start = temp;

}

}

else if(index >= size)//end

{

temp.prev = end;

end.next = temp;

end = temp;

}

else//middle

{

if(index > size)

index = size;

MyNode current = start;

for(int i = 1; i < index; i++)

{

current = current.next;

}

temp.next = current.next;//rest of list comes after new value

temp.prev = current;

current.next = temp;//new value is after current

temp.next.prev = temp;

}

size++;

}

public void add(E obj)

{

insert(obj, size);

}

/*

* Test edge cases:

* 0 -> 1 -> 2 -> 3

* delete 1 (middle)

* 0 -> 2 -> 3

* delete 0 (begin)

* 2 -> 3

* delete 3 (end)

* 2

*/

public E remove(E obj)

{

if(start == null)//prevent runtime error on empty list

return null;

if(obj.equals(start.data))//first item needs to be deleted

{

E temp = start.data;

start = start.next;

if(start != null)

{

start.prev = null;

}

size--;

return temp;

}

else

{

MyNode current = start;

while(current.next != null && !current.next.data.equals(obj))

{

current = current.next;

}

if(current.next != null)

{

E temp = current.next.data;

current.next = current.next.next;

if(current.next != null)

{

current.next.prev = current;

}

else

{

end = current;

}

size--;

return temp;

}

else//end of list, did not find value to delete

return null;

}

}

public E delete(int index)

{

if(index < 0 || index >= size)

return null;

else

{

if(index == 0)//start

{

E temp = start.data;

start = start.next;

if(start != null)

{

start.prev = null;

}

else//if last item removed, list is now empty

{

end = null;

}

size--;

return temp;

}

else if(index == size-1)//end

{

E temp = end.data;

end = end.prev;

if(end != null)

{

end.next = null;

}

size--;

return temp;

}

else//middle

{

MyNode current = start;

for(int i = 1; i < index; i++)

current = current.next;

E temp = current.next.data;

current.next = current.next.next;

current.next.prev = current;

size--;

return temp;

}

}

}

public E find(E obj)

{

if(start == null)//prevent runtime error on empty list

return null;

if(obj.equals(start.data))//first item needs to be deleted

{

return start.data;

}

else

{

MyNode current = start;

while(current.next != null && !current.next.data.equals(obj))

{

current = current.next;

}

if(current.next != null)

{

return current.next.data;

}

else//end of list, did not find value to delete

return null;

}

}

public E findLast(E obj)

{

if(start == null)//prevent runtime error on empty list

return null;

if(obj.equals(end.data))//first item needs to be deleted

{

return end.data;

}

else

{

MyNode current = end;

while(current.prev != null && !current.prev.data.equals(obj))

{

current = current.prev;

}

if(current.prev != null)

{

return current.prev.data;

}

else//end of list, did not find value to delete

return null;

}

}

public E get(int index)

{

if(index < 0 || index >= size)

return null;

else

{

if(index == 0)

{

return start.data;

}

else

{

MyNode current = start;

for(int i = 1; i < index; i++)

current = current.next;

return current.next.data;

}

}

}

private class MyNode

{

MyNode next = null;

MyNode prev = null;

E data = null;

public MyNode(E obj)

{

next = null;

prev = null;

data = obj;

}

public String toString()

{

return data.toString();

}

@Override

public boolean equals(Object obj) {

if (this == obj)

return true;

if (obj == null)

return false;

if (getClass() != obj.getClass())

return false;

MyNode other = (MyNode) obj;

return data.equals(other.data);

}

}

}