WordPress 種子搜索seozou是什么意思
【本節(jié)目標】
1.ArrayList的缺陷
2.鏈表
1. ArrayList的缺陷
上節(jié)課已經(jīng)熟悉了 ArrayList 的使用，并且進行了簡單模擬實現(xiàn)。通過源碼知道， ArrayList 底層使用數(shù)組來存儲元素：
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{// ...
// 默認容量是10private static final int DEFAULT_CAPACITY = 10;//...
// 數(shù)組：用來存儲元素transient Object[] elementData; // non-private to simplify nested class access// 有效元素個數(shù)private int size;public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}
// ...
} 由于其底層是一段連續(xù)空間，當 在 ArrayList 任意位置插入或者刪除元素時，就需要將后序元素整體往前或者往后 搬移，時間復雜度為 O(n) ，效率比較低，因此 ArrayList 不適合做任意位置插入和刪除比較多的場景 。因此： java集合中又引入了LinkedList ，即鏈表結(jié)構(gòu)。
2. 鏈表
2.1 鏈表的概念及結(jié)構(gòu)
鏈表是一種 物理存儲結(jié)構(gòu)上非連續(xù) 存儲結(jié)構(gòu)，數(shù)據(jù)元素的 邏輯順序 是通過鏈表中的 引用鏈接 次序?qū)崿F(xiàn)的 。
實際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有 8 種鏈表結(jié)構(gòu)：
1. 單向或者雙向
2. 帶頭或者不帶頭
3. 循環(huán)或者非循環(huán)
雖然有這么多的鏈表的結(jié)構(gòu)，但是我們重點掌握兩種 :
頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
無頭雙向鏈表：在Java的集合框架庫中LinkedList底層實現(xiàn)就是無頭雙向循環(huán)鏈表。
2.2 無頭單向非循環(huán)鏈表的實現(xiàn)
接口：
public interface Ilinklist {// 1、無頭單向非循環(huán)鏈表實現(xiàn)//頭插法void addFirst(int val);//尾插法void addLast(int val);//任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標void addIndex(int index,int val);//查找是否包含關(guān)鍵字key是否在單鏈表當中boolean contains(int key);//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點void remove(int key);//刪除所有值為key的節(jié)點void removeAllKey(int key);//得到單鏈表的長度int size();//清空單鏈表void clear();//展示單鏈表void display();}
要有鏈表首先得有節(jié)點
如下就是使用內(nèi)部類創(chuàng)建了個頭結(jié)點
有數(shù)值和next節(jié)點的地址
在創(chuàng)建一個成員變量head，指向頭結(jié)點。未初始化默認為null
我們可以寫鏈表的插入
鏈表的頭插不需要考慮是否為空的情況
鏈表的尾差需要考慮為空的情況，如果是空就直接返回，不進行插入
while(cur.next!=null)
這個循環(huán)是遍歷到最后一個鏈表，再將它的next改為新節(jié)點的地址即可
隨機位置插入
1.考慮給的位置是否合法
2.給的是0或者給的鏈表長度
3.在范圍內(nèi)的值找到index前一個的鏈表
4.進行連接
1.合法性
寫了一個異常類
寫了一個函數(shù)捕捉這個異常
再用try-catch來處理異常
2.給的是0或者給的鏈表長度
如果給的是0就進行頭插
如果給的是鏈表長度就進行尾差
剩下的就比較簡單
用了一個函數(shù)進行尋找index的前一個位置
再進行連接
鏈表的打印
再測試下插入是否滿足要求
可見插入是滿足需求的
是否包含某個元素
刪除第一個數(shù)值為val的節(jié)點
測試
刪除所有為為val的節(jié)點
測試
確實沒有1出現(xiàn)，可見全部刪除
刪除所有存在val值的節(jié)點還有一個方法，創(chuàng)建一個哨兵位
測試
也是可以的
2.3總代碼
接口
public interface Ilinklist {// 1、無頭單向非循環(huán)鏈表實現(xiàn)//頭插法void addFirst(int val);//尾插法void addLast(int val);//任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標void addIndex(int index,int val);//查找是否包含關(guān)鍵字key是否在單鏈表當中boolean contains(int val);//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點void remove(int val);//刪除所有值為key的節(jié)點void removeAllKey(int val);//得到單鏈表的長度int getSize();void clear();void display();}
indexNotLegalException.java
public class indexNotLegalException extends RuntimeException{public indexNotLegalException(){}public indexNotLegalException(String msg){super(msg);}
}
LinkList.java
public class LinkList implements Ilinklist {static class ListNode{public int val;ListNode next;public ListNode(int val) {this.val = val;}}ListNode head;@Overridepublic void addFirst(int val) {//鏈表的頭插ListNode node=new ListNode(val);node.next=head;head=node;}public void addLast(int val){//鏈表的尾差ListNode node=new ListNode(val);if(head==null){head=node;return;}ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=node;}public int getSize(){//獲取鏈表的長度ListNode cur=head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}public void addIndex(int index,int val){//1.判斷合法性try{cheakIndexofAddIndex(index);}catch(indexNotLegalException e){e.printStackTrace();return;}//2.index==0||index==size()if(index==0){addFirst(val);return;}if(index==getSize()){addLast(val);return;}//3.找到index的前一個位置ListNode cur=findIndexSubOne(index);//4.進行連接ListNode node=new ListNode(val);node.next=cur.next;cur.next=node;}@Overridepublic boolean contains(int val) {ListNode cur=head;while(cur!=null){if(cur.val==val){return true;}cur=cur.next;}return false;}@Overridepublic void remove(int val) { //刪除第一個節(jié)點為val的值if(head==null){return;}ListNode cur=head;if(cur.val==val){head=head.next;return;}while(cur.next!=null){if(cur.next.val==val){cur.next=cur.next.next;return;}cur=cur.next;}}@Overridepublic void removeAllKey(int val) {//刪除鏈表所有值為val的節(jié)點/* if(head==null){return;}ListNode prev=head;ListNode cur=head.next;while(cur!=null){if(cur.val==val){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}if(head.val==val){head=head.next;}*/ListNode Head=new ListNode(0);Head.next=head;ListNode temp=Head;while(temp.next!=null){if(temp.next.val==val){temp.next=temp.next.next;}else{temp=temp.next;}}head=Head.next;}@Overridepublic void clear() {}@Overridepublic void display() {ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}private void cheakIndexofAddIndex(int index) throws indexNotLegalException{//判斷指定位置插入的index是否合法if(index<0||index>getSize()){throw new indexNotLegalException("AddIndex的index不合法");}}private ListNode findIndexSubOne(int index){ListNode cur=head;while(index-1>0){cur=cur.next;index--;}return cur;}}test.java
public class test {public static void main(String[] args) {LinkList linkList=new LinkList();linkList.addFirst(1);linkList.addFirst(1);linkList.addFirst(1);linkList.addFirst(1);//上面是鏈表的頭插linkList.display();System.out.println("==============");linkList.removeAllKey(1);//刪除所有擁有1的節(jié)點linkList.display();}
}