資料結構之鏈表-動圖演示-有解無憂

鏈表簡介

鏈表是很常見的資料結構，由一個個節點組成，每個節點中儲存著資料和指標(地址參考)，指標負責節點間的連接，

它是一種線性表，線性表有兩種存盤方式：順序存盤和鏈式存盤，鏈表屬于鏈式存盤，順序由元素間的指標決定，元素在記憶體中非連續存放，且鏈表長度可以改變，陣列是順序存盤的線性表，元素在記憶體中連續存放的，且陣列創建時大小已固定，

鏈表可以用來實作堆疊和佇列資料結構(堆疊和佇列可理解為邏輯類資料結構，鏈表屬于存盤類資料結構)，實作快取LRU演算法，Java類別庫也使用了鏈表(如，LinkedList，LinkedHashMap)等，鏈表的形式有很多，常用的有單向鏈表、雙向鏈表、回圈鏈表 ...

單向鏈表

單鏈表中的節點分兩部分，分別是資料(data)和指向下一個節點的地址(next)，尾節點(tail)的next指向null，單向鏈表只能從頭到尾一個方向遍歷，查找節點時需要從頭節點(head)開始向下查找，
插入節點首先遍歷查找到插入的位置，然后將當前插入節點的next指向下一節點，上一節點的next指向當前插入節點，洗掉節點同樣從頭遍歷找到要洗掉的節點，然后將當前洗掉節點的上一個節點next指向當前洗掉節點的下一個節點，

單向鏈表

節點的偽代碼：

class Node<E>{
    private E item;
    private Node<E> next; // 如果是尾節點，next指向null
    Node(E data, Node<E> next) {
        this.item = data;
        this.next = next;
    }
    // ...
}

單向回圈鏈表

回圈鏈表和非回圈鏈表基本一樣，區別是首尾節點連在了一起，最后一個節點的next指向頭節點，形成了一個倍訓，

單向回圈鏈表

節點的偽代碼：

class Node<E>{
    private E item;
    // 如果是末尾節點，指向首節點的參考地址
    private Node<E> next;
    Node(E data, Node<E> next) {
        this.item = data;
        this.next = next;
    }
    // ...
}

雙向鏈表

顧名思義，與單向鏈表相比較，雙向鏈表可以從頭到尾或從尾到頭兩個方向來遍歷資料，雙向鏈表中的節點分三個部分，分別是指向上一個節點的地址(prev)和資料(data)以及指向下一個節點的地址(next)，尾節點(tail)節點的next指向null，頭節點(head)的prev指向null，
增加和洗掉節點和單向鏈表同理，只是增加了修改prev地址的操作，

雙向鏈表

節點的偽代碼：

class Node<E>{
    private E item;
    private Node<E> prev; // 頭節點prev指向null
    private Node<E> next; // 尾節點next指向null
    Node(Node<E> prev, E data, Node<E> next) {
        this.item = data;
        this.prev = prev;
        this.next = next;
    }
   // ... 
}

雙向回圈鏈表

尾節點的next指向頭節點，頭結點的prev指向尾節點，首尾節點連在一起形成倍訓，

雙向回圈鏈表

節點的偽代碼：

class Node<E> { 
    private E item;
    // 如果是第一個節點，其一用指向末尾節點
    private Node<E> prev;
    // 如果是末尾結點，指向第一個結點的參考地址,形成一個環形
    private Node<E> next;
    Node(Node<E> prev, E data, Node<E> next) {
        this.item = data;
        this.prev = prev;
       this.next = next;
   }
   // ...
}

鏈表操作

鏈表的增刪改查操作，鏈表查找節點需要從頭或者尾部(單向鏈表只能從頭開始)開始查找，洗掉或插入節點先查找到節點，然后改變相關節點的指標指向即可，

以雙向鏈表為例：

添加節點

頭部添加節點

添加節點

偽代碼：

Node<E> head;
Node<E> tail;
int size;

// 頭部添加節點
void addHead(E e) {
    Node<E> h = head;
    Node<E> newNode = new Node<>(null, e, h); // (Node<E> prev, E element, Node<E> next)
    head = newNode;
    if(h == null) { // 空鏈表
        tail = newNode;
     } else {
       h.prev = newNode;
    }   
   size++; // 記錄長度
}

尾部添加節點

添加節點

偽代碼：

void addTail(E e) {
    Node<E> t = tail;
    Node<E> newNode = new Node<>(t, e, null);
    tail = newNode;
    if(t == null) {
        head = newNode;
    } else {
       t.next = newNode;      
    }       
    size++;
}

按位置插入節點

添加節點

偽代碼：

void add(int index, E element) {
        if (index == size) {
            // 直接在尾部添加節點
        } else {
           // 查找的節點
           Node<E> temp = null;
           if (index < (size >> 1)) {//由于雙向鏈表，選擇從離index位置最近端查找
                Node<E> x = head;
                for (int i = 0; i < index; i++) {
                    x = x.next;
                }
                temp = x;    
            } else {
                Node<E> x = tail;
                for (int i = size - 1; i > index; i--) {
                    x = x.prev;
                }
                temp = x;   
            }
            
            // 插入節點
            Node<E> pred = temp.prev;
            Node<E> newNode = new Node<>(pred, element, temp);
            temp.prev = newNode;
            if (pred == null) { // 查找到的節點為Head節點
                head = newNode;
            } else {
                pred.next = newNode;
            }   
        } 
        size++;
    }

洗掉節點

洗掉頭部節點

洗掉節點

偽代碼：

E removeHead() {
    Node<E> h = head;    
    if (h != null){
        E element = h.item;
        Node<E> next = h.next;
        head = next;
        if (next == null) {
            tail = null;
        } else {
            next.prev = null;
       }   
       size--; // 減少長度
       return element; // 回傳洗掉元素
    }
    return null;
}

洗掉尾部節點

洗掉節點

偽代碼：

E removeTail() {
    Node<E> t = tail;
    if (t != null) {
        E element = t.item;
        Node<E> prev = t.prev;
        tail = prev;
        if (prev == null) {
            head = null;
        } else {
           prev.next = null;
       }
       size--;
       return element;
    }
    return null; 
}

按節點位置或值洗掉

洗掉節點

偽代碼-按位置洗掉：

E remove(int index) {
    // 根據index查找節點
    Node<E> temp = null;
    if (index < (size >> 1)) {
        Node<E> x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        temp = x;    
    } else {
        Node<E> x = tail;
        for (int i = size - 1; i > index; i--) {
            x = x.prev;
        }
        temp = x;   
    }
    // 洗掉節點
    E element = temp.item;
    Node<E> next = temp.next;
    Node<E> prev = temp.prev;
    if (prev == null) {
        head = next;
    } else {
        prev.next = next;
        temp.prev = null;
    }
    if (next == null) {
        tail= prev;
    } else {
        next.prev = prev;
        temp.next = null;
    }
    temp.item = null;
    size--; 
    return element;
}

查找節點

按位置或值查找節點

查找節點

偽代碼-按位置索引查找：

E get(int index) {
  Node<E> temp = null;
  if (index < (size >> 1)) { // 從近的一端開始查找
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        } 
        temp = x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) {
            x = x.prev;
        } 
        temp = x;
    }
    return temp.item;
}

如果是單向鏈表只能從頭部開始向后查找，

更新節點

更新節點首先查找到節點，然后修改節點data的指標，

具體可參考LinkedList原始碼

鏈表實作堆疊和佇列

堆疊和佇列是一種對資料存取有嚴格順序要求的線性資料結構，使用鏈表和陣列都能實作，下面使用鏈表來實作堆疊和佇列，

堆疊

堆疊只能從一端存取資料，遵循后進先出(LIFO)原則，進出堆疊的一端稱為堆疊頂，另一封閉端稱為堆疊底，資料進入堆疊稱為入堆疊或壓堆疊，取出資料稱為出堆疊或彈堆疊，

偽代碼 - 基于雙向鏈表實作簡單的“堆疊”：

class Stack<E> {
  
    // 回傳堆疊頂元素值
    public E peek() {
        Node<E> h = head;
        return (h == null) ? null : h.item;
    }
    
    // 入堆疊
    public void push(E e) {
        addHead(e); // 在頭部添加節點
    }
    
    // 出堆疊
    public E pop() {
        // 移除頭部節點并回傳值
        return removeHead(); 
    }
    
    // ...
    
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }  
}

佇列

佇列是從兩端存取資料，并且從一端進，從另一端出，遵循先進先出(FIFO)原則，佇列進資料一端稱為隊尾，出資料端稱為隊頭，資料進佇列稱為入隊，取出佇列稱為出隊，

偽代碼 - 基于鏈表實作“佇列”：

class Queue {
    // 入隊
    public boolean offer(E e) {
        return addTail(e); 
    }
    
    // 出隊
    public E poll() {
        return removeHead();
    }
    
    // 回傳頭元素值
    public E peek() {
        Node<E> h = head;
        return (h == null) ? null : h.item;
    }
    
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }   
}

快慢指標

快慢指標是解決鏈表某些問題的常用方法，利用兩個不同步頻的指標fast指標和slow指標演算法來解決很多問題，例如:

查找未知長度的單向鏈表倒數第N個值

由于鏈表長度未知，首先回圈鏈表得到 length，然后再次回圈鏈表到length-(N-1) 處得到元素，但是利用快慢指標來保持固定位置間隔，只需要回圈一次鏈表即可查找到元素，

查找倒數第N個值

偽代碼：

public E getLastN(int n) {
	Node<E> h = head;
	if (h == null || n < 1) {
		return null;
	}
	Node<E> fast = h; // 快
	Node<E> slow = h; // 慢
	int count = 1;
	while ((fast = fast.next) != null) {
		// 倒數第k個節點與倒數第1個節點相隔 n-1 個位置,因此fast先走 n-1 個位置
		if (count++ > n - 1) {
			slow = slow.next;
		}
	}
	// 鏈表中的元素個數小于 n
	if (count < n) {
		return null;
	}
 
	return slow.item;
}

找到鏈表中間節點值

使快指標移動步頻是慢指標二倍，一次遍歷即可快速找到中間節點，

查找中間節點

偽代碼：

public E getMiddle() {
	Node<E> h = head;
	if (h == null) {
		return null;
	}
	Node<E> fast = h; // 快
	Node<E> slow = h; // 慢
	while (fast != null && fast.next != null) {
		fast = fast.next.next;
		// 鏈表長度為偶數會兩個中間節點，回傳第一個
		if (fast != null) {
			slow = slow.next;
		}
	}
	return slow.item;
}

原始碼：https://github.com/newobjectcc/code-example/blob/master/basic/datastructure/Linked.java

除此之外，還可以判斷鏈表中是否有環等等問題，快慢指標在面試時可能會被問到，有興趣朋友可以到網上找些鏈表的演算法題，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/127176.html

標籤：其他

上一篇：CodeForces - 1228D （暴力+思維+亂搞）

下一篇：【LeetCode】11. 盛最多水的容器