如果鏈結串列只能從頭或尾新增節點是不是顯得有點無聊呢？

這篇我們就要來介紹如何從中間新增資料，使得所有資料遞增排序。

定義類別

class SLL {
private:
    SLLNode *head;
public:
    SLL();
    void pushFront(int);
    void printAll();
    int popFront();
    void pushBack(int);
    int popBack();
    void insert(int);
};

class DLL {
private:
    DLLNode *head, *tail;
public:
    DLL();
    void pushFront(int);
    void printAll();
    int popFront();
    void pushBack(int);
    int popBack();
    void insert(int);
};

單向鏈結串列

這個類別方法大致可以用三種狀況來概括：

1. 鏈結串列為空
2. 欲新增的資料 < this -> head -> data ：其實就是實作 pushFront()
3. 剩餘的情況：
   1. 找到資料所屬的區間，否則新增在鏈結串列之後
   2. 將資料賦值給新配置的節點，置於該區間

void SLL::insert(int _data) {
    if (this -> head == NULL) { // 鏈結串列為空
        this -> head = new SLLNode(_data);
        return;
    }
    if (_data <= this -> head -> data) { // pushFront()
        SLLNode *newSLLNode = new SLLNode(_data);
        newSLLNode -> next = this -> head;
        this -> head = newSLLNode;
        return;
    }
    SLLNode *cur = this -> head;
    while (1)
    {
        if (cur -> next == NULL) { // pushBack()
            SLLNode *newSLLNode = new SLLNode(_data);
            cur -> next = newSLLNode;
            return;
        }
        else if (cur -> next -> data < _data)
            cur = cur -> next;
        else {
            SLLNode *newSLLNode = new SLLNode(_data);
            newSLLNode -> next = cur -> next;
            cur -> next = newSLLNode;
            return;
        }
    }
}

雙向鏈結串列

void DLL::insert(int) 其實與 void SLL::insert(int) 大同小異，只是我們要特別注意是否有將 prev 正確的連上。

void DLL::insert(int _data) {
    if (this -> head == NULL) { // 鏈結串列為空
        this -> head = new DLLNode(_data);
        this -> tail = this -> head;
        return;
    }
    if (_data <= this -> head -> data) { // pushFront()
        DLLNode *newDLLNode = new DLLNode(_data);
        newDLLNode -> next = this -> head;
        this -> head -> prev = newDLLNode;
        this -> head = newDLLNode;
        return;
    }
    DLLNode *cur = this -> head;
    while (1)
    {
        if (cur -> next == NULL) { // pushBack()
            DLLNode *newDLLNode = new DLLNode(_data);
            cur -> next = newDLLNode;
            newDLLNode -> prev = cur;
            return;
        }
        else if (cur -> next -> data < _data)
            cur = cur -> next;
        else {
            DLLNode *newDLLNode = new DLLNode(_data);
            newDLLNode -> next = cur -> next;
            newDLLNode -> prev = cur;
            newDLLNode -> next -> prev = newDLLNode;
            cur -> next = newDLLNode;
            return;
        }
    }
}

這一個類別方法的重點在於所有資料都是遞增的，所以我們只需要找到第一個比欲新增的資料大的節點，即可結束。

下一篇，我們來實作能指定刪除某節點的類別方法：linkedList::remove()。