線性表與雙向鏈表實現詳解 (C/C++/Java 三語言版)

本文系統講解線性表的三種主要存儲結構：數組、單向鏈表、雙向鏈表，並提供 C、C++、Java 三種語言的完整雙向鏈表實現代碼，包含增刪改查、正反向遍歷、泛型支援等核心操作。

線性表三大存儲結構對比

雙向鏈表核心操作圖解

節點結構

[prev] ← Node(data) → [next]
  ↑                      ↑
前驅節點               後繼節點

刪除節點

// 刪除 node
node.prev.next = node.next;
node.next.prev = node.prev;
// 釋放 node 記憶體 (C/C++ 需手動 free/delete)

插入節點 (在 index 位置前)

// 新節點 newNode 插入到 indexNode 前
newNode.prev = indexNode.prev;
newNode.next = indexNode;
indexNode.prev.next = newNode;
indexNode.prev = newNode;

C 語言實現 (結構體 + 函數指針模擬 OO)

// double_link.h
#ifndef _DOUBLE_LINK_H
#define _DOUBLE_LINK_H

typedef void* Data;  // 泛型數據指針

typedef struct DLinkNode {
    struct DLinkNode *prev;
    struct DLinkNode *next;
    Data data;
} DLinkNode;

typedef struct {
    DLinkNode *head;  // 哨兵頭節點
    int size;
} DoubleLink;

// 接口函數
DoubleLink* dlink_create();
void dlink_destroy(DoubleLink* list);
int dlink_is_empty(DoubleLink* list);
int dlink_size(DoubleLink* list);
Data dlink_get(DoubleLink* list, int index);
Data dlink_get_first(DoubleLink* list);
Data dlink_get_last(DoubleLink* list);
int dlink_insert(DoubleLink* list, int index, Data data);
int dlink_insert_first(DoubleLink* list, Data data);
int dlink_append_last(DoubleLink* list, Data data);
int dlink_delete(DoubleLink* list, int index);
int dlink_delete_first(DoubleLink* list);
int dlink_delete_last(DoubleLink* list);

#endif

// double_link.c
#include "double_link.h"
#include 
#include 

static DLinkNode* create_node(Data data) {
    DLinkNode* node = (DLinkNode*)malloc(sizeof(DLinkNode));
    if (!node) return NULL;
    node->prev = node->next = node;  // 循環自引用
    node->data = data;
    return node;
}

DoubleLink* dlink_create() {
    DoubleLink* list = (DoubleLink*)malloc(sizeof(DoubleLink));
    if (!list) return NULL;
    list->head = create_node(NULL);  // 哨兵節點不存數據
    if (!list->head) { free(list); return NULL; }
    list->size = 0;
    return list;
}

void dlink_destroy(DoubleLink* list) {
    if (!list) return;
    DLinkNode* cur = list->head->next;
    while (cur != list->head) {
        DLinkNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(list->head);
    free(list);
}

static DLinkNode* get_node(DoubleLink* list, int index) {
    if (index < 0 || index >= list->size) return NULL;
    // 雙向優化：從較近一端遍歷
    DLinkNode* node;
    if (index <= list->size / 2) {
        node = list->head->next;
        for (int i = 0; i < index; i++) node = node->next;
    } else {
        node = list->head->prev;
        for (int i = list->size - 1; i > index; i--) node = node->prev;
    }
    return node;
}

Data dlink_get(DoubleLink* list, int index) {
    DLinkNode* node = get_node(list, index);
    return node ? node->data : NULL;
}

Data dlink_get_first(DoubleLink* list) { return dlink_get(list, 0); }
Data dlink_get_last(DoubleLink* list) { return dlink_get(list, list->size - 1); }

int dlink_insert(DoubleLink* list, int index, Data data) {
    if (index < 0 || index > list->size) return -1;
    if (index == 0) return dlink_insert_first(list, data);
    if (index == list->size) return dlink_append_last(list, data);
    
    DLinkNode* indexNode = get_node(list, index);
    if (!indexNode) return -1;
    
    DLinkNode* newNode = create_node(data);
    if (!newNode) return -1;
    
    newNode->prev = indexNode->prev;
    newNode->next = indexNode;
    indexNode->prev->next = newNode;
    indexNode->prev = newNode;
    list->size++;
    return 0;
}

int dlink_insert_first(DoubleLink* list, Data data) {
    DLinkNode* newNode = create_node(data);
    if (!newNode) return -1;
    newNode->prev = list->head;
    newNode->next = list->head->next;
    list->head->next->prev = newNode;
    list->head->next = newNode;
    list->size++;
    return 0;
}

int dlink_append_last(DoubleLink* list, Data data) {
    DLinkNode* newNode = create_node(data);
    if (!newNode) return -1;
    newNode->next = list->head;
    newNode->prev = list->head->prev;
    list->head->prev->next = newNode;
    list->head->prev = newNode;
    list->size++;
    return 0;
}

int dlink_delete(DoubleLink* list, int index) {
    DLinkNode* node = get_node(list, index);
    if (!node) return -1;
    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node);
    list->size--;
    return 0;
}

int dlink_delete_first(DoubleLink* list) { return dlink_delete(list, 0); }
int dlink_delete_last(DoubleLink* list) { return dlink_delete(list, list->size - 1); }

int dlink_is_empty(DoubleLink* list) { return list->size == 0; }
int dlink_size(DoubleLink* list) { return list->size; }

C++ 實現 (模板類 + RAII)

// DoubleLink.h
#ifndef DOUBLE_LINK_H
#define DOUBLE_LINK_H

template <typename T>
class DoubleLink {
private:
    struct Node {
        T value;
        Node *prev, *next;
        Node(const T& v, Node* p, Node* n) : value(v), prev(p), next(n) {}
    };
    
    Node *head;  // 哨兵節點
    int count;
    
    Node* getNode(int index) const {
        if (index < 0 || index >= count) return nullptr;
        if (index <= count / 2) {
            Node* n = head->next;
            for (int i = 0; i < index; i++) n = n->next;
            return n;
        } else {
            Node* n = head->prev;
            for (int i = count - 1; i > index; i--) n = n->prev;
            return n;
        }
    }

public:
    DoubleLink() : count(0) {
        head = new Node(T(), nullptr, nullptr);
        head->prev = head->next = head;
    }
    
    ~DoubleLink() {
        Node* cur = head->next;
        while (cur != head) {
            Node* next = cur->next;
            delete cur;
            cur = next;
        }
        delete head;
    }
    
    int size() const { return count; }
    bool empty() const { return count == 0; }
    
    T get(int index) const { return getNode(index)->value; }
    T front() const { return get(0); }
    T back() const { return get(count - 1); }
    
    void insert(int index, const T& value) {
        if (index == 0) { insertFront(value); return; }
        if (index == count) { pushBack(value); return; }
        Node* idx = getNode(index);
        Node* node = new Node(value, idx->prev, idx);
        idx->prev->next = node;
        idx->prev = node;
        count++;
    }
    
    void insertFront(const T& value) {
        Node* node = new Node(value, head, head->next);
        head->next->prev = node;
        head->next = node;
        count++;
    }
    
    void pushBack(const T& value) {
        Node* node = new Node(value, head->prev, head);
        head->prev->next = node;
        head->prev = node;
        count++;
    }
    
    void erase(int index) {
        Node* node = getNode(index);
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete node;
        count--;
    }
    
    void popFront() { erase(0); }
    void popBack() { erase(count - 1); }
};

#endif

Java 實現 (泛型 + 內部類)

public class DoubleLink<T> {
    private static class Node<T> {
        T value;
        Node<T> prev, next;
        Node(T value, Node<T> prev, Node<T> next) {
            this.value = value; this.prev = prev; this.next = next;
        }
    }
    
    private Node<T> head;  // 哨兵節點
    private int count;
    
    public DoubleLink() {
        head = new Node<>(null, null, null);
        head.prev = head.next = head;
        count = 0;
    }
    
    public int size() { return count; }
    public boolean isEmpty() { return count == 0; }
    
    private Node<T> getNode(int index) {
        if (index < 0 || index >= count) throw new IndexOutOfBoundsException();
        if (index <= count / 2) {
            Node<T> n = head.next;
            for (int i = 0; i < index; i++) n = n.next;
            return n;
        } else {
            Node<T> n = head.prev;
            for (int i = count - 1; i > index; i--) n = n.prev;
            return n;
        }
    }
    
    public T get(int index) { return getNode(index).value; }
    public T getFirst() { return get(0); }
    public T getLast() { return get(count - 1); }
    
    public void insert(int index, T value) {
        if (index == 0) { insertFirst(value); return; }
        if (index == count) { appendLast(value); return; }
        Node<T> idx = getNode(index);
        Node<T> node = new Node<>(value, idx.prev, idx);
        idx.prev.next = node;
        idx.prev = node;
        count++;
    }
    
    public void insertFirst(T value) {
        Node<T> node = new Node<>(value, head, head.next);
        head.next.prev = node;
        head.next = node;
        count++;
    }
    
    public void appendLast(T value) {
        Node<T> node = new Node<>(value, head.prev, head);
        head.prev.next = node;
        head.prev = node;
        count++;
    }
    
    public void delete(int index) {
        Node<T> node = getNode(index);
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node = null;  // 幫助 GC
        count--;
    }
    
    public void deleteFirst() { delete(0); }
    public void deleteLast() { delete(count - 1); }
}

測試代碼與輸出 (三語言一致)

// 測試邏輯：插入 30, 20, 10 → 列表順序: 30, 20, 10
DoubleLink list = new DoubleLink<>();
list.insert(0, 20);      // [20]
list.appendLast(10);     // [20, 10]
list.insertFirst(30);    // [30, 20, 10]

// 輸出
for (int i = 0; i < list.size(); i++) {
    System.out.println("list(" + i + ") = " + list.get(i));
}
// list(0) = 30
// list(1) = 20
// list(2) = 10

關鍵設計模式總結

Java 實際開發建議

生產代碼不要手寫鏈表，直接使用 JDK 內建：

• java.util.LinkedList<E>：雙向鏈表實現 List、Deque
• java.util.concurrent.ConcurrentLinkedDeque：線程安全雙端隊列

// 實際使用
List list = new LinkedList<>();
list.addFirst("first");
list.addLast("last");
list.removeFirst();
list.get(0);

總結

雙向鏈表通過 prev/next 雙指針實現 O(1) 插入刪除與雙向遍歷，是理解數據結構的基礎。三語言實現展示了同一邏輯在不同抽象層級的表達：C 手動管理記憶體、C++ 模板+RAII、Java 泛型+GC。實際開發中優先使用標準庫，手寫僅用於教學、面試或極致性能定製場景。