{"id":2358,"date":"2022-04-08T01:20:44","date_gmt":"2022-04-07T17:20:44","guid":{"rendered":"https:\/\/jimmyswebnote.com\/?p=2358"},"modified":"2022-04-10T15:06:27","modified_gmt":"2022-04-10T07:06:27","slug":"%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list","status":"publish","type":"post","link":"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/","title":{"rendered":"\u8cc7\u6599\u7d50\u69cb\u7b46\u8a18 1 &#8211; Array (\u9663\u5217), Linked List (\u93c8\u7d50\u4e32\u5217)"},"content":{"rendered":"\n<p>\u8cc7\u6599\u7d50\u69cb\u5927\u81f4\u4e0a\u53ef\u4ee5\u5206\u70ba linear \u548c non-linear \u5169\u7a2e\u985e\u5225\uff0c\u5176\u4e2d linear data structure \u5305\u542b array, linked-list stack, queue\uff0c non-linear data structure \u5305\u542b trees, graphs\u3002<\/p>\n\n\n\n<p>\u5176\u4e2d non-linear \u5176\u5be6\u4e5f\u53ef\u4ee5\u7528 linear data structure \u4f86\u8868\u793a\uff0c\u56e0\u6b64\u5148\u4f86\u4ecb\u7d39 linear data structure\u3002<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><a href=\"https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/data-structure.png\"><img loading=\"lazy\" width=\"681\" height=\"301\" src=\"https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/data-structure.png\" alt=\"\" class=\"wp-image-2366\" srcset=\"https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/data-structure.png 681w, https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/data-structure-300x133.png 300w\" sizes=\"(max-width: 681px) 100vw, 681px\" \/><\/a><figcaption>\u25b2 \u5716\u7247\u4f86\u6e90\uff1a<a href=\"https:\/\/www.geeksforgeeks.org\/difference-between-linear-and-non-linear-data-structures\/\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/www.geeksforgeeks.org\/difference-between-linear-and-non-linear-data-structures\/\" rel=\"noreferrer noopener\">Difference between Linear and Non-linear Data Structures<\/a><\/figcaption><\/figure><\/div>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-6633524322bbf\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-6633524322bbf\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#1_Linear_data_structure_%E5%AE%9A%E7%BE%A9\" title=\"1. Linear data structure \u5b9a\u7fa9\">1. Linear data structure \u5b9a\u7fa9<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#2_Array_%E9%99%A3%E5%88%97\" title=\"2. Array (\u9663\u5217)\">2. Array (\u9663\u5217)<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#21_%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6\" title=\"2.1 \u6642\u9593\u8907\u96dc\u5ea6\">2.1 \u6642\u9593\u8907\u96dc\u5ea6<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#3_Linked-list_%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97\" title=\"3. Linked-list (\u93c8\u7d50\u4e32\u5217)\">3. Linked-list (\u93c8\u7d50\u4e32\u5217)<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#31_%E5%88%86%E9%A1%9E\" title=\"3.1 \u5206\u985e\">3.1 \u5206\u985e<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#311_Singly_Linked-list\" title=\"3.1.1 Singly Linked-list\">3.1.1 Singly Linked-list<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#312_Doubly_Linked-list\" title=\"3.1.2 Doubly Linked-list\">3.1.2 Doubly Linked-list<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#313_Circular_Linked-list\" title=\"3.1.3 Circular Linked-list\">3.1.3 Circular Linked-list<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#32_JavaScript_%E5%AF%A6%E4%BD%9C\" title=\"3.2 JavaScript \u5be6\u4f5c\">3.2 JavaScript \u5be6\u4f5c<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#321_node\" title=\"3.2.1 node\">3.2.1 node<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#322_Singly_linked-list\" title=\"3.2.2 Singly linked-list\">3.2.2 Singly linked-list<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#33_%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6\" title=\"3.3 \u6642\u9593\u8907\u96dc\u5ea6\">3.3 \u6642\u9593\u8907\u96dc\u5ea6<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#4_Linked-list_Array_%E6%AF%94%E8%BC%83\" title=\"4. Linked-list, Array \u6bd4\u8f03\">4. Linked-list, Array \u6bd4\u8f03<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/jimmyswebnote.com\/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b%e7%ad%86%e8%a8%98-1-array-linked-list\/#5_%E5%8F%83%E8%80%83%E8%B3%87%E6%96%99\" title=\"5. \u53c3\u8003\u8cc7\u6599\">5. \u53c3\u8003\u8cc7\u6599<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"1_Linear_data_structure_%E5%AE%9A%E7%BE%A9\"><\/span>1. Linear data structure \u5b9a\u7fa9<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<ul><li>\u5143\u7d20\u4e4b\u9593\u6709\u9806\u5e8f\u6027\u7684<\/li><li>\u82e5\u5143\u7d20\u5b58\u5728\u591a\u500b\uff0c\u5247\u7b2c\u4e00\u500b\u5143\u7d20\u6c92\u6709 predecessor (\u524d\u9a45\u5143\u7d20)\uff0c\u6700\u5f8c\u4e00\u500b\u5143\u7d20\u6c92\u6709 successor (\u5f8c\u7e7c\u5143\u7d20)<\/li><li>\u9664\u4e86\u7b2c\u4e00\u500b\u5143\u7d20\u548c\u6700\u5f8c\u4e00\u500b\u5143\u7d20\uff0c\u5176\u9918\u5143\u7d20\u90fd\u53ea\u6709\u4e00\u500b predecessor \u548c successor<\/li><\/ul>\n\n\n\n<p>Linear data structure \u6309\u7167\u5132\u5b58\u65b9\u5f0f\u53c8\u5206\u70ba\uff1a<\/p>\n\n\n\n<ul><li>Sequential list (\u5faa\u5e8f\u5132\u5b58\u7d50\u69cb)\uff1aArray<\/li><li>Linked list (\u93c8\u5f0f\u5132\u5b58\u7d50\u69cb)\uff1aLinked-list<\/li><\/ul>\n\n\n\n<p>\u6709\u4e9b\u6587\u7ae0\u6703\u628a stack \u548c queue \u6b78\u985e\u5728\u5faa\u5e8f\u5132\u5b58\u7d50\u69cb\uff0c\u4f46\u5be6\u969b\u4e0a stack \u548c queue \u4e5f\u90fd\u5b58\u5728\u93c8\u5f0f\u5132\u5b58\u7d50\u69cb\u3002<\/p>\n\n\n\n<h2><span class=\"ez-toc-section\" id=\"2_Array_%E9%99%A3%E5%88%97\"><\/span>2. Array (\u9663\u5217)<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Array \u70ba linear data structure \u7684\u5faa\u5e8f\u5132\u5b58\u7d50\u69cb\uff0c\u6307\u7684\u662f\u6703\u5206\u914d\u4e00\u6bb5\u9023\u7e8c\u8a18\u61b6\u9ad4\u4f4d\u7f6e\u4f86\u5132\u5b58\u9019\u500b linear list\u3002\u56e0\u6b64\u4e00\u822c\u4f86\u8aaa\u5728\u9ad8\u968e\u7684\u7a0b\u5f0f\u8a9e\u8a00\u4e2d array \u7684\u9577\u5ea6\u662f\u56fa\u5b9a\u7684\uff0c<strong><span style=\"color:#ff0000\" class=\"has-inline-color\">\u9664\u4e86 JavaScript \u4e4b\u5916\uff01<\/span><\/strong>JavaScript \u7684 array \u9577\u5ea6\u662f\u53ef\u4ee5\u96a8\u8457\u5143\u7d20\u7684\u589e\u6e1b\u81ea\u52d5\u4f38\u7e2e\u3002\u4f46\u8209\u4f8b\u4f86\u8aaa\uff0c\u5728 go \u88e1\u9762\uff0carray \u4e00\u65e6\u5ba3\u544a\u4e86\uff0c\u9577\u5ea6\u5c31\u662f\u56fa\u5b9a\u7684\uff0c\u82e5\u662f\u8981\u4f7f\u7528\u50cf JavaScript \u4e2d array \u7684 data structure\uff0c\u5247\u5fc5\u9700\u7528 slice \u9019\u500b\u8cc7\u6599\u578b\u614b\u3002<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"21_%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6\"><\/span>2.1 \u6642\u9593\u8907\u96dc\u5ea6<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>\u5c0d array CRUD \u7684 time complexity (Average)<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>Access<\/td><td>Search<\/td><td>Insertion<\/td><td>Deletion<\/td><\/tr><tr><td>O(1)<\/td><td>O(n)<\/td><td>O(n)<\/td><td>O(n)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<h2><span class=\"ez-toc-section\" id=\"3_Linked-list_%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97\"><\/span>3. Linked-list (\u93c8\u7d50\u4e32\u5217)<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Linked-list \u70ba linear data structure \u7684\u93c8\u5f0f\u5132\u5b58\u7d50\u69cb\u3002\u5728 array \u4e2d\uff0c\u5ba3\u544a\u6642\u5373\u78ba\u5b9a\u4e86\u8a72 array \u7684\u9577\u5ea6\uff0c\u56e0\u6b64\u5982\u679c\u5ba3\u544a\u7684\u9577\u5ea6\u592a\u5c0f\uff0c\u5247\u9700\u8981\u91cd\u65b0\u5ba3\u544a\u65b0\u7684 array\uff0c\u5ba3\u544a\u7684\u9577\u5ea6\u592a\u5927\uff0c\u5247\u6703\u9020\u6210\u8a18\u61b6\u9ad4\u7a7a\u9593\u7684\u6d6a\u8cbb\u3002<\/p>\n\n\n\n<p>Linked-list \u548c array \u6700\u5927\u7684\u5dee\u5225\u5247\u662f\u8a18\u61b6\u9ad4\u5132\u5b58\u7684\u4f4d\u7f6e\u662f\u4e0d\u9023\u7e8c\u7684\u3002Linked-list \u7684\u6bcf\u500b\u5143\u7d20\u7a31\u70ba node (\u7bc0\u9ede)\uff0c\u6bcf\u500b node \u7531 data \u548c pointer (\u6307\u6a19) \u7d44\u6210\uff0c\u5176\u4e2d\u53c8\u5206\u70ba\u4ee5\u4e0b\u4e09\u7a2e\uff1a<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"31_%E5%88%86%E9%A1%9E\"><\/span>3.1 \u5206\u985e<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<h4><span class=\"ez-toc-section\" id=\"311_Singly_Linked-list\"><\/span>3.1.1 Singly Linked-list<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" width=\"408\" height=\"41\" src=\"https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/Singly-linked-list.svg.png\" alt=\"Linked-list\" class=\"wp-image-2361\" srcset=\"https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/Singly-linked-list.svg.png 408w, https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/Singly-linked-list.svg-300x30.png 300w\" sizes=\"(max-width: 408px) 100vw, 408px\" \/><figcaption>\u25b2 \u5716\u7247\u4f86\u6e90\uff1a<a href=\"https:\/\/en.wikipedia.org\/wiki\/Linked_list\" target=\"_blank\" rel=\"noreferrer noopener\">\u7dad\u57fa\u767e\u79d1<\/a><\/figcaption><\/figure>\n\n\n\n<p>\u6bcf\u500b node \u7684 pointer \u6703\u6307\u5411\u4e0b\u4e00\u500b node\u3002<\/p>\n\n\n\n<h4><span class=\"ez-toc-section\" id=\"312_Doubly_Linked-list\"><\/span>3.1.2 Doubly Linked-list<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" width=\"610\" height=\"41\" src=\"https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/610px-Doubly-linked-list.svg.png\" alt=\"Linked-list\" class=\"wp-image-2362\" srcset=\"https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/610px-Doubly-linked-list.svg.png 610w, https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/610px-Doubly-linked-list.svg-300x20.png 300w\" sizes=\"(max-width: 610px) 100vw, 610px\" \/><figcaption>\u25b2 \u5716\u7247\u4f86\u6e90\uff1a<a href=\"https:\/\/en.wikipedia.org\/wiki\/Linked_list\" target=\"_blank\" rel=\"noreferrer noopener\">\u7dad\u57fa\u767e\u79d1<\/a><\/figcaption><\/figure>\n\n\n\n<p>\u6bcf\u500b node \u6709\u5169\u500b pointer\uff0c\u4e00\u500b\u6307\u5411\u524d\u9762\u7684 node\uff0c\u53e6\u4e00\u500b\u6307\u5411\u5f8c\u9762\u7684 node\u3002<\/p>\n\n\n\n<h4><span class=\"ez-toc-section\" id=\"313_Circular_Linked-list\"><\/span>3.1.3 Circular Linked-list<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" width=\"350\" height=\"60\" src=\"https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/350px-Circularly-linked-list.svg.png\" alt=\"Linked-list\" class=\"wp-image-2363\" srcset=\"https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/350px-Circularly-linked-list.svg.png 350w, https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2022\/04\/350px-Circularly-linked-list.svg-300x51.png 300w\" sizes=\"(max-width: 350px) 100vw, 350px\" \/><figcaption>\u25b2 \u5716\u7247\u4f86\u6e90\uff1a<a href=\"https:\/\/en.wikipedia.org\/wiki\/Linked_list\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/en.wikipedia.org\/wiki\/Linked_list\" rel=\"noreferrer noopener\">\u7dad\u57fa\u767e\u79d1<\/a><\/figcaption><\/figure>\n\n\n\n<p>\u548c singly linked-list \u4e00\u6a23\uff0c\u6bcf\u500b node \u90fd\u53ea\u6709\u4e00\u500b pointer\uff0c\u552f\u4e00\u7684\u5dee\u5225\u662f\u6700\u5f8c\u4e00\u500b node \u7684 pointer \u6703\u6307\u5411\u7b2c\u4e00\u500b node\u3002<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"32_JavaScript_%E5%AF%A6%E4%BD%9C\"><\/span>3.2 JavaScript \u5be6\u4f5c<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<h4><span class=\"ez-toc-section\" id=\"321_node\"><\/span>3.2.1 node<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"javascript\" class=\"language-javascript\">class Node {\n  constructor(data, next = null) {\n    this.data = data;\n    this.next = next;\n  }\n}<\/code><\/pre>\n\n\n\n<h4><span class=\"ez-toc-section\" id=\"322_Singly_linked-list\"><\/span>3.2.2 Singly linked-list<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"javascript\" class=\"language-javascript\">class LinkedList {\n  constructor() {\n    this.head = null;\n  }\n\n  insertFirst(data) {\n    this.insertAt(data, 0);\n  }\n\n  size() {\n    let counter = 0;\n    let node = this.head;\n    while (node) {\n      counter++;\n      node = node.next;\n    }\n    return counter;\n  }\n\n  getFirst() {\n    return this.getAt(0);\n  }\n\n  getLast() {\n    return this.getAt(this.size() - 1);\n  }\n\n  clear() {\n    this.head = null;\n  }\n\n  removeFirst() {\n    if (!this.head) {\n      return;\n    }\n    this.head = this.head.next;\n  }\n\n  removeLast() {\n    if (!this.head) {\n      return;\n    }\n    if (!this.head.next) {\n      this.head = null;\n      return;\n    }\n\n    let previous = this.head;\n    let node = this.head.next;\n    while (node.next) {\n      previous = node;\n      node = node.next;\n    }\n    previous.next = null;\n  }\n\n  insertLast(data) {\n    const lastNode = this.getLast();\n\n    if (lastNode) {\n      lastNode.next = new Node(data);\n    } else {\n      this.head = new Node(data);\n    }\n  }\n\n  getAt(index) {\n    let counter = 0;\n    let node = this.head;\n    while (node) {\n      if (counter === index) {\n        return node;\n      }\n      counter++;\n      node = node.next;\n    }\n    return null;\n  }\n\n  removeAt(index) {\n    if (!this.head) {\n      return;\n    }\n    if (index === 0) {\n      this.head = this.head.next;\n      return;\n    }\n    if (index &gt; this.size()) {\n      return;\n    }\n    const previous = this.getAt(index - 1);\n    if (!previous || !previous.next) {\n      return;\n    }\n    previous.next = previous.next.next;\n  }\n\n  insertAt(data, index) {\n    if (!this.head) {\n      this.head = new Node(data);\n      return;\n    }\n    if (index === 0) {\n      this.head = new Node(data, this.head);\n      return;\n    }\n    const previous = this.getAt(index - 1) || this.getLast();\n    const node = new Node(data, previous.next);\n    previous.next = node;\n  }\n\n  forEach(fn) {\n    let node = this.head;\n    let counter = 0;\n    while (node) {\n      fn(node, counter);\n      node = node.next;\n      counter++;\n    }\n  }\n\n  *[Symbol.iterator]() {\n    let node = this.head;\n    while (node) {\n      yield node;\n      node = node.next;\n    }\n  }\n}<\/code><\/pre>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"33_%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6\"><\/span>3.3 \u6642\u9593\u8907\u96dc\u5ea6<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>\u5c0d linked-list CRUD \u7684 time complexity (Average)<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>Access<\/td><td>Search<\/td><td>Insertion<\/td><td>Deletion<\/td><\/tr><tr><td>O(n)<\/td><td>O(n)<\/td><td>O(1)<\/td><td>O(1)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<h2><span class=\"ez-toc-section\" id=\"4_Linked-list_Array_%E6%AF%94%E8%BC%83\"><\/span>4. Linked-list, Array \u6bd4\u8f03<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><\/td><td>Array<\/td><td>Linked-list<\/td><\/tr><tr><td>\u512a\u9ede<\/td><td>\u2022 \u53ef\u4ee5\u7528 index \u5feb\u901f\u5b58\u53d6\u5143\u7d20 (O(1))<br>\u2022 \u8f03\u7bc0\u7701\u8a18\u61b6\u9ad4\u7a7a\u9593\uff0c\u56e0\u70ba linked-list \u9700\u8981\u984d\u5916\u5206\u914d\u8a18\u61b6\u9ad4\u7d66 pointer<\/td><td>\u2022 \u9577\u5ea6\u4e0d\u56fa\u5b9a\uff0c\u4e0d\u7528\u9810\u5148\u5206\u914d\u8a18\u61b6\u9ad4\u7d66 linked-list<br>\u2022 insert \u548c delete \u7684\u6642\u9593\u8907\u96dc\u5ea6\u70ba O(1)<\/td><\/tr><tr><td>\u7f3a\u9ede<\/td><td>\u2022 \u9577\u5ea6\u4e0d\u53ef\u6539\u8b8a\uff0c\u5ba3\u544a\u592a\u9577\u6d6a\u8cbb\u8a18\u61b6\u9ad4\u7a7a\u9593\uff0c\u5ba3\u544a\u592a\u77ed\u5247\u4e0d\u5920\u7528<br>\u2022 insert \u548c delete \u7684\u6642\u9593\u8907\u96dc\u5ea6\u70ba O(n)<\/td><td>\u2022 \u5b58\u53d6\u5143\u7d20\u7684\u6642\u9593\u8907\u96dc\u5ea6\u70ba O(n)<br>\u2022 \u8a18\u61b6\u9ad4\u4f7f\u7528\u91cf\u8f03 array \u5927<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<h2><span class=\"ez-toc-section\" id=\"5_%E5%8F%83%E8%80%83%E8%B3%87%E6%96%99\"><\/span>5. \u53c3\u8003\u8cc7\u6599<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p><a href=\"https:\/\/www.books.com.tw\/products\/0010883039\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/www.books.com.tw\/products\/0010883039\" rel=\"noreferrer noopener\">\u5927\u8a71\u8cc7\u6599\u7d50\u69cb(\u5168\u65b0\u5f69\u8272\u7248)<\/a><br><a href=\"https:\/\/chupai.github.io\/tags\/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B\/\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/chupai.github.io\/tags\/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B\/\" rel=\"noreferrer noopener\">JavaScript \u5b78\u6f14\u7b97\u6cd5<\/a><br><a href=\"https:\/\/www.geeksforgeeks.org\/difference-between-linear-and-non-linear-data-structures\/\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/www.geeksforgeeks.org\/difference-between-linear-and-non-linear-data-structures\/\" rel=\"noreferrer noopener\">Difference between Linear and Non-linear Data Structures<\/a><br><a href=\"https:\/\/www.bigocheatsheet.com\/\" target=\"_blank\" rel=\"noopener\">Big-O Cheat Sheet<\/a><br><a href=\"https:\/\/medium.com\/@maggieliao.cm04g\/%E8%B3%87%E7%B5%90%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95%E7%AD%86%E8%A8%98-1-linked-list-%E8%88%87-array-%E6%96%BCo-n-%E4%B9%8B%E5%B7%AE%E7%95%B0%E6%AF%94%E8%BC%83-badbf08b17ce\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/medium.com\/@maggieliao.cm04g\/%E8%B3%87%E7%B5%90%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95%E7%AD%86%E8%A8%98-1-linked-list-%E8%88%87-array-%E6%96%BCo-n-%E4%B9%8B%E5%B7%AE%E7%95%B0%E6%AF%94%E8%BC%83-badbf08b17ce\" rel=\"noreferrer noopener\">\u8cc7\u7d50\u8207\u6f14\u7b97\u6cd5\u7b46\u8a18 (1)\u2014 linked list \u8207 array \u65bcO(n)\u4e4b\u5dee\u7570\u6bd4\u8f03<\/a><br><a href=\"https:\/\/www.udemy.com\/course\/coding-interview-bootcamp-algorithms-and-data-structure\/\" target=\"_blank\" rel=\"noreferrer noopener\">The Coding Interview Bootcamp: Algorithms + Data Structures<\/a><\/p>\n\n\n\n\n\n<p>\u5982\u679c\u89ba\u5f97\u6211\u7684\u6587\u7ae0\u6709\u5e6b\u52a9\u7684\u8a71\uff0c\u6b61\u8fce\u5e6b\u6211\u7684\u7c89\u5c08\u6309\u8b9a\u54e6~\u8b1d\u8b1d\u4f60\uff01<br><\/p>\n\n<iframe loading=\"lazy\" src=\"https:\/\/www.facebook.com\/plugins\/page.php?href=https%3A%2F%2Fwww.facebook.com%2Fjimmyswebnote&amp;tabs=timeline&amp;width=340&amp;height=500&amp;small_header=false&amp;adapt_container_width=true&amp;hide_cover=false&amp;show_facepile=true&amp;appId\" width=\"340\" height=\"500\" style=\"border:none;overflow:hidden\" scrolling=\"no\" frameborder=\"0\" allowfullscreen=\"true\" allow=\"autoplay; clipboard-write; encrypted-media; picture-in-picture; web-share\"><\/iframe>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u8cc7\u6599\u7d50\u69cb\u5927\u81f4\u4e0a\u53ef\u4ee5\u5206\u70ba linear \u548c non-linear \u5169\u7a2e\u985e\u5225\uff0c\u5176\u4e2d linear data structure \u5305\u542b array, linked-list stack, queue\uff0c non-linear data structure \u5305\u542b trees, graphs\u3002<\/p>\n","protected":false},"author":1,"featured_media":2369,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[147,152],"tags":[161,160],"_links":{"self":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts\/2358"}],"collection":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/comments?post=2358"}],"version-history":[{"count":13,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts\/2358\/revisions"}],"predecessor-version":[{"id":2524,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts\/2358\/revisions\/2524"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/media\/2369"}],"wp:attachment":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/media?parent=2358"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/categories?post=2358"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/tags?post=2358"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}