public class DoublyLinkedList {

private Node head = null;

private Node tail = null;

private int size = 0;

private class Node {

private Object data;

private Node next;

private Node prev;

private Node(Object input) {

this.data = input;

this.next = null;

this.prev = null;

}// Node.constructor

}// class Node

public Node node(int k) {

Node x = head;

for (int i = 0; i < k; i++) {

x = x.next;

}

return x;

}// DoublyLinkedList.node

public void addFirst(Object input) {

Node newNode = new Node(input);

if (head == null) {

head = newNode;

tail = head;

} else {

newNode.next = head;

head.prev = newNode;

head = newNode;

}

size++;

System.out.print(input + " is added as the first element. ");

print();

}// DoublyLinkedList.addFirst

public void addLast(Object input) {

Node newNode = new Node(input);

if (tail == null) {

tail = newNode;

head = tail;

} else {

tail.next = newNode;

newNode.prev = tail;

tail = newNode;

}

size++;

System.out.print(input + " is added as the last element. ");

print();

}// DoublyLinkedList.addLast

public void add(int k, Object input) {

if (k == 0) {

addFirst(input);

} else if (k == size) {

addLast(input);

} else {

Node newNode = new Node(input);

Node x = node(k - 1);

newNode.next = x.next;

newNode.prev = x;

x.next.prev = newNode;

x.next = newNode;

size++;

System.out.print(input + " is added in the list. ");

print();

}

}// DoublyLinkedList.add

public Object removeFirst() {

if (head == null) {

System.out.print("this list is empty. you cannot remove anymore. ");

print();

return null;

} else if (head == tail) {

Object removedData = head.data;

head = null;

tail = null;

System.out.print(removedData + " is removed from the list. ");

size--;

print();

return null;

} else {

Object removedData = head.data;

head.next.prev = null;

head = head.next;

head.prev = null;

System.out.print(removedData + " is removed from the list. ");

size--;

print();

return removedData;

}

}// DoublyLinkedList.removeFirst

public Object removeLast() {

if (tail == null) {

System.out.print("this list is empty. you cannot remove anymore. ");

print();

return null;

} else if (head == tail) {

Object removedData = tail.data;

head = null;

tail = null;

System.out.print(removedData + " is removed from the list. ");

size--;

print();

return null;

} else {

Object removedData = tail.data;

tail.prev.next = null;

tail = tail.prev;

System.out.print(removedData + " is removed from the list. ");

size--;

print();

return removedData;

}

}// DoublyLinkedList.removeLast

public Object remove(int k) {

Node x = node(k);

Object removedData = x.data;

if( k == 0)

removeFirst();

else if (k == size-1 )

removeLast();

else {

x.prev.next = x.next;

x.next.prev = x.prev;

System.out.print(removedData + " is removed from the list. ");

size--;

print();

}

return removedData;

}// DoublyLinkedList.remove

public void print() {

if (head != null) {

System.out.print("list = [ ");

Node x = head;

while (true) {

System.out.print(x.data);

if (x == tail)

break;

else

System.out.print(", ");

x = x.next;

}

System.out.print(" ]");

System.out.print(System.lineSeparator());

} else {

System.out.print("list is now empty.");

}

}// DoublyLinkedList.print

public int size() {

return size;

}// DoublyLinkedList.size

public Object get(int k) {

Object x = node(k).data;

return x;

}// DoublyLinkedList.get

public int indexOf(Object data) {

Node x = head;

for(int i = 0; i < size; i++) {

if(x.data == data) 

return i;

x = x.next;

}

return -1;

}// DoublyLinkedList.indexOf

}// class DoublyLInkedList