devbox
一键难忘520
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java数据结构-循环链表的设计与实现(头歌平台，详细注释)_循环链表java

作者：一键难忘520 | 2024-07-14 04:07:19

赞

踩

循环链表java

目录

第1关：单循环链表的实现—链表的添加、遍历

任务描述

相关知识

单循环链表

添加操作

遍历循环链表

代码： 

第2关：单循环链表的实现—链表的删除

任务描述

相关知识

单循环链表删除操作

代码：  

第3关：双向循环链表的实现—链表的插入

任务描述

相关知识

双向循环链表

双向链表结点表示

双向循环链表图示

双向循环链表添加操作

代码：  

第4关：双向循环链表的实现—链表的删除

任务描述

相关知识

双向循环链表的删除操作

代码：  

单链表：由左到右指向，左指右，单向的

双链表：由左到右指向，左指右，又有由右到左指向，右指左，双向的

第1关：单循环链表的实现—链表的添加、遍历

任务描述

在操作单链表时，我们有时希望从单链表中的任一结点出发都能遍历整个链表，但对于单链表来说，只有从头结点开始才能扫描表中的全部结点。因此我们需要改动链表，使其首尾相接，这样就能满足我们的需求。

本关任务：完成带头结点的单循环链表的添加功能，遍历链表并输出。

相关知识
单循环链表

循环链表是一种首尾相接的链表。其特点是无需增加存储量，只需对表的链接方式稍作改变，即可使得表操作更加方便灵活。

在单链表中，将末尾结点的指针域null改为指向表头结点或开始结点，就得到单链形式的循环链表，称为单循环链表。

为使空表和非空表的处理方式一致，循环链表中也可以设置一个头结点。这样空循环链表仅有一个自成循环的头结点。 如下图：

添加操作

单循环链表的添加操作与普通的单链表操作类似，只需添加时注意处理尾结点，使其指向头结点。下面是添加操作示意图。

这里采用的是尾插法，即在链表的末尾添加结点。我们使tail指向链表尾结点，因此添加结点node时只需改动tail和新结点node之间的链接关系即可。由于有头结点，所以空表和非空表的处理方式是一样的。

 
 
  1. node.next=tail.next;
  2. tail.next=node;
  3. tail=node;
 
 
遍历循环链表
 
 
在循环链表中，链表的尾结点不是指向null。因此要输出链表元素时，其终止条件就不再是像非循环链表那样判断p==null或p.next==null，而是判别它们是否等于某一指定结点，如头结点head。如下图所示：
 
 
 
 
 

 

代码： 
 

  1. package step1;
  2.  
  3. /**
  4.  * Created by sykus on 2018/1/15.
  5.  */
  6. public class MyCircleLinkedList {
  7.     private Node head;//头结点, 不存数据
  8.     private Node tail;//尾结点, 指向链表的最后一个节点
  9.     private int size;
  10.  
  11.     public MyCircleLinkedList() {
  12.         head = new Node(Integer.MIN_VALUE, null);
  13.         head.next = head;
  14.         tail = head;
  15.         size = 0;
  16.     }
  17.  
  18.     /**
  19.      * 添加到链表尾部
  20.      *
  21.      * @param item
  22.      */
  23.     public void add(int item) {
  24.         /********** Begin *********/
  25.         //添加到链表尾部
  26.         Node newNode = new Node(item, null);//创建新结点，并赋元素
  27.         newNode.next=tail.next;//让新结点指向当前尾结点的下一个结点(即头结点)(即循环单链表的最后一个结点需要指向头结点)
  28.         tail.next=newNode;//让尾结点指向新结点
  29.         tail=newNode;//让新结点变为尾结点
  30.         size++;//元素个数+1
  31.  
  32.         /********** End *********/
  33.     }
  34.  
  35.     /**
  36.      * 遍历链表并输出元素
  37.      */
  38.     public void output() {
  39.         /********** Begin *********/
  40.         //遍历链表并输出元素
  41.         Node n = head;//保存头结点
  42.         while (n.next!= head) {//因为循环单链表尾部指向头，所以不为头则代表还没遍历完元素
  43.         n = n.next;//让n变为当前结点
  44.         System.out.println(n.item);//输出每个被遍历的元素
  45.         }
  46.         /********** End *********/
  47.     }
  48.  
  49.     public boolean isEmpty() {
  50.         return head.next == head;
  51.     }
  52.  
  53.     public int size() {
  54.         return size;
  55.     }
  56.  
  57.     //结点内部类
  58.     private static class Node {
  59.         int item;
  60.         Node next;
  61.  
  62.         Node(int item, Node next) {
  63.             this.item = item;
  64.             this.next = next;
  65.         }
  66.     }
  67. }
 

 
 
 
 
以下是测试样例：
 
 
测试输入：2 0 5 1 1
 
 
预期输出：
 
 
  1. 2
  2. 0
  3. 5
  4. 1
  5. 1
 

 

第2关：单循环链表的实现—链表的删除
 

 
 
任务描述
 
 
在上一关，我们已经完成了单循环链表的添加、遍历功能，我们已经可以向表中添加数据并输出，现在我们将要实现其删除功能。
 
 
本关任务：删除循环链表中指定位置的结点，并返回其值。
 
 
相关知识
 
 
单循环链表删除操作
 
 
单循环链表的删除操作与普通的单链表操作基本类似，通过遍历找到要删除结点的直接前驱，然后改变前驱的链接情况。如下图：
 
 
 
 
 
 
这里删除的是尾结点，由于我们在构建单循环链表时是用tail指向尾结点的，所以在删除尾结点后需改变tail的指向，如果删除的不是尾结点则不需改变tail指向。
 

 

代码：  
 

  1. package step2;
  2.  
  3. /**
  4.  * Created by sykus on 2018/1/15.
  5.  */
  6. public class MyCircleLinkedList {
  7.     private Node head;//头结点, 不存数据
  8.     private Node tail;//尾结点, 指向链表的最后一个节点
  9.     private int size;
  10.  
  11.     public MyCircleLinkedList() {
  12.         head = new Node(Integer.MIN_VALUE, null);
  13.         head.next = head;
  14.         tail = head;
  15.         size = 0;
  16.     }
  17.  
  18.     /**
  19.      * 添加到链表尾部
  20.      *
  21.      * @param item
  22.      */
  23.     public void add(int item) {
  24.         Node node = new Node(item, tail.next);
  25.         tail.next = node;
  26.         tail = node;
  27.         ++size;
  28.  
  29.     }
  30.  
  31.     /**
  32.      * 遍历链表并输出元素
  33.      */
  34.     public void output() {
  35.         Node p = head;
  36.         while (p.next != head) {
  37.             p = p.next;
  38.             System.out.println(p.item);
  39.         }
  40.     }
  41.  
  42.  
  43.     /**
  44.      * 删除从头结点开始的第index个结点
  45.      * index从0开始
  46.      *
  47.      * @param index
  48.      * @return
  49.      */
  50.     public int remove(int index) {
  51.         checkPosIndex(index);
  52.  
  53.         /********** Begin *********/
  54.         //删除从头结点开始的第index个结点
  55.         //index从0开始
  56.         Node n = head;//保存头结点
  57.         for(int i=0;i<index;i++){//寻找要删除的结点的前一个结点
  58.         n = n.next;//保存当前结点
  59.         }
  60.         Node del = n.next;//保存要删除的结点
  61.         n.next = del.next;//将要删除的结点的前一个结点的指向，指向要删除的结点的下一个结点
  62.         --size;//元素个数-1
  63.         return del.item;//返回删除元素
  64.         /********** End *********/
  65.     }
  66.  
  67.     public boolean isEmpty() {
  68.         return head.next == head;
  69.     }
  70.  
  71.     public int size() {
  72.         return size;
  73.     }
  74.  
  75.     private void checkPosIndex(int index) {
  76.         if (index < 0 || index >= size) {
  77.             throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  78.         }
  79.     }
  80.  
  81.     //结点内部类
  82.     private static class Node {
  83.         int item;
  84.         Node next;
  85.  
  86.         Node(int item, Node next) {
  87.             this.item = item;
  88.             this.next = next;
  89.         }
  90.     }
  91. }
  92.  
 

 
 
 
 
预期输入：2 0 5 1 1 预期输出：
 
 
  1. 0
  2. 2
  3. 5
  4. 1
  5. 1
 

 

第3关：双向循环链表的实现—链表的插入
 

 
 
任务描述
 
 
在单链表中，当我们要访问某一个结点的前驱结点时，要从头结点开始遍历；要删除链表中的一个结点时，仅给出该结点的指针还不行；在指定结点前插入一个新结点，同样需要从头开始遍历。对于这些问题，双向循环链表可以解决。
 
 
本关任务：实现双向循环链表的添加功能。
 
 
相关知识
 
 
双向循环链表
 
 
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
 
 
双向链表结点表示
 
 
双向链表中的结点由三个域组成，两个链接域一个数据域，如下图：
 
 
 
 
 
 
prev链接域指向结点的直接前驱，next链接域链接该结点的直接后继。
 
 
双向循环链表图示
 
 
下图是带头结点head的双向循环链表示意图：
 
 
 
 
 
 
双向循环链表添加操作
 
 
双向循环链表的添加操作示意图如下：
 
 
 
 
 

 

代码：  
 

  1. package step3;
  2.  
  3. /**
  4.  * Created by sykus on 2018/1/15.
  5.  */
  6. public class MyDoubleLinkedList {
  7.  
  8.     private Node head;//头结点
  9.     private Node tail;//指向链表的尾结点
  10.     private int size;
  11.  
  12.     public MyDoubleLinkedList() {
  13.         head = new Node(null, Integer.MIN_VALUE, null);
  14.         head.next = head.prev = head;
  15.         tail = head;
  16.         size = 0;
  17.     }
  18.  
  19.     /**
  20.      * 添加元素到表尾
  21.      *
  22.      * @param item
  23.      */
  24.     public void add(int item) {
  25.  
  26.         /********** Begin *********/
  27.         //添加元素到表尾
  28.         Node newNode = new Node(null, item, null);//创建新结点，并赋元素
  29.         tail.next = newNode;//尾结点指向新结点
  30.         newNode.prev = tail;//新结点的前一个结点指向此时的尾结点(因为为双向链表)
  31.         newNode.next = head;//新结点指向头结点(因为为循环链表)
  32.         head.prev = newNode;//头结点的前一个结点指向新结点(同理)
  33.         tail = newNode;//将尾结点变为新结点
  34.         ++size;//元素+1
  35.         /********** End *********/
  36.  
  37.     }
  38.  
  39.     /**
  40.      * 打印双向链表
  41.      *
  42.      * @param flag true从左向右顺序打印, false从右向左顺序打印
  43.      */
  44.     public void printList(boolean flag) {
  45.         Node f = head;
  46.         if (flag) {//向右
  47.             while (f.next != head) {
  48.                 f = f.next;
  49.                 System.out.print(f.item + " ");
  50.             }
  51.         } else {//向左
  52.             while (f.prev != head) {
  53.                 f = f.prev;
  54.                 System.out.print(f.item + " ");
  55.             }
  56.         }
  57.     }
  58.  
  59.     public int size() {
  60.         return size;
  61.     }
  62.  
  63.     //结点内部类
  64.     private static class Node {
  65.         int item;
  66.         Node next;//直接后继引用
  67.         Node prev;//直接前驱引用
  68.  
  69.         Node(Node prev, int item, Node next) {
  70.             this.prev = prev;
  71.             this.item = item;
  72.             this.next = next;
  73.         }
  74.     }
  75. }
 

 
 
测试输入：1 2 3 4 5 预期输出：
 
 
  1. 1 2 3 4 5
  2. 5 4 3 2 1
 

 

第4关：双向循环链表的实现—链表的删除
 

 
 
任务描述
 
 
上一关实现了双向循环链表的添加功能，可以向表中添加元素，现在实现双向循环链表的删除功能。
 
 
本关任务：在上一关的基础上，实现双向循环链表的删除功能。
 
 
相关知识
 
 
双向循环链表的删除操作
 
 
双向循环链表的删除操作示意图如下：
 
 
 
 
 

 

代码：  
 

  1. package step4;
  2.  
  3. /**
  4.  * Created by sykus on 2018/1/15.
  5.  */
  6. public class MyDoubleLinkedList {
  7.  
  8.     private Node head;//头结点
  9.     private Node tail;//指向链表的尾结点
  10.     private int size;
  11.  
  12.     public MyDoubleLinkedList() {
  13.         head = new Node(null, Integer.MIN_VALUE, null);
  14.         head.next = head.prev = head;
  15.         tail = head;
  16.         size = 0;
  17.     }
  18.  
  19.     /**
  20.      * 添加元素到表尾
  21.      *
  22.      * @param item
  23.      */
  24.     public void add(int item) {
  25.         Node newNode = new Node(null, item, null);
  26.         tail.next = newNode;
  27.         newNode.prev = tail;
  28.         newNode.next = head;
  29.         head.prev = newNode;
  30.         tail = newNode;
  31.         ++size;
  32.     }
  33.  
  34.     /**
  35.      * 删除指定位置index出的结点，并返回其值
  36.      *
  37.      * @param index
  38.      * @return
  39.      */
  40.     public int remove(int index) {
  41.         checkPosIndex(index);//
  42.  
  43.         /********** Begin *********/
  44.          Node n = head;//保存头结点
  45.         for(int i=0;i<index;i++){//寻找要删除的结点的前一个结点
  46.         n = n.next;//将当前结点保存
  47.         }
  48.         Node del=n.next;//保存要删除的结点
  49.         Node nextnode=del.next;//保存要删除的结点的下一个       
  50.         n.next=nextnode;//将当前要删除的结点的前一个结点的指向，指向要删除的结点的下一个结点
  51.         nextnode.prev=n;//将上述结点的前一个结点指向，n为要删除的结点的前一个结点(即双链表需要连接前面的结点)
  52.         return del.item;//返回要删除的结点
  53.         /********** End *********/
  54.     }
  55.  
  56.     /**
  57.      * 打印双向链表
  58.      *
  59.      * @param flag true从左向右顺序打印, false从右向左顺序打印
  60.      */
  61.     public void printList(boolean flag) {
  62.         Node f = head;
  63.         if (flag) {//向右
  64.             while (f.next != head) {
  65.                 f = f.next;
  66.                 System.out.print(f.item + " ");
  67.             }
  68.         } else {//向左
  69.             while (f.prev != head) {
  70.                 f = f.prev;
  71.                 System.out.print(f.item + " ");
  72.             }
  73.         }
  74.     }
  75.  
  76.     public int size() {
  77.         return size;
  78.     }
  79.  
  80.     private void checkPosIndex(int index) {
  81.         if (index < 0 || index >= size) {
  82.             throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  83.         }
  84.     }
  85.  
  86.     //结点内部类
  87.     private static class Node {
  88.         int item;
  89.         Node next;//直接后继引用
  90.         Node prev;//直接前驱引用
  91.  
  92.         Node(Node prev, int item, Node next) {
  93.             this.prev = prev;
  94.             this.item = item;
  95.             this.next = next;
  96.         }
  97.     }
  98. }
 

 
 
 
 
预期输入：1 2 3 4 5 预期输出：
 
 
  1. 2 3 4 5 
  2. 5 4 3 2 
 

 


                

        
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/823066
推荐阅读
相关标签
Copyright ©  2003-2013 www.wpsshop.cn  版权所有，并保留所有权利。

  
闽ICP备14008679号