/**
* 自定义简易双向 链表
*/
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 IndexOutOfBounds Exception ();
}
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<>();
//测试略
}
}