-
Notifications
You must be signed in to change notification settings - Fork 1
/
368ec959.33b8ae25.js
1 lines (1 loc) · 58.6 KB
/
368ec959.33b8ae25.js
1
(window.webpackJsonp=window.webpackJsonp||[]).push([[26],{159:function(e,n,t){"use strict";t.d(n,"a",(function(){return o})),t.d(n,"b",(function(){return p}));var i=t(0),r=t.n(i);function a(e,n,t){return n in e?Object.defineProperty(e,n,{value:t,enumerable:!0,configurable:!0,writable:!0}):e[n]=t,e}function c(e,n){var t=Object.keys(e);if(Object.getOwnPropertySymbols){var i=Object.getOwnPropertySymbols(e);n&&(i=i.filter((function(n){return Object.getOwnPropertyDescriptor(e,n).enumerable}))),t.push.apply(t,i)}return t}function l(e){for(var n=1;n<arguments.length;n++){var t=null!=arguments[n]?arguments[n]:{};n%2?c(Object(t),!0).forEach((function(n){a(e,n,t[n])})):Object.getOwnPropertyDescriptors?Object.defineProperties(e,Object.getOwnPropertyDescriptors(t)):c(Object(t)).forEach((function(n){Object.defineProperty(e,n,Object.getOwnPropertyDescriptor(t,n))}))}return e}function s(e,n){if(null==e)return{};var t,i,r=function(e,n){if(null==e)return{};var t,i,r={},a=Object.keys(e);for(i=0;i<a.length;i++)t=a[i],n.indexOf(t)>=0||(r[t]=e[t]);return r}(e,n);if(Object.getOwnPropertySymbols){var a=Object.getOwnPropertySymbols(e);for(i=0;i<a.length;i++)t=a[i],n.indexOf(t)>=0||Object.prototype.propertyIsEnumerable.call(e,t)&&(r[t]=e[t])}return r}var d=r.a.createContext({}),u=function(e){var n=r.a.useContext(d),t=n;return e&&(t="function"==typeof e?e(n):l(l({},n),e)),t},o=function(e){var n=u(e.components);return r.a.createElement(d.Provider,{value:n},e.children)},A={inlineCode:"code",wrapper:function(e){var n=e.children;return r.a.createElement(r.a.Fragment,{},n)}},b=r.a.forwardRef((function(e,n){var t=e.components,i=e.mdxType,a=e.originalType,c=e.parentName,d=s(e,["components","mdxType","originalType","parentName"]),o=u(t),b=i,p=o["".concat(c,".").concat(b)]||o[b]||A[b]||a;return t?r.a.createElement(p,l(l({ref:n},d),{},{components:t})):r.a.createElement(p,l({ref:n},d))}));function p(e,n){var t=arguments,i=n&&n.mdxType;if("string"==typeof e||i){var a=t.length,c=new Array(a);c[0]=b;var l={};for(var s in n)hasOwnProperty.call(n,s)&&(l[s]=n[s]);l.originalType=e,l.mdxType="string"==typeof e?e:i,c[1]=l;for(var d=2;d<a;d++)c[d]=t[d];return r.a.createElement.apply(null,c)}return r.a.createElement.apply(null,t)}b.displayName="MDXCreateElement"},278:function(e,n,t){"use strict";t.r(n),n.default="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAABhwAAAGwCAMAAABlzz/EAAACWFBMVEXp8vT/sgHwZ4V1dXX///8AAAAjJCXBycomJygKCgr+9Pbf6Oppbm783+UgIiIFBQX/24suMDBDRkbGzc97f4B/hIXe5uj/+/Tm7/GcoqP9+/sZGhr2qbr/9Nz/0GXc5OakqasQERH4uMbxeZP+/f45Ozzo8fNeYWLj7O6ttLVydnfh6uyOlJX/ylIVFhbU3N7K0tQ2ODm+xsf4use3vb/2qrs8Pj//xDwNDg3/tQmTmJrZ4ePQ2Nq0u70eHx///fr3tcR4fH3W3+D/7cT/677zi6LzhJzwbIn/txFZXV1LTk/O1tiHjI0+QUH86Oz/+ev73eT5w8/2pbenra//4Z7waYdAQ0P/wTH/ux2wt7iDiInb29uXnZ7xcY3/vSYTExQICAfEy8y4v8FhZWb19fWqsbL//v74+Pj98PP60tv1nbD0lqr/2H0xMzPi4uK8wsSdnZ2UmpscHR2vr69tcXJlaWpSVVZHSkr/9eDygJn/3Y8qLCx1eHlrb3AsLi7+9/j98/X/+vD96+/84ujf39//8M7/5q6hp6j0kaeQlZbxdZBVWVlPUlP/89b3r7//6bj0k6jyfZaLkZLwbov/2ob/zl3/yU3l7vDJz9G/xMV9goP/9+T71976z9n6zdf1mq7zh5//3pJbXl/yqAD72eD5yNP/7sn3s8L/46Twa4j/023/zFb/x0YlJif//Pj72OD4vsv/68D/y1Pt7e3ZlwCueQCFXQBTOQCxuLnooQDT09P/1XL6rgDDhwB3UgAwIQAhFgDm5ub/35aZagBsSwBrSgBELwA0JACSgaHSAAAbh0lEQVR42uzdMU9aURiH8XfoX2valLTIDYahdSiiEkUHYqQ0kU1ga9KkxgSt6WiMDdFB49o0ZWLBOvZT9OP13svlgt7TxjS2uSTPb+CcwyGw8YS8A/YIAIA77JEBAHALcQAAEAcAAHEAABAHAABxAAAEiAMAIIE4AAASiAMAIIE4AAASiAMAIIE4AAASiAMAIIE4AAASiAMAIIE4AAASiAMAIOE/xeGlxU5WzWn10HlRtLueFM0p32jkDQCQRq44ZKudNxZpHWwtmMuClLWkvcKSBWrfLXK02DaXTWnTAABp5IrDk8d6nbehXXVq5nKu5+6ne+ab7aw1bGhGC8QBAKaLKw42e6BLC2WlvrnUMtqzpPyi2uG6oRcWakkNi304jc1L8+PTBwMApIZ75lCW6hZo6ipvLmVlGpZ0Ii3d+IqVOfVtvdvtNrXVDexE7ye3pgEAUuNuHErZ0PnKYbC8k8rhuWRDy/ORCxXmJ321UE5DeetrsbGpsY4FVl7HnkvPx6cVAwCkxt04zMpp1oaeym00gHivmReBouWvlFvf2elK3Z1AjpkDAEwNRxw+vw0VpMJw93kyDltVh7dRHFoTX/j1vvm2dWzGQBoAposjDrV4Fp21UG0yDhvmsBLFoZu43lB/fXth8gM+Rval/dF+1gAAKfKgcSit6dRuOdRBbVkFG7uQw4UBAFLkQeOwr8XKesCzyA/9sNtxqK5FOlJntK8aACBFHHE42w01peZwd3bfOBzpqUI3m2XfG8tmdB3EgZkDAEyVZBwcEnE4ex17PxGHYvk6IymTyeXkW7aezj3vlQqe560SBwCYGo44tLdDN9LNcNdOxOGZYnOjOES2NWNmr3q9OS3bjGLfzOe9HKtL9YmjZwCAtPi7mcMznbVDS+44DF+zbEsHvozkP+6a71i/dWwAgLT42ziULfTuz3EIRTMH4gAAU8MRh5YXOpFOvFDr3nHIDwZfNTMYDIruOAxKkWxBK6Wq9kqxgQEA0iIZB4d7x6GjyKkrDmPXBTWL/sXi6FeKAQBS5J/GobQeWNBasLy02JeOqk/8dUNHFthR2wAA6RHEwS2aOUTuF4dWpZLTs0ql4oVx+KkJXYt4S9K3kvk+hdXJH0k9/jEUAFLkgeLgHkjX5wIHUrBcWqi015HO4wF11epX0mXRAADp8Yt9+/dJI4zjOP5dPtVLEy9tKoF0AIYKKUahaYzxsAlsIkxONST1RxwbI9E6iF0NoVOXpozu3f3zygG5Ozw1QRxueL+2536t7+S55/vcOCy2Rn7OdlrJss2Ohgo2tuCoJXVuDACQJFNxOHUiDqSD6Pr0wSG4meLwd8eRlnqXKoRPa3NQMgBAokzF4UhPOIrEYXU5sD9DHDLS0tYfa4RxsL429wwAkCxTcUh9jshImeg6FcQhJhaHlFk1r7PYtlLhLG0WxmHX7PWVOKoEAEnzvH8OT8eh+HHDyl8k93cQh1AQh3Ltn3/d+yAdMwEHAInyMnE4DuOwrG+Lel+6Uqsv7dTNzDvZjsWh3qxoyL9d7PubTRxlBYAEmTcOhzd7J1+31nRrY8W85Jx7F3pTsp6kTuO8WxsM3tW6GZvwOsq7krvRrNpIV9KrNnkAgMSYNw4ZjeVsouFerFvWcQ/N7K6i0H74Dcl926tbYOFSWssaACAh5o2DJ9/3ZjF4bdeG2tc2sn63en3b//FrqGwTn5xG+34JtittAwAkxeNxSOVyKbvPK1dt2ko6nV6xmLQ9jrkGAEg4Pw4AABAHAABxAAAQBwAAcQAAEAcAQAxxAADEEAcAQAxxAADEEAcA/9mrAwEAAAAAQf7WA6xQEsHIAYCRAwAjBwBGDgCMHAAYOQAwcgBg5ADAyAGAkQMAIwcARg4AjBwAGDkAMHIAYOQAwMgBgJEDACMHAGKvDgQAAAAABPlbD7BCSTRyAGDkAMDIAYCRAwAjBwBGDgCMHAAYOQAwcgBg5ADAyAGAkQMAIwcARg4AjBwAGDkAMHIAYOQAwMgBgJEDACMHAEYOAIwcABg5ADByAGDkAMDIAYCRAwAjBwBGDgCMHAAYOQAwcgBg5ADAyAGAkQMAIwcARg4AjBwAiL06tkEYCIIoeskuIGcmJEYEJFRDYVQMEpIdTOAC7r0SRhr9IA4ABHEAIIgDAEEcAAjiAEAQBwCCOAAQxAGAIA4ABHEAIIgDAEEcAAjiAEAQBwCCOAAQxAGAIA4ABHHg79ndn7F7dF/HoXuvY1IGsxfiMIOlqi6vsVmrTuPQrc5jUgazF+Iwg6V+3r5rsC87d8/SVhiHYfxeLptQ8SDVkuBgzlBfWjEaShGrAbOZtJMQaBCiho6lUGoc1KxSunVp7djdvR+v5jznaLQf4bl/4+GZbrj4T0nOe5l8HKxol22368EC72XycbDQbhnSutv1YBnvZfJxsNDu1DS03a4Hy3gvk4+D5e0+nYGr/9pdql2cfdkcrNV1Z3eu/WWmfViZaLfT+37TfDHXUiw8mPcyH4cYjNvVKqy/fdRuvUvQP1BQuSQ479y1W90ik14rEh7Me5mPQwyydrUM+w/bPVmHcvfrsAnsaezVG+B8eTBKKKV5u6fjR5f7N5B+Vhw8mPcyH4cYhHYXF+DjZLtLI3ixI6myB1zrVg/S17p13ITQ7ip8+jV+/e6IdFFR8GDey3wcYhDaVQ2azyfa3YZRRZl5eDN+uA4NZer90O7PEv3W3aMfioIH817m4xCDvF0N4XSi3RtYVbAyAyfSNzhTbi+0ewU9BZUms4qCB/Ne5uMQg6LdVh9279pdgaYKF/BNmoaqcnUohYQbyu3DhmLgwbyX+TjEoGhXh1BaKdo9hq4Kh/BVOoOGCltZu0OYKaTwVzHwYN7LfBxiULSbxfmyaLcGAxVOoC2NoKVCKWt3xANVxcCDeS/zcYjBfbs7WySNvN1dGKpwAH+k99B59APWLgym771WDDyY9zIfhxjct6s1mK2Edlswq0IP5qUBrCr3k6zdU3im2Hgw72U+DjEI7Qbv4XdoVynlReWGUJPm4aVyB6HdH3Cl3K8PH14pBh7Me5mPQwwm290oczQV2v0O0woakL6VNhLS5wq6UFL2aVO5cxaWFAMP5r3MxyEGk+2qB4R2O2WSmsZ2ZqGnW8tw9lRjc4R2dQp7odhtuFQUPJj3Mh+HGDxot7JZtKsLYPljq/GuD1MrCjkzWjveqQ5JktBuawu61WedtXbCekdR8GDey3wcYhDaLRwnRbtL8wm5bl2ZJ1MER7UFSuFTiVw5lv9F82Dey/6xa4cqCENRHIdPGQgLe4QtWQwaDAYRjAaTaTbxAQaCyZf3himM8wj3+9qtfzj8yhWHGixvN87z7RbT9VAe3ee+jll/eTXFaozf7Ub7PjVF9zxGJQxmL8Sherth2sTC9rZvY6kfh4d/JAazF+IAgDgAIA4AiAMAf+IAQCIOACTiAEAiDgAk4gBAIg4AJOIAQCIOACTiAEAiDgAk4gBAIg4AJOIAQCIOwJe9OrhxAIShKGig/573bCKt4BAJOzMlfGEefBAHAD6IAwAfxKGV+WXj2+J/5QbbFzPYj72w9WVRiTjccbqt/zpxeGwvcbghDo3MzOmGONQabGyqD7YyceCc023914nDY3uJww1xaGRmTjfEodZgY1N9sJWJA+ecbuu/Thwe20scbohDIzNzuiEOtQYbm+qDrUwcOOd0W/914vDYXuJwQxwamZnTDXGoNdjYVB9sZeLAOafb+q8Th8f2Eocb4tDIzJxuiEOtwcam+mArEwfOOd3Wf504PLaXONwQh0Zm5nRDHGoNNjbVB1uZOHDO6bb+68Thsb3E4YY4NDIzpxviUGuwsak+2MrEgXNOt/VfJw6P7SUON8ShkZk53RCHWoONTfXBViYOf+zVvWoVQRiH8fnYd0FBgqiHPY3GQgWjEiyCxKSwVxFSiCCioF0MoqVYi5BrsMklnKMSUbTJfWWLpJglkBkyS2bePL9L+DPvPIjH6ar+64hDYXsRhxTEQREX4nQNcahrMDtQ+2A+RBwQj9NV/dcRh8L2Ig4piIMiLsTpGuJQ12B2oPbBfIg4IB6nq/qvIw6F7UUcUhAHRVyI0zXEoa7B7EDtg/kQcUA8Tlf1X0ccCtuLOKQgDoq4EKdriENdg9mB2gfzIeKAeJyu6r+OOBS2F3FIQRwUcSFO1xCHugazA7UP5kPEAfE4XdV/HXEobC/ikII4KOJCnK4hDnUNZgdqH8yHiAPicbqq/zriUNhexCEFcVDEhThdQxzqGswO1D6YDxEHxON0Vf91xKGwvYhDCuJw6E7brpsTmLbthknG6Wr+64hDYXvVFIfV2eyr7/2ebXlPHE7VFZF3J4qLyNSMr8t1ut+fPnOJbB7PNzdf2SMZY1QNNvpiZgQ3YwardK8xButGisOHpvnke1vNW08ckp3FOKzcWs/z111ozrtENo+rTXPXHmFnfumayW7x/eOH+QcrYrE/u/fXOpPZ5OPt5eNfWJV72d358tIYF0kciEMJcbgo0l5e0xeHnZ//pPf5Ue4+LIosbG90+uLw99drEXmw/cJkNRGRG98m+uIw3/svIgsrq90YF0kciEMJceg9ebmkKw4/zsmB69Pscejd+/JGVxz22TvPr6iBKIpP4n32shZUVlHRtXtsqLD2hl2aKNg7goi9i4Ii2HvF3nvvvR/9t5xMJixhdRHPBiee/X0Zndl8uZ7rzXuZTK6+JIsNg8IcDpw6+7p2+r/C4UMjktSu5YwjI+EQCQcVwoEoofOQ/ygcXlA5zjgQDhzeXvp/wuH1JwrQcHBYw0HC20v/Tzi8e0kB6nR1yJGRcPifw2FI5y09+1xpxywmzth3f2jHZiOZRdP6k2v2rDkgaiKTDFq1MK9V3trT1R0OJIrZfx4Oxz1PNP+TzcUxJcfHaRaZd24diHm8TEz4j3s88XJ+mceTkenxHAJKPJ675esGshHtSDiY7aV/Hg5hUezdDypPXncHwsFsL/3zcAiLXto3Kk/saecdGToc+q2IrjEiunT50zf9mlkza6zFBSvWRMJBKYxwWEcmV7owQXQCCWJLmaDlPpIkyLuEvkNJ0Ciq2sMhuJjVy0iMi8vVJZfi4hKNcerSCynZO4pSd9u8uzsubqpuMpv/UF7e/lxh0oWDmyq3bguk+x9DcNZy6N3tECRnCL8CG01X3wFuaBmQpJdrkdQhG7FtHQkH2V5yXjDnFXtBdpo5Eg7B7SW36vWe7Ex23pGhw2EJ5o+YCcHTPXJmp7XoxcxIOChFFNEEoj6d104moh5iah03x7St4+8Txa4QE1eIqOb4/PE9+UI9xtk1j681WbthLr/yX4SDvZjVy9gEJOmS64BhwsRsSK6X9+5wYKxu0gForRvc9EHgXfoH1r11CGdLjqcnc4dqgs1Ai0PH0w9Y3n0sbTrnAbZnahkxMcnc5jExx3//Xx2NcCocZHvJWcGcV+zqPLKT0NyJcAhuL7lUL+07VWCIw46sPBxOzwQvG+Yv4umQHwkHxYkyfCD+WWcRDWWcrkR5Rv3ZadI882a2lKi2qBvb5hFN52N3nhL7Who/WUv0L8LBXszaanpuWMHUAhQZbq4LFJwb3v6aDzgY2rs5wLW0S4lpRUD7yq2bhct+/odxN4ATGiceuDFH3MY9QLKxksmtepJX/8V8+HVH+CNVYIuD4SDbSw4K5rxiz6kiu5wKB3t7yaV6XaWKrHPakZWGgw+lRig0Ww60i4SD4hjh0JcJJhMNYuxUbZo7smztKB9miGfWMj/OyGpDVt35FcOh+4RG5Dj2YlYPkAYM1wWHTUeeFwPnIvAwhHfFpTdN18cBYyq1Lko0TVp2szEeQLLsDb8F2hjjSRhTm8V65dZ1Htleckww5xX7QNWNbC+5VK/nVK1IR4YOB7ypIdgDlEbCQXGiiPYzk7VEtRjbRTRDTrQcSo350OPKleZlt6Pd+LCaaAUzaZtQIRx6UPUhi1k9wGyvVfanwreXD3WRIpeS4A3l3WOFOCcnphbhQuXWnaMJ/FkoMX16R5PEoNhqA5Tcy8KN3+wleUbVjmwvOSOY84q9pOpGtpdcqtdXqmakI0OGw6Qagnwf3kTCQXGiAlnQTDSNRhiVhGQ8UW8WoG+eCIfmRLWZRWelwkG/IG/KptZFjuHl1FSrv1sEhPJuf+CSLlkK35HKrLtdkwzDaPPpYIYmSbd8XQzwH2aqHA4OCBYGxdQNB1fppWI4LCoXBZFwUJwoona2cFhP1NAiluiVWOpUa8/WJquJRDj0JZoQuF6ptpKeK8v+3cDF8vO3WyO0d6+jQNcDMxcrs26x3bq3gBiLZCBeLM1pAWFXhdtKDggWDsWUbSu5Si8V20rLI+HgHoytrLZw2Ba8+b7X1lgySGgiwmEX0UJmEa3UA2l9aiGSzKK/4LacOrb7YGoDL0J7l89nty/Dh4OVWXeU3brFsPFEExwCsjL4qO4DaQcEC4tiqj6QdpVerxV8IL0zEg7uISgcphEtrB+gH2O95xLF7m8WXatLPxEOQ4jGM4seKm1l5ciHfYVIlc8Nr/lgkLIjtHfrwkZqlawrTHrZE8D06wlwYvx26yq1lTWcgjmmmEJbWd2ll4pbWSPh4CKCwmEdUVNmYwtR/S7MwAyHkUQdmUW+Si/BccaIfYKJQKJlZV+DuLTEvXpOaO8mIal/OXKraN3NogtsJ3M7zqYD6XbrKvUSXDgFc0wxhV6Cc5leCr4E9/twaIZIOChGUDgcLVesn54+vTvrFXj+PEWEA0ugOoOYJE+14zOKsEPXH2GH1SHeIXcN2r17EzimmxwR3s2RV0iqZl3hy5OaZE58vN8YRwH3/DHAXZt1lTs+IwyCOauYYsdnuEgv5Y7PCA6HRWUzeyLhoBpB4dC7EfUJ1AytOhmJ0JmZLDTDYXygA9KPVDt4r79R9mfL3eiPAk/+UmzeTQOOyIU04d04YLYumZ2b26GK1s0cFpgpNl9pXSZu6eKzsD1T6YP3wiVYWBVT+OA9N+ml2sF7weHwuSwDTkfCQTUqhoPoK40wa+qBRFsZW0GUZ/59FxkTIj/qTBEzvWuSakd27/WhfSJ3pmXYvXLaa/PubuCwbvJQeDcXgWeE7eGrajhol4FlmtUH9mjCsxvHme2AUdb8CRWP7A6XYM4opt6R3a7SS7Eju4PD4Q2w0jyN1RcJB9UIDoeRCUTToptO7ME3pfacyFiXeUTr+zY/3W4/NSIa0Ku7yA/aunhkv6ieVEe5j/3w+j3OejPpvGXRY9cAjA149whwruy+Dq2FhQukYccUIKfK1h23HTh0d05mm5JhOJvJ/74RuKdx/Aekqe8BB962iVfvYz/hEcw5xVT72I+79FLqYz/B4RANLFoTdWZgqW/R00g4KEZwOLBatUlSZwXjHCVJzVJjZQFjLbuRZNoM5T4TehHwIk0XHASyl+6dfSktm8/h8GzhXcvVqbwpPPWmL8n07iYfsoXPl2ajsOr3dVrGAUhaZJjb0r9ogvgsZMUb5k4GJ129z4SGRzDnFFPtM6Fu00uhz4RWDAfOTph4V36OhINiBIUDp966ocRptFDeGPRoSJy5V5obvyYRGLv6zCOi2PFdqrqV1fnv5d+uC3hle/dYEkx87ZcCyAl4d5OXTyaleHFukzwdJ7cQKEhJ4VcXJlbRugL/5Y3gPLicaVb4G/2aiUeerRw/OjlLWtcOY+y/EsxxxVj46dQpxKLb9XJCsJaMhSUc8ku5UFgys0eNSDi4hLbT283vzixaNl08xQyKwVN6yblTpe0mMiXQK5AKnNclHa77AHiLdutjs8W05V39SAo4dVNvl52ovDfHK2z+aPbffqdrXPzJOX6tyrDQuE6wv1TMNYK5Tq/qFqxGlciftHLSLxci4fCTvXo5rQMGwjCqRympJTf7gJdpwGkkZaTUYIgXI4ORsA2a4ZyN9j+MPj5qvOvX39+Pp/Hi+//31bc/Px8jeHo8Pz9+jEU/c/3pfvlg62K1B0uw191xeCEOfInxucqfbhuLdIu196UbrC+yDzYjcWCf0y3914nDZXuJwwlxKGRETreJQ67B+iL7YDMSB/Y53dJ/nThctpc4nBCHQkbkdJs45BqsL7IPNiNxYJ/TLf3XicNle4nDCXEoZEROt4lDrsH6IvtgMxIH9jnd0n+dOFy2lzicEIdCRuR0mzjkGqwvsg82I3Fgn9Mt/deJw2V7icMJcShkRE63iUOuwfoi+2AzEgf2Od3Sf504XLaXOJwQh0JG5HSbOOQarC+yDzYjcWCf0y3914nDZXuJwwlxKGRETreJQ67B+iL7YDMSB/Y53dJ/nThctpc4nBCHQkbkdJs45BqsL7IPNiNxYJ/TLf3XicNle4nDCXEoZEROt4lDrsH6IvtgMxIH9jnd0n+dOFy2lzicEIdCRuR0mzjkGqwvsg82I3Fgn9Mt/deJw2V7icMJcShkRE63iUOuwfoi+2AzEgf2Od3Sf504XLaXOJwQh0JG5HSbOOQarC+yDzYjcWCf0y3914nDZXuJwwlxKGRETreJQ67B+iL7YDMSB/Y53dJ/nThctpc4nBCHQkbkdJs45BqsL7IPNiNxYJ/TLf3XicNle4nDCXEoZEROt4lDrsH6IvtgMxIHABAHAMQBAHEAQBwAEAcA3hAHAN4Qh3/s1YEAAAAAgCB/6wFWKIkAGDkAMHIAYOQAwMgBgJEDACMHAEYOAIwcABg5ADByAGDkAMDIAYCRAwAjBwBGDgCMHAAYOQAwcgBg5ADAyAGAkQMAIwcARg4AjBwAGDkAMHIAYOQAwMgBgJEDACMHAEYOAIwcABg5ADByAGDkAMDIAYCRAwAjBwBGDrFXBwIAAAAAgvytB1ihJAJg5ADAyAGAkQMAIwcARg4AjBwAGDkAMHIAYOQAwMgBgJEDACMHAEYOAIwcABg5ADByAGDkAMDIAYCRAwAjBwBGDgCMHAAYOQAwcgBg5ADAyAGAkQMAIwcARg4AjBwAGDkAMHIAYOQAwMgBgJEDACMHAEYOAIwcABg5xF4dCAAAAAAI8rceYIWSCICRAwAjBwBGDgCMHAAYOQAwcgBg5ADAyAGAkQMAIwcARg4AjBwAGDkAMHIAYOQAwMgBgJEDACMHAEYOAIwcABg5ADByAGDkAMDIAYCRAwAjBwBGDgCMHAAYOQAwcgBg5ADAyAGAkQMAIwcARg4AjBwAGDkAMHIAYOQQe3UgAAAAACDI33qAFUoiAEYOAIwcABg5ADByAGDkAMDIAYCRAwAjBwBGDgCMHAAYOQAwcgBg5ADAyAGAkQMAIwcARg4AjBwAGDkAMHIAYOQAwMgBgJEDACMHAEYOAIwcABg5ADByAGDkAMDIAYCRAwAjBwBGDgCMHAAYOQAwcgBg5ADAyAGAkUPt1SEBAAAAAqD/r+2abXACAIYcABiPHACgBJowgNwoYlDAAAAAAElFTkSuQmCC"},279:function(e,n,t){"use strict";t.r(n),n.default=t.p+"assets/images/doubly-linked-list-d4ed2db18d234f36832a213a679fb6e1.png"},280:function(e,n,t){"use strict";t.r(n),n.default=t.p+"assets/images/circular-linked-list-a5dfac50c8ffbac46d803671c8b8dd1f.png"},95:function(e,n,t){"use strict";t.r(n),t.d(n,"frontMatter",(function(){return c})),t.d(n,"metadata",(function(){return l})),t.d(n,"rightToc",(function(){return s})),t.d(n,"default",(function(){return u}));var i=t(3),r=t(7),a=(t(0),t(159)),c={id:"linked-list",title:"\u94fe\u8868 LinkedList"},l={unversionedId:"interview/data-structure/linked-list",id:"interview/data-structure/linked-list",isDocsHomePage:!1,title:"\u94fe\u8868 LinkedList",description:"\u94fe\u8868\uff08Linked list\uff09\u662f\u4e00\u79cd\u5e38\u89c1\u7684\u57fa\u7840\u6570\u636e\u7ed3\u6784\uff0c\u662f\u4e00\u79cd\u7ebf\u6027\u8868\uff0c\u94fe\u8868\u4e2d\u7684\u5143\u7d20\u5728\u5185\u5b58\u4e2d\u5e76\u4e0d\u662f\u8fde\u7eed\u653e\u7f6e\u7684\u3002\u6bcf\u4e2a\u5143\u7d20\u7531\u4e00\u4e2a\u5b58\u50a8\u5143\u7d20\u672c\u8eab\u7684\u8282\u70b9\u548c\u4e00\u4e2a\u6307\u5411\u4e0b\u4e00\u4e2a\u5143\u7d20\u7684\u5f15\u7528(\u4e5f\u79f0\u6307\u9488\u6216\u94fe\u63a5)\u7ec4\u6210\u3002",source:"@site/docs/interview/data-structure/linked-list.md",slug:"/interview/data-structure/linked-list",permalink:"/docs/interview/data-structure/linked-list",editUrl:"https://github.com/kenve/kenve.github.io/edit/docusaurus/docs/interview/data-structure/linked-list.md",version:"current",sidebar:"interviewSideBar",previous:{title:"\u53cc\u7aef\u961f\u5217 Deque",permalink:"/docs/interview/data-structure/deque"},next:{title:"\u96c6\u5408 Set",permalink:"/docs/interview/data-structure/set"}},s=[{value:"\u5355\uff08\u5411\uff09\u94fe\u8868",id:"\u5355\uff08\u5411\uff09\u94fe\u8868",children:[{value:"\u5b9e\u73b0\u94fe\u8868",id:"\u5b9e\u73b0\u94fe\u8868",children:[]},{value:"\u6d4b\u8bd5",id:"\u6d4b\u8bd5",children:[]}]},{value:"\u53cc\uff08\u5411\uff09\u94fe\u8868",id:"\u53cc\uff08\u5411\uff09\u94fe\u8868",children:[{value:"\u5b9e\u73b0\u53cc\u94fe\u8868",id:"\u5b9e\u73b0\u53cc\u94fe\u8868",children:[]}]},{value:"\u5faa\u73af\u94fe\u8868",id:"\u5faa\u73af\u94fe\u8868",children:[{value:"\u5b9e\u73b0\u5faa\u73af\u94fe\u8868",id:"\u5b9e\u73b0\u5faa\u73af\u94fe\u8868",children:[]}]},{value:"\u6709\u5e8f\u94fe\u8868",id:"\u6709\u5e8f\u94fe\u8868",children:[{value:"\u5b9e\u73b0\u6709\u5e8f\u94fe\u8868",id:"\u5b9e\u73b0\u6709\u5e8f\u94fe\u8868",children:[]}]},{value:"\u521b\u5efa StackLinkedList \u7c7b",id:"\u521b\u5efa-stacklinkedlist-\u7c7b",children:[]},{value:"\u76f8\u5173\u9898\u76ee",id:"\u76f8\u5173\u9898\u76ee",children:[]}],d={rightToc:s};function u(e){var n=e.components,c=Object(r.a)(e,["components"]);return Object(a.b)("wrapper",Object(i.a)({},d,c,{components:n,mdxType:"MDXLayout"}),Object(a.b)("p",null,Object(a.b)("strong",{parentName:"p"},"\u94fe\u8868"),"\uff08Linked list\uff09\u662f\u4e00\u79cd\u5e38\u89c1\u7684\u57fa\u7840\u6570\u636e\u7ed3\u6784\uff0c\u662f\u4e00\u79cd\u7ebf\u6027\u8868\uff0c\u94fe\u8868\u4e2d\u7684\u5143\u7d20\u5728\u5185\u5b58\u4e2d\u5e76\u4e0d\u662f\u8fde\u7eed\u653e\u7f6e\u7684\u3002\u6bcf\u4e2a\u5143\u7d20\u7531\u4e00\u4e2a\u5b58\u50a8\u5143\u7d20\u672c\u8eab\u7684\u8282\u70b9\u548c\u4e00\u4e2a\u6307\u5411\u4e0b\u4e00\u4e2a\u5143\u7d20\u7684\u5f15\u7528(\u4e5f\u79f0\u6307\u9488\u6216\u94fe\u63a5)\u7ec4\u6210\u3002"),Object(a.b)("ul",null,Object(a.b)("li",{parentName:"ul"},"\u4ece\u6570\u7ec4\u7684\u8d77\u70b9\u6216\u4e2d\u95f4\u63d2\u5165\u6216\u79fb\u9664\u9879\u7684\u6210\u672c\u5f88\u9ad8\uff0c\u7531\u4e8e\u94fe\u8868\u4e0d\u5fc5\u987b\u6309\u987a\u5e8f\u5b58\u50a8\uff0c\u94fe\u8868\u5728\u63d2\u5165\u7684\u65f6\u5019\u53ef\u4ee5\u8fbe\u5230 O(1) \u7684\u590d\u6742\u5ea6\uff0c\u6bd4\u6570\u7ec4\u5feb\u5f97\u591a\uff0c\u4f46\u662f\u67e5\u627e\u4e00\u4e2a\u8282\u70b9\u6216\u8005\u8bbf\u95ee\u7279\u5b9a\u7f16\u53f7\u7684\u8282\u70b9\u5219\u9700\u8981 O(n) \u7684\u65f6\u95f4\uff0c\u800c\u6570\u7ec4\u76f8\u5e94\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u5206\u522b\u662f O(logn) \u548c O(1)\u3002"),Object(a.b)("li",{parentName:"ul"},"\u4f7f\u7528\u94fe\u8868\u7ed3\u6784\u53ef\u4ee5\u514b\u670d\u6570\u7ec4\u94fe\u8868\u9700\u8981\u9884\u5148\u77e5\u9053\u6570\u636e\u5927\u5c0f\u7684\u7f3a\u70b9\uff0c\u94fe\u8868\u7ed3\u6784\u53ef\u4ee5\u5145\u5206\u5229\u7528\u8ba1\u7b97\u673a\u5185\u5b58\u7a7a\u95f4\uff0c\u5b9e\u73b0\u7075\u6d3b\u7684\u5185\u5b58\u52a8\u6001\u7ba1\u7406\u3002\u4f46\u662f\u94fe\u8868\u5931\u53bb\u4e86\u6570\u7ec4\u968f\u673a\u8bfb\u53d6\u7684\u4f18\u70b9\uff0c\u540c\u65f6\u94fe\u8868\u7531\u4e8e\u589e\u52a0\u4e86\u7ed3\u70b9\u7684\u6307\u9488\u57df\uff0c\u7a7a\u95f4\u5f00\u9500\u6bd4\u8f83\u5927\u3002")),Object(a.b)("div",{className:"admonition admonition-tip alert alert--success"},Object(a.b)("div",Object(i.a)({parentName:"div"},{className:"admonition-heading"}),Object(a.b)("h5",{parentName:"div"},Object(a.b)("span",Object(i.a)({parentName:"h5"},{className:"admonition-icon"}),Object(a.b)("svg",Object(i.a)({parentName:"span"},{xmlns:"http://www.w3.org/2000/svg",width:"12",height:"16",viewBox:"0 0 12 16"}),Object(a.b)("path",Object(i.a)({parentName:"svg"},{fillRule:"evenodd",d:"M6.5 0C3.48 0 1 2.19 1 5c0 .92.55 2.25 1 3 1.34 2.25 1.78 2.78 2 4v1h5v-1c.22-1.22.66-1.75 2-4 .45-.75 1-2.08 1-3 0-2.81-2.48-5-5.5-5zm3.64 7.48c-.25.44-.47.8-.67 1.11-.86 1.41-1.25 2.06-1.45 3.23-.02.05-.02.11-.02.17H5c0-.06 0-.13-.02-.17-.2-1.17-.59-1.83-1.45-3.23-.2-.31-.42-.67-.67-1.11C2.44 6.78 2 5.65 2 5c0-2.2 2.02-4 4.5-4 1.22 0 2.36.42 3.22 1.19C10.55 2.94 11 3.94 11 5c0 .66-.44 1.78-.86 2.48zM4 14h5c-.23 1.14-1.3 2-2.5 2s-2.27-.86-2.5-2z"})))),"\u73b0\u5b9e\u4e2d\u94fe\u8868\u7684\u4f8b\u5b50")),Object(a.b)("div",Object(i.a)({parentName:"div"},{className:"admonition-content"}),Object(a.b)("p",{parentName:"div"},"\u4e00\u5217\u706b\u8f66\u662f\u7531\u4e00\u7cfb\u5217\u8f66\u53a2\u7ec4\u6210\u7684\u3002\u6bcf\u8282\u8f66\u53a2\u90fd\u76f8\u4e92\u8fde\u63a5\uff0c\u4f60\u5f88\u5bb9\u6613\u5206\u79bb\u4e00\u8282\u8f66\u53a2\uff0c\u6539\u53d8\u5b83\u7684\u4f4d\u7f6e\u3001\u6dfb\u52a0\u6216\u79fb\u9664\u5b83\u3002\u6bcf\u8282\u8f66\u53a2\u90fd\u662f\u94fe\u8868\u7684\u5143\u7d20\uff0c\u8f66\u53a2\u95f4\u7684\u8fde\u63a5\u5c31\u662f\u6307\u9488\u3002"))),Object(a.b)("h2",{id:"\u5355\uff08\u5411\uff09\u94fe\u8868"},"\u5355\uff08\u5411\uff09\u94fe\u8868"),Object(a.b)("p",null,"\u94fe\u8868\u4e2d\u6700\u7b80\u5355\u7684\u4e00\u79cd\u662f\u5355\u5411\u94fe\u8868\uff0c\u5b83\u5305\u542b\u4e24\u4e2a\u57df\uff0c\u4e00\u4e2a\u4fe1\u606f\u57df\u548c\u4e00\u4e2a\u6307\u9488\u57df\u3002\u8fd9\u4e2a\u94fe\u63a5\u6307\u5411\u5217\u8868\u4e2d\u7684\u4e0b\u4e00\u4e2a\u8282\u70b9\uff0c\u800c\u6700\u540e\u4e00\u4e2a\u8282\u70b9\u5219\u6307\u5411\u4e00\u4e2a\u7a7a\u503c\u3002"),Object(a.b)("p",null,Object(a.b)("img",{alt:"\u5355\u5411\u94fe\u8868\u56fe",src:t(278).default})),Object(a.b)("h3",{id:"\u5b9e\u73b0\u94fe\u8868"},"\u5b9e\u73b0\u94fe\u8868"),Object(a.b)("p",null,"LinkedList \u7c7b\u5305\u542b\u7684\u65b9\u6cd5\uff1a"),Object(a.b)("ul",null,Object(a.b)("li",{parentName:"ul"},Object(a.b)("inlineCode",{parentName:"li"},"push(element)"),"\uff1a\u5411\u94fe\u8868\u5c3e\u90e8\u6dfb\u52a0\u4e00\u4e2a\u65b0\u5143\u7d20\u3002"),Object(a.b)("li",{parentName:"ul"},Object(a.b)("inlineCode",{parentName:"li"},"insert(element, position)"),"\uff1a\u5411\u94fe\u8868\u7684\u7279\u5b9a\u4f4d\u7f6e\u63d2\u5165\u4e00\u4e2a\u65b0\u5143\u7d20\u3002"),Object(a.b)("li",{parentName:"ul"},Object(a.b)("inlineCode",{parentName:"li"},"getElementAt(index)"),"\uff1a\u8fd4\u56de\u94fe\u8868\u4e2d\u7279\u5b9a\u4f4d\u7f6e\u7684\u5143\u7d20\u3002\u5982\u679c\u94fe\u8868\u4e2d\u4e0d\u5b58\u5728\u8fd9\u6837\u7684\u5143\u7d20\uff0c\u5219\u8fd4\u56de ",Object(a.b)("inlineCode",{parentName:"li"},"null"),"\u3002"),Object(a.b)("li",{parentName:"ul"},Object(a.b)("inlineCode",{parentName:"li"},"remove(element)"),"\uff1a\u4ece\u94fe\u8868\u4e2d\u79fb\u9664\u4e00\u4e2a\u5143\u7d20\u3002"),Object(a.b)("li",{parentName:"ul"},Object(a.b)("inlineCode",{parentName:"li"},"indexOf(element)"),"\uff1a\u8fd4\u56de\u5143\u7d20\u5728\u94fe\u8868\u4e2d\u7684\u7d22\u5f15\u3002\u5982\u679c\u94fe\u8868\u4e2d\u6ca1\u6709\u8be5\u5143\u7d20\u5219\u8fd4\u56de ",Object(a.b)("inlineCode",{parentName:"li"},"-1"),"\u3002"),Object(a.b)("li",{parentName:"ul"},Object(a.b)("inlineCode",{parentName:"li"},"removeAt(position)"),"\uff1a\u4ece\u94fe\u8868\u7684\u7279\u5b9a\u4f4d\u7f6e\u79fb\u9664\u4e00\u4e2a\u5143\u7d20\u3002"),Object(a.b)("li",{parentName:"ul"},Object(a.b)("inlineCode",{parentName:"li"},"isEmpty()"),"\uff1a\u5982\u679c\u94fe\u8868\u4e2d\u4e0d\u5305\u542b\u4efb\u4f55\u5143\u7d20\uff0c\u8fd4\u56de ",Object(a.b)("inlineCode",{parentName:"li"},"true"),"\uff0c\u5982\u679c\u94fe\u8868\u957f\u5ea6\u5927\u4e8e ",Object(a.b)("inlineCode",{parentName:"li"},"0")," \u5219\u8fd4\u56de ",Object(a.b)("inlineCode",{parentName:"li"},"false"),"\u3002"),Object(a.b)("li",{parentName:"ul"},Object(a.b)("inlineCode",{parentName:"li"},"size()"),"\uff1a\u8fd4\u56de\u94fe\u8868\u5305\u542b\u7684\u5143\u7d20\u4e2a\u6570\uff0c\u4e0e\u6570\u7ec4\u7684 ",Object(a.b)("inlineCode",{parentName:"li"},"length")," \u5c5e\u6027\u7c7b\u4f3c\u3002"),Object(a.b)("li",{parentName:"ul"},Object(a.b)("inlineCode",{parentName:"li"},"toString()"),"\uff1a\u8fd4\u56de\u8868\u793a\u6574\u4e2a\u94fe\u8868\u7684\u5b57\u7b26\u4e32\u3002\u7531\u4e8e\u5217\u8868\u9879\u4f7f\u7528\u4e86 ",Object(a.b)("inlineCode",{parentName:"li"},"Node")," \u7c7b\uff0c\u5c31\u9700\u8981\u91cd\u5199\u7ee7\u627f\u81ea JavaScript \u5bf9\u8c61\u9ed8\u8ba4\u7684 ",Object(a.b)("inlineCode",{parentName:"li"},"toString")," \u65b9\u6cd5\uff0c\u8ba9\u5176\u53ea\u8f93\u51fa\u5143\u7d20\u7684\u503c\u3002")),Object(a.b)("pre",null,Object(a.b)("code",Object(i.a)({parentName:"pre"},{className:"language-js"}),"/**\n * \u5224\u65ad\u5143\u7d20\u662f\u5426\u76f8\u7b49\n */\nfunction defaultEquals(a, b) {\n return a === b;\n}\n\n/**\n * \u5b9a\u4e49\u8282\u70b9\u5143\u7d20\n */\nclass Node {\n constructor(element, next) {\n // value\n this.element = element;\n this.next = next || null;\n }\n}\n\n/**\n * \u5b9a\u4e49\u94fe\u8868\u7c7b\n */\nclass LinkedList {\n constructor(equalsFn = defaultEquals) {\n // \u5bf9\u6bd4\u51fd\u6570\n this.equalsFn = equalsFn;\n // \u7528\u6765\u5b58\u50a8\u94fe\u8868\u4e2d\u7684 \u5143\u7d20\u6570\u91cf\n this.count = 0;\n // head \u521d\u59cb\u5316\u4e3a null\n this.head = null;\n }\n\n /**\n * \u5411\u94fe\u8868\u5c3e\u90e8\u6dfb\u52a0\u5143\u7d20\n * \u4e24\u79cd\u573a\u666f\uff1a\u94fe\u8868\u4e3a\u7a7a\uff0c\u6dfb\u52a0\u7684\u662f\u7b2c\u4e00\u4e2a \u5143\u7d20;\u94fe\u8868\u4e0d\u4e3a\u7a7a\uff0c\u5411\u5176\u8ffd\u52a0\u5143\u7d20\n */\n push(element) {\n // \u5b9e\u4f8b\u5316\u4e00\u4e2a node \u8282\u70b9\n const node = new Node(element);\n let current;\n if (this.head === null) {\n // \u94fe\u8868\u4e3a\u7a7a\uff0chead \u5143\u7d20\u6307\u5411 node \u5143\u7d20\n this.head = node;\n } else {\n // \u94fe\u8868\u4e0d\u4e3a\u7a7a\uff0c\u8981\u5411\u94fe\u8868\u7684\u5c3e\u90e8\u6dfb\u52a0\u4e00\u4e2a\u5143\u7d20\n // \u5faa\u73af\u8bbf\u95ee\u5217\u8868\uff0c\u627e\u5230\u6700\u540e\u4e00\u4e2a\u5143\u7d20\n // current \u5b58\u50a8\u5faa\u73af\u5230\u7684\u5177\u4f53\u5143\u7d20\n current = this.head;\n while (current.next !== null) {\n current = current.next;\n }\n // \u5f53 current.next \u4e3a null \u65f6\uff0c\u5373\u4e3a\u6700\u540e\u7684\u5143\u7d20\n // \u6700\u540e\u5143\u7d20\u7684 next \u6307\u9488\u6307\u5411\u60f3\u8981\u6dfb\u52a0\u5230\u94fe\u8868\u7684\u8282\u70b9\n current.next = node;\n }\n // \u94fe\u8868\u957f\u5ea6 +1\n this.count++;\n }\n\n /**\n * \u6839\u636e index \u4f4d\u7f6e\u83b7\u53d6\u5143\u7d20\n */\n getElementAt(index) {\n // \u53c2\u6570\u5408\u6cd5\u6027\u9a8c\u8bc1\n if (index >= 0 && index <= this.count) {\n let node = this.head;\n // \u9700\u8981\u8fed\u4ee3\u94fe\u8868\u7684\u8282\u70b9\uff0c\u76f4\u5230\u5230\u8fbe\u76ee\u6807\u4f4d\u7f6e\n for (let i = 0; i < index && node != null; i++) {\n node = node.next;\n }\n return node;\n }\n return null;\n }\n\n /**\n * \u5728\u4efb\u610f\u4f4d\u7f6e\u63d2\u5165\u5143\u7d20\n * \u4e24\u79cd\u573a\u666f\uff1a\u7b2c\u4e00\u79cd\u573a\u666f\u662f\u5728\u94fe\u8868\u7684\u8d77\u70b9\u6dfb\u52a0\u4e00\u4e2a\u5143\u7d20\uff0c\u7b2c\u4e8c\u79cd\u573a\u666f\u662f\u5728\u94fe\u8868\u4e2d\u95f4\u6216\u5c3e\u90e8\u6dfb\u52a0\u4e00\u4e2a\u5143\u7d20\n */\n insert(element, index) {\n // \u5408\u6cd5\u6027\u6821\u9a8c\n if (index >= 0 && index <= this.count) {\n const node = new Node(element);\n // \u4e00\u3001\u5728\u7b2c\u4e00\u4e2a\u4f4d\u7f6e\u6dfb\u52a0\n if (index === 0) {\n // 1. current \u662f\u94fe\u8868\u4e2d\u7b2c\u4e00\u4e2a\u5143\u7d20\u7684\u5f15\u7528\n const current = this.head;\n // 2. \u628a node.next \u7684 \u503c\u8bbe\u4e3a current\n node.next = current;\n // 3. \u628a head \u7684\u5f15\u7528\u6539\u4e3a node\n this.head = node;\n } else {\n // \u4e8c\u3001\u4e2d\u95f4\u6216\u5c3e\u90e8\u6dfb\u52a0\n // 1. \u8fed\u4ee3\u94fe\u8868\uff0c\u627e\u5230\u76ee\u6807\u4f4d\u7f6e\n const previous = this.getElementAt(index - 1);\n // 2. \u65b0\u5143\u7d20\u6307\u9488\u6307\u5411 previous \u539f\u6765\u7684\u6307\u5411\u5730\u5740\n node.next = previous.next;\n // 3. \u4e4b\u524d\u5143\u7d20\u6307\u9488\u6307\u5411\u5f53\u524d\u6dfb\u52a0\u7684\u5143\u7d20\n previous.next = node;\n }\n // \u94fe\u8868\u957f\u5ea6 +1\n this.count++;\n return true;\n }\n return false;\n }\n\n /**\n * \u6309\u7279\u5b9a\u4f4d\u7f6e\u4ece\u94fe\u8868\u4e2d\u79fb\u9664\u5143\u7d20\n * \u4e24\u79cd\u573a\u666f:\u7b2c\u4e00\u79cd\u662f\u79fb\u9664\u7b2c\u4e00\u4e2a\u5143\u7d20\uff0c\u7b2c\u4e8c\u79cd\u662f\u79fb\u9664\u7b2c\u4e00\u4e2a\u5143\u7d20\u4e4b\u5916\u7684\u5176\u4ed6\u5143\u7d20\n */\n removeAt(index) {\n // \u6821\u9a8c\u53c2\u6570\u5408\u6cd5\u6027\uff08\u8d8a\u754c\u503c\uff09\uff08index \u4ece\u96f6\u5f00\u59cb\uff09\n if (index >= 0 && index < this.count) {\n let current = this.head;\n // \u79fb\u9664\u7b2c\u4e00\u4e2a\u5143\u7d20\n if (index === 0) {\n // \u7528 head \u7684\u6307\u5411\u7684\u4e0b\u4e00\u4e2a\u5143\u7d20\u8d4b\u503c\u4e3a head\n // \u8fd9\u6837 head \u5c31\u6307\u5411\u5217\u8868\u7684\u7b2c\u4e8c\u4e2a\u5143\u7d20\n this.head = current.next;\n } else {\n // \u79fb\u9664\u94fe\u8868\u7684\u6700\u540e\u4e00\u4e2a\u6216\u8005\u4e2d\u95f4\u67d0\u4e2a\u5143\u7d20\n // 1. \u83b7\u53d6\u9700\u79fb\u9664\u5143\u7d20\u7684\u524d\u4e00\u4e2a\u5143\u7d20\n const previous = this.getElementAt(index - 1);\n // 2. \u53d6\u51fa\u9700\u8981\u79fb\u9664\u5143\u7d20\u8282\u70b9\u5f15\u7528\n current = previous.next;\n // 3. \u628a\u524d\u4e00\u4e2a\u5143\u7d20\u7684\u6307\u9488\u6307\u5411\u79fb\u9664\u5143\u7d20\u7684\u4e0b\u4e00\u4e2a\u5143\u7d20\u5730\u5740\n // \u4e22\u5f03\u79fb\u9664\u8282\u70b9\u5728\u8ba1\u7b97\u673a\u5185\u5b58\u4e2d\uff0c\u7b49\u7740\u88ab\u5783\u573e\u56de\u6536\u5668\u6e05\u9664\n previous.next = current.next;\n }\n // \u957f\u5ea6 -1\n this.count--;\n // \u8fd4\u56de\u8282\u70b9\u5143\u7d20\n return current.element;\n }\n return null;\n }\n\n /**\n * indexOf \u7684\u65b9\u6cd5\uff0c\u4f20\u5165\u5143\u7d20\u8fd4\u56de\u4e00\u4e2a\u5143\u7d20\u7684\u4f4d\u7f6e\n * \u8981\u6bd4\u8f83\u94fe\u8868\u4e2d\u7684\u5143\u7d20\u662f\u5426\u76f8\u7b49\uff0c\u6211\u4eec\u9700\u8981\u4f7f\u7528\u4e00\u4e2a\u5185\u90e8\u8c03\u7528\u7684\u51fd\u6570\uff0c\u540d\u4e3a equalsFn\n */\n indexOf(element) {\n let current = this.head;\n // \u8fed\u4ee3\u5143\u7d20\uff0c\u627e\u5230\u8fd4\u56de\u4f4d\u7f6e i\n for (let i = 0; i < this.size() && current != null; i++) {\n // current \u8282\u70b9\u7684\u5143\u7d20\u548c\u76ee\u6807\u5143\u7d20\u662f\u5426\u76f8\u7b49\n if (this.equalsFn(element, current.element)) {\n return i;\n }\n // \u8fed\u4ee3 \u4e0b\u4e00\u4e2a\u94fe\u8868\u8282\u70b9\n current = current.next;\n }\n // \u5426\u5219\u8fd4\u56de -1\n return -1;\n }\n\n /**\n * \u4ece\u94fe\u8868\u4e2d\u79fb\u9664\u5143\u7d20\n */\n remove(element) {\n // \u627e\u5230\u5143\u7d20\u4f4d\u7f6e\n const index = this.indexOf(element);\n // \u6839\u636e\u4f4d\u7f6e\u79fb\u9664\u5143\u7d20\n return this.removeAt(index);\n }\n\n /**\n * \u94fe\u8868\u662f\u5426\u4e3a\u7a7a\n */\n isEmpty() {\n return this.size() === 0;\n }\n\n /**\n * \u94fe\u8868\u957f\u5ea6\n */\n size() {\n return this.count;\n }\n\n /**\n * \u83b7\u53d6\u94fe\u8868\u7b2c\u4e00\u4e2a\u5143\u7d20\uff08head\uff09\n */\n getHead() {\n return this.head;\n }\n\n /**\n * \u6e05\u7a7a\u94fe\u8868\n */\n clear() {\n this.head = null;\n this.count = 0;\n }\n\n /**\n * \u83b7\u53d6\u94fe\u8868\u503c\u7684\u5b57\u7b26\u4e32\n */\n toString() {\n // \u94fe\u8868\u4e3a\u7a7a\uff0c\u8fd4\u56de\u4e00\u4e2a\u7a7a\u5b57\u7b26\u4e32\n if (this.head == null) {\n return '';\n }\n // \u5faa\u73af\u62fc\u63a5\u5b57\u7b26\u4e32\n let objString = `${this.head.element}`;\n let current = this.head.next;\n for (let i = 1; i < this.size() && current != null; i++) {\n objString = `${objString}, ${current.element}`;\n current = current.next;\n }\n return objString;\n }\n}\n")),Object(a.b)("h3",{id:"\u6d4b\u8bd5"},"\u6d4b\u8bd5"),Object(a.b)("pre",null,Object(a.b)("code",Object(i.a)({parentName:"pre"},{className:"language-js"}),"let linkedList = new LinkedList(defaultEquals);\nlinkedList.push('1');\nlinkedList.push('2');\nlinkedList.push('3');\n// and so on ...\n")),Object(a.b)("h2",{id:"\u53cc\uff08\u5411\uff09\u94fe\u8868"},"\u53cc\uff08\u5411\uff09\u94fe\u8868"),Object(a.b)("p",null,"\u4e00\u79cd\u66f4\u590d\u6742\u7684\u94fe\u8868\u662f\u201c\u53cc\u5411\u94fe\u8868\u201d\u6216\u201c\u53cc\u9762\u94fe\u8868\u201d\u3002\u6bcf\u4e2a\u8282\u70b9\u6709\u4e24\u4e2a\u8fde\u63a5\uff1a\u4e00\u4e2a\u6307\u5411\u524d\u4e00\u4e2a\u8282\u70b9\uff08\u5f53\u6b64\u201c\u8fde\u63a5\u201d\u4e3a\u7b2c\u4e00\u4e2a\u201c\u8fde\u63a5\u201d\u65f6\uff0c\u6307\u5411\u7a7a\u503c\u6216\u8005\u7a7a\u5217\u8868\uff09\uff1b\u800c\u53e6\u4e00\u4e2a\u6307\u5411\u4e0b\u4e00\u4e2a\u8282\u70b9\uff08\u5f53\u6b64\u201c\u8fde\u63a5\u201d\u4e3a\u6700\u540e\u4e00\u4e2a\u201c\u8fde\u63a5\u201d\u65f6\uff0c\u6307\u5411\u7a7a\u503c\u6216\u8005\u7a7a\u5217\u8868\uff09\u3002"),Object(a.b)("p",null,Object(a.b)("img",{alt:"\u53cc\u5411\u94fe\u8868\u56fe",src:t(279).default})),Object(a.b)("h3",{id:"\u5b9e\u73b0\u53cc\u94fe\u8868"},"\u5b9e\u73b0\u53cc\u94fe\u8868"),Object(a.b)("p",null,Object(a.b)("inlineCode",{parentName:"p"},"DoublyLinkedList")," \uff08\u53cc\u5411\u94fe\u8868\uff09\u7c7b\u662f\u4e00\u79cd\u7279\u6b8a\u7684 ",Object(a.b)("inlineCode",{parentName:"p"},"LinkedList")," \u7c7b\uff0c\u6211\u4eec\u8981\u6269\u5c55 ",Object(a.b)("inlineCode",{parentName:"p"},"LinkedList")," \uff08\u5355\u5411\u94fe\u8868\uff09\u7c7b\uff0c\u91cd\u5199\u90e8\u5206\u65b9\u6cd5\u3002"),Object(a.b)("pre",null,Object(a.b)("code",Object(i.a)({parentName:"pre"},{className:"language-js",metastring:"{1,6,10,17,22}","{1,6,10,17,22}":!0}),"// \u4f9d\u8d56\u4e0a\u9762\u5355\u94fe\u8868\u5b9a\u4e49\u7684 defaultEquals\n\n/**\n * \u7ee7\u627f\u524d\u9762\u5355\u94fe\u8868\u7684 Node \u7c7b\n */\nclass DoublyNode extends Node {\n constructor(element, next, prev) {\n super(element, next);\n // \u65b0\u589e\u524d\u6307\u9488\n this.prev = prev || null;\n }\n}\n\n/**\n * \u7ee7\u627f\u5355\u94fe\u8868 LinkedList \u7c7b\n */\nclass DoublyLinkedList extends LinkedList {\n constructor(equalsFn = defaultEquals) {\n // \u8c03\u7528 LinkedList \u7684\u6784\u9020\u51fd\u6570\n super(equalsFn);\n // \u65b0\u589e\u5c3e\u90e8\uff0c\u4fdd\u5b58\u5bf9\u94fe\u8868\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u7684\u5f15\u7528\n this.tail = null;\n }\n\n /**\n * \u5411\u53cc\u5411\u94fe\u8868\u6dfb\u52a0\u5143\u7d20\n */\n push(element) {\n const node = new DoublyNode(element);\n // \u94fe\u8868\u4e3a\u7a7a \u8d4b\u7ed9\u5934\u90e8\u548c\u5c3e\u90e8\n if (this.head == null) {\n this.head = node;\n this.tail = node;\n } else {\n // \u6dfb\u52a0\u5230\u5c3e\u90e8\n this.tail.next = node;\n node.prev = this.tail;\n this.tail = node;\n }\n this.count++;\n }\n\n /**\n * \u5411\u53cc\u5411\u94fe\u8868\u4efb\u610f\u4f4d\u7f6e\u63d2\u5165\u4e00\u4e2a\u65b0\u5143\u7d20\n */\n insert(element, index) {\n if (index >= 0 && index <= this.count) {\n const node = new DoublyNode(element);\n let current = this.head;\n // \u573a\u666f\u4e00\uff1a\u5728\u53cc\u5411\u94fe\u8868\u7684\u7b2c\u4e00\u4e2a\u4f4d\u7f6e(\u8d77\u70b9)\u63d2\u5165\u4e00\u4e2a\u65b0\u5143\u7d20\n if (index === 0) {\n if (this.head == null) {\n // \u5982\u679c\u53cc\u5411\u94fe\u8868\u4e3a\u7a7a\n // \u628a head \u548c tail \u90fd\u6307\u5411\u8fd9\u4e2a\u65b0\u8282\u70b9\n this.head = node;\n this.tail = node;\n } else {\n // \u5982\u679c\u4e0d\u4e3a\u7a7a\n // 1. \u628a node.next \u8bbe\u4e3a current\n // node.next = current;\n node.next = this.head;\n // 2. current.prev \u6307\u9488\u5c06\u7531\u6307\u5411\u65b0\u5143\u7d20 node\n this.head.prev = node;\n // 3. head \u6307\u5411\u65b0\u5143\u7d20 node\n this.head = node;\n }\n } else if (index === this.count) {\n // \u573a\u666f\u4e8c\uff1a\u5728\u53cc\u5411\u94fe\u8868\u6700\u540e\u6dfb\u52a0\u4e00\u4e2a\u65b0\u5143\u7d20\n // current \u53d8\u91cf\u5c06\u5f15\u7528\u6700\u540e\u4e00\u4e2a\u5143\u7d20\n current = this.tail;\n // \u539f\u6700\u540e\u5143\u7d20 current.next \u6307\u9488\u5c06\u6307\u5411\u65b0\u5143\u7d20 node\n current.next = node;\n // \u65b0\u5143\u7d20 node.prev \u7684\u6307\u9488\u6307\u5411\u539f\u6700\u540e\u4e00\u4e2a\u5143\u7d20 current\n node.prev = current;\n // \u66f4\u65b0 tail \u6307\u5411\u65b0\u6700\u540e\u4e00\u4e2a\u5143\u7d20 node\n this.tail = node;\n } else {\n // \u573a\u666f\u4e09\uff1a\u5728\u53cc\u5411\u94fe\u8868\u4e2d\u95f4\u63d2\u5165\u4e00\u4e2a\u65b0\u5143\u7d20\n // \u8fed\u4ee3\u53cc\u5411\u94fe\u8868\uff0c\u76f4\u5230\u8981\u4e0b\u6807\u524d\u4e00\u4e2a\u5143\u7d20\u4f4d\u7f6e\n const previous = this.getElementAt(index - 1);\n // \u628a current \u8d4b\u503c\u4e3a\u8981\u63d2\u5165\u4e0b\u6807\u7684\u4e0b\u4e00\u4e2a\u4f4d\u7f6e\u5143\u7d20\n current = previous.next;\n // \u5728 current \u548c previous \u5143\u7d20\u4e4b\u95f4\u63d2\u5165\u65b0\u5143\u7d20\n // \u65b0\u5143\u7d20 node.next \u6307\u9488\u5c06\u6307\u5411 current\n node.next = current;\n // \u800c previous.next \u5c06\u6307\u5411\u65b0\u5143\u7d20 node\n previous.next = node;\n // \u65b0\u5143\u7d20\u7684\u4e0b\u4e00\u4e2a\u5143\u7d20 current.prev \u6307\u9488\u6307\u5411\u65b0\u5143\u7d20 node\n current.prev = node;\n // \u800c\u65b0\u5143\u7d20 node.prev \u6307\u9488\u5c06\u6307\u5411 previous\n node.prev = previous;\n }\n // \u53cc\u94fe\u8868\u957f\u5ea6 +1\n this.count++;\n return true;\n }\n return false;\n }\n\n /**\n * \u4ece\u4efb\u610f\u4f4d\u7f6e\u79fb\u9664\u5143\u7d20\n */\n removeAt(index) {\n if (index >= 0 && index < this.count) {\n let current = this.head;\n // \u573a\u666f\u4e00\uff1a\u4ece\u5934\u90e8\u79fb\u9664\u4e00\u4e2a\u5143\u7d20\n // current \u662f\u5bf9\u53cc\u5411\u94fe\u8868\u4e2d\u7b2c\u4e00\u4e2a\u5143\u7d20\u7684\u5f15\u7528\uff0c\u5373\u8981\u79fb\u9664\u7684\u5143\u7d20\u3002\n if (index === 0) {\n // \u9700\u8981\u6539\u53d8 head \u7684\u5f15\u7528\uff0c\u5c06\u5176\u4ece current \u6539\u4e3a\u4e0b\u4e00\u4e2a\u5143\u7d20 current.next\n this.head = this.head.next;\n // \u5982\u679c\u53ea\u6709\u4e00\u9879\uff0c\u66f4\u65b0 tail\n if (this.count === 1) {\n // \u9700\u8981\u628a tail \u4e5f\u8bbe\u4e3a null\n this.tail = null;\n } else {\n // \u628a\u65b0\u7684\u7b2c\u4e00\u4e2a\u5143\u7d20 head.prev \u7684\u5f15\u7528\u6539\u4e3a null (\u4e5f\u53ef\u4ee5\u7528 current.next.prev\uff09\n this.head.prev = null;\n }\n } else if (index === this.count - 1) {\n // \u573a\u666f\u4e8c\uff1a\u4ece\u5c3e\u90e8\u79fb\u9664\u4e00\u4e2a\u5143\u7d20\n // \u628a tail \u7684\u5f15\u7528\u8d4b\u7ed9 current \u53d8\u91cf\n current = this.tail;\n // \u628a tail \u7684\u5f15\u7528\u66f4\u65b0\u4e3a\u53cc\u5411\u94fe\u8868\u4e2d\u5012\u6570\u7b2c\u4e8c\u4e2a\u5143\u7d20\uff08current.prev \u6216\u8005 tail.prev\uff09\n this.tail = current.prev;\n // \u628a next \u6307\u9488\u66f4\u65b0\n this.tail.next = null;\n } else {\n // \u573a\u666f\u4e09\uff1a\u4ece\u4e2d\u95f4\u79fb\u9664\u4e00\u4e2a\u5143\u7d20\n // \u9996\u5148\u9700\u8981\u8fed\u4ee3\u53cc\u5411\u94fe\u8868\uff0c\u76f4\u5230\u8981\u627e\u7684\u4f4d\u7f6e\n // current \u6240\u5f15\u7528\u7684\u5c31\u662f\u8981\u79fb\u9664\u7684\u5143\u7d20\n current = this.getElementAt(index);\n // \u9700\u8981\u79fb\u9664\u5143\u7d20 current \u7684\u524d\u4e00\u4e2a\u5143\u7d20 previous\n const previous = current.prev;\n // \u5c06 previous \u4e0e current \u7684\u4e0b\u4e00\u9879\u94fe\u63a5\u8d77\u6765\n // previous.next \u5c06\u6307\u5411 current.next\n previous.next = current.next;\n // current.next.prev \u5c06\u6307\u5411 previous\n current.next.prev = previous;\n }\n // \u957f\u5ea6 -1\n this.count--;\n return current.element;\n }\n return null;\n }\n\n /**\n * \u67e5\u627e\u5143\u7d20\u4f4d\u7f6e\n */\n indexOf(element) {\n let current = this.head;\n let index = 0;\n while (current != null) {\n if (this.equalsFn(element, current.element)) {\n return index;\n }\n index++;\n current = current.next;\n }\n return -1;\n }\n\n /**\n * \u67e5\u770b\u5934\u90e8\n */\n getHead() {\n return this.head;\n }\n\n /**\n * \u67e5\u770b\u5c3e\u90e8\n */\n getTail() {\n return this.tail;\n }\n\n /**\n * \u6e05\u7a7a\n */\n clear() {\n super.clear();\n this.tail = null;\n }\n\n /**\n * \u4ece\u5934\u90e8\u5230\u5c3e\u90e8\u8f6c\u5b57\u7b26\u4e32\n */\n toString() {\n if (this.head == null) {\n return '';\n }\n let objString = `${this.head.element}`;\n let current = this.head.next;\n while (current != null) {\n objString = `${objString}, ${current.element}`;\n current = current.next;\n }\n return objString;\n }\n\n /**\n * \u4ece\u5c3e\u90e8\u5230\u5934\u90e8\u8f6c\u5b57\u7b26\u4e32\n */\n inverseToString() {\n if (this.tail == null) {\n return '';\n }\n let objString = `${this.tail.element}`;\n let previous = this.tail.prev;\n while (previous != null) {\n objString = `${objString}, ${previous.element}`;\n previous = previous.prev;\n }\n return objString;\n }\n}\n")),Object(a.b)("div",{className:"admonition admonition-tip alert alert--success"},Object(a.b)("div",Object(i.a)({parentName:"div"},{className:"admonition-heading"}),Object(a.b)("h5",{parentName:"div"},Object(a.b)("span",Object(i.a)({parentName:"h5"},{className:"admonition-icon"}),Object(a.b)("svg",Object(i.a)({parentName:"span"},{xmlns:"http://www.w3.org/2000/svg",width:"12",height:"16",viewBox:"0 0 12 16"}),Object(a.b)("path",Object(i.a)({parentName:"svg"},{fillRule:"evenodd",d:"M6.5 0C3.48 0 1 2.19 1 5c0 .92.55 2.25 1 3 1.34 2.25 1.78 2.78 2 4v1h5v-1c.22-1.22.66-1.75 2-4 .45-.75 1-2.08 1-3 0-2.81-2.48-5-5.5-5zm3.64 7.48c-.25.44-.47.8-.67 1.11-.86 1.41-1.25 2.06-1.45 3.23-.02.05-.02.11-.02.17H5c0-.06 0-.13-.02-.17-.2-1.17-.59-1.83-1.45-3.23-.2-.31-.42-.67-.67-1.11C2.44 6.78 2 5.65 2 5c0-2.2 2.02-4 4.5-4 1.22 0 2.36.42 3.22 1.19C10.55 2.94 11 3.94 11 5c0 .66-.44 1.78-.86 2.48zM4 14h5c-.23 1.14-1.3 2-2.5 2s-2.27-.86-2.5-2z"})))),"\u6539\u8fdb")),Object(a.b)("div",Object(i.a)({parentName:"div"},{className:"admonition-content"}),Object(a.b)("p",{parentName:"div"},"\u53ef\u4ee5\u5bf9 ",Object(a.b)("inlineCode",{parentName:"p"},"insert")," \u548c ",Object(a.b)("inlineCode",{parentName:"p"},"remove")," \u8fd9\u4e24\u4e2a\u65b9\u6cd5\u7684\u5b9e\u73b0\u505a\u4e00\u4e9b\u6539\u8fdb\u3002\u5982\u679c ",Object(a.b)("inlineCode",{parentName:"p"},"index")," \u5927\u4e8e ",Object(a.b)("inlineCode",{parentName:"p"},"length / 2"),"\uff0c\u5c31\u6700\u597d\u4ece\u5c3e\u90e8\u5f00\u59cb\u8fed\u4ee3\uff0c\u800c\u4e0d\u662f\u4ece\u5934\u5f00\u59cb(\u8fd9\u6837\u5c31 \u80fd\u8fed\u4ee3\u53cc\u5411\u94fe\u8868\u4e2d\u66f4\u5c11\u7684\u5143\u7d20)\u3002"))),Object(a.b)("h2",{id:"\u5faa\u73af\u94fe\u8868"},"\u5faa\u73af\u94fe\u8868"),Object(a.b)("p",null,"\u5728\u4e00\u4e2a",Object(a.b)("strong",{parentName:"p"},"\u5faa\u73af\u94fe\u8868"),"\u4e2d\u7684\u9996\u8282\u70b9\u548c\u672b\u8282\u70b9\u88ab\u8fde\u63a5\u5728\u4e00\u8d77\u3002\u5b9e\u73b0\u65b9\u5f0f\u53ef\u4ee5\u50cf\u94fe\u8868\u4e00\u6837\u53ea\u6709\u5355\u5411\u5f15\u7528\uff0c\u4e5f\u53ef\u4ee5\u50cf\u53cc\u5411\u94fe\u8868\u4e00\u6837\u6709\u53cc\u5411\u5f15\u7528\u3002",Object(a.b)("br",{parentName:"p"}),"\n","\u5faa\u73af\u94fe\u8868\u548c\u94fe\u8868\u4e4b\u95f4\u552f\u4e00\u7684\u533a\u522b\u5728\u4e8e\uff0c\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u6307\u5411\u4e0b\u4e00\u4e2a\u5143\u7d20\u7684\u6307\u9488\uff08",Object(a.b)("inlineCode",{parentName:"p"},"tail.next"),"\uff09\u4e0d\u662f\u5f15\u7528 ",Object(a.b)("inlineCode",{parentName:"p"},"null"),"\uff0c\u800c\u662f\u6307\u5411\u7b2c\u4e00\u4e2a\u5143\u7d20(",Object(a.b)("inlineCode",{parentName:"p"},"head"),")\u3002",Object(a.b)("br",{parentName:"p"}),"\n","\u53cc\u5411\u5faa\u73af\u94fe\u8868\u6709\u6307\u5411 ",Object(a.b)("inlineCode",{parentName:"p"},"head")," \u5143\u7d20\u7684 ",Object(a.b)("inlineCode",{parentName:"p"},"tail.next")," \u548c\u6307\u5411 ",Object(a.b)("inlineCode",{parentName:"p"},"tail")," \u5143\u7d20\u7684 ",Object(a.b)("inlineCode",{parentName:"p"},"head.prev"),"\u3002"),Object(a.b)("p",null,Object(a.b)("img",{alt:"\u5faa\u73af\u94fe\u8868\u56fe",src:t(280).default})),Object(a.b)("h3",{id:"\u5b9e\u73b0\u5faa\u73af\u94fe\u8868"},"\u5b9e\u73b0\u5faa\u73af\u94fe\u8868"),Object(a.b)("p",null,Object(a.b)("inlineCode",{parentName:"p"},"CircularLinkedList")," \u7c7b\u4e0d\u9700\u8981\u4efb\u4f55\u989d\u5916\u7684\u5c5e\u6027\uff0c\u6240\u4ee5\u76f4\u63a5\u6269\u5c55 ",Object(a.b)("inlineCode",{parentName:"p"},"LinkedList")," \u7c7b\u5e76\u8986\u76d6\u9700\u8981\u6539\u5199\u7684\u65b9\u6cd5\u5373\u53ef\u3002"),Object(a.b)("pre",null,Object(a.b)("code",Object(i.a)({parentName:"pre"},{className:"language-js"}),"class CircularLinkedList extends LinkedList {\n constructor(equalsFn = defaultEquals) {\n super(equalsFn);\n }\n\n /**\n * \u6dfb\u52a0\u5143\u7d20\n */\n push(element) {\n const node = new Node(element);\n let current;\n if (this.head == null) {\n this.head = node;\n } else {\n current = this.getElementAt(this.size() - 1);\n current.next = node;\n }\n // \u628a node.next \u6307\u5411 head\uff0c\u5f62\u6210\u5faa\u73af\u5217\u8868\n node.next = this.head;\n this.count++;\n }\n\n /**\n * \u5728\u4efb\u610f\u4f4d\u7f6e\u63d2\u5165\u65b0\u5143\u7d20\n */\n insert(element, index) {\n // \u5411\u5faa\u73af\u94fe\u8868\u4e2d\u63d2\u5165\u5143\u7d20\u7684\u903b\u8f91\u548c\u5411\u666e\u901a\u94fe\u8868\u4e2d\u63d2\u5165\u5143\u7d20\u7684\u903b\u8f91\u662f\u4e00\u6837\u7684\n // \u4e0d\u540c\u4e4b\u5904\u5728\u4e8e\u6211\u4eec\u9700\u8981\u5c06\u5faa\u73af\u94fe\u8868\u5c3e\u90e8\u8282\u70b9\u7684 next \u5f15\u7528\u6307\u5411\u5934\u90e8\u8282\u70b9\n if (index >= 0 && index <= this.count) {\n const node = new Node(element);\n let current = this.head;\n //\u573a\u666f\u4e00\uff1a\u5728\u5faa\u73af\u94fe\u8868\u7b2c\u4e00\u4e2a\u4f4d\u7f6e\u63d2\u5165\u65b0\u5143\u7d20\n if (index === 0) {\n if (this.head == null) {\n // \u94fe\u8868\u4e3a\u7a7a\n // \u5c06 head \u8d4b\u503c\u4e3a\u65b0\u521b\u5efa\u7684\u5143\u7d20 node\n this.head = node;\n // \u5e76\u4e14\u5c06\u6700\u540e\u4e00\u4e2a\u8282\u70b9\u94fe\u63a5\u5230 head\n node.next = this.head;\n } else {\n // \u573a\u666f\u4e8c\uff1a\u5728\u4e00\u4e2a\u975e\u7a7a\u5faa\u73af\u94fe\u8868\u7684\u7b2c\u4e00\u4e2a\u4f4d\u7f6e\u63d2\u5165\u5143\u7d20\n // \u5c06 node.next \u6307\u5411\u73b0\u5728\u7684 head \u5f15\u7528\u7684\u8282\u70b9(current \u53d8\u91cf)\n node.next = current;\n // \u83b7\u53d6\u53d6\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u7684\u5f15\u7528\n current = this.getElementAt(this.size());\n // \u5934\u90e8\u5143\u7d20\u66f4\u65b0\u4e3a\u65b0\u5143\u7d20\uff0c\u518d\u5c06\u6700\u540e\u4e00\u4e2a\u8282\u70b9\uff08current\uff09 \u6307\u5411\u65b0\u7684\u5934\u90e8\u8282\u70b9\n this.head = node;\n current.next = this.head;\n }\n } else {\n // \u573a\u666f\u4e09\uff1a\u5728\u5faa\u73af\u94fe\u8868\u4e2d\u95f4\u63d2\u5165\u65b0\u5143\u7d20\n // \u8fd9\u79cd\u573a\u666f\u76f8\u5bf9\u666e\u901a\u94fe\u8868\u6ca1\u6709\u53d8\u5316\n const previous = this.getElementAt(index - 1);\n node.next = previous.next;\n previous.next = node;\n }\n this.count++;\n return true;\n }\n return false;\n }\n\n /**\n *\n */\n removeAt(index) {\n if (index >= 0 && index < this.count) {\n let current = this.head;\n // \u573a\u666f\u4e00\uff1a\u4ece\u53ea\u6709\u4e00\u4e2a\u5143\u7d20\u7684\u5faa\u73af\u94fe\u8868\u4e2d\u79fb\u9664\u4e00\u4e2a\u5143\u7d20\n if (index === 0) {\n if (this.size() === 1) {\n this.head = null;\n } else {\n // \u573a\u666f\u4e8c\uff1a\u76f8\u5bf9\u4e8e\u666e\u901a\u94fe\u8868\u53ea\u9700\u8981\u8003\u8651\u7b2c\u4e8c\u79cd\u60c5\u51b5\uff0c\u4e5f\u5c31\u662f\u4e00\u4e2a\u975e\u7a7a\u5faa\u73af\u94fe\u8868\u4e2d\u79fb\u9664\u7b2c\u4e00\u4e2a\u5143\u7d20\n // \u5373\u4fee\u6539\u5faa\u73af\u94fe\u8868\u7684 head \u5143\u7d20\uff0c\u7531\u4e8e head \u7684\u6307\u5411\u4f1a\u6539\u53d8\uff0c\u9700\u4fee\u6539\u6700\u540e\u4e00\u4e2a\u8282\u70b9\u7684 next \u5c5e\u6027\n // 1. \u9996\u5148\u4fdd\u5b58\u73b0\u5728\u7684 head \u5143\u7d20\u7684\u5f15\u7528\uff0c\u5b83\u5c06\u4ece\u5faa\u73af\u94fe\u8868\u4e2d\u79fb\u9664\n const removed = this.head;\n // 2. \u83b7\u5f97\u5faa\u73af\u94fe\u8868\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u7684\u5f15\u7528\n current = this.getElementAt(this.size() - 1);\n // 3. \u5148\u66f4\u65b0 head \u5143\u7d20\uff0c\u5c06\u5176\u6307\u5411\u7b2c\u4e8c\u4e2a\u5143\u7d20 head.next\n this.head = this.head.next;\n // \u5c06\u6700\u540e\u4e00\u4e2a\u5143\u7d20\uff08current.next\uff09\u6307\u5411\u65b0\u7684 head\n current.next = this.head;\n // \u66f4\u65b0 current \u53d8\u91cf\u7684\u5f15\u7528\n current = removed;\n }\n } else {\n // \u4e0d\u9700\u8981\u4fee\u6539\u5faa\u73af\u94fe\u8868\u6700\u540e\u4e00\u4e2a\u5143\u7d20\n const previous = this.getElementAt(index - 1);\n current = previous.next;\n previous.next = current.next;\n }\n this.count--;\n return current.element;\n }\n return null;\n }\n}\n")),Object(a.b)("h2",{id:"\u6709\u5e8f\u94fe\u8868"},"\u6709\u5e8f\u94fe\u8868"),Object(a.b)("p",null,Object(a.b)("strong",{parentName:"p"},"\u6709\u5e8f\u94fe\u8868"),"\u662f\u6307\u4fdd\u6301\u5143\u7d20\u6709\u5e8f\u7684\u94fe\u8868\u7ed3\u6784\u3002\u9664\u4e86\u4f7f\u7528\u6392\u5e8f\u7b97\u6cd5\u4e4b\u5916\uff0c\u6211\u4eec\u8fd8\u53ef\u4ee5\u5c06\u5143\u7d20\u63d2\u5165\u5230\n\u6b63\u786e\u7684\u4f4d\u7f6e\u6765\u4fdd\u8bc1\u94fe\u8868\u7684\u6709\u5e8f\u6027\u3002"),Object(a.b)("h3",{id:"\u5b9e\u73b0\u6709\u5e8f\u94fe\u8868"},"\u5b9e\u73b0\u6709\u5e8f\u94fe\u8868"),Object(a.b)("p",null,Object(a.b)("inlineCode",{parentName:"p"},"SortedLinkedList")," \u7c7b\u4f1a\u4ece ",Object(a.b)("inlineCode",{parentName:"p"},"LinkedList")," \u7c7b\u4e2d\u7ee7\u627f\u6240\u6709\u7684\u5c5e\u6027\u548c\u65b9\u6cd5\uff0c\u4f46\u7531\u4e8e\u8fd9\u4e2a\u7c7b\u6709\u7279\u522b\u7684\u884c\u4e3a\uff0c\u6211\u4eec\u9700\u8981\u4e00\u4e2a\u7528\u6765\u6bd4\u8f83\u5143\u7d20\u7684\u51fd\u6570\u3002\u56e0\u6b64\uff0c\u8fd8\u9700\u8981\u58f0\u660e ",Object(a.b)("inlineCode",{parentName:"p"},"compareFn")," \u51fd\u6570\u6765\u6bd4\u8f83\u5143\u7d20\u3002\u8be5\u51fd\u6570\u4f1a\u9ed8\u8ba4\u4f7f\u7528 ",Object(a.b)("inlineCode",{parentName:"p"},"defaultCompare"),"\u3002\u5982\u679c\u5143\u7d20\u6709\u76f8\u540c\u7684\u5f15\u7528\uff0c\u5b83\u5c31\u8fd4\u56de ",Object(a.b)("inlineCode",{parentName:"p"},"0"),"\u3002\u5982\u679c\u7b2c\u4e00\u4e2a\u5143\u7d20\u5c0f\u4e8e\u7b2c\u4e8c\u4e2a\u5143\u7d20\uff0c\u5b83\u5c31\u8fd4\u56de ",Object(a.b)("inlineCode",{parentName:"p"},"-1"),"\uff0c\u53cd\u4e4b\u5219\u8fd4\u56de ",Object(a.b)("inlineCode",{parentName:"p"},"1"),"\u3002"),Object(a.b)("p",null,"\u4e3a\u4e86\u4fdd\u8bc1\u4ee3\u7801\u4f18\u96c5\uff0c\u6211\u4eec\u53ef\u4ee5\u58f0\u660e\u4e00\u4e2a ",Object(a.b)("inlineCode",{parentName:"p"},"Compare")," \u5e38\u91cf\u6765\u8868\u793a\u6bcf\u4e2a\u503c\u3002\u5982\u679c\u7528\u4e8e\u6bd4\u8f83\u7684\u5143\u7d20\u66f4\u590d\u6742\u4e00\u4e9b\uff0c\u6211\u4eec\u53ef\u4ee5\u521b\u5efa\u81ea\u5b9a\u4e49\u7684 \u6bd4\u8f83\u51fd\u6570\u5e76\u5c06\u5b83\u4f20\u5165 ",Object(a.b)("inlineCode",{parentName:"p"},"SortedLinkedList")," \u7c7b\u7684\u6784\u9020\u51fd\u6570\u4e2d\u3002"),Object(a.b)("pre",null,Object(a.b)("code",Object(i.a)({parentName:"pre"},{className:"language-javascript"}),"// \u6bd4\u8f83\u5e38\u91cf\nconst Compare = {\n LESS_THAN: -1,\n BIGGER_THAN: 1,\n};\n\n/**\n * \u6bd4\u8f83\u51fd\u6570\n */\nfunction defaultCompare(a, b) {\n if (a === b) {\n return 0;\n }\n return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;\n}\n\n/**\n * \u6709\u5e8f\u94fe\u8868\u7ee7\u627f\u666e\u901a\u94fe\u8868\n */\nclass SortedLinkedList extends LinkedList {\n constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {\n super(equalsFn);\n this.equalsFn = equalsFn;\n this.compareFn = compareFn;\n }\n\n /**\n * \u6dfb\u52a0\u5143\u7d20\n */\n push(element) {\n if (this.isEmpty()) {\n // \u4e3a\u7a7a\n super.push(element);\n } else {\n // \u90e8\u4f4d\u7a7a\uff0c\u6839\u636e\u4f4d\u7f6e\u6dfb\u52a0\n const index = this.getIndexNextSortedElement(element);\n super.insert(element, index);\n }\n }\n\n /**\n * \u6709\u5e8f\u63d2\u5165\u5143\u7d20\n * \u7531\u4e8e\u4e0d\u5141\u8bb8\u5728\u4efb\u4f55\u4f4d\u7f6e\u63d2\u5165\u5143\u7d20\uff0c\u8981\u7ed9 index \u53c2\u6570\u8bbe\u7f6e\u4e00\u4e2a\u9ed8\u8ba4\u503c\n * \u76f4\u63a5\u8c03\u7528 sortlist.insert(element)\u65e0\u987b\u4f20\u5165 index \u53c2\u6570\n */\n insert(element, index = 0) {\n // \u5982\u679c index \u53c2\u6570\u4f20\u5165\uff0c\u5b83\u7684\u503c\u4f1a\u88ab\u5ffd\u7565\uff0c\u56e0\u4e3a\u63d2\u5165\u5143\u7d20\u7684\u4f4d\u7f6e\u662f\u5185\u90e8\u63a7\u5236\u7684\n // \u539f\u56e0\u662f\u4e0d\u60f3\u91cd\u5199\u6574\u4e2a LinkedList \u7c7b\u7684\u65b9\u6cd5\uff0c\u6211\u4eec\u53ea\u9700\u8981\u8986\u76d6 insert \u65b9\u6cd5\u7684\u884c\u4e3a\u3002\n if (this.isEmpty()) {\n // \u5982\u679c\u6709\u5e8f\u94fe\u8868\u4e3a\u7a7a\uff0c\u76f4\u63a5\u8c03\u7528 LinkedList \u7684 insert \u65b9\u6cd5\u5e76\u4f20\u5165 0 \u4f5c\u4e3a index\n // return super.insert(element, 0);\n return super.insert(element, index === 0 ? index : 0);\n }\n // \u6709\u5e8f\u94fe\u8868\u4e0d\u4e3a\u7a7a\uff0c\u8981\u83b7\u53d6\u63d2\u5165\u5143\u7d20\u7684\u6b63\u786e\u4f4d\u7f6e\n const pos = this.getIndexNextSortedElement(element);\n // \u5e76\u6839\u636e\u4f4d\u7f6e\u5e76\u8c03\u7528 LinkedList \u7684 insert \u65b9\u6cd5\uff0c\u4f20\u5165\u8be5\u4f4d\u7f6e\u6765\u4fdd\u8bc1\u94fe\u8868\u6709\u5e8f\n return super.insert(element, pos);\n }\n\n /**\n * \u83b7\u5f97\u63d2\u5165\u5143\u7d20\u7684\u6b63\u786e\u4f4d\u7f6e\n */\n getIndexNextSortedElement(element) {\n let current = this.head;\n let i = 0;\n // \u8fed\u4ee3\u6574\u4e2a\u6709\u5e8f\u94fe\u8868\u76f4\u81f3\u627e\u5230\u9700\u8981\u63d2\u5165\u5143\u7d20\u7684\u4f4d\u7f6e\n for (; i < this.size() && current; i++) {\n // \u4f7f\u7528 compareFn \u6765\u6bd4\u8f83\u4f20\u5165\u6784\u9020\u51fd\u6570\u7684\u5143\u7d20\n const comp = this.compareFn(element, current.element);\n // \u6211\u4eec\u8981\u63d2\u5165\u6709\u5e8f\u94fe\u8868 \u7684\u5143\u7d20\u5c0f\u4e8e current \u7684\u5143\u7d20\u65f6\uff0c\u6211\u4eec\u5c31\u627e\u5230\u4e86\u63d2\u5165\u5143\u7d20\u7684\u4f4d\u7f6e\n if (comp === Compare.LESS_THAN) {\n return i;\n }\n current = current.next;\n }\n // \u6216\u662f\u8fed\u4ee3\u5b8c\u6240\u6709\u7684\u5143\u7d20\uff0c\u8fd4\u56de\u7684 index \u5c06\u662f\u6709\u5e8f\u94fe\u8868\u7684\u957f\u5ea6(\u5143\u7d20\u5c06\u88ab\u63d2\u5165\u5728\u94fe\u8868\u7684\u672b\u5c3e)\n return i;\n }\n}\n")),Object(a.b)("h2",{id:"\u521b\u5efa-stacklinkedlist-\u7c7b"},"\u521b\u5efa StackLinkedList \u7c7b"),Object(a.b)("p",null,Object(a.b)("inlineCode",{parentName:"p"},"LinkedList")," \u7c7b\u53ca\u5176\u53d8\u79cd\u4f5c\u4e3a\u5185\u90e8\u7684\u6570\u636e\u7ed3\u6784\u6765\u521b\u5efa\u5176\u4ed6\u6570\u636e\u7ed3\u6784\uff0c\u4f8b\u5982",Object(a.b)("a",Object(i.a)({parentName:"p"},{href:"/docs/interview/data-structure/stack"}),"\u6808"),"\u3001",Object(a.b)("a",Object(i.a)({parentName:"p"},{href:"/docs/interview/data-structure/queue"}),"\u961f\u5217"),"\u548c",Object(a.b)("a",Object(i.a)({parentName:"p"},{href:"/docs/interview/data-structure/deque"}),"\u53cc\u5411\u961f\u5217"),"\u3002"),Object(a.b)("p",null,"\u4f7f\u7528\u53cc\u5411\u94fe\u8868\u5b9e\u73b0\u6808\u6570\u636e\u7ed3\u6784\uff1a\u4e4b\u6240\u4ee5\u4f7f\u7528\u53cc\u5411\u94fe\u8868\u800c\u4e0d\u662f\u94fe\u8868\uff0c\u662f\u56e0\u4e3a\u5bf9\u6808\u6765\u8bf4\uff0c\u6211\u4eec\u4f1a\u5411\u94fe\u8868\u5c3e\u90e8\u6dfb\u52a0\u5143\u7d20\uff0c\u4e5f\u4f1a\u4ece\u94fe\u8868\u5c3e\u90e8\u79fb\u9664\u5143\u7d20\u3002",Object(a.b)("inlineCode",{parentName:"p"},"DoublyLinkedList")," \u7c7b\u6709\u5217\u8868\u6700\u540e\u4e00\u4e2a\u5143\u7d20\uff08",Object(a.b)("inlineCode",{parentName:"p"},"tail"),"\uff09\u7684\u5f15\u7528\uff0c\u65e0\u987b\u8fed\u4ee3\u6574\u4e2a\u94fe\u8868\u7684\u5143\u7d20\u5c31\u80fd\u83b7\u53d6\u5b83\u3002\u53cc\u5411\u94fe\u8868\u53ef\u4ee5\u76f4\u63a5\u83b7\u53d6\u5934\u5c3e\u7684\u5143\u7d20\uff0c\u51cf\u5c11\u8fc7\u7a0b\u6d88\u8017\uff0c\u5b83\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u548c\u539f\u59cb\u7684 ",Object(a.b)("inlineCode",{parentName:"p"},"Stack")," \u5b9e\u73b0\u76f8\u540c\uff0c\u4e3a O(1)\u3002"),Object(a.b)("div",{className:"admonition admonition-tip alert alert--success"},Object(a.b)("div",Object(i.a)({parentName:"div"},{className:"admonition-heading"}),Object(a.b)("h5",{parentName:"div"},Object(a.b)("span",Object(i.a)({parentName:"h5"},{className:"admonition-icon"}),Object(a.b)("svg",Object(i.a)({parentName:"span"},{xmlns:"http://www.w3.org/2000/svg",width:"12",height:"16",viewBox:"0 0 12 16"}),Object(a.b)("path",Object(i.a)({parentName:"svg"},{fillRule:"evenodd",d:"M6.5 0C3.48 0 1 2.19 1 5c0 .92.55 2.25 1 3 1.34 2.25 1.78 2.78 2 4v1h5v-1c.22-1.22.66-1.75 2-4 .45-.75 1-2.08 1-3 0-2.81-2.48-5-5.5-5zm3.64 7.48c-.25.44-.47.8-.67 1.11-.86 1.41-1.25 2.06-1.45 3.23-.02.05-.02.11-.02.17H5c0-.06 0-.13-.02-.17-.2-1.17-.59-1.83-1.45-3.23-.2-.31-.42-.67-.67-1.11C2.44 6.78 2 5.65 2 5c0-2.2 2.02-4 4.5-4 1.22 0 2.36.42 3.22 1.19C10.55 2.94 11 3.94 11 5c0 .66-.44 1.78-.86 2.48zM4 14h5c-.23 1.14-1.3 2-2.5 2s-2.27-.86-2.5-2z"})))),"tip")),Object(a.b)("div",Object(i.a)({parentName:"div"},{className:"admonition-content"}),Object(a.b)("p",{parentName:"div"},"\u4e5f\u53ef\u4ee5\u5bf9 ",Object(a.b)("inlineCode",{parentName:"p"},"LinkedList")," \u7c7b\u8fdb\u884c\u4f18\u5316\uff0c\u4fdd\u5b58\u4e00\u4e2a\u6307\u5411\u5c3e\u90e8\u5143\u7d20\u7684\u5f15\u7528\uff0c\u5e76\u4f7f\u7528\u8fd9\u4e2a\u4f18\u5316\u7248\u672c\u6765\u4ee3\u66ff ",Object(a.b)("inlineCode",{parentName:"p"},"DoublyLinkedList"),"\u3002"))),Object(a.b)("pre",null,Object(a.b)("code",Object(i.a)({parentName:"pre"},{className:"language-js"}),"class StackLinkedList {\n constructor() {\n // \u5c06\u4f7f\u7528\u53cc\u5411\u94fe\u8868\uff08DoublyLinkedList\uff09\u6765\u5b58\u50a8\u6570\u636e\n this.items = new DoublyLinkedList();\n }\n\n push(element) {\n this.items.push(element);\n }\n\n pop() {\n if (this.isEmpty()) {\n return undefined;\n }\n const result = this.items.removeAt(this.size() - 1);\n return result;\n }\n\n peek() {\n if (this.isEmpty()) {\n return undefined;\n }\n return this.items.getElementAt(this.size() - 1).element;\n }\n\n isEmpty() {\n return this.items.isEmpty();\n }\n\n size() {\n return this.items.size();\n }\n\n clear() {\n this.items.clear();\n }\n\n toString() {\n return this.items.toString();\n }\n}\n")),Object(a.b)("div",{className:"admonition admonition-info alert alert--info"},Object(a.b)("div",Object(i.a)({parentName:"div"},{className:"admonition-heading"}),Object(a.b)("h5",{parentName:"div"},Object(a.b)("span",Object(i.a)({parentName:"h5"},{className:"admonition-icon"}),Object(a.b)("svg",Object(i.a)({parentName:"span"},{xmlns:"http://www.w3.org/2000/svg",width:"14",height:"16",viewBox:"0 0 14 16"}),Object(a.b)("path",Object(i.a)({parentName:"svg"},{fillRule:"evenodd",d:"M7 2.3c3.14 0 5.7 2.56 5.7 5.7s-2.56 5.7-5.7 5.7A5.71 5.71 0 0 1 1.3 8c0-3.14 2.56-5.7 5.7-5.7zM7 1C3.14 1 0 4.14 0 8s3.14 7 7 7 7-3.14 7-7-3.14-7-7-7zm1 3H6v5h2V4zm0 6H6v2h2v-2z"})))),"info")),Object(a.b)("div",Object(i.a)({parentName:"div"},{className:"admonition-content"}),Object(a.b)("p",{parentName:"div"},"\u76f8\u540c\u7684\u903b\u8f91\uff0c\u53ef\u4ee5\u4f7f\u7528 ",Object(a.b)("inlineCode",{parentName:"p"},"DoublyLinkedList")," \u6765\u521b\u5efa ",Object(a.b)("inlineCode",{parentName:"p"},"Queue")," \u548c ",Object(a.b)("inlineCode",{parentName:"p"},"Deque")," \u7c7b\uff0c\u751a\u81f3\u4f7f\u7528 ",Object(a.b)("inlineCode",{parentName:"p"},"LinkedList")," \u7c7b\u4e5f\u662f\u53ef\u4ee5\u7684!"))),Object(a.b)("h2",{id:"\u76f8\u5173\u9898\u76ee"},"\u76f8\u5173\u9898\u76ee"),Object(a.b)("ul",null,Object(a.b)("li",{parentName:"ul"},Object(a.b)("a",Object(i.a)({parentName:"li"},{href:"https://github.com/kenve/leetcode/#%E9%93%BE%E8%A1%A8"}),"LeetCode \u94fe\u8868\u76f8\u5173\u9898\u76ee"))))}u.isMDXComponent=!0}}]);