java实现循环链表：http://www.cnblogs.com/lixiaolun/p/4643911.html
在单链表中，查询下一个元素的时间是O(1)。查询上一个元素的时间却是O(n)。
为了克服这种缺点，我们开始学习双向链表。
双向链表类的代码：
package doublelinkedlist;
public class DoubleLinkedList {
class Element
{
private Element prior=null;
public Object value=null;
private Element next=null;
}
private Element header = null;//头结点
/**
* 初始化链表
* */
void initList()
{
header = new Element();
header.prior=header;
header.value=null;
header.next=header;
}
/**
* 向链表中第i个位置插入元素o
* */
void insertList(Object o,int i)
{
if(i<=0||i>size())
{
System.out.println("插入位置不合法！链表长度为："+size());
}else
{
Element e = new Element();
e.value=o;
if(header.prior==header)//第一次插入元素
{
e.prior=header;
e.next=header;
header.next=e;
header.prior=e;
}else if(i==size())//在最后插入
{
System.out.println("在链表尾部插入");
e.next=header;
e.prior=header.prior;
header.prior.next=e;
header.prior=e;
}else
{
Element temp = header;
int count=0;
while(temp.next!=header)
{
count++;
if(count == i)
{
e.prior=temp;
e.next=temp.next;
temp.next.prior=e;
temp.next=e;
}
temp=temp.next;
}
}
}
}
/**
* 删除链表中的某个元素
* */
void deleteList(int i)
{
if(i<=0||i>size())
{
System.out.println("插入位置不合法！链表长度为："+size());
}else
{
int count=0;
Element temp = header;
while(temp.next!=header)
{
temp=temp.next;
count++;
if(i==count)
{
//删除第i个元素
temp.next.prior=temp.prior;
temp.prior.next=temp.next;
}
}
}
}
/**
* 打印链表
* */
void print()
{
System.out.print("打印双向循环链表：");
Element temp = header;
while(temp.next!=header)
{
System.out.print(temp.next.value+"\t");
temp=temp.next;
}
System.out.println();
}
/**
* 获取链表的大小
* */
int size()
{
int count=1;
Element temp = header;
while(temp.next!=header)
{
count++;
temp=temp.next;
}
return count;
}
}
双向链表的测试类
package doublelinkedlist;
public class DoubleLinkedListMain {
public static void main(String[] args) {
DoubleLinkedList dlList = new DoubleLinkedList();//有头结点
dlList.initList();
dlList.insertList(1, 1);
dlList.insertList(2, 2);
dlList.insertList(3, 1);
dlList.insertList(4, 1);
dlList.insertList(5, 1);
dlList.insertList(6, 6);
dlList.print();
dlList.deleteList(3);
dlList.print();
}
}
