import java.util.NoSuchElementException;
public class DLL {
private class Cell {
private Integer value;
private Cell next;
private Cell prev;
private Cell begin;
private Cell end;
public Cell(Integer value) {
this.value = value;
next = null;
prev = null;
begin = null;
end = null;
}
public void setBegin(Cell begin) {
this.begin = begin;
}
public void setEnd(Cell end) {
this.end = end;
}
public Integer getValue() {
return value;
}
public Cell getNext() {
return next;
}
public Cell getPrev() {
return prev;
}
public void setValue(Integer value) {
this.value = value;
}
public void setNext(Cell next) {
this.next = next;
}
public void setPrev(Cell prev) {
this.prev = prev;
}
}
private Cell begin;
private Cell end;
private int size;
public DLL() {
begin = null;
end = null;
size = 0;
}
private Cell getCell(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
} else if (isEmpty()) {
throw new NoSuchElementException();
}
Cell cell = begin;
int s = 0;
while (s < index) {
cell = cell.getNext();
s++;
}
return cell;
}
public void add(int value) {
if (isEmpty()) {
Cell newCell = new Cell(value);
begin = newCell;
end = newCell;
newCell.setBegin(newCell);
newCell.setEnd(newCell);
} else {
Cell newCell = new Cell(value);
end.setNext(newCell);
newCell.setPrev(end);
end.setBegin(null);
end = newCell;
newCell.setBegin(begin);
begin.setEnd(newCell);
}
size++;
}
public int get(int index) {
return getCell(index).getValue();
}
public int indexOf(int value) {
int ans = -1;
Cell cell = begin;
int index = 0;
while (cell != null) {
if (cell.getValue() == value) {
ans = index;
break;
}
cell = cell.getNext();
index++;
}
return ans;
}
public boolean isEmpty() {
return size == 0;
}
public int remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
int ans;
Cell cell = getCell(index);
ans = cell.getValue();
Cell prev = cell.getPrev();
Cell next = cell.getNext();
prev.setNext(next);
next.setPrev(prev);
size--;
return ans;
}
public void set(int index, int value) {
Cell cell = getCell(index);
cell.setValue(value);
}
}