代码借鉴于LinkedList源码
public class LinkedList<E> {
/* 头部 */
Node<E> first;
/* 尾部 */
Node<E> last;
/* 长度 */
int size;
/* 操作次数 */
int modCount;
public LinkedList(){
}
/**
* 获取长度
* @return
*/
public int size(){
return size;
}
/**
* 获取头部元素
* @return
*/
public E getFist(){
/* 获取头部元素 */
Node<E> f = first;
/* 为空直接抛出异常 */
if(f == null){
throw new NoSuchElementException();
}
return f.item;
}
/**
* 获取尾部元素
* @return
*/
public E getLast(){
/* 获取头部元素 */
Node<E> l = last;
/* 为空直接抛出异常 */
if(l == null){
throw new NoSuchElementException();
}
return l.item;
}
/**
* 根据下标获取元素
* @param index
* @return
*/
public E get(int index){
/* 检查下标 */
checkElementIndex(index);
/* 返回查询到的元素 */
return node(index).item;
}
/**
* 添加一个元素
* @param e
*/
public void add(E e){
Node<E> l = last;
Node<E> newNode = new Node<>(l,e,null);
// 当前添加的元素设置给尾部
last = newNode;
/* 如果l为空,说明链表中还无数据,将当前元素设置给头部元素 */
if(l == null){
first = newNode;
}else{
/* 如果l不为空,就将添加的数据加在上一个元素的尾部 */
l.next = newNode;
}
/* 长度增加 */
size++;
/* 操作增加 */
modCount++;
}
/**
* 根据下标删除一个元素
* @param index
* @return
*/
public E remove(int index){
/* 检查下标 */
checkElementIndex(index);
/* 根据下标查询对应的元素*/
final Node<E> node = node(index);
/* 获取元素值 */
final E element = node(index).item;
/* 获取查询到的元素的下一个元素 */
final Node<E> next = node.next;
/* 获取查询到的元素的上一个元素 */
final Node<E> prev = node.prev;
/* 如果上一个元素为空,说明当前为头部元素 */
if(prev == null){
/* 则当前元素的下一个设置成头部 */
first = next;
}else{
/* 将上一个元素的下一个引用直接指向当前元素的下一个元素 */
prev.next = next;
/* 设置当前元素的上一个为空 */
node.prev = null;
}
/* 如果当前元素的下一个元素为null */
if(next == null){
/* 则尾部元素将设置成当前元素的上一个元素 */
last = prev;
}else{
/* 如果下一个元素不为空,则下一个元素的prev指向上一个元素 */
next.prev = prev;
/* 当前元素的下一个元素设置为null */
node.next = null;
}
/* 当前元素的值设置为null*/
node.item = null;
/* 长度减1 */
size--;
/* 操作加1 */
modCount++;
/* 返回删除的元素值 */
return element;
}
/**
* 判断下标不小于0,并且小于总长度
* @param index
* @return
*/
private boolean isElementIndex(int index){
return index >= 0 && index < size;
}
/**
* 检查下标是否正常
* @param index
*/
private void checkElementIndex(int index){
if(!isElementIndex(index)){
throw new IndexOutOfBoundsException("index:"+index+",size:"+size);
}
}
/**
* 根据下标查询对应的Node
* @param index
* @return
*/
Node<E> node(int index){
/* 如果index < size除于2 则从头部开始寻找 */
if(index < (size >> 1)){
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
}else{/* 如果index > size除于2 则从尾部开始寻找 */
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
/**
* 节点
* @param <E>
*/
public static class Node<E> {
/* 当前节点的上一个节点 */
Node<E> prev;
/* 当前节点的下一个节点 */
Node<E> next;
/* 当前节点的值 */
E item;
public Node(Node<E> prev,E value,Node<E> next){
this.prev = prev;
this.item = value;
this.next = next;
}
}
}
