对于普通的单向链表，如果在它的内部类中再加一个Node prev 属性（这属性代表向前的指针，指向它前面一个结点），然后在链表类中加一个Node tail指向它的尾部，就构成了双向链表。
链表只能从头往尾遍历， 那我可以在Node内部类中再添加一个属性Node prev,这样Node内部类中就有了三个属性:E data保存数据，Node next 指向下一个结点， Node prev指向上一个结点。
类似地，也可以来一个虚拟尾节点dummyTail，在链表类的构造方法中，分别令dummyHead指向虚拟头结点，dummyTail指向虚拟尾结点，然后令dummyHead.next = dummyTail, dummyTail.prev = dummyHead , 而dummyHead. prev = null, dummyTail.next = null 。 这样就构造好了初始的链表。
然后向链表中增添或者删除一个结点，先判断这个索引是离头结点还是离尾节点更近，如果index < size/2,说明离头近，从头遍历， 如果index > size/2 说明离尾近，从尾遍历。 遍历的方法都是类似的，都是设置一个临时指针temp,如果离头近，那么我就 Node temp = dummyhead ,(循环 temp =temp.next ) ； 如果离尾近，我就Node temp = dummyTail,(循环 temp = temp.prev) .
这样的话，添加头，添加尾 和 删除头，删除尾的时间复杂度都是1 . 这样的话，链表就对称了，意思是从头到尾进行操作，和从尾到头进行操作，并没有复杂度不同的问题。
以下为代码
public class myLinkList<E> implements LinkList<E>{
private class Node{
E data;
Node prev;
Node next;
Node(E data,Node prev,Node next)
{
this.data = data;
this.prev = prev;
this.next = next;
}
Node(E data)
{
this(data,null,null);
}
Node()
{
this(null,null,null);
}
}
private Node dummyHead;
private Node dummyTail;
private int size;
public myLinkList()
{
dummyHead = new Node();
dummyTail = new Node();
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
size = 0;
}
@Override
public int getSize()
{
return size;
}
@Override
public boolean isEmpty()
{
return (size==0);
}
@Override
public void addTo(int index, E elem)
{
if((index < 0)||(index > size))
{
throw new NullPointerException("无法添加结点，索引不合法");
}
Node insert = new Node(elem);
if(index < size/2)
{
Node temp = dummyHead;
for(int i=0 ; i<index ; i++)
{
temp = temp.next;
}
Node afterInsert = temp.next;
insert.next = afterInsert;
insert.prev = temp;
temp.next = insert;
afterInsert.prev = insert;
}
else
{
Node temp = dummyTail;
for(int i = size-1; i>=index ; i--)
{
temp = temp.prev;
}
Node beforeInsert = temp.prev;
insert.prev = beforeInsert;
insert.next = temp;
temp.prev = insert;
beforeInsert.next = insert;
}
size++;
}
@Override
public void addFirst(E elem)
{
addTo(0, elem);
}
@Override
public void addLast(E elem)
{
addTo(size, elem);
}
@Override
public void set(int index, E elem)
{
if((index < 0)||(index >= size))
{
throw new NullPointerException("无法改变，索引不合法");
}
if(index <size/2)
{
Node temp = dummyHead.next;
for(int i =0;i<index;i++)
{
temp = temp.next;
}
temp.data = elem;
}
else
{
Node temp = dummyTail.prev;
for(int i=size-1;i>index;i--)
{
temp = temp.prev;
}
temp.data = elem;
}
}
@Override
public E get(int index)
{
if((index < 0)||(index >= size))
{
throw new NullPointerException("无法获取到索引，索引不合法");
}
if(index <size/2)
{
Node temp = dummyHead.next;
for(int i =0;i<index;i++)
{
temp = temp.next;
}
return temp.data;
}
else
{
Node temp = dummyTail.prev;
for(int i=size-1;i>index;i--)
{
temp = temp.prev;
}
return temp.data;
}
}
@Override
public E getFirst()
{
return get(0);
}
@Override
public E getLast()
{
return get(size-1);
}
@Override
public int indexOf(E elem)
{
Node temp = dummyHead.next;
for(int i=0;i<size;i++)
{
if(temp.data.equals(elem)==true)
{
return i;
}
temp = temp.next;
}
return -1;
}
@Override
public boolean contains(E elem)
{
return (indexOf(elem)!=-1);
}
@Override
public E deleteAt(int index)
{
if((index < 0)||(index >= size))
{
throw new NullPointerException("无法删除结点，索引不合法");
}
E result = get(index);
if(index < size/2)
{
Node temp = dummyHead;
for(int i = 0; i<index ;i++)
{
temp = temp.next;
}
Node wannaDelete = temp.next;
temp.next = wannaDelete.next;
wannaDelete.next.prev = temp;
wannaDelete.prev = null;
wannaDelete.next = null;
}
else
{
Node temp = dummyTail;
for(int i = size-1;i>index;i--)
{
temp = temp.prev;
}
Node wannaDelete = temp.prev;
temp.prev = wannaDelete.prev;
wannaDelete.prev.next = temp;
wannaDelete.prev = null;
wannaDelete.next = null;
}
size--;
return result;
}
@Override
public E deleteFirst()
{
return deleteAt(0);
}
@Override
public E deleteLast()
{
return deleteAt(size-1);
}
@Override
public void delete(E elem)
{
if(contains(elem)==true)
{
deleteAt(indexOf(elem));
}
}
@Override
public void deleteAll(E elem)
{
while(contains(elem)==true)
{
deleteAt(indexOf(elem));
}
}
@Override
public String toString()
{
StringBuilder result = new StringBuilder("[");
if(size ==0)
{
result.append("]");
return result.toString();
}
for(int i =0; i <size;i++)
{
result.append(get(i));
if(i<size-1)
{
result.append(", ");
}
else
{
result.append("]");
}
}
return result.toString();
}
}
interface LinkList<E>{
int getSize();
boolean isEmpty();
void addTo(int index,E elem);
void addFirst(E elem);
void addLast(E elem);
E get(int index);
E getFirst();
E getLast();
void set(int index,E elem);
boolean contains(E elem);
E deleteAt(int index);
E deleteFirst();
E deleteLast();
int indexOf(E elem);
void delete(E elem);
void deleteAll(E elem);
}经过测试，我写的双向链表可以成功地进行数据的增删改查。