今日复习数据结构的单链表和双向循环链表的知识。

单链表

一、链表的基本信息

1、链表是以结点的方式存储的；

2、每个结点都包含一个data域（数据域）与一个next域（data域存储数据 next域指向下一个结点的位置）；

3、链表中每个结点的存储不一定是连续存储的；

4、链表分为带头结点的与不带头结点的。

单链表的逻辑结构图

二、头节点的作用

1、不存放具体的数据；

2、作用就是表示单链表头，此外next域指向第一个结点。

三、单链表的创建

1、步骤：

（1）创建一个单链表的结点对象类，内部至少要有一个数值变量与指向下一个结点的单链表结点对象（其实是结点对象的引用，作用是替代c语言中的指针）；

（2）创建一个对单链表进行遍历、添加、修改和删除等操作的工具类，用于对单链表进行操作；

（3）创建一个对单链表进行测试和运行的类。

单链表的结点对象

package 链表.单链表.链表的实现;
/**
 * 该类的作用是链表中的节点对象
 */
public class LinkedNode {
    int number;
    Object data;
    LinkedNode next;

    public LinkedNode() {
    }

    public LinkedNode(int number, Object data) {
        this.number = number;
        this.data = data;
    }

    @Override
    public String toString() {
        return "LinkedNode{" +
                "number=" + number +
                ", data=" + data +
                '}';
    }
}

工具类属性

public class SingleLinkedNode {
    LinkedNode headNode = null;//头节点
    int size;//单链表中有效结点的个数

    /**
     * 初始化头节点
     * @param headNode
     */
    public SingleLinkedNode(LinkedNode headNode) {
        this.headNode = headNode;
        this.size = 0;
    }
}

四、单链表的工具类

1、单链表的非空判断

（1）思路

当一个单链表为空时，单链表中只有一个头结点，所以单链表为空否的判断条件为 head.next == null。

（2）代码实现

/**
 * 判断单链表是否为空
 * @return
 */
public boolean isEmpty() {
    return headNode.next == null ? true : false;
}

2、单链表的遍历

（1）思路

判断链表是否为空（判断头节点的next域是否为空 head.next == null）；
非空创建一个临时结点对象引用（充当指针）；
使用while循环，输出结点对象（需要重写结点类中的toString（）方法），使用temp = temp.next移动单链表索引，相当于移动c语言中的指针。

（2）代码实现

/**
 * 遍历单链表
 */
public void traversal() {
    //判断单链表是否为空
    if (isEmpty()) System.out.println("该单链表为空！");

    //定义一个临时节点索引用于代替指针
    LinkedNode tempNode = headNode.next;
    for (int i = 0; i < size; i++) {
        System.out.println(tempNode);
        tempNode = tempNode.next;
    }
}

3、按照单链表的index查找结点

（1）思路

先判断该单链表是否非空，若非空则无需查找直接返回null；
检验要查询的index的值是否正确；
根据index的值使用for循环找到要相应位置处的结点对象然后返回。

（2）代码实现

/**
 * 根据位置查找节点是否存在，返回该位置的节点对象
 * @param index
 * @return
 */
public LinkedNode findByIndex(int index) {
    //判断单链表是否为空
    if (isEmpty()) {
        System.out.println("单链表为空！");
        return null;
    } else if (index == size) {
        //此时是单链表的最后一个元素,创建一个临时节点索引用于遍历单链表
        LinkedNode tempNode = headNode.next;
        for (int i = 0; i < index - 1; i++) {
            tempNode = tempNode.next;
        }
        return tempNode;
    } else if (index < 0 || index > size) {
        System.out.println("您输入的index有误！" + index);
        return null;
    } else if (index == 0){
      return headNode;
    } else {
        LinkedNode temp = headNode.next;
        for (int i = 0; i < index - 1; i++) {
            temp = temp.next;
        }
        //此时的temp指向的就是index处的节点对象
        return temp;
    }
}

4、单链表的添加(尾部)

（1）思路

创建一个结点对象引用,将头结点对象赋值给临时变量对象引用；
使用while循环找到单链表的最后一个结点（此处也可以使用findByIndex()方法找到最后结点对象）；
设置最后一个结点的next指向要加入的结点。

（2）代码实现

 /**
   * 向一个节点的末尾追加元素
   * @param number
   * @param obj
   */
  public void add(int number, Object obj) {
      //创建一个要加入的节点对象
      LinkedNode addNode = new LinkedNode(number, obj);
      //判断单链表是否为空,为空则直接将节点添加在头节点后方
      if (isEmpty()) {
          headNode.next = addNode;
          size++;
          return;
      }
/*
//也可以使用该方法得到单链表的最后一个结点对象
LinkedNode tempNode = findByIndex(size);
*/
      //创建一个临时节点变量，用于找到最后一个节点
      LinkedNode tempNode = headNode.next;
      while (tempNode.next != null) {
          tempNode = tempNode.next;
      }
      //此时已经找到了最后一个节点元素
      tempNode.next = addNode;
      //单链表中实际元素的个数加一
      size++;
  }

5、向单链表的头部添加结点对象

（1）思路

使用头结点即可完成；
先将头结点的next的值赋值给新加入结点的next值（addNode.next = head.next）;
再将新加入的结点赋值给头结点的next。

（2）代码实现

/**
 * 向单链表的头添加元素
 * @param number
 * @param obj
 */
public void addFirst(int number, Object obj) {
    //创建一个要加入的节点对象
    LinkedNode addNode = new LinkedNode(number, obj);
    //将头节点的next赋值给要加入的新节点的next
    addNode.next = headNode.next;
    //再将头节点的next指向新加入的节点
    headNode.next = addNode;
    //单链表中实际元素的个数加一
    size++;
}

6、向单链表的指定位置插入结点

（1）思路

先对 index 要插入的位置进行检测；
创建一个临时变量引用指向头结点，使用for循环循环遍历移动索引指向index位置的前一个结点对象；
之后的步骤和向链表头部添加结点对象一样，将新结点赋值给 index 的前一个结点的next，再将前一个结点的next指向新加入的结点即可。

（2）代码实现

/**
  * 在单链表的指定位置插入节点
  * @param index
  * @param number
  * @param obj
  */
 public boolean addByIndex(int index, int number, Object obj) {
     //创建一个要加入的节点对象
     LinkedNode addNode = new LinkedNode(number, obj);
     //判断插入的位置是否超过单链表实际长度
     if (index > size) {
         System.out.println("插入的位置有误！无法插入！");
         return false;
     }

     //先创建一个临时节点索引指向头节点的下一个节点
     LinkedNode tempNode = headNode.next;
     //使用for循环遍历单链表，找到要插入的位置的前一个节点
     for (int i = 0; i < index - 1; i++) {
         tempNode = tempNode.next;
     }
     //此时已经找到了要插入位置的前一个节点元素
     //让插入的节点指向原先在index位置的节点
     addNode.next = tempNode.next;
     //让擦汗如位置前的节点指向新加入的节点
     tempNode.next = addNode;
     size++;
     return true;
 }

7、删除指定位置的结点

（1）思路

先判断当前要删除的节点是否存在，即对index进行检测；
若存在则找到要删除结点的前一个结点；
让前一个结点的next指向要删除结点所指向的next即可。

（2）代码实现

/**
 * 根据节点的位置删除节点
 * @param index
 * @return
 */
public LinkedNode removerNodeByIndex(int index) {
    //判断单链表是否为空
    if (isEmpty()) {
        System.out.println("该单链表为空！无法删除！");
        return null;
    }

    //单链表是否存在要删除的元素
    LinkedNode delNode = findByIndex(index);
    if (delNode == null) {
        System.out.println("您要删除的元素不存在！");
        return null;
    }

    //循环单链表找到要删除元素的前一个节点
    LinkedNode tempNode;
    if (index == 1){
        tempNode = headNode;
    }else {
        tempNode = findByIndex(index - 1);
    }

    tempNode.next = tempNode.next.next;
    size--;
    return delNode;
}

8、修改指定位置的结点

（1）思路

同样是先判断要修改的结点是否存在；
若存在则找到当前要修改的节点，然后有两种做法，一种是直接根据传进来的参数修改当前结点的数据即可，另外一种则是根据传入的数据新创建一个结点对其进行交换即可，本次采用第二种方式进行修改；
第二种的修改方法，要新加入结点，先找到要修改的前一个结点。
将要修改结点的next的值赋值给要修改结点的next；
将修改结点的前一个结点的next指向新的结点即可。其实这几步的操作可以简单概括为先删除index位置的结点，再在index位置新加入一个结点即可。

（2）代码实现

/**
 * 根据位置信息修改节点
 * @param index
 * @param newNumber
 * @param obj
 * @return
 */
public LinkedNode updByIndex(int index, int newNumber, Object obj) {
    //先判断该元素是否存在
    LinkedNode oldUpdNode = findByIndex(index);
    if (oldUpdNode == null) {
        System.out.println("您要修改的元素不存在");
        return null;
    }
    //创建好要修改的节点对象
    LinkedNode updNode = new LinkedNode(newNumber, obj);
    //创建一个临时节点变量索引
    LinkedNode tempNode = headNode.next;
    //根据位置信息找到要修改元素的前一个元素
    for (int i = 0; i < index - 2; i++) {
        tempNode = tempNode.next;
    }
    updNode.next = tempNode.next.next;
    tempNode.next = updNode;
    return oldUpdNode;//返回修改前的结点信息
}

9、根据结点的编号对其进行排序

（1）思路

本次采用冒泡排序的方式对插入的结点进行排序；
先检测数组不为空则开始排序；
从第一个结点开始比较，当第一个结点的number值比后一个大时交换两个结点的位置。

（2）代码实现

//排序，根据number的值进行排序
  public boolean sort(){
      //判断链表是否为空！
      if (isEmpty()) {
          System.out.println("单链表为空！无法排序");
          return false;
      }
      //根据编号进行排序,考虑冒泡排序
      for (int i = 1; i <= size - 1; i++) {
          for (int j = 1; j <= size - i; j++) {
              LinkedNode temp0 = findByIndex(j - 1);//当index的值为0时，返回头结点
              LinkedNode temp1 = findByIndex(j);
              LinkedNode temp2 = findByIndex(j + 1);
              if (temp1.number > temp2.number) {
                  temp1.next = temp2.next;
                  temp2.next = temp1;
                  temp0.next = temp2;
              }
          }
      }
      return true;
  }

五、单链表总结

单链表在结构上十分简单，但在实际操作中却十分的繁琐，像是删除添加等情况时总是需要找到要操作结点的前一个结点才能操作。但是单链表在增删等方面却要比数组的效率高，数组在指定位置增加删除时需要前后移动剩余的元素，效率相对较低。但数组在查询和修改方面的效率要比链表的效率高，因为数组不需要遍历即可对索引位置的数据进行操作。但单链表却要每次遍历找到相应的结点。

而且在HashMap集合的底层实现中是数组加链表的形式实现的，为了解决HashMap中的Hash冲突所以在数组中存放的便是链表。

双向循环链表

一、双向循环链表的基本信息

1、双向循环链表相比于单链表，在结点对象的属性里又多了一个pre引用，该引用的作用与next引用的作用刚好相反，pre是指向当前节点的前一个结点的引用；

2、双向循环链表相比于单链表还是在逻辑上成一个环状的结构，双向循环链表的尾结点的nextt域不是null，而是指向头结点，头结点的pre指向的是尾结点。之后只要在头结点和尾结点之间进行对节点的增删改查操作即可，如此可不用担心会破坏双向循环链表的逻辑环状结构。

双向循环链表的结构图

二、双向循环链表的结点

1、结点的私有属性

public class DoubleLinkedNode {
    int number;//编号
    Object object;//数据域
    DoubleLinkedNode next;//下一个对象
    DoubleLinkedNode pre;//上一个对象
}

2、结点的初始化

//无参构造器
public DoubleLinkedNode() {
}
//带参构造器
public DoubleLinkedNode(int number, Object object) {
    this.number = number;
    this.object = object;
}

三、双向循环链表的工具类

1、工具类的私有属性与构造器

public class SingleLinkedNode {
    private DoubleLinkedNode headNode;//头节点
    private DoubleLinkedNode endNode;//尾结点
    private int size = 0;//链表中有效的结点个数

    /**
     * 成环，环形双向队列
     * @param headNode 头节点
     */
    public SingleLinkedNode(DoubleLinkedNode headNode) {
        this.headNode = headNode;
        endNode = new DoubleLinkedNode();
        this.headNode.next = endNode;
        endNode.pre = this.headNode;
        this.headNode.pre = endNode;
        endNode.next = this.headNode;
    }
}

2、双向循环链表的非空判断

（1）思路

由于该链表是循环的链表，所以head.next永远不可能为null；
需要借助size工具类的私有属性来判断，当 size == 0 时链表为null。

（2）代码实现

/**
 * 判断链表非空
 * 如果为空则返回true
 * @return 布尔类型
 */
public boolean isEmpty() {
    if (size == 0) {
        return true;
    } else {
        return false;
    }
}

3、双向循环链表的遍历

（1）思路

由于循环链表的特性，所以使用for循环取遍历链表较为合适；
先判断链表非空；
创建一个临时引用指向第一个实际元素结点，循环遍历size次，输出结点信息。

（2）代码实现

/**
 * 对双向链表进行遍历
 */
public void traversal() {
    if (isEmpty()) {
        System.out.println("单链表为空！");
        return;
    }
    DoubleLinkedNode temp = headNode.next;
    for (int i = 0; i < size; i++) {
        System.out.println(temp);
        temp = temp.next;
    }
}

4、根据位置索引查询结点信息

（1）思路

判断链表是否为空，为空则无需查找；
对index的数值进行校验；
当index == 0时返回头节点；
判断index的方位是在链表的前半部分还是后半部分，若是前半部分则从头结点开始遍历查找，反之则从尾结点开始查找。

（2）代码实现

/**
    * 根据index找相应的节点对象
    * @param index 查询的位置
    * @return 查询的结点
    */
   public DoubleLinkedNode findByIndex(int index) {
       if (index < 0 || index > size) {//
           System.out.println("您输入的位置索引有误！");
           return null;
       }
       if (index == 0) {//
           return headNode;
       }
       //如果要查找的位置在链表的前半部分则从头开始遍历
       //反之从尾部开始遍历
       if (index <= (size / 2)) {
           DoubleLinkedNode temp1 = headNode.next;
           for (int i = 1; i < index; i++) {
               temp1 = temp1.next;
           }
           return temp1;
       }else {
           DoubleLinkedNode temp2 = endNode.pre;
           for (int i = 1; i <= (size - index); i++) {
               temp2 = temp2.pre;
           }
           return temp2;
       }
   }

5、向双向循环链表的尾部添加结点

（1）思路

根据传入的参数创建一个新的结点对象；
创建一个临时变量引用，调用findByIndex()方法，让临时变量引用指向最后一个结点；
找到最后一个节点，让最后一个结点的next指向新加入的结点，让尾结点的pre也指向新加入的结点；
让新结点的pre指向原最后一个结点，让新结点的next指向尾结点。

（2）代码实现

/**
 * 向双向链表的末尾添加元素
 * @param number 新加入节点的编号
 * @param object 新加入结点存储的数据
 */
public void add(int number, Object object) {
    DoubleLinkedNode addNode = new DoubleLinkedNode(number, object);
    DoubleLinkedNode temp;
    temp = findByIndex(size);
    temp.next = addNode;
    addNode.next = endNode;
    addNode.pre = temp;
    endNode.pre = addNode;
    size++;
}

/**
 * 添加元素的方法重载
 * @param addNode 要加入的结点对象
 */
public void add(DoubleLinkedNode addNode) {
    add(addNode.number, addNode.object);
}

6、向双向循环链表的指定位置添加结点

（1）思路

先对要插入的index进行数值检测；
根据传入的参数创建要插入的结点；
创建一个临时结点变量引用；
找到要index位置处的结点对象让临时变量的引用指向该节点；
让新加入的结点的next指向index位置处的结点对象，；
使新加入结点的pre指向index位置处的结点对象的前一个结点。

（2）代码实现

/**
 * 在指定位置添加结点对象
 * @param index 要插入的位置
 * @param number 插入的编号
 * @param object 插入的数据域
 */
public void addByIndex(int index, int number, Object object) {
    if (size < index || index <= 0) {//对要插入的位置进行检查
        System.out.println("您插入的位置有误！");
        return;
    }
    DoubleLinkedNode addNode = new DoubleLinkedNode(number, object);
    DoubleLinkedNode temp = headNode.next;
    for (int i = 1; i < index; i++) {
        temp = temp.next;//找到要插入处的结点
    }
    addNode.pre = temp.pre;
    temp.pre.next = addNode;
    temp.pre = addNode;
    addNode.next = temp;
    size++;
}

/**
 * 在指定位置插入结点对象的方法重载
 * @param index
 * @param addNode
 */
public void addByIndex(int index,DoubleLinkedNode addNode){
    addByIndex(index,addNode.number,addNode.object);
}

7、向双向循环链表的头部添加结点

（1）思路

根据传入的参数创建一个新加入节点对象；
将头结点的next赋值给新加入结点的next，将第一个结点的pre指向新加入的结点；
将新加入的结点赋值给头结点的next，修改新加入的结点的pre为头结点。

（2）代码实现

/**
 * 在双向链表的开头添加元素
 * @param number
 * @param object
 */
public void addFirst(int number,Object object){
    DoubleLinkedNode addNode = new DoubleLinkedNode(number,object);
    addNode.next = headNode.next;
    headNode.next.pre = addNode;
    headNode.next = addNode;
    addNode.pre = headNode;
    size++;
}

/**
 * 向双向循环链表的开头添加元素的方法重载
 * @param addNode
 */
public void addFirst(DoubleLinkedNode addNode){
    addFirst(addNode.number,addNode.object);
}

8、删除指定位置的结点对象

（1）思路

先判断链表是否为空，若为空则结束运行；
调用findByIndex()方法找到要删除的结点对象，此时是对index进行了校验的，所以无需校验；
将要删除结点后一个结点赋值给删除节点的前一个结点的next，修改要删除结点后一个结点的pre为要删除结点的前一个结点。

（2）代码实现

/**
 * 根据位置信息删除结点，并将删除的结点对象返回
 * @param index
 * @return
 */
public DoubleLinkedNode removerByIndex(int index){
    if (isEmpty()) {
        System.out.println("双向链表为空！无法删除！");
        return null;
    }

    DoubleLinkedNode delNode = findByIndex(index);//找到要删除的结点
    delNode.next.pre = delNode.pre;
    delNode.pre.next = delNode.next;
    size--;
    return delNode;
}

9、删除双线链表的头结点

（1）思路

先判断链表非空，若为空则无法删除；
创建一个临时结点引用指向要删除的结点对象；
修改头结点与要删除节点的后一个结点的next与pre指向对象即可；

（2）代码实现

/**
 * 删除双向循环链表的开头结点
 * @return
 */
public DoubleLinkedNode removerFirst(){
    if (isEmpty()) {
        System.out.println("链表为空！无法删除");
        return null;
    }
    DoubleLinkedNode delNode = headNode.next;
    headNode.next.next.pre = headNode;
    headNode.next = headNode.next.next;
    size--;
    return delNode;
}

10、根据索引修改指定位置的结点对象

（1）思路

使用findByIndex()方法找到要修改的那个结点对象，findByIndex（）方法已经对index进行校验了所以无需再次校验；
对找到的结点进行判断，若为null则说明要删除的结点对象不存在；
若存在则修改找到的结点的number与object。

（2）代码实现

/**
 * 修改指定位置的结点内容
 * @param index
 * @param number
 * @param object
 * @return
 */
public DoubleLinkedNode updByIndex(int index,int number,Object object){
    DoubleLinkedNode updNode = findByIndex(index);//获取到要修改的那个结点
    if (updNode == null) {
        return null;
    }
    DoubleLinkedNode temp = updNode;
    updNode.number = number;
    updNode.object = object;
    return temp;
}

/**
 * 修改方法的方法重载
 * @param index
 * @param newNode
 * @return
 */
public DoubleLinkedNode updByIndex(int index,DoubleLinkedNode newNode){
    return updByIndex(index,newNode.number,newNode.object);
}

11、对双向循环链表进行排序

（1）思路

先对链表判断是非空，若链表为空则无法排序；
本次选择使用快速选择排序的算法进行排序；
该算法的排序思路是每次遍历找到最小的那个节点的索引放在链表的前端和次前端。

（2）代码实现

//练习测试排序
public boolean sort(){
    if (isEmpty()) {
        System.out.println("链表为空，无法排序！");
        return false;
    }
    //本次选择快速选择排序
    int minIndex;//每次循环遍历找到的最小结点编号的索引值
    DoubleLinkedNode temp = null;//主要用于后移结点指针
    DoubleLinkedNode minNode = null;//用于指向每次遍历找到的编号值最小的结点对象
    DoubleLinkedNode temp1 = null;//与每次找到的最小的结点对象交换的结点对象
    for (int i = 1; i <= size; i++) {
        temp1 = minNode = findByIndex(i);//初始化赋值
        minIndex = i;//初始化赋值
        for (int j = i + 1; j <= size; j++) {//先从第i个节点的后一个结点开始与minNode进行比较
            temp = findByIndex(j);
            if (minNode.number > temp.number) {//如果找到了满足条件的结点对象则修改变量的值
                minIndex = j;
                minNode = temp;
            }
            temp = temp.next;//后移指针
        }
        int number = temp1.number;//用于存储其中一个交换节点的编号值
        Object object = temp1.object;//用于存储其中一个交换节点的数据域值
        updByIndex(i,minNode);//调用修改指定位置结点的方法
        updByIndex(minIndex,number,object);//同样调用修改指定位置结点的方法
    }
    return true;
}

四、双向循环链表的总结

双向循环链表的结构虽然比单链表要复杂一些，但在实际的操作中却要比单链表方便很多。因为双向链表不需要再像单链表一样始终要去寻找前一个结点，双向链表只需要找到相应要操作的结点即可完成对应的操作。

在LinkedList集合底层实现时，所使用的就是双向循环链表。

约瑟夫问题（josephu）

一、约瑟夫环基本介绍

1、简介

设编号为1，2，….n的n个人围成一个环坐在一起，约定编号为k的人（1 <= k <= n）的人从1开始报数，数到m的那个人出列，他的下一个位又从1开始报数，数到m的人再次出列，一次类推，直到所有人出列为止，由此产生一个出队的编号序列。

2、示意图

（1）初始状态

（2）出队列结束后的示意图

二、实现方式

1、实现技术方式

采用双向循环链表的方式实现约瑟夫问题

2、实现代码

/**
     * 约瑟夫问题实现
     * @param n 链表中结点的总数
     * @param k 从第几号结点开始
     * @param m 数几个结点
     * @return
     */
    public String josephu(int n,int k,int m) {
        //对传入的参数进行检查
        if (n <= 0 || k <= 0 || m <= 0) {
            System.out.println("您输入的参数有误！");
            return null;
        }
        //清除链表中的数据,需保证链表中无其他数据
        for (int i = 0; i < size; i++) {
            removerFirst();
        }
        //根据传入的参数创建双向循环链表
        //传入参数
        for (int i = 1; i <= n; i++) {
            add(i,null);
        }
        //创建一个辅助引用
        DoubleLinkedNode temp = headNode.next;//从第一个结点开始
        //从k号位置开始
        for (int i = 0; i < k -1; i++) {
            temp = temp.next;
        }
        StringBuilder str = new StringBuilder();
        //每过m个结点弹出一个结点对象
        while (size > 0){
            for (int i = 0; i < m - 1; i++) {
                temp = temp.next;
            }//此时temp所指的结点就是要出队列的结点
            //但此时需要判断，去掉头尾结点
            while (temp.number == 0){//头尾结点的number的值为0，当number的值不为0时则不循环
                temp = temp.next;//移动第一个实际结点
            }//此处只要判断到temp.number == 0，就可以调用findByIndex方法直接赋值给temp = findByIndex(1)
            if (size != 1) {
                str.append(temp.number + " -> ");
            }else {
                str.append(temp.number);
            }
            //出队列
            temp.pre.next = temp.next;
            temp.next.pre = temp.pre;
            temp = temp.next;//此时没有引用再指向出队列的结点对象，过后会被垃圾回收车回收
            size--;
        }
        return str.toString();
    }

3、测试代码

public static void main(String[] args) {
       DoubleLinkedNode headNode = new DoubleLinkedNode();//创建一个头结点
       SingleLinkedNode node = new SingleLinkedNode(headNode);//传入双向循环链表的工具类
       String josephu = node.josephu(5, 1, 2);//传入参数
       System.out.println(josephu);//运行结果为：2 -> 4 -> 1 -> 5 -> 3
   }

数据结构（二）链表、双向循环链表

单链表

一、链表的基本信息

二、头节点的作用

三、单链表的创建

1、步骤：

四、单链表的工具类

1、单链表的非空判断

（1）思路

（2）代码实现

2、单链表的遍历

（1）思路

（2）代码实现

3、按照单链表的index查找结点

（1）思路

（2）代码实现

4、单链表的添加(尾部)

（1）思路

（2）代码实现

5、向单链表的头部添加结点对象

（1）思路

（2）代码实现

6、向单链表的指定位置插入结点

（1）思路

（2）代码实现

7、删除指定位置的结点

（1）思路

（2）代码实现

8、修改指定位置的结点

（1）思路

（2）代码实现

9、根据结点的编号对其进行排序

（1）思路

（2）代码实现

五、单链表总结

双向循环链表

一、双向循环链表的基本信息

二、双向循环链表的结点

1、结点的私有属性

2、结点的初始化

三、双向循环链表的工具类

1、工具类的私有属性与构造器

2、双向循环链表的非空判断

（1）思路

（2）代码实现

3、双向循环链表的遍历

（1）思路

（2）代码实现

4、根据位置索引查询结点信息

（1）思路

（2）代码实现

5、向双向循环链表的尾部添加结点

（1）思路

（2）代码实现

6、向双向循环链表的指定位置添加结点

（1）思路

（2）代码实现

7、向双向循环链表的头部添加结点

（1）思路

（2）代码实现

8、删除指定位置的结点对象

（1）思路

（2）代码实现

9、删除双线链表的头结点

（1）思路

（2）代码实现

10、根据索引修改指定位置的结点对象

（1）思路

（2）代码实现

11、对双向循环链表进行排序

（1）思路

（2）代码实现

四、双向循环链表的总结

约瑟夫问题（josephu）

一、约瑟夫环基本介绍

1、简介

2、示意图

二、实现方式

1、实现技术方式

2、实现代码