手寫一個LinkedList

實現鏈表思路

LinkedList和ArrayList使用上基本相同，實際上它們有著截然不同的底層數據結構。ArrayList底層使用的是數組，LinkedList使用的鏈表。那什麼是鏈表呢，下面我們簡單圖解一下。

鏈表顧名思義，就像鏈子一樣環環相扣鏈接起來，通常我們把鏈子設計為一個Node類，每一個鏈子就是一個Node對象，上圖是Node對象以及Node對象需要定義的一般屬性,下面我們描述下每個屬性的作用：

pre屬性：保存前面Node對象引用
val屬性：保存當前Node的值（可以是個POJO，也可以是包裝後的基本數據類型）
next屬性：保存後面Node對象引用

下面我們再圖解一下的多個鏈子鏈接起來的鏈表是怎麼樣子的：

在閱讀代碼前，最好先帶著下面這幾個問題去閱讀：

1、鏈表初始化應該是怎麼樣子的

2、新增一個Node需要怎麼操作，相對ArrayList來說性能怎麼樣

3、插入一個Node需要怎麼操作，相對ArrayList來說性能怎麼樣

4、刪除一個Node需要怎麼操作，相對ArrayList來說性能怎麼樣

5、獲取一個Node需要怎麼操作，相對ArrayList來說性能怎麼樣

實現鏈表代碼

/** * 
 * 數據結構 - 鏈表 * 
 * * @author laizhiyuan * @since 2019/9/26. */public class LinkedList {
 /** * 鏈尾 */ private Node footer; /** * 鏈頭 */ private Node header; /** * 大小 */ private int size;
 /** * 添加一個元素,默認追加到最後 * * @param eleVal 元素值 */ public void add(T eleVal) { Node newNode = new Node(); newNode.eleValue = eleVal; if (footer != null) { footer.next = newNode; newNode.pre = footer; } if (header == null) { header = newNode; } footer = newNode; size++; }
 /** * 隨機插入元素 * * @param i 下標 * @param eleVal 元素值 */ public void set(int i, T eleVal) {
 this.checkRange(i);
 Node node = this.getNode(i); node.eleValue = eleVal; }
 /** * 隨機獲取對象 * * @param i 下標 * @return 元素值 */ public T get(int i) {
 //檢查是否越界 this.checkRange(i); 

 return this.getNode(i).eleValue; }
 private Node getNode(int i) { //計算中間值 int center = this.size() / 2; //判斷是從前往後查找還是從後往前查找 if (i < center) { return this.getNodeFromHeader(i); } else { return this.getNodeFromFooter(i); } }
 /** * 根據下標獲取結點對象 從後往前查找 * * @param i 下標 * @return 元素值 */ private Node getNodeFromFooter(int i) {
 //計算倒數數量 int descNum = this.size() - i; Node node = this.footer; //大於1是因為排除上面已經賦值的鏈尾 while (descNum-- > 1) { //pre:往前 node = node.pre; } return node; }
 /** * 根據下標獲取結點對象 從前往後查找 * * @param i 下標 * @return 元素值 */ private Node getNodeFromHeader(int i) { Node node = this.header; //大於1是因為排除上面已經賦值的鏈頭 while (i-- > 1) { //next:往後 node = node.next; } return node; }
 private void checkRange(int index) { if (index >= size || index < 0) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } }
 private String outOfBoundsMsg(int index) { return "Index: " + index + ", Size: " + this.size; }
 /** * 根據元素值獲取節點對象 * * @param eleVal 元素值 * @return 節點對象 */ private Node get(T eleVal) {
 if (isEmpty()) { throw new IndexOutOfBoundsException(outOfBoundsMsg(1)); }
 Node node = this.header;
 //處理null值 if (eleVal == null) { if (node.eleValue == null) { return node; } while (node.next != null) { node = node.next; if (node.eleValue == null) { return node; } }
 } else { //處理非null值 if (node.eleValue.equals(eleVal)) { return node; } while (node.next != null) { node = node.next; if (node.eleValue.equals(eleVal)) { return node; } } }
 return null; }
 /** * 根據下標刪除元素 * * @param i 下標 */ public void remove(int i) { this.checkRange(i); Node node = this.getNode(i); this.removeAfter(node); }
 private void removeAfter(Node node){ if (node != null) { if (node == header){ header = header.next; header.pre = null; }else if (node == footer){ footer = footer.pre; footer.next = null; }else {
 node.pre.next = node.next; node.next.pre = node.pre; } } size--; }
 /** * 刪除一個元素值 * * @param eleVal 元素值 */ public void remove(T eleVal) { if (isEmpty()) { throw new IndexOutOfBoundsException(outOfBoundsMsg(1)); } Node node = this.get(eleVal); this.removeAfter(node); }
 /** * 是否為空 * * @return 是 否 */ public boolean isEmpty() { return this.size < 1; }
 /** * 返回鏈表大小 * * @return 鏈表大小 */ public int size() { return size; }
 /** * 鏈表節點類 */ private class Node {
 //鏈表前一個對象引用 private Node pre; //鏈表存儲的值，支持任意對象 private T eleValue; //鏈表後一個對象引用 private Node next;
 }

測試鏈表代碼

public static void main(String[] args) {
 LinkedList<string> list = new LinkedList<>();
 System.out.println("插入前size:" + list.size()); System.out.println("插入前isEmpty:" + list.isEmpty());
 list.add("L1"); list.add("L2"); list.add("L3"); list.add("L4"); list.add("L5"); list.add(null);
 System.out.println("插入後size:" + list.size()); System.out.println("插入後isEmpty:" + list.isEmpty());
 for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); }
 System.out.println("第一個元素值為：" + list.get(0)); System.out.println("最後一個元素值為：" + list.get(list.size() - 1));
 System.out.println("修改前index為0的值：" + list.get(0)); list.set(0, "L0"); System.out.println("修改後index為0的值：" + list.get(0));
 System.out.println("獲取null為:" + list.get(5));
 System.out.println(list.size()); System.out.println(list.isEmpty());
 list.remove(0); System.out.println("刪除後index為0的值：" + list.get(0));
 System.out.println("刪除一個元素後的值：" + list.size()); System.out.println(list.isEmpty());
 }
/<string>

測試鏈表輸出

插入前size:0插入前isEmpty:true插入後size:6插入後isEmpty:falseL1L1L2L4L5null第一個元素值為：L1最後一個元素值為：null修改前index為0的值：L1修改後index為0的值：L0獲取null為:null6false刪除後index為0的值：L2刪除一個元素後的值：5false