二、线性表

一、线性表的概述

1、线性表的概念

线性表属于最基本、最简单、也是最常用的一种数据结构，从逻辑上划分它属于线性结构。一个线性表是由n个相同特性的数据元素组成的有限序列，数据元素之间有一种线性的或“一对一”的逻辑关系。

线性表应该满足下面三个要求：

• 第一个数据元素没有直接前驱，这个数据元素被称为开始结点。

• 最后一个数据元素没有直接后继，这个元素被称为终端结点。

• 除了第一个和最后一个数据元素外，其它数据元素有且仅有一个直接前驱和一个直接后继。

线性表特点：

• 顺序性：在线性表中，相邻数据元素之间存在序偶关系，也就是存在着先后关系。

• 相同数据类型：在线性表中，每一个元素都属于相同数据类型。相同数据类型意味着在内存中存储时，每个元素会占用相同的内存空间，便于后续的查询定位。

• 有序性：在线性表中，数据元素的个数$n$就是为线性表的长度，$n$是一个有限值。当$n=0$时线性表为空表。在非空的线性表中每个数据元素在线性表中都有唯一确定的序号，例如第一个元素的序号是$0$，第$i$个元素的序号为$i-1$。在一个具有$n>0$个数据元素的线性表中，数据元素的序号范围是$[0,n-1]$。

2、线性表的存储结构

1、顺序存储结构（顺序表）：顺序表是采用一组地址连续的存储单元来依次存放线性表中的各个元素。

2、链式存储结构（链表）：链表中存储元素的地址不一定是连续的，元素结点中存放数据元素以及相邻元素的地址信息。

二、顺序表

1、顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

2、顺序表的特点

• 随机访问元素，即通过首地址和元素索引可在时间$O(1)$内找到指定的元素。

• 存储密度高，每个结点只存储数据元素。

• 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

3、根据索引查询元素的特点

创建一个int类型的arr数组，存放6个元素，每个元素都是int类型，也就是每个元素所占的存储空间都是4个字节。假设元素首地址为0x1000，那么每个元素的存储地址等于上一个元素的存储地址加上元素所占用的字节数。时间复杂度为O(1)。

寻址公式：元素的地址值 = 数组的首地址 + 元素占用的存储单元 * 索引值

4、删除元素的特点

假设需要删除索引为2的元素，删除后的数组为：{11,22,44,55,66}

实现步骤：

• 将要删除索引之后的元素往前挪动一位。

• 将数组的最后一个元素设置为默认值。

5、插入元素的特点

假设需要在索引为2的位置上插入元素33，不能直接在索引为2的位置上插入元素33，因为数组采用的是一块连续的存储空间。

实现步骤：

1、判断数组是否需要扩容，当数组的空间长度等于数组实际存放元素的个数时，那么就需要做扩容操作。

• 创建一个比原数组空间长度更大的新数组。

• 把原数组中的元素拷贝进入新数组中。

• 让原数组指向新数组，也就是让原数组保存新数组的地址值。

2、 把插入索引及其之后的元素往后挪动一位（从后往前挪动）。

3、把元素插入到要插入的索引位置中。

6、顺序表基本运算的实现

public class SequenceTable {/*** 定义一个数组，用于保存集合中的数据*/private Object [] elementData;/*** 定义一个变量，用于保存数据实际存放元素的个数*/private int size;/*** 返回数据中元素的个数* @return*/public int getSize() {return size;}/*** 无参构造方法（默认设置数组的空间长度为10）*/public SequenceTable() {this.elementData = new Object[10];}/*** 有参构造方法（指定数组的空间长度）* @param cap 需要设置的空间长度*/public SequenceTable(int cap) {if (cap < 0) {throw new RuntimeException("数组长度不能小于0，cap = " + cap);}this.elementData = new Object[cap];}/*** 添加元素* @param element*/public void add(Object element) {//判断数组是否需要扩容ensureCapacityInternal();//把element添加进数组中this.elementData[size] = element;//更新size值size ++;}/*** 根据索引获取数组元素* @param index* @return*/public Object get(int index) {//判断索引是否有效，有效范围[0,size)rangeCheck(index);//根据索引获取元素return elementData[index];}/*** 根据索引删除元素* @param index*/public void remove(int index) {//判断索引是否有效，有效范围[0,size)rangeCheck(index);//获得删除索引及在它后面的所有元素索引值for (int i = index; i < size - 1; i++) {//把后一个元素往前挪动一位elementData[i] = elementData[i + 1];}//最后一个元素设置为默认值elementData[size - 1] = null;//更新size的值size --;}/*** 根据索引添加元素* @param index* @param element*/public void add(int index,Object element) {//判断索引是否有效，有效的范围[0,size]，插入元素可以是最末尾if (index < 0 || index > size) {throw new ArrayIndexOutOfBoundsException("数组索引异常，index：" + index);}//判断数组是否需要扩容ensureCapacityInternal();//获取插入索引及在它后面的所有元素索引值for (int i = size - 1; i >= index; i--) {//把前一个元素往后挪动一位elementData[i + 1] = elementData[i];}//在插入索引位置实现赋值操作elementData[index] = element;//更新size的值size ++;}/*** 判断索引是否有效* @param index*/private void rangeCheck(int index) {//判断索引是否有效，有效范围[0,size)if (index < 0 || index >= size) {throw new ArrayIndexOutOfBoundsException("数组索引异常，index：" + index);}}/*** 判断是否需要扩容*/private void ensureCapacityInternal() {//当数组的长度等于数组实际存放元素个数时，需要扩容操作if (elementData.length == size) {//创建一个比原数组空间长度更大的新数组Object[] newArr = new Object[elementData.length * 2 + 1];//拷贝数组元素for (int i = 0; i < size; i++) {newArr[i] = elementData[i];}//原数组指向新数组this.elementData = newArr;}}@Overridepublic String toString() {return "ArrayList{" +"elementData=" + Arrays.toString(elementData) +'}';}
}

三、单链表

1、单链表的定义

线性表的链式存储结构又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。如图是单链表结点结构：

data：数据域，存放自身数据信息。

next：指针域，存放其后继结点的地址。

2、单链表结构

通常用头指针来标识一个单链表，如单链表L，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。

头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

使用头结点的两个优点：

• 由于第一个数据结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。

• 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

3、顺序表和单链表的比较

1、存储方式比较

• 顺序表采用一组地址连续的存储单元依次存放数据元素，通过元素之间的先后顺序来确定元素之间的位置，因此存储空间的利用率较高。

• 单链表采用一组地址任意的存储单元来存放数据元素，通过存储下一个结点的地址值来确定结点之间的位置，因此存储空间的利用率较低。

2、时间性能比较

• 顺序表查找的时间复杂度为O(1)，插入和删除元素需要移动元素位置，因此时间复杂度为O(n)。若是需要频繁的执行查找操作，但是很少进行插入和删除操作，那么建议使用顺序表。

• 单链表的查找时间复杂度为O(n)，插入和删除元素无需移动元素位置，因此时间复杂度为O(1)。若是需要频繁的执行插入和删除操作，但是很少进行查找操作，那么建议使用链表。

• 在单链表中根据序号来插入和删除结点，需要通过序号来找到插入和删除结点的位置，那么整体的时间复杂度为O(n)。因此，单链表适合数据量较小时的插入和删除操作，如果存储量较大，那么建议使用其他的数据结构，如二叉树。

3、空间性能比较

• 顺序表需要预先分配一定长度的存储空间，如果事先不知道需要存储元素的个数，分配空间过大会造成存储空间的浪费，分配空间过小则需要执行耗时的扩容操作。

• 单链表不需要固定长度的存储空间，可根据需求来进行临时分配，只需要内存足够就可以分配，在链表中存储元素的个数是没有限制的，无需考虑扩容操作。

4、单链表添加元素

单链表添加元素有两种方式，头插法和尾插法。

1、头插法：在链表的头部不断添加元素，链表的尾结点固定不变，将新结点设置成链表的头结点，然后新结点的指针域指向原来的头结点。

2、尾插法：在链表的尾部不断添加元素，链表的头结点固定不变，将新结点设置成链表的尾结点，指针域设置为空。

结点类

/*** 结点类*/
public class Node {/*** 数据域，用于保存结点的数据*/private Object data;/*** 指针域：用于保存指向下一个结点的地址值*/private Node next;/*** 构造方法* @param data*/public Node(Object data) {this.data = data;}public Object getData() {return data;}public void setData(Object data) {this.data = data;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}
}

添加元素方法的实现

/*** 模拟单链表实现*/
public class SingleLinkedList {/*** 用于保存单链表的首结点*/private Node headNode;/*** 用于保存单链表的尾结点*/private Node tailNode;/*** 链表长度*/private int size;public int getSize() {return size;}/*** 头插法创建单链表，尾结点不变，头结点不断变化* @param element*/public void headAppend(Object element) {//把需要添加的元素封装成一个结点对象Node node = new Node(element);//判断单链表是否为空if (headNode == null) {//将node结点设置为单链表的头结点和尾结点headNode = node;tailNode = node;} else {//链表不为空，将要插入的结点指向原来的头结点node.setNext(headNode);//更新头结点的值headNode = node;}//更新链表长度size ++;}/*** 尾插法创建单链表，头结点不变，尾结点不断变化* @param element*/public void tailAppend(Object element) {//把需要添加的元素封装成一个结点对象Node node = new Node(element);//判断单链表是否为空if (headNode == null) {//将node结点设置为单链表的头结点和尾结点headNode = node;tailNode = node;} else {//链表不为空，将尾结点指向node结点tailNode.setNext(node);//更新尾结点的值tailNode = node;}//更新链表长度size ++;}
}

测试类

public class Test02 {@Testpublic void test1() {//创建一个单链表SingleLinkedList list = new SingleLinkedList();list.headAppend("11");list.headAppend("22");list.headAppend("33");list.headAppend("44");System.out.println();}@Testpublic void test2() {//创建一个单链表SingleLinkedList list = new SingleLinkedList();list.tailAppend("11");list.tailAppend("22");list.tailAppend("33");list.tailAppend("44");System.out.println();}
}

测试结果：

5、单链表查找元素

按序号查找元素：在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从第一个结点出发，顺指针域next逐个结点往下搜索，直至搜索到第i个节点为止。

根据序号查找元素

/*** 根据序号获取结点值* @param index* @return*/
public Object findIndex(int index) {//判断序号是否合法，序号范围[0,size-1]if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}//根据序号获得对应的结点对象Node node = getNodeByIndex(index);//返回结点值return node.getData();
}/*** 根据序号获得对应的结点对象* @param index* @return*/
private Node getNodeByIndex(int index) {//定义一个临时结点，用于辅助单链表遍历操作Node tempNode = headNode;for (int i = 0; i < index; i++) {//更新tempNode的值tempNode = tempNode.getNext();}//返回index对应的结点对象return tempNode;
}/*** 计数器方式根据序号获取结点值* @param index* @return*/
private Node findNode(int index) {//定义一个计数器，初始为1int j = 1;//定义一个临时结点，用于辅助单链表遍历操作Node tempNode = headNode;//若序号为0，返回头结点if (index == 0) {return headNode;}while (j <= index && tempNode !=null) {j ++;//更新tempNode的值tempNode = tempNode.getNext();}return tempNode;
}

6、单链表删除元素

删除元素操作是将单链表的第i个结点删除，实际上还是利用查找算法，先检查删除位置的合法性，再查找表中第i-1个结点（即被删除结点的直接前驱结点），再将其删除。

假设p结点为找到被删结点的直接前驱结点，为实现这一操作后的逻辑关系变化，仅需将p的指针域next指向被删除结点的下一个结点（即直接后继结点）。

/*** 根据序号删除元素* @param index*/
public void remove(int index) {//判断序号是否合法，序号范围[0,size-1]if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}if (index == 0) {//判断删除结点是否为头结点，即index = 0//获取删除元素的直接后继结点Node nextNode = headNode.getNext();//获取删除结点并设置指针域为nullheadNode.setNext(null);//设置直接后继结点为头结点headNode = nextNode;} else if (index == size - 1) {//判断删除结点是否为尾结点，即index = size-1//获取删除元素的直接前驱结点Node preNode = getNodeByIndex(index - 1);//设置直接前驱结点的指针域为nullpreNode.setNext(null);//设置直接前驱结点为尾结点tailNode = preNode;} else{//获取删除元素的直接前驱结点，即index-1位置上的结点Node preNode = getNodeByIndex(index - 1);//获取删除元素的直接后继结点，即index+1位置上的结点Node nextNode = preNode.getNext().getNext();//获取删除结点并设置指针域为nullpreNode.getNext().setNext(null);//将直接前驱结点指针域直接指向直接后继结点preNode.setNext(nextNode);}//更新链表长度size --;
}

7、单链表插入元素

插入元素操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的直接前驱结点（即index - 1结点），再在其后插入新结点，并将新结点的指针域指向待插入位置的直接后继结点（即index + 1结点）。插入的位置可能有三种：链表头部、中部、尾部。

/*** 向指定位置插入元素* @param index* @param element*/
public void insert(int index,Object element) {//判断序号是否合法，序号范围[0,size]，因为可以在结尾添加元素，即index=sizeif (index < 0 || index > size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}//把需要添加的元素封装成一个结点对象Node newNode = new Node(element);if (index == 0) {//判断要插入位置是否为头结点，即index = 0//将新结点的指针域指向原先的头结点newNode.setNext(headNode);//新结点作为头结点headNode = newNode;} else if (index == size) {//判断要插入位置是否为尾结点，即index = size//设置原先的尾结点的指针域指向新的结点tailNode.setNext(newNode);//新结点作为尾结点tailNode = newNode;} else{//获取要插入位置的结点的直接前驱结点，即index-1位置上的结点Node preNode = getNodeByIndex(index - 1);//获取要插入位置的结点Node nextNode = preNode.getNext();//设置前驱结点的指针域指向新结点preNode.setNext(newNode);//设置新结点的指针域指向要插入位置的结点newNode.setNext(nextNode);}//更新链表长度size ++;
}

四、双链表

1、双链表的定义

双链表也叫双向链表，它依旧采用的是链式存储结构。在双链表中，每个结点都有两个指针pre和next，分别指向其直接前驱结点（保存前一个结点的地址值）和直接后继结点（保存后一个结点的地址值）。

2、双链表和单链表的比较

• 单链表结点中只有一个指向直接后继的指针，使得单链表只能从头结点依次顺序地向后遍历，要想访问某一个结点，只能从头结点依次遍历查找。

• 双链表结点中有两个指针pre和next，分别指向直接前驱和直接后继结点，双链表既可以从头结点访问某个结点，也可以从尾结点访问某个元素，双链表可以很快找到直接前驱结点。

3、双链表添加元素

双链表添加元素和单链表类似，只不过有两个指针，如果是头部添加，那么新结点的pre指针域为NULL，新结点的next指针域指向原来的头结点，原来的头结点pre指针域指向新结点。如果是尾部添加，那么新结点的next指针域为NULL，新结点的pre指针域指向原来的尾结点，原来的尾结点next指针域指向新结点。

结点类

/*** 节点类*/
public class Node {/*** 数据域，用于保存结点的数据*/private Object data;/*** 指针域：用于保存指向上一个节点的地址值*/private Node pre;/*** 指针域：用于保存指向下一个结点的地址值*/private Node next;/*** 构造方法* @param data*/public Node(Object data) {this.data = data;}public Object getData() {return data;}public void setData(Object data) {this.data = data;}public Node getPre() {return pre;}public void setPre(Node pre) {this.pre = pre;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}
}

添加元素方法的实现

/*** 模拟单链表实现*/
public class DoubleLinkedList {/*** 用于保存单链表的首结点*/private Node headNode;/*** 用于保存单链表的尾结点*/private Node tailNode;/*** 链表长度*/private int size;public int getSize() {return size;}/*** 头插法创建单链表，尾结点不变，头结点不断变化* @param element*/public void headAppend(Object element) {//把需要添加的元素封装成一个结点对象Node node = new Node(element);//判断单链表是否为空if (headNode == null) {//将node结点设置为单链表的头结点和尾结点headNode = node;tailNode = node;} else {//链表不为空，将要插入的结点指向原来的头结点node.setNext(headNode);//设置原来头结点的指针域pre指向添加的结点headNode.setPre(node);//更新头结点的值headNode = node;}//更新链表长度size ++;}/*** 尾插法创建单链表，头结点不变，尾结点不断变化* @param element*/public void tailAppend(Object element) {//把需要添加的元素封装成一个结点对象Node node = new Node(element);//判断单链表是否为空if (headNode == null) {//将node结点设置为单链表的头结点和尾结点headNode = node;tailNode = node;} else {//链表不为空，将尾结点指向node结点tailNode.setNext(node);//设置node指针域pre指向原来的尾结点node.setPre(tailNode);//更新尾结点的值tailNode = node;}//更新链表长度size ++;}
}

4、双链表查找元素

######双链表由于结点中有两个指针pre和next，分别指向直接前驱和直接后继结点，因此双链表既可以从头结点访问某个结点，也可以从尾结点访问某个元素。在查找时可以判断序号的位置，决定从头结点或者尾结点开始查找，这样能快速查找到需要的结点。

/*** 根据序号获取结点值* @param index* @return*/
public Object findIndex(int index) {//判断序号是否合法，序号范围[0,size-1]if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}//根据序号获得对应的结点对象Node node = getNodeByIndex(index);//返回结点值return node.getData();
}/*** 根据序号获得对应的结点对象* @param index* @return*/
private Node getNodeByIndex(int index) {//定义一个临时结点，用于辅助单链表遍历操作Node tempNode = null;//index在链表前半部分就从头节点开始查找if (index < size / 2) {tempNode = headNode;//从头结点开始查找for (int i = 0; i < index; i++) {//更新tempNode的值tempNode = tempNode.getNext();}} else {//从尾结点开始查找tempNode = tailNode;//从尾结点开始查找for (int i = size - 1; i > index; i--) {//更新tempNode的值tempNode = tempNode.getPre();}}//返回index对应的结点对象return tempNode;
}

5、双链表插入元素

插入元素操作是将s结点插入到m和n结点之间。先检查插入位置的合法性，然后根据插入位置结点n的pre指针域找到直接前驱结点m，在其后插入新结点s，并将s结点的pre指针域指向m结点，next指针域指向n结点，然后将m结点的next指针域指向新结点s，n结点的pre指针域指向新结点s。插入的位置可能有三种：链表头部、中部、尾部。

/*** 向指定位置插入元素* @param index* @param element*/
public void insert(int index,Object element) {//判断序号是否合法，序号范围[0,size]，因为可以在结尾添加元素，即index=sizeif (index < 0 || index > size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}//把需要添加的元素封装成一个结点对象Node newNode = new Node(element);if (index == 0) {//判断要插入位置是否为头结点，即index = 0//将新结点的next指针域指向原来的头结点newNode.setNext(headNode);//设置原来头结点的指针域pre指向添加的结点headNode.setPre(newNode);//新结点作为头结点headNode = newNode;} else if (index == size) {//判断要插入位置是否为尾结点，即index = size//设置原来的尾结点的next指针域指向新的结点tailNode.setNext(newNode);//设置新结点的pre指针域指向原来的尾结点newNode.setPre(tailNode);//新结点作为尾结点tailNode = newNode;} else{//获取要插入位置的结点Node currNode = getNodeByIndex(index);//获取插入位置结点的直接前驱结点Node preNode = currNode.getPre();//设置直接前驱结点的next指针域指向新结点preNode.setNext(newNode);//设置新结点的pre和next指针域newNode.setPre(preNode);newNode.setNext(currNode);//设置currNode结点的pre指针域指向新结点currNode.setPre(newNode);}//更新链表长度size ++;
}

6、双链表删除元素

删除双链表中结点B，首先找到结点B，然后根据pre和next指针域找到直接前驱和后继结点（A、C），然后将A结点的next指针域指向C结点，C结点的pre指针域指向A结点。再将B结点的pre和next设置为NULL即可。

/*** 根据序号删除元素* @param index*/
public void remove(int index) {//判断序号是否合法，序号范围[0,size-1]if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}if (index == 0) {//判断删除结点是否为头结点，即index = 0//获取删除元素的直接后继结点Node nextNode = headNode.getNext();//设置删除结点next指针域为nullheadNode.setNext(null);//判断nextNode是否为空，防止空指针异常if (nextNode != null) {//设置直接后继结点的pre指针域为nullnextNode.setPre(null);}//设置直接后继结点为头结点headNode = nextNode;} else if (index == size - 1) {//判断删除结点是否为尾结点，即index = size-1//获取删除元素的直接前驱结点Node preNode = tailNode.getPre();//设置删除结点pre指针域为nulltailNode.setPre(null);//设置直接前驱结点的next指针域为nullpreNode.setNext(null);//设置直接前驱结点为尾结点tailNode = preNode;} else{//获取删除元素的结点Node currNode = getNodeByIndex(index);//获取删除结点的直接前驱结点Node preNode = currNode.getPre();//获取删除结点的直接后继结点Node nextNode = currNode.getNext();//设置直接前驱结点的next指针域指向直接后继结点preNode.setNext(nextNode);//设置直接后继结点的pre指针域指向直接前驱结点nextNode.setPre(preNode);//设置删除结点的pre和next指针域为nullcurrNode.setPre(null);currNode.setNext(null);}//更新链表长度size --;
}

五、环形链表

1、环形链表概述

环形链表依旧采用的是链式存储结构，它的特点是设置头结点和尾结点相互指向，从而实现让整个链表形成一个环。环形链表分为：环形单链表和环形双链表。

1、环形单链表：环形单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而是指向头结点，从而整个形成一个环。

特点：

• 链表中没有指针域为NULL的结点。

• 在单链表中只能从头结点开始遍历整个链表，而环形单链表可以从任意结点遍历整个链表。

2、环形双链表：在双链表中，尾结点的指针指向了头结点，头结点的指针指向了尾结点，从而整个链表形成一个环。

2、环形单链表实现

/*** 模拟环形单链表实现*/
public class CycleSingleLinkedList {/*** 用于保存单链表的首结点*/private Node headNode;/*** 用于保存单链表的尾结点*/private Node tailNode;/*** 链表长度*/private int size;public int getSize() {return size;}/*** 头插法创建环形单链表，尾结点不变，头结点不断变化* @param element*/public void headAppend(Object element) {//把需要添加的元素封装成一个结点对象Node node = new Node(element);//判断单链表是否为空if (headNode == null) {//将node结点设置为单链表的头结点和尾结点headNode = node;tailNode = node;} else {//链表不为空，将要插入的结点指向原来的头结点node.setNext(headNode);//更新头结点的值headNode = node;}//设置tailNode的next指针域指向headNodetailNode.setNext(headNode);//更新链表长度size ++;}/*** 尾插法创建环形单链表，头结点不变，尾结点不断变化* @param element*/public void tailAppend(Object element) {//把需要添加的元素封装成一个结点对象Node node = new Node(element);//判断单链表是否为空if (headNode == null) {//将node结点设置为单链表的头结点和尾结点headNode = node;tailNode = node;} else {//链表不为空，将尾结点指向node结点tailNode.setNext(node);//更新尾结点的值tailNode = node;}//设置tailNode的next指针域指向headNodetailNode.setNext(headNode);//更新链表长度size ++;}/*** 根据序号获取结点值* @param index* @return*/public Object findIndex(int index) {//判断序号小于0为不合法if (index < 0) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}//根据序号获得对应的结点对象Node node = getNodeByIndex(index);//返回结点值return node.getData();}/*** 根据序号删除元素* @param index*/public void remove(int index) {//判断序号是否合法，序号范围[0,size-1]if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}if (index == 0) {//判断删除结点是否为头结点，即index = 0//获取删除元素的直接后继结点Node nextNode = headNode.getNext();//获取删除结点并设置指针域为nullheadNode.setNext(null);//设置直接后继结点为新的头结点headNode = nextNode;//设置尾结点的next指针域指向新的头结点tailNode.setNext(headNode);} else if (index == size - 1) {//判断删除结点是否为尾结点，即index = size-1//获取删除元素的直接前驱结点Node preNode = getNodeByIndex(index - 1);//设置直接前驱结点的指针域为nullpreNode.setNext(null);//设置直接前驱结点为新的尾结点tailNode = preNode;//新的尾结点next指针域指向头结点tailNode.setNext(headNode);} else{//获取删除元素的直接前驱结点，即index-1位置上的结点Node preNode = getNodeByIndex(index - 1);//获取删除元素的直接后继结点，即index+1位置上的结点Node nextNode = preNode.getNext().getNext();//获取删除结点并设置指针域为nullpreNode.getNext().setNext(null);//将直接前驱结点指针域直接指向直接后继结点preNode.setNext(nextNode);}//更新链表长度size --;//判断size值是否为0，如果等于0，则设置headNode与tailNode为nullif (size == 0) {headNode = null;tailNode = null;}}/*** 向指定位置插入元素* @param index* @param element*/public void insert(int index,Object element) {//判断序号是否合法，序号范围[0,size]，因为可以在结尾添加元素，即index=sizeif (index < 0 || index > size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}//把需要添加的元素封装成一个结点对象Node newNode = new Node(element);if (index == 0) {//判断要插入位置是否为头结点，即index = 0//将新结点的指针域指向原先的头结点newNode.setNext(headNode);//新结点作为头结点headNode = newNode;//设置尾结点的next指针域指向头结点tailNode.setNext(headNode);} else if (index == size) {//判断要插入位置是否为尾结点，即index = size//设置原先的尾结点的指针域指向新的结点tailNode.setNext(newNode);//新结点作为尾结点tailNode = newNode;//设置尾结点的next指针域指向头结点tailNode.setNext(headNode);} else{//获取要插入位置的结点的直接前驱结点，即index-1位置上的结点Node preNode = getNodeByIndex(index - 1);//获取要插入位置的结点Node nextNode = preNode.getNext();//设置前驱结点的指针域指向新结点preNode.setNext(newNode);//设置新结点的指针域指向要插入位置的结点newNode.setNext(nextNode);}//更新链表长度size ++;}/*** 根据序号获得对应的结点对象* @param index* @return*/private Node getNodeByIndex(int index) {//判断环形单链表是否为空表if (headNode == null) {throw new NullPointerException("环形单链表为空");}//定义一个临时结点，用于辅助单链表遍历操作Node tempNode = headNode;for (int i = 0; i < index % size; i++) {//更新tempNode的值tempNode = tempNode.getNext();}//返回index对应的结点对象return tempNode;}
}

3、环形单链表解决约瑟夫环问题

约瑟夫问题：N个人围成一圈，从第一个开始报数，第M个出圈，剩下的人继续从1开始报数，报到M出圈，如此往复，直到所有人都出圈。

/*** 节点类*/
public class Node {/*** 数据域，用于保存结点的数据*/private Object data;/*** 指针域：用于保存指向下一个结点的地址值*/private Node next;/*** 构造方法* @param data*/public Node(Object data) {this.data = data;}public Object getData() {return data;}public void setData(Object data) {this.data = data;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}
}/*** 模拟环形单链表实现*/
public class CycleSingleLinkedList {/*** 用于保存单链表的首结点*/private Node headNode;/*** 用于保存单链表的尾结点*/private Node tailNode;/*** 链表长度*/private int size;public int getSize() {return size;}public Node getHeadNode() {return headNode;}public Node getTailNode() {return tailNode;}/*** 头插法创建环形单链表，尾结点不变，头结点不断变化* @param element*/public void headAppend(Object element) {//把需要添加的元素封装成一个结点对象Node node = new Node(element);//判断单链表是否为空if (headNode == null) {//将node结点设置为单链表的头结点和尾结点headNode = node;tailNode = node;} else {//链表不为空，将要插入的结点指向原来的头结点node.setNext(headNode);//更新头结点的值headNode = node;}//设置tailNode的next指针域指向headNodetailNode.setNext(headNode);//更新链表长度size ++;}/*** 尾插法创建环形单链表，头结点不变，尾结点不断变化* @param element*/public void tailAppend(Object element) {//把需要添加的元素封装成一个结点对象Node node = new Node(element);//判断单链表是否为空if (headNode == null) {//将node结点设置为单链表的头结点和尾结点headNode = node;tailNode = node;} else {//链表不为空，将尾结点指向node结点tailNode.setNext(node);//更新尾结点的值tailNode = node;}//设置tailNode的next指针域指向headNodetailNode.setNext(headNode);//更新链表长度size ++;}/*** 根据序号获取结点值* @param index* @return*/public Object findIndex(int index) {//判断序号小于0为不合法if (index < 0) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}//根据序号获得对应的结点对象Node node = getNodeByIndex(index);//返回结点值return node.getData();}/*** 根据序号删除元素* @param index*/public void remove(int index) {//判断序号是否合法，序号范围[0,size-1]if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}if (index == 0) {//判断删除结点是否为头结点，即index = 0//获取删除元素的直接后继结点Node nextNode = headNode.getNext();//获取删除结点并设置指针域为nullheadNode.setNext(null);//设置直接后继结点为新的头结点headNode = nextNode;//设置尾结点的next指针域指向新的头结点tailNode.setNext(headNode);} else if (index == size - 1) {//判断删除结点是否为尾结点，即index = size-1//获取删除元素的直接前驱结点Node preNode = getNodeByIndex(index - 1);//设置直接前驱结点的指针域为nullpreNode.setNext(null);//设置直接前驱结点为新的尾结点tailNode = preNode;//新的尾结点next指针域指向头结点tailNode.setNext(headNode);} else{//获取删除元素的直接前驱结点，即index-1位置上的结点Node preNode = getNodeByIndex(index - 1);//获取删除元素的直接后继结点，即index+1位置上的结点Node nextNode = preNode.getNext().getNext();//获取删除结点并设置指针域为nullpreNode.getNext().setNext(null);//将直接前驱结点指针域直接指向直接后继结点preNode.setNext(nextNode);}//更新链表长度size --;//判断size值是否为0，如果等于0，则设置headNode与tailNode为nullif (size == 0) {headNode = null;tailNode = null;}}/*** 向指定位置插入元素* @param index* @param element*/public void insert(int index,Object element) {//判断序号是否合法，序号范围[0,size]，因为可以在结尾添加元素，即index=sizeif (index < 0 || index > size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}//把需要添加的元素封装成一个结点对象Node newNode = new Node(element);if (index == 0) {//判断要插入位置是否为头结点，即index = 0//将新结点的指针域指向原先的头结点newNode.setNext(headNode);//新结点作为头结点headNode = newNode;//设置尾结点的next指针域指向头结点tailNode.setNext(headNode);} else if (index == size) {//判断要插入位置是否为尾结点，即index = size//设置原先的尾结点的指针域指向新的结点tailNode.setNext(newNode);//新结点作为尾结点tailNode = newNode;//设置尾结点的next指针域指向头结点tailNode.setNext(headNode);} else{//获取要插入位置的结点的直接前驱结点，即index-1位置上的结点Node preNode = getNodeByIndex(index - 1);//获取要插入位置的结点Node nextNode = preNode.getNext();//设置前驱结点的指针域指向新结点preNode.setNext(newNode);//设置新结点的指针域指向要插入位置的结点newNode.setNext(nextNode);}//更新链表长度size ++;}/*** 根据序号获得对应的结点对象* @param index* @return*/private Node getNodeByIndex(int index) {//判断环形单链表是否为空表if (headNode == null) {throw new NullPointerException("环形单链表为空");}//定义一个临时结点，用于辅助单链表遍历操作Node tempNode = headNode;for (int i = 0; i < index % size; i++) {//更新tempNode的值tempNode = tempNode.getNext();}//返回index对应的结点对象return tempNode;}
}

测试

@Test
public void test2() {//创建一个环形单链表CycleSingleLinkedList list = new CycleSingleLinkedList();ArrayList<Object> startList = new ArrayList<>();//初始化环形单链表for (int i = 1; i <= 10; i++) {list.tailAppend(i);startList.add(i);}System.out.println(startList);ArrayList<Object> endList = JosephRing(list.getHeadNode(), list.getTailNode(), 10, 1, 3);System.out.println(endList);
}/*** 返回取出元素列表* @param headNode 头结点* @param tailNode 尾结点* @param size 链表长度* @param start 开始位置* @param count 间隔次数* @return*/
private ArrayList<Object> JosephRing(Node headNode, Node tailNode, int size, int start, int count) {ArrayList<Object> endList = new ArrayList<>();//判断头结点是否为空if (headNode == null) {throw new NullPointerException("链表为空");}//判断开始位置和次数是否合理，位置为1-10，次数应大于0if (start < 1 || start > size || count < 1) {throw new IllegalArgumentException("参数不合法");}//设置start开始位置为头结点，尾结点紧跟头结点之后for (int i = 0; i < start - 1; i++) {headNode = headNode.getNext();tailNode = tailNode.getNext();}//循环取出，size为0终止循环while (size != 0) {//headNode与tailNode往后移动count - 1for (int i = 0; i < count - 1; i++) {headNode = headNode.getNext();tailNode = tailNode.getNext();}endList.add(headNode.getData());//获取头结点的直接后继结点Node nextNode = headNode.getNext();//设置尾结点指向直接后继结点tailNode.setNext(nextNode);//设置头结点的next指针域为nullheadNode.setNext(null);//设置直接后继结点为新的头结点headNode = nextNode;//更新size的值size --;}return endList;
}
/** 运行结果 */
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[3, 6, 9, 2, 7, 1, 8, 5, 10, 4]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！