public class LinkedList<E> implements List<E>{

transient int size = 0;

transient Node<E> first;

transient Node<E> last;

public LinkedList() {

}

public E get(int index) {

return node(index).item;

}

//@TODO BASE로

public ListIterator<E> listIterator() {

return listIterator(0);

}

public ListIterator<E> listIterator(int index) {

return new ListItr(index);

}

public int size(){

return size;

}

public boolean isEmpty(){

return size == 0;

}

public boolean add(E e){

linkLast(e);

return true;

}

public boolean remove(Object o){

if (o == null) {

for (Node<E> x = first; x != null; x = x.next) {

if (x.item == null) {

unlink(x);

return true;

}

}

} else {

for (Node<E> x = first; x != null; x = x.next) {

if (o.equals(x.item)) {

unlink(x);

return true;

}

}

}

return false;

}

private void linkFirst(E e) {

final Node<E> f = first;

final Node<E> newNode = new Node<>(null, e, f);

first = newNode;

if (f == null)

last = newNode;

else

f.prev = newNode;

size++;

}

void linkLast(E e){

final Node<E> l = last;

final Node<E> newNode = new Node<>(l, e, null);

last = newNode;

if (l == null)

first = newNode;

else

l.next = newNode;

size++;

}

E unlink(Node<E> x) {

// assert x != null;

final E element = x.item;

final Node<E> next = x.next;

final Node<E> prev = x.prev;

if (prev == null) {

first = next;

} else {

prev.next = next;

x.prev = null;

}

if (next == null) {

last = prev;

} else {

next.prev = prev;

x.next = null;

}

x.item = null;

size--;

return element;

}

Node<E> node(int index) {

if (index < (size >> 1)) {

Node<E> x = first;

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

x = x.next;

return x;

} else {

Node<E> x = last;

for (int i = size - 1; i > index; i--)

x = x.prev;

return x;

}

}

//@TODO BASE로 변경

public Iterator<E> iterator() {

return new ListItr(0);

}

// 외부에서는 접근 불가능한 InnerClass

// static Inner class 안에는 static variable 선언 가능함

private static class Node<E> {

E item;

Node<E> next;

Node<E> prev;

Node(Node<E> prev, E element, Node<E> next){

this.prev = prev;

this.item = element;

this.next = next;

}

}

private class ListItr implements ListIterator<E> {

private Node<E> lastReturned = null;

private Node<E> next;

private int nextIndex;

ListItr(int index) {

next = (index == size) ? null : node(index);

nextIndex = index;

}

public boolean hasNext() {

return nextIndex < size;

}

public E next() {

if (!hasNext())

{

}

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.item;

}

public void remove() {

if (lastReturned == null)

{

}

Node<E> lastNext = lastReturned.next;

unlink(lastReturned);

if (next == lastReturned)

next = lastNext;

else

nextIndex--;

lastReturned = null;

}

}

}