鐵嶺做網(wǎng)站公司哪家好東營(yíng)優(yōu)化公司
目錄
1.LinkedList的介紹
LinkedList的結(jié)構(gòu)
2.LinkedList的模擬實(shí)現(xiàn)
2.1創(chuàng)建雙鏈表?
2.2頭插法
2.3尾插法
2.4任意位置插入
2.5查找關(guān)鍵字
2.6鏈表長(zhǎng)度
2.7遍歷鏈表
2.8刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
2.9刪除所有值為key的節(jié)點(diǎn)
2.10清空鏈表
2.11完整代碼
3.LinkedList的使用?
3.1LinkedList的構(gòu)造
3.2LinkedList的其他常用方法介紹?
?3.3LinkedList的遍歷
3.4ArrayList和LinkedList的區(qū)別
1.LinkedList的介紹
LinkedList的底層是雙向鏈表結(jié)構(gòu)，元素存儲(chǔ)在單獨(dú)的節(jié)點(diǎn)中，通過(guò)引用將節(jié)點(diǎn)連接起來(lái)了。
如果對(duì)雙向鏈表或鏈表不太清晰，可以先看看本博主寫(xiě)的有關(guān)鏈表的文章。
鏈表的頂級(jí)理解_WHabcwu的博客-CSDN博客
在集合框架中，LinkedList也實(shí)現(xiàn)了List接口，具體如下：
注意：?
1. LinkedList 實(shí)現(xiàn)了 List 接口2. LinkedList 的底層使用了雙向鏈表3. LinkedList 沒(méi)有實(shí)現(xiàn) RandomAccess 接口，因此 LinkedList 不支持隨機(jī)訪問(wèn)4. LinkedList 的任意位置插入和刪除元素時(shí)效率比較高，時(shí)間復(fù)雜度為 O(1)5. LinkedList 比較適合任意位置插入的場(chǎng)景
?
LinkedList的結(jié)構(gòu)
?
- 前驅(qū)節(jié)點(diǎn)：用于存儲(chǔ)前一節(jié)點(diǎn)的位置，用prev表示
- 后繼節(jié)點(diǎn)：用于儲(chǔ)存下一節(jié)點(diǎn)的位置，用next表示
- 所需要儲(chǔ)存的數(shù)據(jù)，用val表示
- 頭節(jié)點(diǎn)：用head表示
- 尾節(jié)點(diǎn)：用last表示
2.LinkedList的模擬實(shí)現(xiàn)
無(wú)非是增刪查改，在某位置的插入與刪除，對(duì)數(shù)據(jù)內(nèi)容進(jìn)行管理和操作。
具體實(shí)現(xiàn)內(nèi)容：
（1）創(chuàng)建雙鏈表
（2）頭插法
（3）尾插法
（4）任意位置插入
（5）查找關(guān)鍵字
（6）鏈表長(zhǎng)度
（7）遍歷鏈表
（8）刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
（9）刪除所有值為key的節(jié)點(diǎn)
（10）清空鏈表
2.1創(chuàng)建雙鏈表?
public class MyLinkedList {static class ListNode {public int val;public ListNode prev;//前驅(qū)public ListNode next;//后繼public ListNode(int val) {this.val = val;}}public ListNode head;//頭節(jié)點(diǎn)public ListNode last;//尾節(jié)點(diǎn)
}
2.2頭插法
（1）首先判斷頭節(jié)點(diǎn)是否為null若為null，則該節(jié)點(diǎn)就是頭節(jié)點(diǎn)，也是尾節(jié)點(diǎn).
（2）頭節(jié)點(diǎn)不為null，將原先head的前驅(qū)節(jié)點(diǎn)指向新增節(jié)點(diǎn)位置，新增節(jié)點(diǎn)后驅(qū)節(jié)點(diǎn)指向head節(jié)點(diǎn)的位置。
(3)head指向新增節(jié)點(diǎn)位置。
//插法 O(1)public void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {head = node;last = node;}else {node.next = head;head.prev = node;head = node;}}
2.3尾插法
與頭插法大同小異
//尾插法 O(1)public void addLast(int data){ListNode node = new ListNode(data);if(head == null) {head = node;last = node;}else {last.next = node;node.prev = last;last = node;}}2.4任意位置插入
需要插入的位置必須為合法，如果不合法，我們會(huì)拋出一個(gè)異常進(jìn)行提醒
public class ListIndexOutOfException extends RuntimeException{public ListIndexOutOfException() {}public ListIndexOutOfException(String message) {super(message);}
}
任意位置插入，我們可以分為種情況，插在開(kāi)頭，插在結(jié)尾，插在中間
?
//任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)public void addIndex(int index,int data){if(index < 0 || index > size()) {throw new ListIndexOutOfException("違規(guī)數(shù)據(jù)");}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}ListNode cur = findIndex(index);//ListNode node = new ListNode(data);cur.prev.next = node;node.next = cur;node.prev = cur.prev;cur.prev = node;}2.5查找關(guān)鍵字
直接遍歷查找即可
//查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}
2.6鏈表長(zhǎng)度
用一個(gè)len變量進(jìn)行記錄，遍歷鏈表
public int size(){int len = 0;ListNode cur = head;while (cur != null) {len++;cur = cur.next;}return len;}
2.7遍歷鏈表
public void display(){ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}
2.8刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
（1）一個(gè)節(jié)點(diǎn)都沒(méi)有
（2）刪除數(shù)據(jù)在第一個(gè)
（3）沒(méi)有你要?jiǎng)h除的數(shù)據(jù)
（4）有你要?jiǎng)h除的數(shù)據(jù)且不是第一個(gè)（5）刪除數(shù)據(jù)最后一個(gè)
?找到就return;
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)public void remove(int key){ListNode cur = head;while (cur != null) {//開(kāi)始刪除了if(cur.val == key) {//1. 刪除的是頭節(jié)點(diǎn)if(cur == head) {head = head.next;//只有一個(gè)節(jié)點(diǎn)if(head != null) {head.prev = null;}}else {//中間 尾巴cur.prev.next = cur.next;//不是尾巴節(jié)點(diǎn)if(cur.next != null) {cur.next.prev = cur.prev;}else {//是尾巴節(jié)點(diǎn)last = last.prev;}}return;}cur = cur.next;}}2.9刪除所有值為key的節(jié)點(diǎn)
與刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)幾乎是一模一樣的；
我們只需要遍歷完就好，只需要return刪掉就好。
//刪除所有值為key的節(jié)點(diǎn)public void removeAllKey(int key){ListNode cur = head;while (cur != null) {//開(kāi)始刪除了if(cur.val == key) {//1. 刪除的是頭節(jié)點(diǎn)if(cur == head) {head = head.next;//只有一個(gè)節(jié)點(diǎn)if(head != null) {head.prev = null;}}else {//中間 尾巴cur.prev.next = cur.next;//不是尾巴節(jié)點(diǎn)if(cur.next != null) {cur.next.prev = cur.prev;}else {//是尾巴節(jié)點(diǎn)last = last.prev;}}}cur = cur.next;}}2.10清空鏈表
只需要遍歷整個(gè)鏈表，將每個(gè)節(jié)點(diǎn)的前驅(qū)與后繼節(jié)點(diǎn)都置為null就好
public void clear(){ListNode cur = head;while(cur != null) {cur.prev = null;cur = cur.next;cur.prev.next = null;}head = null;last = null;}2.11完整代碼
public class MyLinkedList {static class ListNode {public int val;public ListNode prev;//前驅(qū)public ListNode next;//后繼public ListNode(int val) {this.val = val;}}public ListNode head;//頭節(jié)點(diǎn)public ListNode last;//尾節(jié)點(diǎn)//頭插法 O(1)public void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {head = node;last = node;}else {node.next = head;head.prev = node;head = node;}}//尾插法 O(1)public void addLast(int data){ListNode node = new ListNode(data);if(head == null) {head = node;last = node;}else {last.next = node;node.prev = last;last = node;}}//任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)public void addIndex(int index,int data){if(index < 0 || index > size()) {throw new ListIndexOutOfException("違規(guī)數(shù)據(jù)");}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}ListNode cur = findIndex(index);//ListNode node = new ListNode(data);cur.prev.next = node;node.next = cur;node.prev = cur.prev;cur.prev = node;}private ListNode findIndex(int index) {ListNode cur = head;while (index != 0) {cur = cur.next;index--;}return cur;}//查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)public void remove(int key){ListNode cur = head;while (cur != null) {//開(kāi)始刪除了if(cur.val == key) {//1. 刪除的是頭節(jié)點(diǎn)if(cur == head) {head = head.next;//只有一個(gè)節(jié)點(diǎn)if(head != null) {head.prev = null;}}else {//中間 尾巴cur.prev.next = cur.next;//不是尾巴節(jié)點(diǎn)if(cur.next != null) {cur.next.prev = cur.prev;}else {//是尾巴節(jié)點(diǎn)last = last.prev;}}return;}cur = cur.next;}}//刪除所有值為key的節(jié)點(diǎn)public void removeAllKey(int key){ListNode cur = head;while (cur != null) {//開(kāi)始刪除了if(cur.val == key) {//1. 刪除的是頭節(jié)點(diǎn)if(cur == head) {head = head.next;//只有一個(gè)節(jié)點(diǎn)if(head != null) {head.prev = null;}}else {//中間 尾巴cur.prev.next = cur.next;//不是尾巴節(jié)點(diǎn)if(cur.next != null) {cur.next.prev = cur.prev;}else {//是尾巴節(jié)點(diǎn)last = last.prev;}}}cur = cur.next;}}public int size(){int len = 0;ListNode cur = head;while (cur != null) {len++;cur = cur.next;}return len;}public void display(){ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}public void clear(){ListNode cur = head;while(cur != null) {cur.prev = null;cur = cur.next;cur.prev.next = null;}head = null;last = null;}
}
3.LinkedList的使用?
3.1LinkedList的構(gòu)造
3.2LinkedList的其他常用方法介紹?
?
?3.3LinkedList的遍歷
public static void main(String[] args) {LinkedList<Integer> linkedList = new LinkedList<>();linkedList.add(1);linkedList.add(2);linkedList.add(3);linkedList.add(4);linkedList.add(5);// foreach遍歷for (int e:list) {System.out.print(e + " ");}System.out.println();System.out.println("=====================");// 使用迭代器遍歷---正向遍歷Iterator<Integer> iterator1 = linkedList.iterator();while(iterator1.hasNext()){System.out.println(iterator1.next());}System.out.println("=====================");// 使用反向迭代器---反向遍歷ListIterator<Integer> iterator2 = linkedList.listIterator(linkedList.size());while (iterator2.hasPrevious()){System.out.println(iterator2.previous());}}3.4ArrayList和LinkedList的區(qū)別
?
以上為我個(gè)人的小分享，如有問(wèn)題，歡迎討論！！！?
都看到這了，不如關(guān)注一下，給個(gè)免費(fèi)的贊?
?