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();
}
}
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();
}
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;
}
}
}
}
