數(shù)據(jù)結(jié)構(gòu)之實現(xiàn)單鏈表和雙向鏈表

單鏈表的實現(xiàn)

image.png

每個鏈表都有一個節(jié)點next和一個value表示這個節(jié)點的值,一般我們都會有個頭節(jié)點指向第一個元素，而最后一個節(jié)點next指向的是NULL

首先需要定義單鏈表的節(jié)點

template相當于Java中的泛型

template<class E>
struct Node {
    E value;
    Node<E> *next;
public:
    Node(E value, Node<E> *next) {
        this->value = value;
        this->next = next;
    }
};

常用的一些方法:添加，刪除，插入等

template<class E>
class LinkedList {

    // 頭指針
    Node<E> *head = NULL;
    //數(shù)組的長度
    int len = 0;
public:
    /**
     * 添加數(shù)據(jù)
     * @param e
     */
    void push(E e);

    int size();

    E get(int index);

    void insert(int index, E e);

    void remove(int index);

    ~LinkedList();

    Node<E> *node(int i);
};

添加數(shù)據(jù)

添加數(shù)據(jù)添加到的是尾部，那么我們首先需要找到這個鏈表的尾部，可以從頭指針開始遍歷到鏈表的大小

template<class E>
Node<E> *LinkedList<E>::node(int index) {//O(n)的時間復雜度
    Node<E> *h = head;
    for (int i = 0; i < index; ++i) {
        h = h->next;
    }
    return h;
}

添加數(shù)據(jù)就很簡單了

template<class E>
void LinkedList<E>::push(E e) {
    //添加一個數(shù)據(jù)
    Node<E> *new_node = new Node<E>(e, NULL);
    if (head) {//head是否為空
        //找到尾節(jié)點
        Node<E> *h = node(len - 1);
        h->next = new_node;

    } else {
        head = new_node;
    }
    len++;
}

獲取數(shù)據(jù)

template<class E>
E LinkedList<E>::get(int index) {
    assert(index >= 0 && index < len);
    return node(index)->value;
}

插入數(shù)據(jù)

此時分為兩種情況，插入頭部還是其他位置，插入其實就是將要插入的前一個節(jié)點，指向要插入的節(jié)點，而要插入的節(jié)點，指向之前插入的前一個節(jié)點指向的下一個節(jié)點，如下圖


image.png
template<class E>
void LinkedList<E>::insert(int index, E e) {

    //找到前一個
    Node<E> *new_node = new Node<E>(e, NULL);
    if (index == 0) {//插入在頭節(jié)點
        //當前頭節(jié)點需要保存下
        Node<E> *h = head;
        head = new_node;
        new_node->next = h;
    } else {
        //首先你必須獲得了要插入的前一個節(jié)點
        Node<E> *prev = node(index - 1);
        //保存下prev原本指向的下一個指針的位置
        Node<E> *next = prev->next;
        //然后前一個指針指向新節(jié)點
        prev->next = new_node;
        //新節(jié)點指向之前prev原本指向的下一個指針的位置
        new_node->next = next;
    }
    len++;
}

刪除節(jié)點

image.png

刪除節(jié)點就是將要刪除的節(jié)點的前一個節(jié)點指向要刪除的節(jié)點的i下一個節(jié)點

template<class E>
void LinkedList<E>::remove(int index) {
    assert(index >= 0 && index <= len);
    if (index == 0) {
        Node<E> *h = head;
        head = h->next;
        //刪除不要的節(jié)點
        delete h;
    } else {
        Node<E> *prev = node(index - 1);
        // 找到要刪除的節(jié)點
        Node<E> *cur = prev->next;
        //獲取刪除節(jié)點的下個節(jié)點
        Node<E> *next = cur->next;
        prev->next = next;//合并就是prev->next=cur->next
        //刪除當前節(jié)點
        delete cur;
    }
    len--;

}

上面我們是通過遍歷去獲得節(jié)點，此時的時間復雜度是O(n)級別，所以我們需要對這個時間復雜度進行優(yōu)化

單鏈表時間復雜度優(yōu)化

首先我們可以測試下我們沒有優(yōu)化前消耗多少時間

 LinkedList<int> linkedList;

    time_t start = clock();
    for (int i = 0; i < 50000; ++i) {
        linkedList.push(i);
    }
    time_t end = clock();
    //沒優(yōu)化14s
    __android_log_print(ANDROID_LOG_ERROR, "TAG", "%d", (end - start) / CLOCKS_PER_SEC);

我電腦運行消耗的時間是14s。
優(yōu)化思路：我們每次添加數(shù)據(jù)到最后一個位置的時候，如果知道最后一個位置的節(jié)點，這樣就不需要遍歷for循環(huán)了
LinkedList中定義尾節(jié)點

    //尾節(jié)點
    Node<E> *last = NULL;

修改代碼后

template<class E>
void LinkedList<E>::push(E e) {
    //添加一個數(shù)據(jù)
    Node<E> *new_node = new Node<E>(e, NULL);
    if (head) {//head是否為空

        last->next = new_node;
    } else {
        head = new_node;
    }
    last=new_node;
    len++;
}

此時我們時間復雜度變成了O(1)級別，再運行剛才測試時間代碼，我們發(fā)現(xiàn)消耗時間是0

雙向鏈表的實現(xiàn)

雙向鏈表.png

雙向鏈表結(jié)構(gòu)就是有個前節(jié)點+值+后節(jié)點，當前節(jié)點的next節(jié)點指向下個節(jié)點，而下個節(jié)點的prev指向上個節(jié)點

首先定以一個雙鏈表的節(jié)點

template<class E>
struct Node {
    E value;
    Node<E> *next, *prev;
public:
    Node(E value, Node<E> *prev, Node<E> *next) {
        this->value = value;
        this->next = next;
        this->prev = prev;
    }
};

雙鏈表節(jié)點的常用方法定義

template<class E>
class LinkedList {

    // 頭指針
    Node<E> *head = NULL;
    //數(shù)組的長度
    int len = 0;
    //尾節(jié)點
    Node<E> *last = NULL;
public:
    /**
     * 添加數(shù)據(jù)
     * @param e
     */
    void push(E e);

    int size();

    E get(int index);

    void insert(int index, E e);

    E remove(int index);

    ~LinkedList();

    Node<E> *node(int i);

    void linkedLast(E e);

    void linkBefore(Node<E> *node, E e);

    E unlink(Node<E> *node);
};

t添加數(shù)據(jù)

添加數(shù)據(jù)首先要獲取最后一個節(jié)點，讓最后一個節(jié)點等于要添加的新節(jié)點

template<class E>
void LinkedList<E>::push(E e) {
    linkedLast(e);
    len++;
}

linkedLast代碼

template<class E>
void LinkedList<E>::linkedLast(E e) {
    //保存上一個最后一個節(jié)點
    Node<E> *l = last;
    Node<E> *new_node = new Node<E>(e, last, NULL);
    //最后節(jié)點變成new_node
    last = new_node;
    if (head) {
        l->next = new_node;
    } else {
        head = new_node;
    }
}

二分查找的方式獲得當前位置的上個節(jié)點

/**
 * 遍歷找到當前節(jié)點的前一個節(jié)點
 */
template<class E>
Node<E> *LinkedList<E>::node(int index) {//O(n)的時間復雜度
    if (index < len >> 1) {
        //從前往后遍歷
        Node<E> *cur = head;
        for (int i = 0; i < index; ++i) {
            cur = cur->next;
        }
        return cur;
    } else {
        // 從后往前遍歷
        Node<E> *cur = last;
        for (int i = len - 1; i > index; i--) {
            cur = cur->prev;
        }
        return cur;
    }
}

獲得數(shù)據(jù)和鏈表的大小

template<class E>
int LinkedList<E>::size() {
    return len;
}
template<class E>
E LinkedList<E>::get(int index) {
    assert(index >= 0 && index < len);
    return node(index)->value;
}

插入數(shù)據(jù)

image.png

首先我們要被插入數(shù)據(jù)的節(jié)點是node節(jié)點，node的前節(jié)點需要進行保存，此時，node的前節(jié)點的next指向的是node節(jié)點，而新節(jié)點的next指向的是node節(jié)點

template<class E>
void LinkedList<E>::insert(int index, E e) {

    if (index == len) {
        linkedLast(e);
    } else {
        linkBefore(node(index), e);
    }
    len++;
}
template<class E>
void LinkedList<E>::linkBefore(Node<E> *node, E e) {
    Node<E> *prev = node->prev;
    Node<E> *new_node = new Node<E>(e, prev, node);
    node->prev = new_node;

    if (prev) {
        prev->next = new_node;
    } else {
        head = new_node;
    }

}

移除節(jié)點

image.png

首先要被刪除的節(jié)點定義名為node,我們需要獲取當前node的前后兩個節(jié)點，然后讓node的前節(jié)點的next指向node的后節(jié)點，而node的后節(jié)點的prev指向node的前節(jié)點

template<class E>
E LinkedList<E>::remove(int index) {
    assert(index >= 0 && index <= len);
    return unlink(node(index));
}
template<class E>
E LinkedList<E>::unlink(Node<E> *node) {
    //首先需要獲得移除的左右節(jié)點
    Node<E> *prev = node->prev;
    Node<E> *next = node->next;
    E value = node->value;
    //如果prev等于空
    if (prev) {
        prev->next = next;
    } else {
        head = next;
    }
    if (next) {
        next->prev = prev;
    } else {
        last = prev;
    }
    delete node;
    len--;
    return value;
}

最后需要調(diào)用析構(gòu)函數(shù)釋放內(nèi)存

template<class E>
LinkedList<E>::~LinkedList() {
    // 析構(gòu)釋放內(nèi)存,析構(gòu)所有的節(jié)點指針就可以了
    Node<E> *h = head;
    while (h) {
        //要保存下個指針，不然當釋放的時候找不到下個指針
        Node<E> *next = h->next;
        delete h;
        h = next;
    }
    //頭指針和尾指針要置空
    head = NULL;
    last = NULL;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容