时间戳

首页 > 技术文章 > 数据结构-链表

数据结构-链表

Joy2013Ru 2020-09-11 09:19 原文

目录

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。与数组相比，查找索引需要从头开始遍历性能糟糕，但是插入删除元素则有优势。

C++实现单向链表加深理解

#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>
#include <algorithm>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) :val(x), next(NULL){}
};

class MyList {
public:
    MyList();
    ~MyList();
    /*创建*/
    ListNode* CreatNewList(int val);
    /*增*/
    void addNewNodeBack(ListNode* Head, int val);
    ListNode* addNewNodeFront(ListNode* Head, int val);
    void InsertNewNodeIntoList(ListNode* Head, int locate, int val);
    /*删*/
    void DeleteList(ListNode* Head);
    ListNode* DeleteNode(ListNode* Head, int locate);
    /*查*/
    int CheckNodeData(ListNode* Head, int locate);
    /*改*/
    void ChangeNodeData(ListNode* Head, int locate, int val);
    /*翻转链表*/
    ListNode* MyListReverse(ListNode* Head);
    /*链表排序(从小到大)*/
    ListNode* MyListSort(ListNode* Head);
    /*移除重复节点*/
    ListNode* MyListRemoveDuplicateNodes(ListNode* Head);
public:
    void ShowListValue(ListNode* Head);
private:
};

MyList::MyList() {

}

MyList::~MyList() {

}

ListNode* MyList::CreatNewList(int val) {
    ListNode* NewNode = new ListNode(val);
    return NewNode;
}

void MyList::DeleteList(ListNode* Head) {
    ListNode* node;
    while (Head->next != NULL) {
        node = Head->next;
        delete Head;
        Head = node;
    }
    delete Head;
}

void MyList::addNewNodeBack(ListNode* Head,int val) {
    ListNode* NewNode = new ListNode(val);
    while (Head->next != NULL) {
        Head = Head->next;
    }
    Head->next = NewNode;
}

ListNode* MyList::addNewNodeFront(ListNode* Head, int val) {
    ListNode* NewHead = new ListNode(val);
    NewHead->next = Head;
    return NewHead;
}

void MyList::InsertNewNodeIntoList(ListNode* Head, int locate, int val) {
    int offset = 0;
    while (offset != locate-1 && Head->next != NULL) {
        offset++;
        Head = Head->next;
    }
    if (offset == locate-1) {
        ListNode* temp = Head->next;
        ListNode* NewNode = new ListNode(val);
        Head->next = NewNode;
        NewNode->next = temp;
    }
    else {
        std::cout << "locate over the list" << std::endl;
    }
}

ListNode* MyList::DeleteNode(ListNode* Head, int locaet) {
    int offset = 0;
    ListNode* CopyHead = Head;
    ListNode* temp = Head;
    while (offset != locaet - 1 && Head->next != NULL) {
        offset++;
        temp = Head;
        Head = Head->next;
    }
    if (offset == locaet - 1 && locaet != 1) {
        temp->next = Head->next;
        delete Head;
    }
    else if(locaet == 1){
        ListNode* Node = Head->next;
        delete Head;
        return Node;
    }
    else {
        std::cout << "locate over the list" << std::endl;
    }
    return CopyHead;
}

void MyList::ShowListValue(ListNode* Head) {
    while (Head->next) {
        std::cout << Head->val << "->";
        Head = Head->next;
    }
    std::cout << Head->val << std::endl;
}

int MyList::CheckNodeData(ListNode* Head, int locate) {
    int offset = 0;
    int val = 0;
    while (offset != locate - 1 && Head->next != NULL) {
        offset++;
        Head = Head->next;
    }
    if (offset == locate - 1) {
        val = Head->val;
    }
    else {
        std::cout << "locate over the list" << std::endl;
    }
    return val;
}

void MyList::ChangeNodeData(ListNode* Head, int locate, int val) {
    int offset = 0;
    while (offset != locate - 1 && Head->next != NULL) {
        offset++;
        Head = Head->next;
    }
    if (offset == locate - 1) {
        Head->val = val;
    }
    else {
        std::cout << "locate over the list" << std::endl;
    }
}

ListNode* MyList::MyListReverse(ListNode* Head) {
    if (Head == NULL) return NULL;
    ListNode* NewEnd = new ListNode(Head->val);
    NewEnd->next = NULL;
    ListNode* CopyNewNode = NewEnd;
    while (Head->next) {
        Head = Head->next;
        ListNode* NewNode = new ListNode(Head->val);
        NewNode->next = CopyNewNode;
        CopyNewNode = NewNode;
    }
    DeleteList(Head);
    return CopyNewNode;
}

ListNode* MyList::MyListSort(ListNode* Head) {
    if (Head == NULL) return NULL;
    std::vector<int> box;
    ListNode* copyhead1 = Head;
    ListNode* copyhead2 = Head;
    int locate = 0;
    box.push_back(Head->val);
    while (Head->next) {
        Head = Head->next;
        box.push_back(Head->val);
    }
    sort(box.begin(), box.end());
    while (copyhead1->next) {
        copyhead1->val = box[locate];
        locate++;
        copyhead1 = copyhead1->next;
    }
    copyhead1->val = box[locate];
    return copyhead2;
}

ListNode* MyList::MyListRemoveDuplicateNodes(ListNode* Head) {
    std::unordered_set<int> box;
    ListNode* cur = Head;
    while (cur && cur->next) { 
        box.insert(cur->val);
        if (box.count(cur->next->val)) {
            ListNode* DeleteNode = cur->next;
            cur->next = cur->next->next;
            delete DeleteNode;
        }
        else {
            cur = cur->next;
        }
    }
    return Head;
}

int main()
{
    MyList M;
    ListNode* Head;
    Head = M.CreatNewList(1);
    for (int i = 2; i < 11; ++i) {
        M.addNewNodeBack(Head, i);
    }
    M.ShowListValue(Head);
    ListNode* NewHead1 = M.MyListReverse(Head);
    M.ShowListValue(NewHead1);
    M.MyListSort(NewHead1);
    M.ShowListValue(NewHead1);
    ///////////////
    M.InsertNewNodeIntoList(NewHead1, 4, 4);
    M.InsertNewNodeIntoList(NewHead1, 5, 5);
    M.InsertNewNodeIntoList(NewHead1, 6, 6);
    M.InsertNewNodeIntoList(NewHead1, 6, 9);
    M.ShowListValue(NewHead1);
    M.MyListRemoveDuplicateNodes(NewHead1);
    M.ShowListValue(NewHead1);
    ///////////////
    M.DeleteList(NewHead1);
    return 0;
}

STL标准模板库的单向链表-Forword_list

#include <iostream>
#include <forward_list>
#include <algorithm>
#include <time.h>
using namespace std;

void showlist(forward_list<string>& ForwardList) {
    for (string s : ForwardList) {
        cout << s << "->";
    }
    cout << "NULL" << endl;
}

int main()
{
    forward_list<string> ForwardList;
    int starttime = 0;
    int endtime = 0;
    starttime = clock();
    for (int i = 0; i < 500000; ++i) { //头插50万个“abc”
        ForwardList.push_front("abc");
    }
    endtime = clock();
    cout << "push from front time:" << endtime - starttime << endl;
    starttime = clock();
    for (int i = 0; i < 500000; ++i) {//删50万个“abc”
        ForwardList.pop_front();
    }
    endtime = clock();
    cout << "delete from front time:" << endtime - starttime << endl;
    for (int i = 0; i < 500000; ++i) { //再头插50万个“abc”
        ForwardList.push_front("abc");
    }
    starttime = clock();
    ForwardList.clear();
    endtime = clock();
    cout << "delete from clear() time:" << endtime - starttime << endl;
    /**********************************************/
    ForwardList.emplace_front("def");
    ForwardList.emplace_front("abc");
    ForwardList.emplace_after(ForwardList.begin(), "ghi");//第一个参数是迭代器，支持在链表任意位置插入元素的，这里插入begin()的下一个位置
    showlist(ForwardList);
    ForwardList.erase_after(ForwardList.begin());//删除begin()的下一个位置的节点
    showlist(ForwardList);
    ForwardList.emplace_front("aaa");//同push_front
    showlist(ForwardList);
    ForwardList.remove("aaa");//删除链表中的指定的元素，不管在什么位置，有多少个
    showlist(ForwardList);
    ForwardList.reverse();//库里的反转链表
    showlist(ForwardList);
    return 0;
}

输出：

push from front time:1176
delete from front time:416
delete from clear() time:325
abc->ghi->def->NULL
abc->def->NULL
aaa->abc->def->NULL
abc->def->NULL
def->abc->NULL

还有很多api,需要用到时参考www.cplusplus.com

STL标准模板库的双向循环链表-List

#include <iostream>
#include <list>
#include <algorithm>
#include <time.h>
using namespace std;

void showlist(list<int>& List) {
    for (int i : List) {
        cout << i << "->";
    }
    cout <<"NULL"<< endl;
}

int main()
{
    list<int> List;
    clock_t timestart = 0;
    clock_t timeend = 0;
    timestart = clock();
    for (int i = 0; i < 1000000; i++) {
        List.push_back(i);//在链表尾添加元素
    }
    timeend = clock();
    cout << "insert from back 1000000 time:" << timeend - timestart << endl;
    timestart = clock();
    for (int i = 0; i < 1000000; i++) {
        List.pop_back();//从表尾开始删除元素
    }
    timeend = clock();
    cout << "delete from back 1000000 time:" << timeend - timestart << endl;
    timestart = clock();
    for (int i = 0; i < 1000000; i++) {
        List.push_front(i);//从表头开始添加元素
    }
    timeend = clock();
    cout << "insert from front 1000000 time:" << timeend - timestart << endl;
    timestart = clock();
    for (int i = 0; i < 1000000; i++) {
        List.pop_front();//从表头开始删除元素
    }
    timeend = clock();
    cout << "delete from front 1000000 time:" << timeend - timestart << endl;
    /***************************************************************************/
    for (int i = 1; i <= 10; i++) {
        List.emplace_back(i);//效果同push_back
    }
    showlist(List);
    cout << "List First data is:" << List.front() << endl;
    cout << "List Last data is:" << List.back() << endl;
    List.pop_back();//删除最后一个节点
    showlist(List);
    List.pop_front();//删除第一个节点
    showlist(List);
    List.erase(List.begin(), ++++List.begin());//删除指定位置的节点用迭代器指示，也可以定个区间，这里贪方便就这样写了
    showlist(List);
    return 0;
}

输出：

insert from back 1000000 time:678
delete from back 1000000 time:374
insert from front 1000000 time:658
delete from front 1000000 time:345
1->2->3->4->5->6->7->8->9->10->NULL
List First data is:1
List Last data is:10
1->2->3->4->5->6->7->8->9->NULL
2->3->4->5->6->7->8->9->NULL
4->5->6->7->8->9->NULL

用库还是很难体现出双向循环列表的底层结构，参考www.cplusplus.com

推荐阅读