链表
链表：一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
单向链表：只有一个指向下一个节点的指针（引用）。
双向链表：有两个指针，一个指向前一个节点，一个后一个节点。
循环链表：链表的两头连接，形成了一个环状链表，称为循环链表。
约瑟夫环问题：一个经典的循环链表问题，题意是：已知 n 个人（以编号1，2，3，…，n分别表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到m的那个人出列；他的下一个人又从 1 还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，要求找到最后出列的那个人。
单向链表&双向链表
单向链表，优点：增加、删除节点简单，遍历时不会死循环；
双向链表，优点：可找到前驱和后继，可进可退；
单向链表，缺点：只能从头到尾遍历，只能找到后继，无法找到前驱，也就是只能前进。
双向链表，缺点：增加删除节点复杂，需要多分配一个指针存储空间。
单向链表，适用：适用于节点的增加删除。
双向链表，适用：适用于需要双向查找节点值的情况。
案例：实现单链表
package com.what21.structure.linked.oneway.case01.mode01;import java.util.Comparator;import java.util.Iterator;public class SingleLinkedList<E> implements Iterable<E> {// 头结点private Element<E> head = new Element<E>();// 链表大小private int size;private Comparator<E> comparator;public SingleLinkedList() {}public SingleLinkedList(Comparator<E> comparator) {this.comparator = comparator;}/** * @param e */public void add(E e) {if (e == null) {return;}// 从头结点开始遍历Element<E> element = head;while (true) {// 找到链表的最后if (element.nextElement == null) {break;}element = element.nextElement;}// 最后一个节点添加节点element.nextElement = new Element<E>(e);size ;}/** * @param index * @param t */public void modify(int index, E e) {if (e == null) {return;}if (index < 0 && index > size - 1) {return;}// 遍历找到对应的元素Element<E> element = head;int i = 0;boolean flag = false;while (true) {if (i == (index 1)) {flag = true;break;}// 找到链表的最后if (element.nextElement == null) {break;}element = element.nextElement;i ;}if (flag) {element.data = e;}}/** * @param index */public void remove(int index) {if (index < 0 && index > size - 1) {return;}// 遍历找到对应的元素Element<E> element = head;int i = 0;boolean flag = false;while (true) {if (i == (index)) {flag = true;break;}// 找到链表的最后if (element.nextElement == null) {break;}element = element.nextElement;i ;}if (flag) {element.nextElement = element.nextElement.nextElement;this.size--;}}/** * @return */public E[] toArray() {// 判断链表是否为空if (head.nextElement == null) {return null;}@SuppressWarnings('unchecked')E[] array = (E[]) new Object[size];Element<E> element = head;int i = 0;while (true) {// 找到链表的最后if (element.nextElement == null) {break;}element = element.nextElement;array[i ] = element.data;}return array;}/** * 是否正序排列 * * @param e * @param isAsc */public void addBySort(E e) {if (e == null) {return;}// 从头结点开始遍历Element<E> element = head;while (true) {// 找到链表的最后if (element.nextElement == null) {break;}// System.out.println('添加数据：' e '，' element.nextElement.data ',' e);int compareResult = comparator.compare(element.nextElement.data, e);if (compareResult >= 0) {break;}element = element.nextElement;}Element<E> newElement = new Element<E>(e);if (element == head && element.nextElement == null) {element.nextElement = newElement;} else {// 当前节点的下一个节点记录Element<E> tempElement = element.nextElement;// 当前节点的下一个节点为新节点element.nextElement = newElement;// 新节点的下一个节点为之前的下一个节点newElement.nextElement = tempElement;}size ;}/** * @return */public int size() {return size;}public int length() {int length = 0;// 不统计头节点Element<E> element = head.nextElement;while (element != null) {length ;element = element.nextElement;}return length;}/** * 倒数第K个节点（不能用size） * * @param bottomIndex * @return */public E getLast(int lastIndex) {// 1、遍历获取到总长度int length = 0;Element<E> element = head.nextElement;while (element != null) {length ;element = element.nextElement;}// 2、求出位置（等于总长度-倒数index）int index = length - lastIndex;if (index < 0 || index > size) {return null;}// 3、遍历查找element = head.nextElement;int i = 0;boolean flag = false;while (element != null) {if (i == index) {flag = true;break;}element = element.nextElement;i ;}if (flag) {return element.data;}return null;}/** * 反转链表 */public void reverse() {// 当前链表为空，或者只有一个节点不需要反转if (head.nextElement == null || head.nextElement.nextElement == null) {return;}// 定义反转头Element<E> reverseElement = new Element<E>();// 遍历并移除Element<E> element = head.nextElement;Element<E> nextElement = null;while (element != null) {nextElement = element.nextElement;// 当前节点的下一个>>>>>指向>>>>>头节点指向的下一个element.nextElement = reverseElement.nextElement;// 头节点的下一个>>>>>指向>>>>>当前节点reverseElement.nextElement = element;element = nextElement;}head.nextElement = reverseElement.nextElement;}/** * 排序 */public void sorted() {// 当前链表为空，或者只有一个节点不用排序if (head.nextElement == null || head.nextElement.nextElement == null) {return;}// 定义反转头Element<E> soredElement = new Element<E>();// 遍历并移除Element<E> element = head.nextElement;Element<E> nextElement = null;while (element != null) {// 当前元素的下一个元素先保存起来；nextElement = element.nextElement;this.addBySort(soredElement, element);element = nextElement;}head.nextElement = soredElement.nextElement;}/** * 是否正序排列 * * @param e * @param isAsc */private void addBySort(Element<E> element, Element<E> newElement) {// System.out.println('添加值：' newElement.data);while (true) {// 如果是第一个就直接添加if (element.nextElement == null) {break;}// 通过比较后大于0那就添加当前节点int compareResult = comparator.compare(element.nextElement.data, newElement.data);if (compareResult >= 0) {break;}element = element.nextElement;}// 新节点的下一个>>>>>指向>>>>>头节点的下一个newElement.nextElement = element.nextElement;// 头节点的下一个>>>>>指向>>>>>新节点element.nextElement = newElement;}@SuppressWarnings('hiding')private class Element<E> {Element<E> nextElement;E data;public Element() {this(null);}public Element(E data) {this.data = data;}}@Overridepublic Iterator<E> iterator() {return null;}}public class SingleLinkedListDemo {public static void main(String[] args) {// 1、创建链表SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<Integer>();// 2、添加数据singleLinkedList.add(1234);singleLinkedList.add(6789);singleLinkedList.add(1010);singleLinkedList.add(2020);singleLinkedList.add(4789);// 3、链表转数组printList(singleLinkedList);printSeparator();// 4、修改节点数据singleLinkedList.modify(1, 6000);singleLinkedList.modify(3, 2000);printList(singleLinkedList);printSeparator();// 5、删除节点数据singleLinkedList.remove(0);printList(singleLinkedList);singleLinkedList.remove(2);printList(singleLinkedList);printSeparator();// 6、链表的有效节点个数System.out.println('链表计数长度：' singleLinkedList.size());System.out.println('有效节点个数：' singleLinkedList.length());printSeparator();System.out.println('倒数第1个：' singleLinkedList.getLast(1));System.out.println('倒数第2个：' singleLinkedList.getLast(2));System.out.println('倒数第3个：' singleLinkedList.getLast(3));System.out.println('倒数第4个：' singleLinkedList.getLast(4));printSeparator();System.out.println('反转链表');singleLinkedList.reverse();printList(singleLinkedList);printSeparator();}static void printList(SingleLinkedList<Integer> singleLinkedList) {Object[] intArray = singleLinkedList.toArray();if (intArray != null) {for (Object value : intArray) {System.out.print(value ' ');}System.out.println();}}/** * @param array */static void printSeparator() {for (int i = 0; i < 45; i ) {System.out.printf('%s', '--');}System.out.println();}}package com.what21.structure.linked.oneway.case01.mode01;import java.util.Comparator;public class SingleLinkedListSortedDemo {public static void main(String[] args) {// 1、创建链表SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<Integer>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {if (o1 == null || o2 == null) {return 0;}return o1 - o2;}});// 使用Lambda表达式singleLinkedList = new SingleLinkedList<>((o1, o2) -> {if (o1 == null || o2 == null) {return 0;}return o1-o2;});// 2、添加数据（排序方式）singleLinkedList.addBySort(1234);singleLinkedList.addBySort(6789);singleLinkedList.addBySort(1010);singleLinkedList.addBySort(2020);singleLinkedList.addBySort(1234);singleLinkedList.addBySort(4789);// 3、链表转数组printList(singleLinkedList);printSeparator();// 4、修改节点数据singleLinkedList.modify(1, 1200);printList(singleLinkedList);printSeparator();// 5、删除节点数据singleLinkedList.remove(0);printList(singleLinkedList);singleLinkedList.remove(2);printList(singleLinkedList);printSeparator();// 6、链表的有效节点个数System.out.println('链表计数长度：' singleLinkedList.size());System.out.println('有效节点个数：' singleLinkedList.length());// 7、 排序printSeparator();singleLinkedList.add(1000);singleLinkedList.add(2000);singleLinkedList.add(7000);printList(singleLinkedList);singleLinkedList.sorted();System.out.println('排序链表');printList(singleLinkedList);System.out.println('链表计数长度：' singleLinkedList.size());System.out.println('有效节点个数：' singleLinkedList.length());printSeparator();}static void printList(SingleLinkedList<Integer> singleLinkedList) {Object[] intArray = singleLinkedList.toArray();if (intArray != null) {for (Object value : intArray) {System.out.print(value ' ');}System.out.println();}}/** * @param array */static void printSeparator() {for (int i = 0; i < 45; i ) {System.out.printf('%s', '--');}System.out.println();}}