鏈表（Linked List）
單鏈表
上篇文章我們設計了一個動態陣列，但發現動態陣列有個明顯的缺點：如果存盤不滿的話，可能會造成記憶體空間的大量浪費
怎樣才能做到用多少就申請多少呢？
鏈表就可以做到這一點
鏈表是一種鏈式存盤的線性表，所有元素的記憶體地址不一定是連續的
單鏈表的設計
下面我們就來設計一個鏈表
由于鏈表的大部分介面和動態陣列是一樣的，所以我們要先將結構做好劃分
完整的設計代碼如下
宣告一個介面檔案
// 定義介面，只宣告
// 介面里的宣告默認都是公共的，不需要再加上public
public interface List<E> {
// 暴露出去，可以給外界判斷使用
static final int ELEMENT_NOT_FOUND = -1;
/**
* 清除所有元素
*/
void clear();
/**
* 元素的數量
* @return
*/
int size();
/**
* 是否為空
* @return
*/
boolean isEmpty();
/**
* 是否包含某個元素
* @param element
* @return
*/
boolean contains(E element);
/**
* 添加元素到尾部
* @param element
*/
void add(E element);
/**
* 獲取index位置的元素
* @param index
* @return
*/
E get(int index);
/**
* 設定index位置的元素
* @param index
* @param element
* @return 原來的元素?
*/
E set(int index, E element);
/**
* 在index位置插入一個元素
* @param index
* @param element
*/
void add(int index, E element);
/**
* 洗掉index位置的元素
* @param index
* @return
*/
E remove(int index);
/**
* 查看元素的索引
* @param element
* @return
*/
int indexOf(E element);
}
將鏈表和動態陣列的共同實作都抽取到一個父類中
// implements List：要實作該介面
// 在該類中實作公共的邏輯
// abstract：意味抽象類，可以不用完全實作介面中的宣告，剩余不是公共的實作交給子類去實作
// 抽象類也是不可以創建實體的
// 該類不對外公開，目的只是為了抽取一些公共邏輯，不需要暴露讓別人知道
public abstract class AbstractList<E> implements List<E> {
/**
* 元素的數量
*/
protected int size;
/**
* 元素的數量
* @return
*/
public int size() {
return size;
}
/**
* 是否為空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某個元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
protected void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
protected void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
}
單鏈表的實作
import com.company.AbstractList;
// extends AbstractList：繼承父類AbstractList
public class SingleLinkedList<E> extends AbstractList<E> {
private Node<E> first; // 首節點
// 內部類
private static class Node<E> {
E element; // 當前節點的元素
Node<E> next; // 下一個節點
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
@Override
public void clear() {
size = 0;
first = null; // 首節點為null，后面的所有節點也就都會被釋放了
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element; // 拿到當前節點元素并覆寫
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index); // 先判斷邊界元素是否合格
if (index == 0) { // 如果是首元素，直接創建新的節點
first = new Node<>(element, first);
} else { // 如果是其他元素，找到其上一個節點來創建
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++; // 增加容量
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = first;
if (index == 0) { // 如果是首元素，指向首元素的下一個節點
first = first.next;
} else { // 如果是其他元素，找到其上一個節點，將其next指向要洗掉的節點的下一個節點
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--; // 減少容量
return node.element;
}
@Override
public int indexOf(E element) {
Node<E> node = first;
if (element == null) {
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 獲取index位置對應的節點物件
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index); // 首先判斷邊界元素是否合格
// 從首節點一直回圈找到index的位置
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node.element);
node = node.next;
}
string.append("]");
return string.toString();
}
}
設計點的詳細講解：
1.因為鏈表和動態陣列的公共介面都是一樣的，所以宣告一個介面檔案共同使用
再將鏈表和動態陣列的共同實作抽取到一個公共父類里，兩者都繼承該父類的實作
不同的介面實作再單獨在各自子類里取實作
// 介面宣告
public interface List<E> {
....
}
// 公共父類
public abstract class AbstractList<E> implements List<E> {
....
}
// 單鏈表
public class SingleLinkedList<E> extends AbstractList<E> {
....
}
// 動態陣列
public class ArrayList<E> extends AbstractList<E> {
....
}
2.清除所有元素時，由于每一個節點都是被上一個節點參考著的，所以只要斷掉首節點的參考，后面的節點就都會被釋放掉了
@Override
public void clear() {
size = 0;
first = null;
}
3.鏈表的查找元素，都是要從首節點一直向后遍歷查找的
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
4.獲取和更改元素時，都是要通過首節點，遍歷找到對應位置的節點元素
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
5.增加和洗掉元素時，都是要區分首節點和其他節點的查找區別來對應處理的
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == 0) { // 如果是首元素，直接創建新的節點
first = new Node<>(element, first);
} else { // 如果是其他元素，找到其上一個節點來創建
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++; // 增加容量
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = first;
if (index == 0) { // 如果是首元素，指向首元素的下一個節點
first = first.next;
} else { // 如果是其他元素，找到其上一個節點，將其next指向要洗掉的節點的下一個節點
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--; // 減少容量
return node.element;
}
其他實作方案
有時候為了讓代碼更加精簡，統一所有節點的處理邏輯，可以在最前面增加一個虛擬的頭結點
虛擬的頭結點不存盤資料
實作代碼如下
public class SingleLinkedList<E> extends AbstractList<E> {
private Node<E> first;
public SingleLinkedList2() {
first = new Node<>(null, null);
}
private static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
@Override
public void clear() {
size = 0;
first.next = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
Node<E> prev = index == 0 ? first : node(index - 1);
prev.next = new Node<>(element, prev.next);
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> prev = index == 0 ? first : node(index - 1);
Node<E> node = prev.next;
prev.next = node.next;
size--;
return node.element;
}
@Override
public int indexOf(E element) {
Node<E> node = first.next; // 從虛擬頭結點的下一個獲取
if (element == null) {
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node<E> node = first.next;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node.element);
node = node.next;
}
string.append("]");
return string.toString();
}
}
以上兩種方案都可以，可以自行選擇哪種更適用
復雜度
get函式和set函式的三種復雜度是一致的：
- 最好復雜度為
O(1) - 最壞復雜度為
O(n) - 平均復雜度為
O(n)
最好復雜度和最壞復雜度都是需要呼叫node(int index)進行遍歷的
最好復雜度也就是需要查找的元素剛好是首元素
最壞復雜度就是需要查找的元素是最后一個，那么就需要遍歷整個節點來找
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
add函式和remove函式的三種復雜度也是一致的：
- 最好復雜度為
O(1) - 最壞復雜度為
O(n) - 平均復雜度為
O(n)
最好復雜度也就是需要插入和移除的元素剛好是首元素，那么就不需要遍歷
最壞復雜度就是需要插入和移除的元素是最后一個，那么就需要遍歷整個節點來找
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == 0) { // 如果是首元素，直接創建新的節點
first = new Node<>(element, first);
} else { // 如果是其他元素，找到其上一個節點來創建
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++; // 增加容量
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = first;
if (index == 0) { // 如果是首元素，指向首元素的下一個節點
first = first.next;
} else { // 如果是其他元素，找到其上一個節點，將其next指向要洗掉的節點的下一個節點
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--; // 減少容量
return node.element;
}
動態陣列和鏈表的復雜度對比
雙向鏈表
使用雙向鏈表可以提升鏈表的綜合性能
雙向鏈表的設計
public class LinkedList<E> extends AbstractList<E> {
private Node<E> first; // 首節點
private Node<E> last; // 尾節點
// 內部類
private static class Node<E> {
E element; // 當前節點的元素
Node<E> prev; // 上一個節點
Node<E> next; // 下一個節點
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (prev != null) {
sb.append(prev.element);
} else {
sb.append("null");
}
sb.append("_").append(element).append("_");
if (next != null) {
sb.append(next.element);
} else {
sb.append("null");
}
return sb.toString();
}
}
@Override
public void clear() {
size = 0;
first = null;
last = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element; // 拿到當前節點元素并覆寫
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == size) { // 往最后面添加元素
Node<E> oldLast = last;
last = new Node<>(oldLast, element, null);
if (oldLast == null) { // 如果鏈表沒有元素的時候，也會進來這里
first = last;
} else {
oldLast.next = last;
}
} else { // 從前面添加元素
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
if (prev == null) { // index == 0，也就是插入到第一個節點的位置
first = node;
} else {
prev.next = node;
}
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
if (prev == null) { // index == 0，也就是洗掉的首節點
first = next;
} else {
prev.next = next;
}
if (next == null) { // index == size - 1，也就是洗掉的尾節點
last = prev;
} else {
next.prev = prev;
}
size--;
return node.element;
}
@Override
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 獲取index位置對應的節點物件
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);
if (index < (size >> 1)) { // 分出兩部分來查找，從前往后找
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else { // 從后往前找
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node);
node = node.next;
}
string.append("]");
return string.toString();
}
}
設計點的詳細講解：
1.鏈表類增加尾節點的成員變數，便于從后往前查找
內部節點增加成員變數保存上一個節點，并調整構造方法
public class LinkedList<E> extends AbstractList<E> {
private Node<E> first; // 首節點
private Node<E> last; // 尾節點
// 內部類
private static class Node<E> {
E element; // 當前節點的元素
Node<E> prev; // 上一個節點
Node<E> next; // 下一個節點
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}
}
2.清空所有元素時，首節點和尾節點都置為null，整個鏈表就會被釋放了
雙向鏈表看似回圈參考，但Java中只要不是被gc root物件參考著的就會被釋放
被堆疊指標指向的物件即為gc root物件，也就是區域變數參考的物件
例如LinkedList<Integer> list = new LinkedList<>()中創建的LinkedList物件即為gc root物件，所以函式作用域一旦結束，區域變數list所指向的LinkedList物件就會被銷毀，鏈表也就會被釋放
@Override
public void clear() {
size = 0;
first = null;
last = null;
}
3.通過索引獲取節點時，如果查找的是整個鏈表長度的前一半，順序就是從前向后查找；如果查找的索引是在后一半，順序就是從后向前查找
這樣做的目的優化了單鏈表只能從前向后查找的效率
private Node<E> node(int index) {
rangeCheck(index);
if (index < (size >> 1)) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else { // 從后往前找
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
4.添加元素時，主要就是找到索引處的節點，然后將其上一個節點的next和下一個節點的prev指向需要添加的節點
添加元素時要區分臨界元素的情況，如果是首尾節點的位置，要對應處理好指向null以及成員變數first、last的指向
如果鏈表還沒有節點的時候，那么first、last指向的都是需要添加的節點，并且它的上一個節點和下一個節點都是null
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == size) { // 往最后面添加元素
Node<E> oldLast = last;
last = new Node<>(oldLast, element, null);
if (oldLast == null) { // 如果鏈表沒有元素的時候，也會進來這里
first = last;
} else {
oldLast.next = last;
}
} else { // 從前面添加元素
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
if (prev == null) { // index == 0，也就是插入到第一個節點的位置
first = node;
} else {
prev.next = node;
}
}
size++;
}
5.洗掉元素時，主要就是找到索引處的節點，然后將其上一個節點的next指向其下一個節點；其下一個節點的prev指向其上一個節點，這樣該節點沒有被任何指引了就會釋放掉了
也是要注意臨界元素的情況，首元素和尾元素的洗掉對應改變first、last的指向
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
if (prev == null) { // index == 0，也就是洗掉的首節點
first = next;
} else {
prev.next = next;
}
if (next == null) { // index == size - 1，也就是洗掉的尾節點
last = prev;
} else {
next.prev = prev;
}
size--;
return node.element;
}
雙向鏈表的對比
雙向鏈表對比單向鏈表
我們來對比下雙向鏈表和單向鏈表的洗掉函式，發現操作資料會縮減一半
雙向鏈表對比動態陣列
動態陣列：開辟、銷毀記憶體空間的次數相對較少，但可能造成記憶體空間浪費（可以通過縮容解決）
雙向鏈表：開辟、銷毀記憶體空間的次數相對較多，但不會造成記憶體空間的浪費
雙向鏈表和動態陣列的選擇
如果頻繁在尾部進行添加、洗掉的操作，動態陣列、雙向鏈表均可選擇
如果頻繁在頭部進行添加、洗掉的操作，建議選擇使用雙向鏈表
如果有頻繁的（在任意位置）添加、洗掉的操作，建議選擇使用雙向鏈表
如果有頻繁的查詢操作，建議選擇使用動態陣列
有了雙向鏈表，那單鏈表是否沒有任何用處了？
不是的，在哈希表的設計中就用到了單鏈表，具體詳情請參照哈希表的設計章節
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272449.html
標籤：其他
上一篇：SIP (Session Initiation Protocol) 協議
下一篇：資料結構與演算法（四）鏈表（上）