鏈表
鏈表：一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。
單向鏈表：只有一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針（引用）。
雙向鏈表：有兩個(gè)指針，一個(gè)指向前一個(gè)節(jié)點(diǎn)，一個(gè)后一個(gè)節(jié)點(diǎn)。
循環(huán)鏈表：鏈表的兩頭連接，形成了一個(gè)環(huán)狀鏈表，稱為循環(huán)鏈表。
約瑟夫環(huán)問題：一個(gè)經(jīng)典的循環(huán)鏈表問題，題意是：已知 n 個(gè)人（以編號1，2，3，…，n分別表示）圍坐在一張圓桌周圍，從編號為 k 的人開始順時(shí)針報(bào)數(shù)，數(shù)到m的那個(gè)人出列；他的下一個(gè)人又從 1 還是順時(shí)針開始報(bào)數(shù)，數(shù)到 m 的那個(gè)人又出列；依次重復(fù)下去，要求找到最后出列的那個(gè)人。
單向鏈表&雙向鏈表
單向鏈表，優(yōu)點(diǎn)：增加、刪除節(jié)點(diǎn)簡單，遍歷時(shí)不會死循環(huán)；
雙向鏈表，優(yōu)點(diǎn)：可找到前驅(qū)和后繼，可進(jìn)可退；
單向鏈表，缺點(diǎn)：只能從頭到尾遍歷，只能找到后繼，無法找到前驅(qū)，也就是只能前進(jìn)。
雙向鏈表，缺點(diǎn)：增加刪除節(jié)點(diǎn)復(fù)雜，需要多分配一個(gè)指針存儲空間。
單向鏈表，適用：適用于節(jié)點(diǎn)的增加刪除。
雙向鏈表，適用：適用于需要雙向查找節(jié)點(diǎn)值的情況。
案例：實(shí)現(xiàn)單鏈表
package com.what21.structure.linked.oneway.case01.mode01;import java.util.Comparator;import java.util.Iterator;public class SingleLinkedList<E> implements Iterable<E> {// 頭結(jié)點(diǎn)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;
}// 從頭結(jié)點(diǎn)開始遍歷Element<E> element = head;while (true) {// 找到鏈表的最后if (element.nextElement == null) {break;
}
element = element.nextElement;
}// 最后一個(gè)節(jié)點(diǎn)添加節(jié)點(diǎn)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;
}// 遍歷找到對應(yīng)的元素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;
}// 遍歷找到對應(yīng)的元素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;
}// 從頭結(jié)點(diǎn)開始遍歷Element<E> element = head;while (true) {// 找到鏈表的最后if (element.nextElement == null) {break;
}// System.out.println('添加數(shù)據(jù)：' 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 {// 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)記錄Element<E> tempElement = element.nextElement;// 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為新節(jié)點(diǎn)element.nextElement = newElement;// 新節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為之前的下一個(gè)節(jié)點(diǎn)newElement.nextElement = tempElement;
}
size ;
}/**
* @return
*/public int size() {return size;
}public int length() {int length = 0;// 不統(tǒng)計(jì)頭節(jié)點(diǎn)Element<E> element = head.nextElement;while (element != null) {
length ;
element = element.nextElement;
}return length;
}/**
* 倒數(shù)第K個(gè)節(jié)點(diǎn)（不能用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、求出位置（等于總長度-倒數(shù)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;
}/**
* 反轉(zhuǎn)鏈表
*/public void reverse() {// 當(dāng)前鏈表為空，或者只有一個(gè)節(jié)點(diǎn)不需要反轉(zhuǎn)if (head.nextElement == null || head.nextElement.nextElement == null) {return;
}// 定義反轉(zhuǎn)頭Element<E> reverseElement = new Element<E>();// 遍歷并移除Element<E> element = head.nextElement;
Element<E> nextElement = null;while (element != null) {
nextElement = element.nextElement;// 當(dāng)前節(jié)點(diǎn)的下一個(gè)>>>>>指向>>>>>頭節(jié)點(diǎn)指向的下一個(gè)element.nextElement = reverseElement.nextElement;// 頭節(jié)點(diǎn)的下一個(gè)>>>>>指向>>>>>當(dāng)前節(jié)點(diǎn)reverseElement.nextElement = element;
element = nextElement;
}
head.nextElement = reverseElement.nextElement;
}/**
* 排序
*/public void sorted() {// 當(dāng)前鏈表為空，或者只有一個(gè)節(jié)點(diǎn)不用排序if (head.nextElement == null || head.nextElement.nextElement == null) {return;
}// 定義反轉(zhuǎn)頭Element<E> soredElement = new Element<E>();// 遍歷并移除Element<E> element = head.nextElement;
Element<E> nextElement = null;while (element != null) {// 當(dāng)前元素的下一個(gè)元素先保存起來；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) {// 如果是第一個(gè)就直接添加if (element.nextElement == null) {break;
}// 通過比較后大于0那就添加當(dāng)前節(jié)點(diǎn)int compareResult = comparator.compare(element.nextElement.data, newElement.data);if (compareResult >= 0) {break;
}
element = element.nextElement;
}// 新節(jié)點(diǎn)的下一個(gè)>>>>>指向>>>>>頭節(jié)點(diǎn)的下一個(gè)newElement.nextElement = element.nextElement;// 頭節(jié)點(diǎn)的下一個(gè)>>>>>指向>>>>>新節(jié)點(diǎn)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、創(chuàng)建鏈表SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<Integer>();// 2、添加數(shù)據(jù)singleLinkedList.add(1234);
singleLinkedList.add(6789);
singleLinkedList.add(1010);
singleLinkedList.add(2020);
singleLinkedList.add(4789);// 3、鏈表轉(zhuǎn)數(shù)組printList(singleLinkedList);
printSeparator();// 4、修改節(jié)點(diǎn)數(shù)據(jù)singleLinkedList.modify(1, 6000);
singleLinkedList.modify(3, 2000);
printList(singleLinkedList);
printSeparator();// 5、刪除節(jié)點(diǎn)數(shù)據(jù)singleLinkedList.remove(0);
printList(singleLinkedList);
singleLinkedList.remove(2);
printList(singleLinkedList);
printSeparator();// 6、鏈表的有效節(jié)點(diǎn)個(gè)數(shù)System.out.println('鏈表計(jì)數(shù)長度：' singleLinkedList.size());
System.out.println('有效節(jié)點(diǎn)個(gè)數(shù)：' singleLinkedList.length());
printSeparator();
System.out.println('倒數(shù)第1個(gè)：' singleLinkedList.getLast(1));
System.out.println('倒數(shù)第2個(gè)：' singleLinkedList.getLast(2));
System.out.println('倒數(shù)第3個(gè)：' singleLinkedList.getLast(3));
System.out.println('倒數(shù)第4個(gè)：' singleLinkedList.getLast(4));
printSeparator();
System.out.println('反轉(zhuǎn)鏈表');
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、創(chuàng)建鏈表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表達(dá)式singleLinkedList = new SingleLinkedList<>((o1, o2) -> {if (o1 == null || o2 == null) {return 0;
}return o1-o2;
});// 2、添加數(shù)據(jù)（排序方式）singleLinkedList.addBySort(1234);
singleLinkedList.addBySort(6789);
singleLinkedList.addBySort(1010);
singleLinkedList.addBySort(2020);
singleLinkedList.addBySort(1234);
singleLinkedList.addBySort(4789);// 3、鏈表轉(zhuǎn)數(shù)組printList(singleLinkedList);
printSeparator();// 4、修改節(jié)點(diǎn)數(shù)據(jù)singleLinkedList.modify(1, 1200);
printList(singleLinkedList);
printSeparator();// 5、刪除節(jié)點(diǎn)數(shù)據(jù)singleLinkedList.remove(0);
printList(singleLinkedList);
singleLinkedList.remove(2);
printList(singleLinkedList);
printSeparator();// 6、鏈表的有效節(jié)點(diǎn)個(gè)數(shù)System.out.println('鏈表計(jì)數(shù)長度：' singleLinkedList.size());
System.out.println('有效節(jié)點(diǎn)個(gè)數(shù)：' 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('鏈表計(jì)數(shù)長度：' singleLinkedList.size());
System.out.println('有效節(jié)點(diǎn)個(gè)數(shù)：' 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();
}
}
