/**
* Description 双向链表
* Date 2017-09-03
* Author Edgar
*/
public class Link {//头结点
private Node first;
//委节点
private Node last;
//节点大小
private int size;
public Link(){
size=0;
}/**
* 向链表尾部添加元素
* @param e
*/
public void addLast(E e){
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
//若链表没有数据则把新节点赋给头节点，否则原尾结点指向新节点
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
}/**
* 向链表头部添加元素
* @param e
*/
public void addFirst(E e) {
final Node f = first;
final Node newNode = new Node<>(null, e, f);
first = newNode;
//若链表没有数据则把新节点赋给尾节点，否则原头结点的前驱节点指向新节点
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
}/**
* 默认采用队列模式添加元素
* @param e
*/
public void add(E e){
addLast(e);
}/**
* 向指定位置添加原
* @param e
* @param index
*/
public void add(E e,int index){
if (index<0 || index > size){
throw new IndexOutOfBoundsException();
}
if (index==size){
addLast(e);
return;
}
if (0==index){
addFirst(e);
return;
}
Node node=first;
//找到要插入位置的前一个节点
for (int i = 0;
i < index-1;
i++) {
node=node.next;
}
Node newNode = new Node<>(node, e, node.next);
node.next=newNode;
size++;
}/**
* 删除指定位置的元素
* @param index
*/
public void remove(int index){
if (index<0 || index >= size){
throw new IndexOutOfBoundsException();
}
if (0==index){
removeFirst();
return;
}
if (index==size-1){
removeList();
return;
}
Node node=first;
//找到要删除元素的前一个节点
for (int i = 0;
i < index-1;
i++) {
node=node.next;
}
Node q=node.next;
node.next=q.next;
size--;
}/**
* 删除链表中的第一个元素
*/
public void removeFirst(){
Node f=first;
if (null==f){
throw new NoSuchElementException();
}
final Node next=f.next;
first=next;
if (null!=next){
next.prev=null;
}
size--;
}/**
* 删除链表中的最后一个元素
*/
public void removeList(){
Node l=last;
if (null==l){
throw new NoSuchElementException();
}
final Node la=l.prev;
last=la;
if (null!=la){
la.next=null;
}
size--;
} /**
* 找指定位置的元素
* @param index
* @return
*/
public E get(int index){
if (index<0 || index >= size){
throw new IndexOutOfBoundsException();
}
Node f=first;
if (null==f){
throw new NoSuchElementException();
}
int j=0;
while (null!=f && j first);
}/**
* 获取链表中的最后一个元素
* @return
*/
public E getLast(){
return getSide(() -> last);
}/**
* 获取链表两端的元素
* @param supplier
* @return
*/
private E getSide(Supplier> supplier){
final Node f=supplier.get();
if (null==f){
throw new NoSuchElementException();
}
return f.data;
}public int size(){
return this.size;
}//节点类
private static class Node{
E data;
Node next;
Node prev;
public Node(Node prev,E data,Node next){
this.data=https://www.it610.com/article/data;
this.next=next;
this.prev=prev;
}
}
}
