三郎数据结构学习笔记：双向循环链表（判断是否对称）附源码-白红宇

三郎数据结构学习笔记：双向循环链表（判断是否对称）附源码

阅读量：1902 次

发布时间：2019-04-26

本文共 2591 字，大约阅读时间需要 8 分钟。

双向循环链表

题目

建立一个带头结点的双向循环链表，

赋值，判断是否对称，写出算法计算时间复杂度

思想

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
   
     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
    
      {    public Anytype data;//数据    public Node
     
       prev;//前一个节点    public Node
      
        next;//后一个节点    public Node(Anytype data,Node
       
         prev,Node
        
          next){ this.data=data; this.prev=prev; this.next=next; }}class DoubleLink
         
           { Node
          
            head;//头指针 Node
           
             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
            
              getNode(int index){ Node
             
               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
              
                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
               
                 n=getNode(i); Node
                
                  renode=new Node<>(a,n.prev,n); n.prev.next=renode; n.prev=renode; size++; } //删除元素 public AnyType remove(int i){ Node
                 
                   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
                  
                    n=getNode(i); AnyType old=n.data; n.data=a; return old; } //清空链表 public void clear(){ initlist(); } public void print(){ for(int i=0;i