顾名思义：双链表就是在数据域之内还保存了直接前驱和直接后继， 除头尾节点除外， 这种双链表的优点是插入和删除花费的时间为O（1）
package link;
/*
* 双链表
*/
public class MyLinkedList<AnyType> implements Iterable<AnyType>{
private int theSize; //除去头尾节点之外的大小（数据的大小）
private int modCount = 0;
private Node<AnyType> beginMarker; // 头节点
private Node<AnyType> endMarker; //尾节点
/*
* @功能 从内存中开辟一个节点并且插入到链表中
* @data 数据域
* @prev 保存前一个节点的地址（指针）
* @next 保存后一个节点的地址
*/
private static class Node<AnyType>{
public AnyType data;
public Node<AnyType> prev;
public Node<AnyType> next;
//构造方法
public Node(AnyType d, Node<AnyType> p, Node<AnyType> n){
this.data = d;
this.prev = p;
this.next = n;
}
}
/*
* 构造方法
*/
public MyLinkedList(){
doClear();
}
/*
* @功能： 清除数据
*/
public void clear(){
doClear();
}
/*
* @beginMarker 头节点，在初始化的时候next没有指向尾节点，因为在初始化时比尾节点先初始化，所以只能等尾节点初始化完成之后才能指向尾节点
* @endMarker 尾节点，在初始化的时候它是指向头节点的
* @theSize 初始化或清空的长度必须为0
*/
private void doClear(){
beginMarker = new Node<AnyType>(null, null, null);
endMarker = new Node<AnyType>(null, beginMarker, null);
beginMarker.next = endMarker;
theSize = 0;
modCount++;
}
/*
* @theSize 返回双链表的大小
*/
public int size(){
return theSize;
}
/*
* @功能 判断是否是空
*/
public boolean isEmpty(){
return size() == 0;
}
/*
* @功能 直接从尾部添加元素
* size 返回数组的大小
* x 保存的数据
*/
public boolean add(AnyType x){
add(size(), x);
return true;
}
/*
* @idx size()的大小，从最后插入
* @x 要插入元素的内容
*/
public void add(int idx, AnyType x){
addBefore(getNode(idx, 0, size()), x);
}
public void addFirst(AnyType x){
addBefore(beginMarker.next, x);
}
public void addLast(AnyType x){
addBefore(endMarker.prev, x);
}
private Node<AnyType> getNode(int idx){
return getNode(idx, 0, size());
}
/*
* 查找链表中是否存在这个元素
*/
public boolean contains(AnyType x){
Node<AnyType> node = beginMarker;
while(node != endMarker && !(node.data.equals(x))){
node = node.next;
}
return (node != endMarker);
}
/*
* @功能 找到要添加的位置
* 假如要是从指定位置插入的话，为了减少时间，当插入的位置在前半部分的时候默认是从头节点开始找位置，
* 假如要插入的位置是在后半部分的时候是从尾节点开始找插入位置
*/
private Node<AnyType> getNode(int idx, int lower, int upper){
Node<AnyType> p;
if(idx < lower || idx > upper)
throw new IndexOutOfBoundsException();
if(idx < size()/2){
p = beginMarker.next;
for(int i=0; i<idx; i++)
p = p.next;
}else{
p = endMarker;
for(int i=size(); i>idx; i--)
p = p.prev;
}
return p;
}
/*
* @功能 将节点插入到要插入的位置
* 第一步： 你的节点已经存好了你指向的前驱以及后继
* 第二步： 将你的前驱指向自己
* 第三部： 将你的后继指向自己
*/
private void addBefore(Node<AnyType> p, AnyType x){
Node<AnyType> newNode = new Node<AnyType>(x, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
modCount++;
}
/*
* @功能查找相应位置的元素 不过这种查找速度太慢
*/
public AnyType get(int idx){
return getNode(idx).data;
}
/*
* @ 获取第一项的值
*/
public AnyType getFirst(){
return getNode(0).data;
}
/*
* @功能 获取最后一项的值
*/
public AnyType getLast(){
return getNode(size()-1).data;
}
/*
* 按照下表来更改链表中的元素
*/
public AnyType set(int idx, AnyType x){
Node<AnyType> p = getNode(idx);
AnyType old = p.data;
p.data = x;
return old;
}
/*
* 按照节点来更改集合中的元素
*/
public AnyType set(Node<AnyType> n, AnyType x){
AnyType old = n.data;
n.data = x;
return old;
}
/*
* 按照下标来进行删除操作
*/
public AnyType remove(int idx){
return remove(getNode(idx));
}
/*
* 迭代器里面的删除操作来进行
*/
private AnyType remove(Node<AnyType> p){
p.prev.next = p.next;
p.next.prev = p.prev;
theSize--;
modCount++;
return p.data;
}
/*
* @功能 删除第一项
*/
public AnyType removeFirst(){
return remove(beginMarker.next);
}
/*
* @功能 删除最后一项
*/
public AnyType removeLast(){
return remove(endMarker.prev);
}
@Override
public java.util.Iterator<AnyType> iterator() {
return new LinkedListIterable();
}
public java.util.ListIterator<AnyType> listIterator(){
return new MyLingedListlistIterator();
}
/*
* 迭代器
*/
private class LinkedListIterable implements java.util.Iterator<AnyType>{
private Node<AnyType> current = beginMarker.next;
private int expectModCount = modCount;
private boolean okToRemove = false;
@Override
public boolean hasNext() {
return current != endMarker;
}
@Override
public AnyType next() {
if(modCount != expectModCount){
throw new java.util.ConcurrentModificationException();
}
if(!hasNext()){
throw new IllegalStateException();
}
AnyType nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
public void remove(){
if(modCount != expectModCount)
throw new java.util.ConcurrentModificationException();
if(!okToRemove){
throw new IllegalStateException();
}
MyLinkedList.this.remove(current.prev);
expectModCount++;
okToRemove = false;
}
}
private class MyLingedListlistIterator implements java.util.ListIterator<AnyType>{
private Node<AnyType> node = beginMarker;
private int expectModeCount = modCount;
boolean bool = false;
@Override
public boolean hasNext() {
// TODO 自动生成的方法存根
return node != endMarker;
}
@Override
public AnyType next() {
if(expectModeCount != modCount)
throw new java.util.ConcurrentModificationException();
if(!hasNext())
throw new java.util.NoSuchElementException();
AnyType nextItem = node.data;
node = node.next;
bool = true;
expectModeCount++;
return nextItem;
}
@Override
public boolean hasPrevious() {
// TODO 自动生成的方法存根
return node.prev != beginMarker;
}
@Override
public AnyType previous() {
if(expectModeCount != modCount)
throw new java.util.ConcurrentModificationException();
if(!hasPrevious())
throw new java.util.NoSuchElementException();
node = node.prev;
AnyType prve = node.data;
bool = true;
return prve;
}
@Override
public int nextIndex() {
throw new java.lang.UnsupportedOperationException();
}
@Override
public int previousIndex() {
throw new java.lang.UnsupportedOperationException();
}
@Override
public void remove() {
if(expectModeCount != modCount)
throw new java.util.ConcurrentModificationException();
if(!bool)
throw new IllegalStateException();
MyLinkedList.this.remove(node.prev);
bool = false;
}
@Override
public void set(AnyType e) {
if(expectModeCount != modCount)
throw new java.util.ConcurrentModificationException();
MyLinkedList.this.set(node.next, e);
}
@Override
public void add(AnyType e) {
if(expectModeCount != modCount)
throw new java.util.ConcurrentModificationException();
MyLinkedList.this.addBefore(node.next, e);
}
}
}