• 数据结构——单向循环链表&双向循环链表

    一、单向循环链表

    (一)概念

    • 将单链表尾节点的指针域置为起始节点的地址，而不再是NULL，这样从表中任一节点出发，均可访问到链表中的所有节点

    (二)单向循环链表的结构图

    （三）程序封装单向循环链表 

       1.创建链表类和节点类

    1.  //节点的结构
    2.         class Cnode {
    3.             constructor(data) {
    4.                 this.data = data
    5.                 this.next = null
    6.             }
    7.  
    8.         }
    9. //链表的结构
    10.         class CycleLinkList {
    11.             constructor() {
    12.                 this.head = null
    13.                 this.length = 0
    14.             }
    15.          }

      2.单向循环链表的操作（方法） 

       1）append() 向链表尾部添加一个节点

    1. append(ele) {
    2.                 let newnode = new Cnode(ele)
    3.  
    4.                 if(this.head==null){
    5.                     //空链表
    6.                     this.head=newnode
    7.                     newnode.next=this.head 
    8.                 }else{
    9.                     //非空链表
    10.                     //需要找到最后一个节点
    11.                     let current=this.head
    12.                     while(current.next!=this.head){
    13.                         current=current.next
    14.                     }
    15.                     //找到了current表示最后一个节点
    16.                     current.next=newnode
    17.                     newnode.next=this.head
    18.                 }
    19.                 this.length++
    20.             }

       2）toString()  将链表中的数据连接为字符串

    1. toString(){
    2.                 let current=this.head,index=0,str=""
    3.                 while(index<this.length){
    4.                     str+="-"+current.data
    5.                     current=current.next
    6.                     index++
    7.                 }
    8.                return str.slice(1)
    9.             }

       3）insert() 向链表中插入元素 

    1.  insert(position, ele) {
    2.                 if (position < 0 || position > this.length || Number.isInteger(position)) {
    3.                     return false
    4.                 }
    5.                 let newnode = new Cnode(ele)
    6.                 let current = this.head,
    7.                     index = 0
    8.                 if (position == 0) {
    9.                     //在头部插入
    10.                     if (this.length == 0) {
    11.                         //空链表
    12.                         this.head = newnode
    13.                         newnode.next = this.head
    14.                     } else {
    15.                         //非空链表
    16.                         while (current.next != this.head) {
    17.                             current = current.next
    18.                         }
    19.                         newnode.next = this.head
    20.                         current.next = newnode
    21.                         this.head = newnode
    22.                     }
    23.                     this.length++
    24.                 } else if (position == this.length) {
    25.                     //在尾部插入
    26.                     this.append(ele)
    27.                 } else {
    28.                     //在中间插入
    29.                     while (index < position - 1) {
    30.                         current = current.next
    31.                         index++
    32.                     }
    33.                     newnode.next = current.next
    34.                     current.next = newnode
    35.                     this.length++
    36.                 }
    37.  
    38.             }

        4）removeAt() 移除在指定位置的元素

    1. removeAt(position) {
    2.                 //判断位置是否合法(越界判断)
    3.                 if (position < 0 || position > this.length - 1 || !Number.isInteger(position)) {
    4.                     return false
    5.                 }
    6.                 //非空链表
    7.                 let current = this.head,
    8.                     index = 0
    9.                 if (position == 0) {
    10.                     //移除头部
    11.                     if (this.length == 1) {
    12.                         //只有一个节点
    13.                         this.head = null
    14.                     } else {
    15.                         //找到最后一个节点 最后一个节点的next指向新头部
    16.                         while (current.next != this.head) {
    17.                             current = current.next
    18.                         }
    19.                         this.head = this.head.next
    20.                         current.next = this.head
    21.                     }
    22.                 } else {
    23.                     //移除任意位置(包括末尾)
    24.                     while (index < position - 1) {
    25.                         current = current.next
    26.                         index++
    27.                     }
    28.                     current.next = current.next.next
    29.                 }
    30.                 this.length--
    31.             }

       5）indexOf() 查找指定元素

    1. indexOf(ele) {
    2.                 let current = this.head,
    3.                     index = 0
    4.                 while (index < this.length) {
    5.                     if (current.data == ele) {
    6.                         return index
    7.                     } else {
    8.                         current = current.next
    9.                         index++
    10.                     }
    11.                 }
    12.                 return -1
    13.             }

        6）remove() 移除指定元素

    1. remove(ele) {
    2.                 let index = this.indexOf(ele)
    3.                 this.removeAt(index)
    4.             }

    (四)完整代码&操作示例

    1.         //节点的结构
    2.         class Cnode {
    3.             constructor(data) {
    4.                 this.data = data
    5.                 this.next = null
    6.             }
    7.  
    8.         }
    9.         //链表的结构
    10.         class CycleLinkList {
    11.             constructor() {
    12.                 this.head = null
    13.                 this.length = 0
    14.             }
    15.  
    16.             //1.append() 向链表尾部添加一个元素
    17.             append(ele) {
    18.                 let newnode = new Cnode(ele)
    19.  
    20.                 if (this.head == null) {
    21.                     //空链表
    22.                     this.head = newnode
    23.                     newnode.next = this.head
    24.                 } else {
    25.                     //非空链表
    26.                     //需要找到最后一个节点 最后一个节点的next指向头结点
    27.                     let current = this.head
    28.                     while (current.next != this.head) {
    29.                         //继续往下找
    30.                         current = current.next
    31.                     }
    32.                     //找到了current表示最后一个节点
    33.                     current.next = newnode
    34.                     newnode.next = this.head
    35.                 }
    36.                 this.length++
    37.             }
    38.  
    39.             //2.toString()  将链表中的数据链接为字符串
    40.             toString() {
    41.                 let current = this.head,
    42.                     index = 0,
    43.                     str = ""
    44.                 while (index < this.length) {
    45.                     str += "-" + current.data
    46.                     current = current.next
    47.                     index++
    48.                 }
    49.                 return str.slice(1)
    50.             }
    51.  
    52.             //3.向链表中插入元素
    53.             insert(position, ele) {
    54.                 if (position < 0 || position > this.length || !Number.isInteger(position)) {
    55.                     return false
    56.                 }
    57.                 let newnode = new Cnode(ele)
    58.                 let current = this.head,
    59.                     index = 0
    60.                 if (position == 0) {
    61.                     //在头部插入
    62.                     if (this.length == 0) {
    63.                         //空链表
    64.                         this.head = newnode
    65.                         newnode.next = this.head
    66.                     } else {
    67.                         //非空链表
    68.                         while (current.next != this.head) {
    69.                             current = current.next
    70.                         }
    71.                         newnode.next = this.head
    72.                         current.next = newnode
    73.                         this.head = newnode
    74.                     }
    75.                     this.length++
    76.                 } else if (position == this.length) {
    77.                     //在尾部插入
    78.                     this.append(ele)
    79.                 } else {
    80.                     //在中间插入
    81.                     while (index < position - 1) {
    82.                         current = current.next
    83.                         index++
    84.                     }
    85.                     newnode.next = current.next
    86.                     current.next = newnode
    87.                     this.length++
    88.                 }
    89.  
    90.             }
    91.  
    92.             //4.移除在指定位置的元素
    93.             removeAt(position) {
    94.                 //判断位置是否合法(越界判断)
    95.                 if (position < 0 || position > this.length - 1 || !Number.isInteger(position)) {
    96.                     return false
    97.                 }
    98.                 //非空链表
    99.                 let current = this.head,
    100.                     index = 0
    101.                 if (position == 0) {
    102.                     //移除头部
    103.                     if (this.length == 1) {
    104.                         //只有一个节点
    105.                         this.head = null
    106.                     } else {
    107.                         //找到最后一个节点 最后一个节点的next指向新头部
    108.                         while (current.next != this.head) {
    109.                             current = current.next
    110.                         }
    111.                         this.head = this.head.next
    112.                         current.next = this.head
    113.                     }
    114.                 } else {
    115.                     //移除任意位置(包括末尾)
    116.                     while (index < position - 1) {
    117.                         current = current.next
    118.                         index++
    119.                     }
    120.                     current.next = current.next.next
    121.                 }
    122.                 this.length--
    123.             }
    124.  
    125.             //5.查找指定元素
    126.             indexOf(ele) {
    127.                 let current = this.head,
    128.                     index = 0
    129.                 while (index < this.length) {
    130.                     if (current.data == ele) {
    131.                         return index
    132.                     } else {
    133.                         current = current.next
    134.                         index++
    135.                     }
    136.                 }
    137.                 return -1
    138.             }
    139.  
    140.  
    141.             //6.移除指定元素
    142.             remove(ele) {
    143.                 let index = this.indexOf(ele)
    144.                 this.removeAt(index)
    145.             }
    146.  
    147.         }
    148.         let clist = new CycleLinkList()
    149.  
    150.        //链表操作
    151.         //在末尾添加元素
    152.         for (let i = 0; i < 9; i++) {
    153.             clist.append(i)
    154.         }
    155.         console.log(clist.toString(),"添加了元素")
    156.         //在指定位置插入元素
    157.         clist.insert(3, "newnode")
    158.         console.log(clist.toString(),"在3的位置插入了newnode")
    159.         //移除指定位置的元素
    160.         clist.removeAt(4)
    161.         console.log(clist.toString(),"移除了第4个节点--3")
    162.         //查找元素
    163.         console.log(clist.indexOf(3),"查找3，已经被移除了所以返回-1")
    164.         console.log(clist.indexOf(5),"存在，返回下标")
    165.         //移除指定元素
    166.         clist.remove(8)
    167.         console.log(clist.toString(),"删除了8")

    打印结果：

    二、双向循环链表

    (一)概念

    • 可以从两个方向进行遍历，可以利用中间的一个节点推出下一个节点和上一个节点

    (二)双向循环链表的结构图

    (三)程序封装双向循环链表 

    1.创建链表类和节点类

    1.  //节点的结构
    2.        class Dnode {
    3.             constructor(data) {
    4.                 this.prev = null;
    5.                 this.data = data;
    6.                 this.next = null;
    7.             }
    8.         }
    9. //链表的结构
    10.        class DoubleCycleLinkList {
    11.             constructor() {
    12.                 this.head = null;
    13.                 this.tail = null;
    14.                 this.length = 0
    15.             }
    16.          }

    2.单向循环链表的操作（方法） 

      1）append() 向链表尾部添加一个节点

    1. append(ele) {
    2.                 let newnode = new Dnode(ele);
    3.                 if (this.length == 0) { //空链表
    4.                     this.head = newnode;
    5.                     this.tail = newnode;
    6.                     newnode.prev = newnode;
    7.                     newnode.next = newnode; //自己连自己
    8.                 } else {
    9.                     //将新节点连接
    10.                     newnode.prev = this.tail; //新节点.prev = 尾节点
    11.                     newnode.next = this.head; //新节点的next指向头结点
    12.                     //断开原来的指向，重新指向新节点
    13.                     this.tail.next = newnode; //尾节点.next指向新节点
    14.                     this.head.prev = newnode; //头结点的prev指向新节点
    15.                     this.tail = newnode; //将尾节点指向新节点
    16.                 }
    17.                 this.length++;
    18.             }

      2）insert() 向链表中插入元素 

    1. insert(position, ele) {
    2.                 // 位置是否合法
    3.                 if (position < 0 || position > this.length || !Number.isInteger(position)) {
    4.                     return false
    5.                 }
    6.                 let newnode = new Dnode(ele);
    7.                 if (position == 0) {
    8.                     //在头部插入
    9.                     if (this.length == 0) { //空链表
    10.                         this.head = newnode;
    11.                         this.tail = newnode;
    12.                         newnode.prev = this.tail
    13.                         newnode.next = this.head
    14.                     } else {
    15.                         //将新节点连接
    16.                         newnode.next = this.head; //新节点.next指向头节点
    17.                         newnode.prev = this.tail; //新节点的prev指向尾结点
    18.                         //断开原来的指向
    19.  
    20.                         this.head.prev = newnode; //头节点.prev指向新节点
    21.                         this.tail.next = newnode //尾节点的next指向新节点
    22.                         this.head = newnode; //头节点指向新节点
    23.                     }
    24.                     this.length++
    25.                 } else if (position == this.length) {
    26.                     //在尾部插入
    27.                     this.append(ele)
    28.                 } else {
    29.                     //在中间任意位置
    30.                     let current = this.head,
    31.                         index = 0;
    32.  
    33.                     while (index < position - 1) {
    34.                         current = current.next;
    35.                         index++;
    36.                     }
    37.                     // 1.将新节点连上去
    38.                     newnode.prev = current;
    39.                     newnode.next = current.next;
    40.                     // 2.断开原来的指向
    41.                     current.next = newnode;
    42.                     newnode.next.prev = newnode;
    43.                     this.length++;
    44.                 }
    45.             }

       3）removeAt() 移除在指定位置的元素

    1.  removeAt(position) {
    2.                 //判断位置的合法性（越界判断）
    3.                 if (position < 0 || position > this.length - 1 || !Number.isInteger(position)) {
    4.                     return false
    5.                 }
    6.                 if (this.length == 0) {
    7.                     //空链表
    8.                     return
    9.                 } else {
    10.                     if (position == 0) {
    11.                         //移除头节点
    12.                         if (this.length == 1) {
    13.                             this.head = null
    14.                             this.tail = null
    15.                         } else {
    16.                             this.head = this.head.next
    17.                             this.tail.prev=this.head
    18.                             this.head.prev = this.head
    19.                         }
    20.                     } else if (position == this.length - 1) {
    21.                         //移除尾结点
    22.                         this.tail = this.tail.prev
    23.                         this.tail.next = this.head
    24.                         this.head.prev=this.tail
    25.                     } else {
    26.                         //移除中间任意位置的节点
    27.                         let current = this.head,
    28.                             index = 0
    29.                         while (index < position - 1) {
    30.                             current = current.next
    31.                             index++
    32.                         }
    33.                         current.next = current.next.next
    34.                         current.next.prev = current
    35.                     }
    36.                     this.length--
    37.                 }
    38.             }

      4）indexOf() 查找指定元素

    1. indexOf(ele) {
    2.                 let current = this.head,
    3.                     index = 0
    4.                 while (index < this.length) {
    5.                     if (current.data == ele) {
    6.                         return index
    7.                     } else {
    8.                         current = current.next
    9.                         index++
    10.                     }
    11.                 }
    12.                 return -1
    13.             }

       5）remove() 移除指定元素

    1. remove(ele) {
    2.                 let index = this.indexOf(ele)
    3.                 this.removeAt(index)
    4.             }

      6）正向遍历

    1.  forwardString() {
    2.                 let current = this.head,
    3.                     index = 0,
    4.                     str = "";
    5.                 while (index < this.length) {
    6.                     str += "-" + current.data
    7.                     current = current.next
    8.                     index++
    9.                 }
    10.                 return str.slice(1)
    11.             }

      7）反向遍历      

    1.  reverseString() {
    2.                 let current = this.tail,
    3.                     index = this.length - 1,
    4.                     str = "";
    5.                 while (index >= 0) {
    6.                     str += "-" + current.data
    7.                     current = current.prev
    8.                     index--
    9.                 }
    10.                 return str.slice(1)
    11.             }

    (四)完整代码&操作示例

    1.         //节点的结构
    2.         class Dnode {
    3.             constructor(data) {
    4.                 this.prev = null;
    5.                 this.data = data;
    6.                 this.next = null;
    7.             }
    8.         }
    9.         //链表的结构
    10.         class DoubleCycleLinkList {
    11.             constructor() {
    12.                 this.head = null;
    13.                 this.tail = null;
    14.                 this.length = 0
    15.             }
    16.  
    17.             //1.在链表尾部添加元素
    18.             append(ele) {
    19.                 let newnode = new Dnode(ele);
    20.                 if (this.length == 0) { //空链表
    21.                     this.head = newnode;
    22.                     this.tail = newnode;
    23.                     newnode.prev = newnode;
    24.                     newnode.next = newnode; //自己连自己
    25.                 } else {
    26.                     //将新节点连接
    27.                     newnode.prev = this.tail; //新节点.prev = 尾节点
    28.                     newnode.next = this.head; //新节点的next指向头结点
    29.                     //断开原来的指向，重新指向新节点
    30.                     this.tail.next = newnode; //尾节点.next指向新节点
    31.                     this.head.prev = newnode; //头结点的prev指向新节点
    32.                     this.tail = newnode; //将尾节点指向新节点
    33.                 }
    34.                 this.length++;
    35.             }
    36.             // 2.向链表指定位置插入元素
    37.             insert(position, ele) {
    38.                 // 位置是否合法
    39.                 if (position < 0 || position > this.length || !Number.isInteger(position)) {
    40.                     return false
    41.                 }
    42.                 let newnode = new Dnode(ele);
    43.                 if (position == 0) {
    44.                     //在头部插入
    45.                     if (this.length == 0) { //空链表
    46.                         this.head = newnode;
    47.                         this.tail = newnode;
    48.                         newnode.prev = this.tail
    49.                         newnode.next = this.head
    50.                     } else {
    51.                         //将新节点连接
    52.                         newnode.next = this.head; //新节点.next指向头节点
    53.                         newnode.prev = this.tail; //新节点的prev指向尾结点
    54.                         //断开原来的指向
    55.  
    56.                         this.head.prev = newnode; //头节点.prev指向新节点
    57.                         this.tail.next = newnode //尾节点的next指向新节点
    58.                         this.head = newnode; //头节点指向新节点
    59.                     }
    60.                     this.length++
    61.                 } else if (position == this.length) {
    62.                     //在尾部插入
    63.                     this.append(ele)
    64.                 } else {
    65.                     //在中间任意位置
    66.                     let current = this.head,
    67.                         index = 0;
    68.  
    69.                     while (index < position - 1) {
    70.                         current = current.next;
    71.                         index++;
    72.                     }
    73.                     // 1.将新节点连上去
    74.                     newnode.prev = current;
    75.                     newnode.next = current.next;
    76.                     // 2.断开原来的指向
    77.                     current.next = newnode;
    78.                     newnode.next.prev = newnode;
    79.                     this.length++;
    80.                 }
    81.  
    82.             }
    83.  
    84.             //3.移除指定位置的节点
    85.             removeAt(position) {
    86.                 //判断位置的合法性（越界判断）
    87.                 if (position < 0 || position > this.length - 1 || !Number.isInteger(position)) {
    88.                     return false
    89.                 }
    90.                 if (this.length == 0) {
    91.                     //空链表
    92.                     return
    93.                 } else {
    94.                     if (position == 0) {
    95.                         //移除头节点
    96.                         if (this.length == 1) {
    97.                             this.head = null
    98.                             this.tail = null
    99.                         } else {
    100.                             this.head = this.head.next
    101.                             this.tail.prev=this.head
    102.                             this.head.prev = this.head
    103.                         }
    104.                     } else if (position == this.length - 1) {
    105.                         //移除尾结点
    106.                         this.tail = this.tail.prev
    107.                         this.tail.next = this.head
    108.                         this.head.prev=this.tail
    109.                     } else {
    110.                         //移除中间任意位置的节点
    111.                         let current = this.head,
    112.                             index = 0
    113.                         while (index < position - 1) {
    114.                             current = current.next
    115.                             index++
    116.                         }
    117.                         current.next = current.next.next
    118.                         current.next.prev = current
    119.                     }
    120.                     this.length--
    121.                 }
    122.             }
    123.             
    124.             //4.查找指定元素的位置
    125.             indexOf(ele) {
    126.                 let current = this.head,
    127.                     index = 0
    128.                 while (index < this.length) {
    129.                     if (current.data == ele) {
    130.                         return index
    131.                     } else {
    132.                         current = current.next
    133.                         index++
    134.                     }
    135.                 }
    136.                 return -1
    137.             }
    138.  
    139.             //5.移除指定元素
    140.             remove(ele) {
    141.                 let index = this.indexOf(ele)
    142.                 this.removeAt(index)
    143.             }
    144.  
    145.             //6.正向遍历
    146.             forwardString() {
    147.                 let current = this.head,
    148.                     index = 0,
    149.                     str = "";
    150.                 while (index < this.length) {
    151.                     str += "-" + current.data
    152.                     current = current.next
    153.                     index++
    154.                 }
    155.                 return str.slice(1)
    156.             }
    157.             //7.反向遍历
    158.             reverseString() {
    159.                 let current = this.tail,
    160.                     index = this.length - 1,
    161.                     str = "";
    162.                 while (index >= 0) {
    163.                     str += "-" + current.data
    164.                     current = current.prev
    165.                     index--
    166.                 }
    167.                 return str.slice(1)
    168.             }
    169.         }
    170.         let clist = new DoubleCycleLinkList()
    171.         //向链表尾部添加元素
    172.         for (let i = 0; i < 9; i++) {
    173.             clist.append(i)
    174.         }
    175.         console.log(clist.forwardString(),"向链表尾部添加元素后的链表")
    176.  
    177.         //向链表中的3的位置插入元素
    178.         clist.insert(3,"newnode")
    179.         console.log(clist.forwardString(),"插入元素后的链表")
    180.  
    181.          //移除指定位置的元素
    182.          clist.removeAt(5)
    183.          console.log(clist.forwardString(),"移除位置为5的元素(4)的链表")
    184.     
    185.          //查找指定元素
    186.          console.log(clist.indexOf(4),"4已经被移除，不存在返回-1")
    187.          console.log(clist.indexOf(6),"6存在返回下标")
    188.  
    189.          //移除指定元素
    190.          clist.remove(8)
    191.          console.log(clist.reverseString(),"移除元素8后的反向遍历的链表")

    打印结果：

  • 相关阅读:
    力扣(LeetCode)42. 接雨水(C++)
    Python3 + Appium + 安卓模拟器实现APP自动化测试并生成测试报告
    力扣20-有效的括号——栈实现
    【C++】构造函数初始化列表 ① ( 类对象作为成员变量时的构造函数问题 | 构造函数初始化列表语法规则 )
    数学术语之源——平凡(trivial)与非平凡(nontrivial)
    剪辑过程中的思考与总结（持续更新ing）
    leetcode200题模式总结
    uniapp 选择地址
    进程间通信--信号
    软件安全性测试要点有哪些?常用软件安全测试工具分享
  • 原文地址：https://blog.csdn.net/qq_56668869/article/details/126498355