{"id":218,"date":"2021-07-22T11:10:15","date_gmt":"2021-07-22T03:10:15","guid":{"rendered":"https:\/\/aisumura.net\/blog\/?p=218"},"modified":"2021-07-22T14:02:55","modified_gmt":"2021-07-22T06:02:55","slug":"%e5%af%a6%e4%bd%9c%e8%b3%87%e7%b5%901-single-linked-list","status":"publish","type":"post","link":"https:\/\/aisumura.net\/blog\/2021\/07\/22\/%e5%af%a6%e4%bd%9c%e8%b3%87%e7%b5%901-single-linked-list\/","title":{"rendered":"\u5be6\u4f5c\u8cc7\u7d50(1) – Single Linked List"},"content":{"rendered":"\n

\u521d\u59cb\u5316<\/h4>\n\n\n\n

Linked List\u7684\u6838\u5fc3\u6982\u5ff5\u662fNode\u7d44\u6210\u7684\u4e32\u5217\uff0c
\u56e0\u6b64\u5fc5\u9808\u5148\u5ba3\u544aNode\u8207Head Node\u7684\u521d\u59cb\u5316\u3002<\/p>\n\n\n\n

\/* \u5be6\u4f5c\u8cc7\u7d50(1) - Single Linked List*\/\n#include <iostream>\nusing namespace std;\n\nstruct Node{\n    int data;\n    Node *next = NULL;\n    Node(int d){\n        data = d; \n    }\n};\n\nclass SingleLinkedList{\n    Node *head;\n    public:\n    \/\/\u521d\u59cb\u5316\u4e00\u500bSingle Linked List\uff0c\u4e26\u7d66\u4e88HEAD\u521d\u503c\u3002\n    SingleLinkedList(int data){\n        head = new Node(data);\n    }\n};\n\n\nint main(){\n    SingleLinkedList list = SingleLinkedList(1);\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u63a5\u8457\u5be6\u4f5cLinked List\u5e38\u898b\u7684\u65b9\u6cd5(\u986f\u793a\u3001\u65b0\u589e\u3001\u79fb\u9664)
\u9996\u5148\uff0c\u5c07Linked List\u4e2d\u6240\u6709\u5143\u7d20\u5370\u51fa<\/p>\n\n\n\n
    \/\/\u8fed\u4ee3List\u4e2d\u6240\u6709\u5143\u7d20\uff0c\u4e26\u4e14\u5370\u51fa\u3002\n    void Show(){\n        Node *tmp = head;\n        cout << tmp->data;\n        while(tmp->next != NULL){\n            tmp = tmp->next;\n            cout << \",\" << tmp->data;\n        }\n        cout << endl;\n    }<\/code><\/pre>\n\n\n\n
\u5c07\u5143\u7d20append\u5230\u5c3e\u7aef<\/p>\n\n\n\n
    \/\/\u52a0\u5165\u4e00\u500b\u5143\u7d20\u5230\u5c3e\u7aef\n    void Append(int data){\n        Node *tmp = head;\n        while(tmp->next != NULL){\n            tmp = tmp->next;\n        }\n        tmp->next = new Node(data);\n    }<\/code><\/pre>\n\n\n\n
Insert\u5230\u6307\u5b9a\u7684\u4f4d\u7f6e<\/p>\n\n\n\n
    \/\/\u63d2\u5165\u5143\u7d20\u81f3\u6307\u5b9aindex\u7684\u4f4d\u7f6e(HEAD\u5f9e0\u8d77\u7b97)\n    bool Insert(int index, int data){\n        Node *tmp = new Node(data);\n\n        \/\/index\u70ba0\u8868\u793a\u63d2\u5165\u5728HEAD\u4f4d\u7f6e\n        if(index == 0){\n            tmp->next = head;\n            head = tmp;\n            return true;\n        }\n\n        int i = 0;\n        Node *before_index = head;\n        \/\/\u8981\u7372\u53d6index\u524d\u4e00\u500bnode\u624d\u80fd\u505ainsert\n        while(i < index - 1){\n            before_index = before_index->next;\n            i++;\n            if(before_index->next == NULL) break; \/\/Linked List\u8fed\u4ee3\u5230\u5c3e\u7aef\u7684\u8a71\u5f37\u5236\u8df3\u51fa\uff0c\u907f\u514d\u8a18\u61b6\u9ad4\u5b58\u53d6\u932f\u8aa4\u3002\n        }\n\n        \/\/\u63d2\u5165\u5728\u5c3e\u7aef\n        if(before_index->next == NULL){\n            before_index->next = new Node(data);\n            return true;\n        }\n        \/\/\u63d2\u5165\u5728\u4e2d\u9593\n        tmp->next = before_index->next;\n        before_index->next = tmp;\n        return true;\n    }<\/code><\/pre>\n\n\n\n

\u7136\u5f8c\u5be6\u4f5c\u522a\u9664\u7bc0\u9ede<\/p>\n\n\n\n
    \/\/\u522a\u9664\u6307\u5b9aindex\u7684\u7bc0\u9ede(HEAD\u5f9e0\u8d77\u7b97)\n    bool Delete(int index){\n        \/\/\u522a\u9664\u7684\u662fHEAD\n        if(index == 0){\n            if(head->next == NULL) return false; \/\/\u53ea\u6709index\u7684\u60c5\u6cc1\u4e0d\u80fd\u518d\u522a\u4e86\uff0c\u4e0d\u7136\u6703\u5168\u8b8a\u6210NULL\n            head = head->next;\n        }\n\n        int i = 0;\n        Node *before_index = head;\n        \/\/\u8981\u7372\u53d6index\u524d\u4e00\u500bnode\u624d\u80fd\u505adelete\n        while(i < index - 1){\n            before_index = before_index->next;\n            i++;\n            if(before_index->next == NULL) break; \/\/Linked List\u8fed\u4ee3\u5230\u5c3e\u7aef\u7684\u8a71\u5f37\u5236\u8df3\u51fa\uff0c\u907f\u514d\u8a18\u61b6\u9ad4\u5b58\u53d6\u932f\u8aa4\u3002\n        }\n        \n        Node *tmp = before_index->next;\n        before_index->next = before_index->next->next;\n        free(tmp); \/\/\u91cb\u653e\u6389\u8a72Node\u4f54\u7684\u8a18\u61b6\u9ad4\u7a7a\u9593\n        \n        return true;\n    }<\/code><\/pre>\n\n\n\n
\u6700\u5f8c\u505a\u4e00\u4e9b\u7c21\u55ae\u7684\u6e2c\u8a66\uff0c\u5b8c\u6574\u7684CODE:<\/p>\n\n\n\n
\/* \u57fa\u672c\u7684Single Linked List\u7df4\u7fd2*\/\n#include <iostream>\nusing namespace std;\n\nstruct Node{\n    int data;\n    Node *next = NULL;\n    Node(int d){\n        data = d; \n    }\n};\n\nclass SingleLinkedList{\n    Node *head;\n    public:\n    \/\/\u521d\u59cb\u5316\u4e00\u500bSingle Linked List\uff0c\u4e26\u7d66\u4e88HEAD\u521d\u503c\u3002\n    SingleLinkedList(int data){\n        head = new Node(data);\n    }\n\n    \/\/\u52a0\u5165\u4e00\u500b\u5143\u7d20\u5230\u5c3e\u7aef\n    void Append(int data){\n        Node *tmp = head;\n        while(tmp->next != NULL){\n            tmp = tmp->next;\n        }\n        tmp->next = new Node(data);\n    }\n\n    \/\/\u8fed\u4ee3List\u4e2d\u6240\u6709\u5143\u7d20\uff0c\u4e26\u4e14\u5370\u51fa\u3002\n    void Show(){\n        Node *tmp = head;\n        cout << tmp->data;\n        while(tmp->next != NULL){\n            tmp = tmp->next;\n            cout << \",\" << tmp->data;\n        }\n        cout << endl;\n    }\n\n    \/\/\u63d2\u5165\u5143\u7d20\u81f3\u6307\u5b9aindex\u7684\u4f4d\u7f6e(HEAD\u5f9e0\u8d77\u7b97)\n    bool Insert(int index, int data){\n        Node *tmp = new Node(data);\n\n        \/\/index\u70ba0\u8868\u793a\u63d2\u5165\u5728HEAD\u4f4d\u7f6e\n        if(index == 0){\n            tmp->next = head;\n            head = tmp;\n            return true;\n        }\n\n        int i = 0;\n        Node *before_index = head;\n        \/\/\u8981\u7372\u53d6index\u524d\u4e00\u500bnode\u624d\u80fd\u505ainsert\n        while(i < index - 1){\n            before_index = before_index->next;\n            i++;\n            if(before_index->next == NULL) break; \/\/Linked List\u8fed\u4ee3\u5230\u5c3e\u7aef\u7684\u8a71\u5f37\u5236\u8df3\u51fa\uff0c\u907f\u514d\u8a18\u61b6\u9ad4\u5b58\u53d6\u932f\u8aa4\u3002\n        }\n\n        \/\/\u63d2\u5165\u5728\u5c3e\u7aef\n        if(before_index->next == NULL){\n            before_index->next = new Node(data);\n            return true;\n        }\n        \/\/\u63d2\u5165\u5728\u4e2d\u9593\n        tmp->next = before_index->next;\n        before_index->next = tmp;\n        return true;\n    }\n\n    \/\/\u522a\u9664\u6307\u5b9aindex\u7684\u7bc0\u9ede(HEAD\u5f9e0\u8d77\u7b97)\n    bool Delete(int index){\n        \/\/\u522a\u9664\u7684\u662fHEAD\n        if(index == 0){\n            if(head->next == NULL) return false; \/\/\u53ea\u6709index\u7684\u60c5\u6cc1\u4e0d\u80fd\u518d\u522a\u4e86\uff0c\u4e0d\u7136\u6703\u5168\u8b8a\u6210NULL\n            head = head->next;\n        }\n\n        int i = 0;\n        Node *before_index = head;\n        \/\/\u8981\u7372\u53d6index\u524d\u4e00\u500bnode\u624d\u80fd\u505adelete\n        while(i < index - 1){\n            before_index = before_index->next;\n            i++;\n            if(before_index->next == NULL) break; \/\/Linked List\u8fed\u4ee3\u5230\u5c3e\u7aef\u7684\u8a71\u5f37\u5236\u8df3\u51fa\uff0c\u907f\u514d\u8a18\u61b6\u9ad4\u5b58\u53d6\u932f\u8aa4\u3002\n        }\n        \n        Node *tmp = before_index->next;\n        before_index->next = before_index->next->next;\n        free(tmp); \/\/\u91cb\u653e\u6389\u8a72Node\u4f54\u7684\u8a18\u61b6\u9ad4\u7a7a\u9593\n        \n        return true;\n    }\n};\n\n\nint main(){\n    SingleLinkedList list = SingleLinkedList(1);\n    list.Append(3);\n    list.Append(5);\n    list.Insert(3,7); \/\/\u63d2\u5165\u5c3e\u7aef\uff0c\u7b49\u540c\u65bcAppend(7)\n    list.Insert(0,0); \/\/\u63d2\u5165\u5728List HEAD\n    list.Insert(2,2); \/\/\u63d2\u5165\u5728List\u4e2d\u9593\n    list.Insert(4,4);\n    list.Insert(6,6);\n    list.Insert(87,87); \/\/\u8d85\u904e\u5c3e\u7aef\uff0c\u5f37\u5236Append\n    list.Delete(8); \/\/\u522a\u9664\u5c3e\u7aef\n    list.Delete(0); \/\/\u522a\u9664HEAD\n    list.Delete(1); \/\/\u522a\u9664List\u4e2d\u9593\n    list.Show();\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u521d\u59cb\u5316 Linked List\u7684\u6838\u5fc3\u6982\u5ff5\u662fNode\u7d44\u6210\u7684\u4e32\u5217\uff0c\u56e0\u6b64\u5fc5\u9808\u5148\u5ba3\u544aNode\u8207Head Node\u7684\u521d\u59cb […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[13,18],"tags":[11,19],"_links":{"self":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/218"}],"collection":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/comments?post=218"}],"version-history":[{"count":6,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/218\/revisions"}],"predecessor-version":[{"id":234,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/218\/revisions\/234"}],"wp:attachment":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/media?parent=218"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/categories?post=218"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/tags?post=218"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}