数据结构--循环链表

循环链表特点：尾结点和头节点连接，构成环

• 单向循环环链表特点：尾结点指向头节点，构成环

• 双向循环环链表特点：每个结点双向连接，尾结点和头节点双向连接，构成环

循环环链表典型例子：约瑟夫问题（以下使用单向循环链表实现）

• 问题描述：有n个小孩围成一圈，给他们依次编号为k（1<=k<=n），从编号为1的小孩开始报数，数到第m个小孩出列，然后从出列的下一个小孩重新开始报数，数到第m个小孩又出列，…，如此反复直到所有的小孩全部出列为止，求整个出列序列。
  如当n=6，m=5时的出列序列是5，4，6，2，3，1。

• 解决思路：用一个不带头结点的循环链表来处理约瑟夫问题

  先构成一个有n个结点的循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数， 直到最后一个结点从链表中删除算法结束。

1. 定义小孩结点类（定义单向循环链表结点类）

   public class Boy {
       int no;//编号
       Boy next;//指向下一个小孩
   
       public Boy(int no) {
           this.no = no;
       }
   }

2. 定义小孩结点围成的环（定义单向循环链表类）

   public class CircularLinkList	{  
       Boy first;
   }

3. 方法实现

• 把小孩添加进环（添加结点进单向循环链表）

  /**
  num 小孩编号
  **/
  public void addBoy(int num) {
      if (num < 1) {
          System.out.println("输入的num值不正确，请重新输入");
          return;
      }
      Boy curBoy = null;//辅助指针
      for (int i = 1; i <= num; i++) {
          Boy boy = new Boy(i);
          //先形成单向列表
          if (i == 1) {
              first = boy;//指向第一个小孩，方便最后一个节点指向第一个，形成环状
              first.next = first;//与自己形成环状
              curBoy = first;
          } else {
              curBoy.next = boy;//链接下一个节点
              boy.next = first;//形成环状
              curBoy = boy;//curBoy下移
          }
      }
  }

• 小孩报数出队列（删除结点）

  /**
  * 思路：定义一个辅助指针，置于first前一个节点，数count下，两指针一起移动count-1次，因为自己需数一下，first指向的即是需要出列的小孩
  *
  * @param being 从第几个小孩开始数
  * @param count 数多少下
  */
  public void countBoy(int being, int count) {
      if (being < 1||first==null) {
          System.out.println("输入的数据错误");
          return;
      }
      Boy temp=first;
      //先把temp指向最后一个节点
      while (true) {
          if (temp.next==first) {//最后
              break;
          }
          temp=temp.next;
      }
      //到达开始数数的位置
      for (int i =0; i < being-1; i++) {
          first=first.next;
          temp=temp.next;
      }
      while (true){
          if (first==temp){//只有一个小孩
              break;
          }
          //数count-1下
          for (int i =0; i < count-1; i++) {
              first=first.next;
              temp=temp.next;
          }
          System.out.println(first.no);
          //小孩出圈（删除小孩）
          first=first.next;//first下移
          temp.next=first;//temp的next域指向first
      }
      System.out.println(first.no);//最后小孩的编号
  }

• 打印出队编号序列（遍历单向循环链表）

  public void list() {
      Boy curBoy = first;
      if (first == null) {
          System.out.println("链表为空");
          return;
      }
      while (true) {
          System.out.println("小孩编号：" + curBoy.no);
          if (curBoy.next == first) {//到最后
              break;
          }
          curBoy = curBoy.next;
      }
  }

---

顺序表和链表比较：

• 顺序表的存储密度为1，而链表的存储密度小于1。仅从存储密度看，顺序表的存储空间利用率高。（存储密度=结点中数据本身占用的存储量/整个结点占用的存储量）（存储密度越大，存储空间的利用率就越高）

• 顺序表需要预先分配空间，所以数据占用一整片地址连续的内存空间，如果分配的空间过小，易出现上溢出，需要扩展空间导致大量元素移动而降低效率；如果分配的空间过大，会导致空间空闲而浪费。而链表的存储空间是动态分配的，只要内存有空闲，就不会出现上溢出。

结论：当线性表的长度变化不大，易于事先确定的情况下，为了节省存储空间，宜采用顺序表作为存储结构。当线性表的长度变化较大，难以估计其存储大小时，为了节省存储空间，宜采用链表作为存储结构。

• 顺序表具有随机存取特性，给定序号查找对应的元素值的时间为O(1)，而链表不具有随机存取特性，只能顺序访问，给定序号查找对应的元素值的时间为O(n)。

• 在顺序表中插入和删除操作时，通常需要平均移动半个表的元素。而在链表中插入和删除操作仅仅需要修改相关结点的指针成员，不必移动结点。

结论：若线性表的运算主要是查找，很少做插入和删除操作，宜采用顺序表作为存储结构。若频繁地做插入和删除操作，宜采用链表作为存储结构。

---

Java 链表

LinkedList

继承关系：

• Iterator 接口：主要用于遍历输出

  • Collection接口
    • List接口：存储有序的、可重复的数据
      • LinkedList 类

• Iterator 接口

  • Collection接口
    • Queue接口：队列
      • Deque接口：双端队列
        • LinkedList 类

特点：线程不安全；对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储，可加入null。实现了Deque接口，可做为双端队列使用。

底层源码分析：LinkedList list = new LinkedList();

• 内部声明了Node类型的first和last属性，默认值为null

• list.add(123);//将123封装到Node中，创建了Node对象。

• 其中，Node定义为：

  private static class Node<E> {
      E item;
      Node<E> next;
      Node<E> prev;
  
      Node(Node<E> prev, E element, Node<E> next) {
          this.item = element;
          this.next = next;
          this.prev = prev;
      }
  }

体现了LinkedList的双向链表的说法

常用方法：

• 增:

  • public boolean add(E e)，链表末尾添加元素，返回是否成功；
  • public void add(int index, E element)，向指定位置插入元素；
  • public boolean addAll(Collection<? extends E> c)，将一个集合的所有元素添加到链表后面，返回是否成功；
  • public boolean addAll(int index, Collection<? extends E> c)，将一个集合的所有元素添加到链表的指定位置后面，返回是否成功；
  • public void addFirst(E e)，添加到第一个元素；
  • public void addLast(E e)，添加到最后一个元素；
  • public boolean offer(E e)，向链表末尾添加元素，返回是否成功；
  • public boolean offerFirst(E e)，头部插入元素，返回是否成功；
  • public boolean offerLast(E e)，尾部插入元素，返回是否成功；

• 删:

  • public void clear()，清空链表；
  • public E removeFirst()，删除并返回第一个元素；
  • public E removeLast()，删除并返回最后一个元素；
  • public boolean remove(Object o)，删除某一元素，返回是否成功；
  • public E remove(int index)，删除指定位置的元素；
  • public E poll()，删除并返回第一个元素；
  • public E remove()，删除并返回第一个元素；

• 查:

  • public boolean contains(Object o)，判断是否含有某一元素；
  • public E get(int index)，返回指定位置的元素；
  • public E getFirst(), 返回第一个元素；
  • public E getLast()，返回最后一个元素；
  • public int indexOf(Object o)，查找指定元素从前往后第一次出现的索引；
  • public int lastIndexOf(Object o)，查找指定元素最后一次出现的索引；
  • public E peek()，返回第一个元素；
  • public E element()，返回第一个元素；
  • public E peekFirst()，返回头部元素；
  • public E peekLast()，返回尾部元素；

• 改:

  • public E set(int index, E element)，设置指定位置的元素；

• 其他:

  • public Object clone()，克隆该列表；
  • public Iterator< E > descendingIterator()，返回倒序迭代器；
  • public int size()，返回链表元素个数；
  • public ListIterator< E > listIterator(int index)，返回从指定位置开始到末尾的迭代器；
  • public Object[] toArray()，返回一个由链表元素组成的数组；
  • public< T > T[] toArray(T[] a)，返回一个由链表元素转换类型而成的数组；

---

ArrayList 类和 LinkedList 类的比较

• ArrayList 与 LinkedList 都是 List 接口的实现类，因此都实现了 List 的所有未实现的方法，只是实现的方式有所不同

• ArrayList 是基于动态数组数据结构的实现，访问元素速度优于 LinkedList。LinkedList 是基于链表数据结构的实现，占用的内存空间比较大，但在批量插入或删除数据时优于 ArrayList

• 对于快速访问对象的需求，使用 ArrayList 实现执行效率上会比较好。需要频繁向集合中插入和删除元素时，使用 LinkedList 类比 ArrayList 类效果高

---

• 本文作者： zzr
• 本文链接： http://zzruei.github.io/2023/02e8ec18c0.html
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！