双向循环链表

• • 题目
  • 思想
  • 实验结果
  • 完整源代码

题目

建立一个带头结点的双向循环链表，
赋值，判断是否对称，写出算法计算时间复杂度

思想

travel the Link ；遍历链表
put values into a array ；赋值给一个数组
compare the array to know whether it belong to symmetry 比较数组是否对称
采用问题转化的思想
将链表问题转换成数组问题，大大降低了思考难度
时间复杂度O（n^2）
因为有两个for循环

实验结果

比较次数本来可以更少点，但是我就不改了，分个数奇数偶数
链表数值：1 2 3 2 1

链表数值：1 2 3 2 3

完整源代码

/*
 * Author：sanlang
 * time：2020.11.5
 * function：建立一个带头结点的双向循环链表，赋值，判断是否对称，写出算法计算时间复杂度
 *  my view：travel the Link ；put values into a array ；compare the array to know whether symmetry
 * */
public class DoubleLinkSys {
    public static void main(String[] args) {
        DoubleLink<Integer> doubleLink = new DoubleLink<>();
        doubleLink.initlist();
        doubleLink.add(1);
        doubleLink.add(2);
        doubleLink.add(3);
        doubleLink.add(2);
        doubleLink.add(1);
        doubleLink.print();
        int array[]=new int[5];  //5是长度，不是最大下标 ，下标范围0-4
        for( int i=0; i<5 ;i++){
            array[i]=doubleLink.get(i);
            System.out.println(array[i]);
        }
        System.out.println("判断是否对称开始：");
        for(int m=0;m<4;m++){
            if (array[m]==array[4-m]){
                System.out.println("匹配");
            }
            else
                System.out.println("不匹配");
        }

    }
}
class Node<Anytype> {
    public Anytype data;//数据
    public Node<Anytype> prev;//前一个节点
    public Node<Anytype> next;//后一个节点
    public Node(Anytype data,Node<Anytype> prev,Node<Anytype> next){
        this.data=data;
        this.prev=prev;
        this.next=next;
    }
}



class DoubleLink<AnyType> {
    Node<AnyType> head;//头指针
    Node<AnyType> end;//尾节点
    int size;//记录链表长度

    //初始化链表
    public void initlist(){
        end=new Node<>(null,null,null);
        head=new Node<>(null,null,end);
        end.prev=head;
        end.next=head;
        size=0;
    }

    //获取长度
    public int length(){

        return size;

    }

    //获取节点
    public Node<AnyType> getNode(int index){
        Node<AnyType> n;
        if(index>=size/2){
            n=end;
            for(int i=length();i>index;i--){
                n=n.prev;
            }
            return n;
        }
        else{
            n=head;
            for(int i=0;i<=index;i++){
                n=n.next;
            }
            return n;
        }
    }

    //添加元素
    public void add(AnyType a){
        Node<AnyType> renode=new Node<>(a,getNode(size-1),end);
        renode.prev.next=renode;
        renode.next.prev=renode;
        size++;
    }

    //插入元素
    public void insert(int i,AnyType a){
        Node<AnyType> n=getNode(i);
        Node<AnyType> renode=new Node<>(a,n.prev,n);
        n.prev.next=renode;
        n.prev=renode;
        size++;
    }

    //删除元素
    public AnyType remove(int i){
        Node<AnyType> n=getNode(i);
        AnyType data=n.data;
        n.prev.next=n.next;
        n.next.prev=n.prev;
        size--;
        return data;
    }

    //获取i位置的数据
    public AnyType get(int i){
        return getNode(i).data;
    }

    //为i位置元素重新赋值
    public AnyType set(int i,AnyType a){
        Node<AnyType> n=getNode(i);
        AnyType old=n.data;
        n.data=a;
        return old;

    }

    //清空链表
    public void clear(){
        initlist();
    }



    public void print(){
        for(int i=0;i<size;i++){
            System.out.println(getNode(i).data);
        }
    }
}