/**
* 自定義簡易雙向鏈表
*/
public class CustomizeLinkedList<E> {
? ?private class Node<E>{
? ? ? ?Node<E> prev;
? ? ? ?E item;
? ? ? ?Node<E> next;

? ? ? ?public Node(Node<E> prev, E item, Node<E> next) {
? ? ? ? ? ?this.prev = prev;
? ? ? ? ? ?this.item = item;
? ? ? ? ? ?this.next = next;
? ? ? ?}
? ?}
? ?private int size;
? ?Node<E> first;
? ?Node<E> last;

? ?public int size(){
? ? ? ?return size;
? ?}
? ?public boolean add(E e){
? ? ? ?linkLast(e);
? ? ? ?return true;
? ?}
? ?private void linkLast(E e){
? ? ? ?Node<E> n = new Node<>(last,e,null);
? ? ? ?if (isEmpty()){
? ? ? ? ? ?first = n;
? ? ? ?}else {
? ? ? ? ? ?last.next = n;
? ? ? ?}
? ? ? ?last = n;
? ? ? ?size++;
? ?}
? ?public boolean isEmpty(){
? ? ? ?return size==0;
? ?}
? ?public E remove(int index){
? ? ? ?checkIndex(index);
? ? ? ?Node<E> n = getNode(index);
? ? ? ?Node<E> pr = n.prev;
? ? ? ?Node<E> ne = n.next;
? ? ? ?if (pr == null){
? ? ? ? ? ?first = ne;
? ? ? ?}else {
? ? ? ? ? ?pr.next = ne;
? ? ? ?}
? ? ? ?if (ne == null){
? ? ? ? ? ?last = pr;
? ? ? ?}else {
? ? ? ? ? ?ne.prev = pr;
? ? ? ?}
? ? ? ?E e = n.item;
? ? ? ?n.prev = null;
? ? ? ?n.next = null;
? ? ? ?n.item = null;
? ? ? ?size--;
? ? ? ?return e;
? ?}
? ?private void checkIndex(int index){
? ? ? ?if (index<0||index>=size)throw new IndexOutOfBoundsException();
? ?}
? ?private Node<E> getNode(int index){
? ? ? ?Node<E> n;
? ? ? ?if (index < size>>1){
? ? ? ? ? ?n = first;
? ? ? ? ? ?for (int i = 0;i<index;i++){
? ? ? ? ? ? ? ?n = n.next;
? ? ? ? ? ?}
? ? ? ?}else {
? ? ? ? ? ?n = last;
? ? ? ? ? ?for (int i = size-1;i>index;i--){
? ? ? ? ? ? ? ?n = n.prev;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return n;
? ?}
? ?public E set(int index,E e){
? ? ? ?checkIndex(index);
? ? ? ?Node<E> n = getNode(index);
? ? ? ?E oldE = n.item;
? ? ? ?n.item = e;
? ? ? ?return oldE;
? ?}
? ?public E get(int index){
? ? ? ?checkIndex(index);
? ? ? ?return getNode(index).item;
? ?}
? ?public void addFirst(E e){
? ? ? ?Node<E> n = new Node<>(null,e,first);
? ? ? ?if (isEmpty()){
? ? ? ? ? ?last = n;
? ? ? ?}else {
? ? ? ? ? ?first.prev = n;
? ? ? ?}
? ? ? ?first = n;
? ? ? ?size++;
? ?}
? ?public void addLast(E e){
? ? ? ?linkLast(e);
? ?}

? ?public static void main(String[] args) {
? ? ? ?CustomizeLinkedList<String> ll1 = new CustomizeLinkedList<>();
? ? ? ?//測試略
? ?}
}