在单链表中，查询下一个元素的时间是O(1)。查询上一个元素的时间倒是O(n)。java
为了克服这种缺点，有了双向链表----继而为了更加高效-----双向循环链表node
此外引用不知哪位大神的一句话：判断数据结构使用数组
若是你要把数据集合当作一个环，能够顺时针走，也能够逆时针走，那你就能够用双向循环链表来描述
若是你要把数据集合当作一条链，能够双向遍历，那你就能够用双向链表来描述
若是你要把数据集合当作一个层次结构，那你能够用树来描述
若是你要把数据集合当作……，比方说，你彻底想不到谁跟谁会有关系，那你能够用图来描述
数据结构
下面是个测试例子，实现了基本功能函数
import java.util.Scanner;
public class DoubleLinkedList<AnyType>{
//定义双向链表节点
private class Node<AnyType>{
AnyType data;
Node<AnyType> next;
Node<AnyType> prev;
//构造函数
private Node()
{
data=null;
prev=null;
next=null;
}
private Node(AnyType data){
this.data=data;
this.prev=null;
this.next=null;
}
private Node(AnyType data,Node<AnyType> prev,Node<AnyType> next){
this.data=data;
this.prev=prev;
this.next=next;
}
}
private int size=0;
private Node<AnyType> beginMarker;
private Node<AnyType> endMarker;
//初始化一个空的双向循环链表
public DoubleLinkedList(){
beginMarker=new Node<AnyType>();
endMarker=new Node<AnyType>();
//key point
beginMarker.prev=endMarker;
beginMarker.next=null;
endMarker.prev=null;
//together
endMarker.next=beginMarker;
}
public void init(){
System.out.println("双向循环链表的操做：");
System.out.println("1.空的双向循环链表已经创建");
}
//2.用于向空的双向循环链表里面添加数据
public void addInit(){
Scanner sc=new Scanner(System.in);
System.out.println("2.该步骤执行初始化节点操做");
System.out.println("a.请输入要插入节点的个数");
int n=sc.nextInt();
for(int i=0;i<n;i++){
System.out.println("b.请输入要插入的元素的数值:");
AnyType data=(AnyType)sc.next();
if(beginMarker.next==null){
Node<AnyType> node=new Node<AnyType>(data);
beginMarker.next=node;
node.prev=beginMarker;
endMarker=node;
endMarker.next=beginMarker;
beginMarker.prev=endMarker;
}
else{
Node<AnyType> node=new Node<AnyType>(data);
endMarker.next=node;
node.prev=endMarker;
endMarker=node;
endMarker.next=beginMarker;
beginMarker.prev=endMarker;
}
}
}
// add 方法
public void add(AnyType data){
if(beginMarker.next==null){
Node<AnyType> node=new Node<AnyType>(data);
beginMarker.next=node;
node.prev=beginMarker;
endMarker=node;
endMarker.next=beginMarker;
}
else{
Node<AnyType> node=new Node<AnyType>(data);
endMarker.next=node;
node.prev=endMarker;
endMarker=node;
endMarker.next=beginMarker;
}
}
public void add(){
Scanner sc=new Scanner(System.in);
System.out.println("3.该步骤/执行插入节点操做");
System.out.print("*请输入要插入节点的个数*");
System.out.println("(可用于插入第一个和最后一个节点)");
int n=sc.nextInt();
for(int i=0;i<n;i++){
System.out.println("a.请输入要插入节点的位置:");
int index=sc.nextInt();
System.out.println("b.请输入要插入的元素的数值");
AnyType data=(AnyType)sc.next();
int j=0;
if (beginMarker==null){
Node<AnyType> Node = new Node<AnyType>(data);
beginMarker.next=Node;
Node.prev=beginMarker;
endMarker=Node;
endMarker.next=beginMarker;
}
else if(index==0){
Node<AnyType> Node=new Node<AnyType>(data);
Node<AnyType> temp=beginMarker.next;
beginMarker.next=Node;
Node.prev=beginMarker;
Node.next=temp;
temp.prev=Node;
}
else if(index>=size()){
add(data);
} else
{
Node<AnyType>Node=new Node<AnyType>(data);
Node<AnyType> prior=beginMarker;
while (j<index)
{
j++;
prior=prior.next;
}
Node<AnyType> temp=prior.next;
prior.next=Node;
Node.prev=prior;
Node.next=temp;
temp.prev=Node;
}
}
}
public void remove() {
int j=0;
Scanner sc=new Scanner(System.in);
System.out.println("4.该步骤执行删除节点操做");
System.out.println("a.请输入要删除节点的个数:");
int n=sc.nextInt();
for(int i=0;i<n;i++){
System.out.println("b.请输入要删除节点的位置:");
int index=sc.nextInt();
if (index<0||index>=size())
{
System.out.println("数组越界");
} else if(index==0||size()==1) {
if (size()==0){
beginMarker.next=null;
endMarker=null;
} else {
Node<AnyType> fitst=beginMarker.next;
beginMarker.next=fitst.next;
fitst=null;
}
} else if(index==(size()-1)){
if(size()==1)
{
if (size()==0){
beginMarker.next=null;
endMarker=null;
} else {
Node<AnyType> fitst=beginMarker.next;
beginMarker.next=fitst.next;
fitst=null;
}
}
else{
Node<AnyType> pre=endMarker.prev;
pre.next=null;
endMarker=pre;
endMarker.next=beginMarker;
endMarker=null;
}
} else {
Node<AnyType> prior=beginMarker.next;
while(j<index){
j++;
prior=prior.next;
}
Node<AnyType> delete=prior;
Node<AnyType> pre=delete.prev;
Node<AnyType> after=delete.next;
pre.next=delete.next;
after.prev=pre;
delete=null;
}
}
System.out.println("**************");
}
//用于计算链表的大小
public int size(){
int size=0;
Node<AnyType> node=beginMarker.next;
while(node.data!=null) {
size++;
node=node.next;
}
return size;
}
//用于获得节点
public Node<AnyType> getNode(int index) {
int j=0;
Node<AnyType> firstNode=beginMarker.next;
if(index<0||index>=size())
{
System.out.println("数组越界");
}
while(j<index){
j++;
firstNode=firstNode.next;
}
return firstNode;
}
public void check(DoubleLinkedList list){
System.out.println("5.是否执行逆置操做(是/否)?");
Scanner sc=new Scanner(System.in);
String str=sc.next();
if(str.equals("是")){
this.inverse(list);
}
else
System.out.println("全部操做都已完成");
}
//实现链表的逆置操做
public void inverse(DoubleLinkedList<AnyType> list1){
System.out.println("逆置后的结果为:");
int size=size();
for(int i=size-1;i>=0;i--)
{
list1.add(this.getNode(i).data);
}
list1.print();
System.out.println("全部操做都已结束");
}
//该方法用于输出链表中的全部数值
public void print(){
Node<AnyType> firstNode=beginMarker.next;
if(firstNode==null){
System.out.println("该链表为空");
}
else
{
while(firstNode.data!=null)
{
System.out.println(firstNode.data);
firstNode=firstNode.next;
}
}
}
public static void main(String[] args) {
DoubleLinkedList<Object> list=new DoubleLinkedList<Object>();
list.init();
DoubleLinkedList<Object> list1=new DoubleLinkedList<Object>();
list.addInit();
list.add();
list.remove();
list.check(list1);
list.print();
}
}