{"id":364,"date":"2026-01-04T12:20:03","date_gmt":"2026-01-04T04:20:03","guid":{"rendered":"http:\/\/4.189.252.43\/?p=364"},"modified":"2026-01-04T12:20:04","modified_gmt":"2026-01-04T04:20:04","slug":"%e9%93%be%e8%a1%a8","status":"publish","type":"post","link":"http:\/\/4.189.252.43\/index.php\/2026\/01\/04\/%e9%93%be%e8%a1%a8\/","title":{"rendered":"\u94fe\u8868"},"content":{"rendered":"\n<h2>1. \u94fe\u8868\u7684\u6982\u5ff5<\/h2>\n<p>\u94fe\u8868\uff08Linked List\uff09\u662f\u4e00\u79cd\u901a\u8fc7\u201c\u6307\u9488\u201d\u5c06\u591a\u4e2a\u8282\u70b9\u8fde\u63a5\u8d77\u6765\u7684\u7ebf\u6027\u6570\u636e\u7ed3\u6784\u3002<\/p>\n<p>\u6570\u636e\u7ed3\u6784\uff1a \u5b58\u653e\u591a\u4e2a\u6570\u636e<\/p>\n<p>\u6bcf\u4e2a\u8282\u70b9\u901a\u5e38\u5305\u542b\uff1a<\/p>\n<ul>\n<li>\u6570\u636e\u57df\uff08data\uff09<\/li>\n<li>\u6307\u9488\u57df\uff08next\uff09\uff0c\u6307\u5411\u4e0b\u4e00\u4e2a\u8282\u70b9<\/li>\n\n<\/ul>\n<blockquote><p>\u6570\u7ec4\u7684\u8282\u70b9\uff1a<\/p>\n<ul>\n<li>\u6570\u636e\u57df<\/li>\n<li>\u4e0b\u6807<\/li>\n\n<\/ul>\n<p><code>arr[0] = 10<\/code><\/p>\n<\/blockquote>\n<p>\u94fe\u8868\u4e0d\u8981\u6c42\u5185\u5b58\u8fde\u7eed\uff0c\u8282\u70b9\u53ef\u6839\u636e\u9700\u8981\u52a8\u6001\u5206\u914d\u3002<\/p>\n<pre><code>[ data | next ] \u2192 [ data | next ] \u2192 [ data | next ] \u2192 NULL\n<\/code><\/pre>\n<p><strong>\u94fe\u8868\u9002\u7528\u4e8e\u9891\u7e41\u63d2\u5165\u3001\u5220\u9664\u7684\u573a\u666f\u3002<\/strong><\/p>\n<hr \/>\n<h2>2. \u5355\u94fe\u8868\uff08Singly Linked List\uff09<\/h2>\n<h3>2.1 \u8282\u70b9\u7ed3\u6784\u5b9a\u4e49<\/h3>\n<pre><code>typedef struct Node {\n    int data;\n    struct Node *next;\n} Node;\n<\/code><\/pre>\n<h3>2.2 \u5934\u6307\u9488<\/h3>\n<p>\u94fe\u8868\u901a\u8fc7\u4e00\u4e2a\u6307\u5411\u9996\u8282\u70b9\u7684\u201c\u5934\u6307\u9488\u201d\u8868\u793a\uff1a<\/p>\n<pre><code>Node *head = NULL;\n<\/code><\/pre>\n<h3>2.3 \u521b\u5efa\u65b0\u8282\u70b9<\/h3>\n<pre><code>Node* create(int x) {\n    Node *p = malloc(sizeof(Node));\n    p-&gt;data = x;\n    p-&gt;next = NULL;\n    return p;\n}\n<\/code><\/pre>\n<hr \/>\n<h2>3. \u5355\u94fe\u8868\u57fa\u672c\u64cd\u4f5c<\/h2>\n<h3>3.1 \u5934\u63d2\u6cd5\uff08\u5934\u90e8\u63d2\u5165\uff09<\/h3>\n<pre><code>void push_front(Node **head, int x) {\n    Node *p = create(x);\n    p-&gt;next = *head;\n    *head = p;\n}\n<\/code><\/pre>\n<p>\u7279\u70b9\uff1a<\/p>\n<ul>\n<li>\u65f6\u95f4\u590d\u6742\u5ea6 O(1)<\/li>\n<li>\u8282\u70b9\u6210\u4e3a\u65b0\u7684\u5934<\/li>\n\n<\/ul>\n<h3>3.2 \u5c3e\u63d2\u6cd5\uff08\u5c3e\u90e8\u63d2\u5165\uff09<\/h3>\n<pre><code>void push_back(Node **head, int x) {\n    Node *p = create(x);\n    if (*head == NULL) {\n        *head = p;\n        return;\n    }\n    Node *cur = *head;\n    while (cur-&gt;next) cur = cur-&gt;next;\n    cur-&gt;next = p;\n}\n<\/code><\/pre>\n<p>\u7279\u70b9\uff1a<\/p>\n<ul>\n<li>\u65f6\u95f4 O(n)\uff08\u82e5\u65e0\u5c3e\u6307\u9488\uff09<\/li>\n\n<\/ul>\n<h3>3.3 \u5220\u9664\u8282\u70b9\uff08\u6309\u503c\u5220\u9664\uff09<\/h3>\n<pre><code>void remove_value(Node **head, int x) {\n    if (*head == NULL) return;\n\n    if ((*head)-&gt;data == x) {\n        Node *tmp = *head;\n        *head = (*head)-&gt;next;\n        free(tmp);\n        return;\n    }\n\n    Node *cur = *head;\n    while (cur-&gt;next &amp;&amp; cur-&gt;next-&gt;data != x)\n        cur = cur-&gt;next;\n\n    if (cur-&gt;next) {\n        Node *tmp = cur-&gt;next;\n        cur-&gt;next = tmp-&gt;next;\n        free(tmp);\n    }\n}\n<\/code><\/pre>\n<h3>3.4 \u904d\u5386\u94fe\u8868<\/h3>\n<pre><code>void print_list(Node *head) {\n    for (Node *p = head; p; p = p-&gt;next) {\n        printf(&quot;%d &quot;, p-&gt;data);\n    }\n}\n<\/code><\/pre>\n<hr \/>\n<h2>4. \u5355\u94fe\u8868\u7684\u5185\u5b58\u6a21\u578b<\/h2>\n<p>\u4f8b\u5982\u94fe\u8868\u5185\u5bb9\uff1a3 \u2192 5 \u2192 7 \u2192 NULL<\/p>\n<p>\u5185\u5b58\u53ef\u80fd\u5982\u4e0b\u5206\u5e03\uff08\u975e\u8fde\u7eed\uff09\uff1a<\/p>\n<pre><code>\u5730\u57403000: [3 | 5000]\n\u5730\u57405000: [5 | 9000]\n\u5730\u57409000: [7 | NULL]\n<\/code><\/pre>\n<p>\u94fe\u8868\u901a\u8fc7 next \u6307\u9488\u4e32\u8054\u8fd9\u4e9b\u4e0d\u8fde\u7eed\u7684\u8282\u70b9\u3002<\/p>\n<hr \/>\n<h2>5. \u53cc\u5411\u94fe\u8868\uff08Doubly Linked List\uff09<\/h2>\n<h3>5.1 \u8282\u70b9\u7ed3\u6784<\/h3>\n<pre><code>typedef struct DNode {\n    int data;\n    struct DNode *prev;\n    struct DNode *next;\n} DNode;\n<\/code><\/pre>\n<h3>5.2 \u4f18\u70b9<\/h3>\n<ul>\n<li>\u652f\u6301 O(1) \u65f6\u95f4\u627e\u5230\u524d\u9a71\u8282\u70b9<\/li>\n<li>\u63d2\u5165\u548c\u5220\u9664\u66f4\u65b9\u4fbf<\/li>\n<li>\u53ef\u53cc\u5411\u904d\u5386<\/li>\n\n<\/ul>\n<h3>5.3 \u63d2\u5165\u793a\u4f8b\uff08\u5728\u540e\u9762\u63d2\u5165\uff09<\/h3>\n<pre><code>void insert_after(DNode *pos, int x) {\n    DNode *p = malloc(sizeof(DNode));\n    p-&gt;data = x;\n    p-&gt;prev = pos;\n    p-&gt;next = pos-&gt;next;\n    if (pos-&gt;next) pos-&gt;next-&gt;prev = p;\n    pos-&gt;next = p;\n}\n<\/code><\/pre>\n<hr \/>\n<h2>6. \u5faa\u73af\u94fe\u8868\uff08Circular Linked List\uff09<\/h2>\n<h3>6.1 \u6982\u5ff5<\/h3>\n<p>\u5c3e\u8282\u70b9\u6307\u5411\u5934\u8282\u70b9\uff1a<\/p>\n<pre><code>[ data | next ] \u2192 [ data | next ] \u2192 [ data | next ]\n       \u2191                                  |\n       \u2514\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2518\n<\/code><\/pre>\n<h3>6.2 \u7279\u70b9<\/h3>\n<ul>\n<li>\u4efb\u610f\u8282\u70b9\u53ef\u4f5c\u4e3a\u5165\u53e3<\/li>\n<li>\u5e38\u7528\u4e8e\u961f\u5217\u3001\u7ea6\u745f\u592b\u73af<\/li>\n\n<\/ul>\n<h3>6.3 \u5224\u65ad\u5faa\u73af<\/h3>\n<pre><code>while (p-&gt;next != head)\n<\/code><\/pre>\n<hr \/>\n<h2>7. \u94fe\u8868\u5178\u578b\u7b97\u6cd5\u4e0e\u9898\u578b<\/h2>\n<h3>7.1 \u5feb\u6162\u6307\u9488\u5224\u65ad\u94fe\u8868\u662f\u5426\u6709\u73af<\/h3>\n<pre><code>Node *slow = head, *fast = head;\nwhile (fast &amp;&amp; fast-&gt;next) {\n    slow = slow-&gt;next;\n    fast = fast-&gt;next-&gt;next;\n    if (slow == fast) return 1;  \/\/ \u6709\u73af\n}\nreturn 0; \/\/ \u65e0\u73af\n<\/code><\/pre>\n<h3>7.2 \u53cd\u8f6c\u94fe\u8868\uff08\u7ecf\u5178\u9762\u8bd5\u9898\uff09<\/h3>\n<pre><code>Node* reverse(Node *head) {\n    Node *prev = NULL, *cur = head;\n    while (cur) {\n        Node *next = cur-&gt;next;\n        cur-&gt;next = prev;\n        prev = cur;\n        cur = next;\n    }\n    return prev;\n}\n<\/code><\/pre>\n<h3>7.3 \u5220\u9664\u5012\u6570\u7b2c k \u4e2a\u8282\u70b9<\/h3>\n<p>\u5feb\u6162\u6307\u9488\u6cd5\u3002<\/p>\n<hr \/>\n<h2>8. \u94fe\u8868\u7684\u4f18\u52bf\u4e0e\u52a3\u52bf<\/h2>\n<h3>\u4f18\u52bf<\/h3>\n<ul>\n<li>\u63d2\u5165\u5220\u9664\u6548\u7387\u9ad8\uff08O(1)\uff09<\/li>\n<li>\u4e0d\u9700\u8981\u8fde\u7eed\u5185\u5b58<\/li>\n<li>\u52a8\u6001\u6269\u5c55\u65b9\u4fbf<\/li>\n\n<\/ul>\n<h3>\u52a3\u52bf<\/h3>\n<ul>\n<li>\u4e0d\u652f\u6301\u968f\u673a\u8bbf\u95ee<\/li>\n<li>\u7a7a\u95f4\u5f00\u9500\u66f4\u5927\uff08\u9700\u8981\u6307\u9488\uff09<\/li>\n<li>\u5c40\u90e8\u6027\u5dee\uff08cache performance \u8f83\u5dee\uff09<\/li>\n\n<\/ul>\n<hr \/>\n<h2>9. \u94fe\u8868\u4e0e\u6570\u7ec4\u5bf9\u6bd4<\/h2>\n<figure><table>\n<thead>\n<tr><th>\u9879\u76ee<\/th><th>\u6570\u7ec4<\/th><th>\u94fe\u8868<\/th><\/tr><\/thead>\n<tbody><tr><td>\u5b58\u50a8<\/td><td>\u8fde\u7eed\u5185\u5b58<\/td><td>\u975e\u8fde\u7eed\uff0c\u9760\u6307\u9488\u8fde\u63a5<\/td><\/tr><tr><td><strong>\u968f\u673a\u8bbf\u95ee<\/strong><\/td><td><strong>O(1)<\/strong><\/td><td><strong>O(n)<\/strong><\/td><\/tr><tr><td><strong>\u63d2\u5165\u5220\u9664<\/strong><\/td><td><strong>O(n)<\/strong><\/td><td><strong>O(1)<\/strong><\/td><\/tr><tr><td>\u8d8a\u754c\u98ce\u9669<\/td><td>\u6709<\/td><td>\u65e0\u6570\u7ec4\u8d8a\u754c\u6982\u5ff5<\/td><\/tr><tr><td>\u7a7a\u95f4\u5f00\u9500<\/td><td>\u5c11<\/td><td>\u591a\uff08\u989d\u5916\u6307\u9488\uff09<\/td><\/tr><\/tbody>\n<\/table><\/figure>\n<hr \/>\n<h2>10. \u94fe\u8868\u5e38\u89c1\u9519\u8bef\u4e0e\u9677\u9631<\/h2>\n<ol>\n<li>\u5fd8\u8bb0\u66f4\u65b0 head \u6307\u9488<\/li>\n<li>\u5fd8\u8bb0\u5904\u7406\u7a7a\u94fe\u8868<\/li>\n<li>free \u540e\u7ee7\u7eed\u4f7f\u7528\u6307\u9488\uff08\u60ac\u7a7a\u6307\u9488\uff09<\/li>\n<li>\u5220\u9664\u8282\u70b9\u65f6\u8df3\u94fe<\/li>\n<li>\u53cc\u5411\u94fe\u8868\u5fd8\u8bb0\u7ef4\u62a4\u524d\u9a71\u6307\u9488<\/li>\n\n<\/ol>\n<hr \/>\n<h2>11. \u7efc\u5408\u793a\u4f8b\uff1a\u5b8c\u6574\u5355\u94fe\u8868\u7a0b\u5e8f<\/h2>\n<pre><code>typedef struct Node {\n    int data;\n    struct Node *next;\n} Node;\n\nNode* create(int x) {\n    Node *p = malloc(sizeof(Node));\n    p-&gt;data = x;\n    p-&gt;next = NULL;\n    return p;\n}\n\nvoid push_front(Node **head, int x) {\n    Node *p = create(x);\n    p-&gt;next = *head;\n    *head = p;\n}\n\nvoid print(Node *head) {\n    for (Node *cur = head; cur; cur = cur-&gt;next)\n        printf(&quot;%d &quot;, cur-&gt;data);\n}\n\nint main() {\n    Node *head = NULL;\n    push_front(&amp;head, 3);\n    push_front(&amp;head, 5);\n    push_front(&amp;head, 7);\n\n    print(head);  \/\/ 7 5 3\n}\n<\/code><\/pre>\n\n","protected":false},"excerpt":{"rendered":"<p>1. \u94fe\u8868\u7684\u6982\u5ff5 \u94fe\u8868\uff08Linked List\uff09\u662f\u4e00\u79cd\u901a\u8fc7\u201c\u6307\u9488\u201d\u5c06\u591a\u4e2a\u8282\u70b9\u8fde\u63a5\u8d77\u6765\u7684\u7ebf\u6027\u6570\u636e\u7ed3\u6784\u3002 \u6570\u636e\u7ed3\u6784 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[23],"tags":[],"class_list":["post-364","post","type-post","status-publish","format-standard","hentry","category-23"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"http:\/\/4.189.252.43\/index.php\/wp-json\/wp\/v2\/posts\/364","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/4.189.252.43\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4.189.252.43\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4.189.252.43\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4.189.252.43\/index.php\/wp-json\/wp\/v2\/comments?post=364"}],"version-history":[{"count":1,"href":"http:\/\/4.189.252.43\/index.php\/wp-json\/wp\/v2\/posts\/364\/revisions"}],"predecessor-version":[{"id":365,"href":"http:\/\/4.189.252.43\/index.php\/wp-json\/wp\/v2\/posts\/364\/revisions\/365"}],"wp:attachment":[{"href":"http:\/\/4.189.252.43\/index.php\/wp-json\/wp\/v2\/media?parent=364"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4.189.252.43\/index.php\/wp-json\/wp\/v2\/categories?post=364"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4.189.252.43\/index.php\/wp-json\/wp\/v2\/tags?post=364"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}