2023年Q2用戶偏好榜：12+256G版本成新主流
3月份的性能榜、性價比榜和好評榜之后，就要輪到2023年的第二季度偏好榜了，上半年的新機(jī)潮已經(jīng)過去，最明顯的肯定就是大內(nèi)存和存儲的機(jī)型了，另外部分中端機(jī)也取消了屏幕塑料支架
前面有很詳細(xì)的講過線性表(順序表和鏈表)，當(dāng)時講的鏈表以單鏈表為主，但在實際應(yīng)用中雙鏈表有很多應(yīng)用場景，例如大家熟知的LinkedList。
單鏈表和雙鏈表都是線性表的鏈?zhǔn)綄崿F(xiàn)，它們的主要區(qū)別在于節(jié)點結(jié)構(gòu)。單鏈表的節(jié)點包含數(shù)據(jù)字段 data 和一個指向下一個節(jié)點的指針 next，而雙鏈表的節(jié)點除了 data 和 next，還包含指向前一個節(jié)點的指針 pre。這個區(qū)別會導(dǎo)致它們在操作上有些差異。
單鏈表的一個節(jié)點，有儲存數(shù)據(jù)的data，還有后驅(qū)節(jié)點next(指針)。單鏈表想要遍歷的操作都得從前節(jié)點—>后節(jié)點。
雙鏈表的一個節(jié)點，有存儲數(shù)據(jù)的data,也有后驅(qū)節(jié)點next(指針)，這和單鏈表是一樣的，但它還有一個前驅(qū)節(jié)點pre(指針)。
上一篇講單鏈表的時候，當(dāng)時設(shè)計一個帶頭結(jié)點的鏈表就錯過了不帶頭結(jié)點操作方式，這里雙鏈表就不帶頭結(jié)點設(shè)計實現(xiàn)。所以本文構(gòu)造的這個雙鏈表是：不帶頭節(jié)點、帶尾指針(tail)的雙向鏈表。
public class DoubleLinkedList<T> { private Node<T> head; private Node<T> tail; private int size; public DoubleLinkedList(){ this.head = null; this.tail = null; size = 0; } public void addHead(T data){} public void add(T data, int index){} public void addTail(T data){} public void deleteHead(){} public void delete(int index){} public void deleteTail(int index){} public T get(int index){} public int getSize() { return size; } private static class Node<T> { T data; Node<T> pre; Node<T> next; public Node() { } public Node(T data) { this.data = data; } }}對于一個鏈表主要的操作還是增刪，查詢的話不做詳細(xì)解釋。
剖析增刪其實可以發(fā)現(xiàn)大概有頭插入、編號插入、末尾插入、頭刪除、編號刪除、尾刪除幾種情況。然而這幾種關(guān)于頭尾操作的可能會遇到臨界點比如鏈表為空時插入刪除、或者刪除節(jié)點鏈表為空。
這個操作是不帶頭結(jié)點的操作，所以復(fù)雜性會高一些！
頭插入?yún)^(qū)分頭為空和頭不為空兩種情況。
頭為空：這種情況head和tail都指向新節(jié)點。
頭不為空：
尾插需要考慮tail為null和不為null的情況。流程和頭插類似，需要考慮tail指針最后的指向。
tail為null：此時head也為null，head和tail指向新節(jié)點。
tail不為null：
按編號插入分情況討論，如果是頭插或者尾插就直接調(diào)用對應(yīng)的方法。普通方法的實現(xiàn)方式比較靈活，可以找到前驅(qū)節(jié)點和后驅(qū)節(jié)點，然后進(jìn)行指針插入，但是往往很多時候只用一個節(jié)點完成表示和相關(guān)操作，就非常考驗對表示的理解，這里假設(shè)只找到preNode節(jié)點。 index為0：調(diào)用頭插。
index為size：調(diào)用尾插
index在(0,size):
頭刪除需要注意的就是刪除不為空時候頭刪除只和head節(jié)點有關(guān)
head不為null：
尾刪除和頭刪除類似，考慮好tail節(jié)點情況
如果tail不為null：
編號刪除和編號插入類似，先考慮是否為頭尾操作，然后再進(jìn)行正常操作。
index為0：調(diào)用頭刪
index為size：調(diào)用尾刪
index在(0,size):
根據(jù)上面的流程，實現(xiàn)一個不帶頭結(jié)點的雙鏈表，在查找方面，可以根據(jù)靠頭近還是尾近，選擇從頭或者尾開始遍歷。
代碼：
/* * 不帶頭節(jié)點的 */package code.linearStructure;/** * @date 2023.11.02 * @author bigsai * @param <T> */public class DoubleLinkedList<T> { private Node<T> head; private Node<T> tail; private int size; public DoubleLinkedList() { this.head = null; this.tail = null; size = 0; } // 在鏈表頭部添加元素 public void addHead(T data) { Node<T> newNode = new Node<>(data); if (head == null) { head = newNode; tail = newNode; } else { newNode.next = head; head.pre = newNode; head = newNode; } size++; } // 在指定位置插入元素 public void add(T data, int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index is out of bounds"); } if (index == 0) { addHead(data); } else if (index == size) { addTail(data); } else { Node<T> newNode = new Node<>(data); Node<T> preNode = getNode(index-1); //step 1 2 新節(jié)點與后驅(qū)節(jié)點建立聯(lián)系 newNode.next = preNode; preNode.next.pre = newNode; //step 3 4 新節(jié)點與前驅(qū)節(jié)點建立聯(lián)系 preNode.next = newNode; newNode.pre = preNode; size++; } } // 在鏈表尾部添加元素 public void addTail(T data) { Node<T> newNode = new Node<>(data); if (tail == null) { head = newNode; tail = newNode; } else { newNode.pre = tail; tail.next = newNode; tail = newNode; } size++; } // 刪除頭部元素 public void deleteHead() { if (head != null) { head = head.next; if (head != null) { head.pre = null; } else { //此時說明之前head和tail都指向唯一節(jié)點，鏈表刪除之后head和tail都應(yīng)該指向null tail = null; } size--; } } // 刪除指定位置的元素 public void delete(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index is out of bounds"); } if (index == 0) { deleteHead(); } else if (index == size - 1) { deleteTail(); } else { Node<T> current = getNode(index); current.pre.next = current.next; current.next.pre = current.pre; size--; } } // 刪除尾部元素 public void deleteTail() { if (tail != null) { tail = tail.pre; if (tail != null) { tail.next = null; } else {//此時說明之前head和tail都指向唯一節(jié)點，鏈表刪除之后head和tail都應(yīng)該指向null head = null; } size--; } } // 獲取指定位置的元素 public T get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index is out of bounds"); } Node<T> node = getNode(index); return node.data; } // 獲取鏈表的大小 public int getSize() { return size; } private Node<T> getNode(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index is out of bounds"); } if (index < size / 2) { Node<T> current = head; for (int i = 0; i < index; i++) { current = current.next; } return current; } else { Node<T> current = tail; for (int i = size - 1; i > index; i--) { current = current.pre; } return current; } } private static class Node<T> { T data; Node<T> pre; Node<T> next; public Node(T data) { this.data = data; } }}在插入刪除的步驟，很多人可能因為繁瑣的過程而弄不明白，這個操作的寫法可能是多樣的，但本質(zhì)操作都是一致的，要保證能成功表示節(jié)點并操作，這個可以畫個圖一步一步捋一下，看到其他不同版本有差距也是正常的。
還有很多人可能對一堆next.next搞不清楚，那我教你一個技巧，如果在等號右側(cè)，那么它表示一個節(jié)點，如果在等號左側(cè)，那么除了最后一個.next其他的表示節(jié)點。例如node.next.next.next可以看成(node.next.next).next。
在做數(shù)據(jù)結(jié)構(gòu)與算法鏈表相關(guān)題的時候，不同題可能給不同節(jié)點去完成插入、刪除操作。這種情況操作時候要謹(jǐn)慎先后順序防止破壞鏈表結(jié)構(gòu)。
本文鏈接：http://www.www897cc.com/showinfo-26-17665-0.html一文搞定雙鏈表，讓你徹底弄懂線性表的鏈?zhǔn)綄崿F(xiàn)
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號