镜像推送阿里云和私有库

当公司有新同事入职时，我们常常会让其从git或svn上拉代码下来，并在本地跑通。若公司开发阶段没有公共的服务器，那么还需要在自己电脑上装各种环境，例如mysql、redis、nginx等。如果环境的配置很复杂，或者对环境的各个版本要求很严格，那每个人都需要花大量的时间去配置，整体效率低下，耽误下班把妹时间。docker镜像是一种轻量级、可执行的独立软件包，它包含运行某个软件所需的所有内容，我们把应用程序和配置依赖打包好形成一个可交付的运行环境(包括代码、运行时需要的库、环境变量和配置文件等)，这个打包好的运行环境就是image镜像文件。所以我们完全可以把所需要用到的环境，打成一个个的镜像文件，放到服务器上。等有新同事入职，直接让他拉取这个镜像文件并运行即可，省去了繁琐的配置过程。且如果后期做服务器文件迁移，也不用再挨个去安装配置环境了，所谓一人得道全家升天，岂不美哉。1.镜像准备上面罗里吧嗦了那么多，现在就以实际案例来演示此过程。首先我们需要准备一个镜像，本文就以nginx为例。需求是我们把nginx的欢迎页改为HelloDocker，并且打包为新的镜像。这样公司每个同事拉取镜像运行后，访问的欢迎页都是HelloDocker，就无需再去手动更改了。1.1拉取镜像[root@localhost/]#dockerpullnginxUsingdefaulttag:latestlatest:Pullingfromlibrary/nginxa2abf6c4d29d:Alreadyexistsa9edb18cadd1:Pullcomplete589b7251471a:Pullcomplete186b1aaa4aa6:Pullcompleteb4df32aa5a72:Pullcompletea0bcbecc962e:PullcompleteDigest:sha256:0d17b565c37bcbd895e9d92315a05c1c3c9a29f762b011a10c54a66cd53c9b31Status:Downloadednewerimagefornginx:latestdocker.io/library/nginx:latest1.2启动nginx容器[root@localhost/]#dockerrun-p80:80-dnginxf02448ffdda35c01c618f81e8ac3d8647c24aa49c68004dcbae70ff99570b3b31.3查看实例[root@localhost~]#dockerpsCONTAINERIDIMAGECOMMANDCREATEDSTATUSPORTSNAMESf02448ffdda3nginx"/docker-entrypoint.…"2secondsagoUp1second0.0.0.0:80->80/tcp,:::80->80/tcpmusing_lovelace1.4访问主页以上步骤完成之后，访问服务器地址，发现来到了nginx的欢迎页。1.5更改nginx欢迎页#根据容器id进入容器[root@localhost~]#dockerexec-itf024/bin/bash#进入nginx的index.html目录root@f02448ffdda3:/#cd/usr/share/nginx/html/#更改文件内容root@f02448ffdda3:/usr/share/nginx/html#echo"HelloDocker">index.html1.6更改后的效果此时再访问服务器地址，发现nginx欢迎页已经变更为了HelloDocker1.7将容器打包为新的镜像按ctrl+p+q退出容器，然后进行打包：[root@localhost~]#dockercommit-a="linzichen"-m="修改nginx欢迎页"f024mynginxsha256:c58dc897ed2999a1a189ef1451714d8505df750c7382e85692a4d58cd12060bb[root@localhost~]#dockerimagesREPOSITORYTAGIMAGEIDCREATEDSIZEmynginxlatestc58dc897ed2920secondsago141MBnginxlatest605c77e624dd10monthsago141MB至此，我们打包好的镜像mynginx就已经ok了。2.镜像推送到阿里云镜像打包完成后，需要推送到远程仓库，这样别人才可以拉取到。这里选择阿里云的仓库。2.1容器镜像服务在阿里云官网，找到【产品】里的【容器镜像服务】，进入控制台后，创个【个人实例】（因为在本地测试，所以选择个人，公司的话需要花money购买企业版的）。2.2创建命名空间2.3创建镜像仓库2.4相关指令以上步骤完成后，我们可以根据操作指南里的描述，将mynginx镜像推送到阿里云仓库。[root@localhost~]#dockerimagesREPOSITORYTAGIMAGEIDCREATEDSIZEmynginxlatestc58dc897ed2920secondsago141MBnginxlatest605c77e624dd10monthsago141MB[root@localhost~]#dockerlogin--username=linzichenregistry.cn-hangzhou.aliyuncs.comPassword:WARNING!Yourpasswordwillbestoredunencryptedin/root/.docker/config.json.Configureacredentialhelpertoremovethiswarning.Seehttps://docs.docker.com/engine/reference/commandline/login/#credentials-storeLoginSucceeded#tag后面需要跟镜像的IMAGEID[root@localhost~]#dockertagc58dc897ed29registry.cn-hangzhou.aliyuncs.com/linzichen/leolinzc-rep:1.1[root@localhost~]#dockerpushregistry.cn-hangzhou.aliyuncs.com/linzichen/leolinzc-rep:1.1Thepushreferstorepository[registry.cn-hangzhou.aliyuncs.com/linzichen/leolinzc-rep]0e6258cdeb54:Pushedd874fd2bc83b:Pushed32ce5f6a5106:Pushedf1db227348d0:Pushedb8d6e692a25e:Pushede379e8aedd4d:Pushed2edcec3590a4:Pushed1.1:digest:sha256:4511d49773f3b1cc8ac350befebbf00178af7f353393f0a073497bafbaf5453dsize:17782.5验证上述操作完成之后，去阿里云镜像仓库，发现我们刚刚推送的已经成功了。2.6拉取如果要拉取仓库中的镜像，只需要根据基本信息里的【操作指南】拉取即可。[root@localhost~]#dockerpullregistry.cn-hangzhou.aliyuncs.com/linzichen/leolinzc-rep:1.11.1:Pullingfromlinzichen/leolinzc-rep[root@localhost~]#dockerimagesREPOSITORYTAGIMAGEIDCREATEDSIZEregistry.cn-hangzhou.aliyuncs.com/linzichen/leolinzc-rep1.1c58dc897ed2958minutesago141MB2.7验证新拉取的镜像[root@localhost~]#dockerrun-p80:80-dc58dc897ed2967463bd36895d7b54d31517799c5a2073cc08c93845d927b8c26967326de9903[root@localhost~]#dockerpsCONTAINERIDIMAGECOMMANDCREATEDSTATUSPORTSNAMES67463bd36895c58dc897ed29"/docker-entrypoint.…"4secondsagoUp2seconds0.0.0.0:80->80/tcp,:::80->80/tcpelastic_curran3.镜像推送到私有库有些时候我们不希望代码放到外网，想类似于gitlab似的在本地服务器创建私有仓库。所以此时我们需要在自己服务器搭建一个私有仓库。##3.1下载镜像仓库[root@localhost~]#dockerpullregistryUsingdefaulttag:latestlatest:Pullingfromlibrary/registry79e9f2f55bf5:Pullcomplete0d96da54f60b:Pullcomplete5b27040df4a2:Pullcompletee2ead8259a04:Pullcomplete3790aef225b9:PullcompleteDigest:sha256:169211e20e2f2d5d115674681eb79d21a217b296b43374b8e39f97fcf866b375Status:Downloadednewerimageforregistry:latestdocker.io/library/registry:latest3.2运行私有库Registry就是相当于在本地服务器上搭建了个dockerhub。[root@localhost~]#dockerrun-d-p5000:5000-v/usr/local/registry/:/tmp/registry--privileged=trueregistry59e4ba84a1bd4102ff4c359d6833a9706f173016facbb89af3805d2be96a983a[root@localhost~]#dockerpsCONTAINERIDIMAGECOMMANDCREATEDSTATUSPORTSNAMES59e4ba84a1bdregistry"/entrypoint.sh/etc…"AboutaminuteagoUpAboutaminute0.0.0.0:5000->5000/tcp,:::5000->5000/tcphappy_bardeen3.3验证本地私服仓库[root@localhost~]#curl-XGEThttp://192.168.2.123:5000/v2/_catalog{"repositories":[]}192.168.2.123是自己服务器的地址，repositories是空的，说明还未向仓库中添加任何镜像。3.4修改镜像命名我们需要把要推送的镜像，重命名为符合私服规范的。dockertag镜像:TagHost:Port/Repository:Tag[root@localhost~]#dockerimagesREPOSITORYTAGIMAGEIDCREATEDSIZEmynginxlatest5db4431fb6836secondsago141MB[root@localhost~]#dockertagmynginx:latest192.168.2.123:5000/mynginx:latest[root@localhost~]#dockerimagesREPOSITORYTAGIMAGEIDCREATEDSIZEmynginxlatest5db4431fb6836minutesago141MB192.168.2.123:5000/mynginxlatest5db4431fb6836minutesago141MB3.5修改配置文件支持http刚学docker时，我们都会把docker的镜像仓库地址改为阿里云的，目的是为了加快镜像的拉取速度。所在在/etc/docker中会存在daemon.json文件：[root@localhost/]#cat/etc/docker/daemon.json{"registry-mirrors":["https://lbws5pbg.mirror.aliyuncs.com"]}vim编辑文件，配置docker允许支持以http方式推送镜像。添加"insecure-registries":["192.168.2.123:5000"]，ip为自己docker服务器的ip。[root@localhost/]#cat/etc/docker/daemon.json{"registry-mirrors":["https://lbws5pbg.mirror.aliyuncs.com"],"insecure-registries":["192.168.2.123:5000"]}3.6推送镜像到私服[root@localhost/]#dockerimagesREPOSITORYTAGIMAGEIDCREATEDSIZE192.168.2.123:5000/mynginxlatest5db4431fb68318minutesago141MB[root@localhost/]#dockerpush192.168.2.123:5000/mynginx:latestThepushreferstorepository[192.168.2.123:5000/mynginx]3cbd1830e9c0:Pushedd874fd2bc83b:Pushed32ce5f6a5106:Pushedf1db227348d0:Pushedb8d6e692a25e:Pushede379e8aedd4d:Pushed2edcec3590a4:Pushedlatest:digest:sha256:ff4733639d1731096c730b222d9dc471f06e83efa3fb6167a6a2c2eb2e5ec718size:1778如果推送时报错，例如：[root@localhost/]#dockerpush192.168.2.123:5000/mynginx:latestThepushreferstorepository[192.168.2.123:5000/mynginx]Get"https://192.168.2.123:5000/v2/":http:servergaveHTTPresponsetoHTTPSclient则需要重启下docker，并且重新运行registory的镜像：#重启docker[root@localhost/]#systemctldaemon-reload[root@localhost/]#systemctlrestartdocker#运行registory镜像[root@localhost/]#dockerrun-d-p5000:5000-v/usr/local/registry/:/tmp/registry--privileged=trueregistry87c6adc3360f8498ae0483f739636cdf6329ad712e58550f2af59516316af6243.7验证推送是否成功#已经存在mynginx，说明推送成功[root@localhost/]#curl-XGEThttp://192.168.2.123:5000/v2/_catalog{"repositories":["mynginx"]}3.8拉取私服镜像#拉取之前[root@localhost/]#dockerimagesREPOSITORYTAGIMAGEIDCREATEDSIZEmynginxlatest5db4431fb68328minutesago141MBnginxlatest605c77e624dd10monthsago141MBregistrylatestb8604a3fe85412monthsago26.2MB[root@localhost/]#dockerpull192.168.2.123:5000/mynginx:latestlatest:PullingfrommynginxDigest:sha256:ff4733639d1731096c730b222d9dc471f06e83efa3fb6167a6a2c2eb2e5ec718Status:Downloadednewerimagefor192.168.2.123:5000/mynginx:latest192.168.2.123:5000/mynginx:latest#拉取之后[root@localhost/]#dockerimagesREPOSITORYTAGIMAGEIDCREATEDSIZE192.168.2.123:5000/mynginxlatest5db4431fb68329minutesago141MBmynginxlatest5db4431fb68329minutesago141MBnginxlatest605c77e624dd10monthsago141MBregistrylatestb8604a3fe85412monthsago26.2MB3.9访问私服的nginx[root@localhost/]#dockerrun-p80:80-d192.168.2.123:5000/mynginx9bef626b40946e8369b3f4af7052b4e19896cff184a0292029e6410027089526[root@localhost/]#dockerpsCONTAINERIDIMAGECOMMANDCREATEDSTATUSPORTSNAMES9bef626b4094192.168.2.123:5000/mynginx"/docker-entrypoint.…"4secondsagoUp1second0.0.0.0:80->80/tcp,:::80->80/tcpgoofy_babbage87c6adc3360fregistry"/entrypoint.sh/etc…"10minutesagoUp10minutes0.0.0.0:5000->5000/tcp,:::5000->5000/tcpquizzical_lumiere··

线性表之链表

在顺序表中查询效率很高，时间复杂度是O(1)，但是其增删的效率是比较低的，因为每一次增删操作都需要伴随着大量元素的移动。如果我们需要经常线性表中的元素做增删操作，可以采用链表结构。链表简介链表时一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能表示为数据元素的逻辑结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表由一系列的结点（每个元素被称为一个结点）组成，结点可以在运行时动态生成。根据上图，元素11的指针指向元素13，如果我们要在11和13中插入一个元素22，那我们只需要生成一个22元素，将11的指针指向22，将22的指针指向13，以此就完成了链表中插入的动作。同样的，删除也是同理，只需要修改关联元素之间的指针，就可以实现元素的动态插入和删除。结点API设计如何使用链表，根据面向对象思想，我们可以设计一个类来描述结点这个事物，用一个属性描述此结点存储的元素，用另一个属性描述此结点的下一个结点.类名Node构造方法Node(Tt,Nodenext)：创建Node对象成员变量Tt：存储数据Nodenext：指向的下一个结点单向链表单向链表是链表的一种，它由多个结点组成，每个结点都有一个数据域和一个指针域,分别用来存储数据和指向其后继的结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。API设计类名LinkList构造方法LinkList(intlength)：创建长度为length的LinkList对象成员方法1.publicvoidclear()：空置线性表2.publicbooleanisEmpty()：判断线性表是否为空3.publicintlength()：获取线性表中元素个数4.publicTget(inti)：获取第i个元素的值5.publicvoidinsert(Tt,inti)：在线性表中第i个元素之前插入t元素6.publicvoidinsert(Tt)：向线性表中添加一个元素7.publicTremove(inti)：删除并返回线性表中第i个数据元素8.publicintindexOf(Tt)：返回线性表中t元素首次出现的位置，若不存在返回-1成员内部类privateclassNode：结点类成员变量1.privateNodehead：存储头结点2.privateintN：链表的长度代码实现/***单向链表*@param<T>*/publicclassLinkList<T>{//记录头结点privateNodehead;//记录链表长度privateintN;/***结点对象*/privateclassNode{//当前结点数据Tt;//指向的下一个结点Nodenext;publicNode(Tt,Nodenext){this.t=t;this.next=next;}}publicLinkList(){//初始化链表时，存在一个头结点，但不存储任何数据，//next指向第一个真实数据结点this.head=newNode(null,null);this.N=0;}/***空置线性表*/publicvoidclear(){head.next=null;N=0;}/***判断线性表是否为空*@return*/publicbooleanisEmpty(){returnN==0;}/***获取元素个数*@return*/publicintlength(){returnN;}/***获取线性表中下标为i的元素*@parami*@return*/publicTget(inti){//从头结点开始遍历Nodenode=head;//i-1结点的next元素就是i处的结点for(intindex=0;index<i;++index){node=node.next;}returnnode.t;}/***向线性表中插入元素*@paramt*/publicvoidinsert(Tt){Nodenode=head;//添加到链表的最后一个元素，所以需要找到最后一个结点//让最后一个结点的next=添加的元素即可//最后一个元素的判定条件是next为空while(node.next!=null){node=node.next;}NodenewNode=newNode(t,null);node.next=newNode;N+=1;}/***向线性表中i位置插入元素*1、找到原i处的前一个结点：pre*@paramt*@parami*/publicvoidinsert(Tt,inti){//1、找到原i处的前一个结点：preNodepre=head;for(intindex=0;index<i;++index){pre=pre.next;}//2、获取原i处的结点NodeoldINode=pre.next;//3、生成新的结点，并且next指向原i处的结点NodenewNode=newNode(t,oldINode);//4、让i-1处的结点next指向新的结点pre.next=newNode;N+=1;}/***删除并返回线性表中第i个元素*就是让i-1处元素的next指向i+1位置的元素*@parami*@return*/publicTremove(inti){//1、获取i-1处的结点Nodepre=head;for(intindex=0;index<i;++index){pre=head.next;}//2、获取i结点NodeiNode=pre.next;//3.让i-1的next指向i的nextpre.next=iNode.next;N-=1;returniNode.t;}/***返回线性表中t元素首次出现的位置*若没有，返回-1*@paramt*@return*/publicintindexOf(Tt){Nodenode=head;for(inti=0;node.next!=null;++i){node=node.next;if(node.t.equals(t)){returni;}}return-1;}}链表反转现有一个链表结构如下：head->1->2->3->4我们希望反转后的结构如下：head->4->3->2->1方案一：遍历思路：由上图可知，我们需要遍历每一个结点，然后将当前结点指向其前驱结点，当遍历完成后，需要将head头结点指向遍历的最后一个结点，即可实现反转。步骤：1).需要定义两个变量pre和next，分别记录当前正在遍历结点的前驱元素和后继元素，初始值为null。2).从第一个结点（head.next）开始遍历，条件为当前遍历允许不为null。3).将当前结点的next赋值给next。4).将当前结点的next重新指向pre。5).准备开始为下轮遍历构建条件，所以需要将当前结点赋值给pre，以作为下次遍历结点的前驱元素。6).把next元素赋值给当前元素。7).循环结束后，head指向最后遍历的结点。代码：/***遍历反转*/publicvoidreverse(){//前驱元素Nodepre=null;//当前元素Nodecurrent=head.next;//后继元素Nodenext=null;while(current!=null){//记录结点的下个元素next=current.next;//让本结点指向上一个结点current.next=pre;//让上一个结点变成本结点pre=current;//让本结点变成下一个结点，再去循环current=next;}//循环结束后，head指向最后的元素head.next=pre;}方案二：递归思路步骤：1).调用reverse(Nodecurrent)方法反转每一个结点，从a结点开始。2).如果发现current还有下一个结点，则递归调用reverse(current.next)对下一个结点先进行反转。3).最终递归的出口是d结点，因为它没有后继元素了，所以此时需要让head指向元素d结点。4).让递归开始返回。代码：/***递归调用*/publicvoidreverse(){if(isEmpty()){return;}Nodenode=reverse(head.next);System.out.println("最后的结点："+node.t);}publicNodereverse(Nodecurrent){if(current.next!=null){//开始压栈，出栈的时候，oldNext一定是d元素//递归3次：oldNext为d，current为c//递归2次，oldNext为c，current为b//递归1次，oldNext为b，current为a//调用方法，返回的current为aNodeoldNext=reverse(current.next);oldNext.next=current;current.next=null;returncurrent;}else{head.next=current;returncurrent;}}快慢指针快慢指针指的是定义两个指针，这两个指针的移动速度一块一慢，以此来制造出自己想要的差值，这个差值可以让我们找到链表上相应的结点。一般情况下，快指针的移动步长为慢指针的两倍。中间值问题如果要查找链表中的中间值，我们就可以用快慢指针。利用快慢指针，可以把链表看成一个跑到，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以此来达到找到中间结点的目的。如下图，最开始slow和fast指针都指向链表的第一个结点，然后slow每次移动一个指针，fast每次移动两个指针。/***获取中间值*@return*/publicTgetMid(){Nodefast=head.next;Nodeslow=head.next;while(fast!=null&&fast.next!=null){//变化fast和slow的值fast=fast.next.next;slow=slow.next;}returnslow.t;}单向链表是否有环使用快慢指针的思想，还是把链表比作一条跑道，链表中有环，那么这条跑道就是一条圆环跑道，在一条圆环跑道中，两个人有速度差，那么迟早两个人会相遇，只要相遇那么就说明有环。/***链表是否有环*@return*/publicbooleanisCircle(){Nodefast=head.next;Nodeslow=head.next;while(fast!=null&&fast.next!=null){//变化fast和slow的值fast=fast.next.next;slow=slow.next;//if(fast.compareTo(slow)==0){if(fast.equals(slow)){returntrue;}}returnfalse;}单向链表入口问题当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样为1，则慢指针与“新"指针相遇的地方就是环的入口。/***查找有环链表中环的入口结点*@return环的入口结点*/publicstaticNodegetEntrance(){//定义快慢指针Node<String>fast=head.next;Node<String>slow=head.next;Node<String>temp=null;//遍历链表，先找到环(快慢指针相遇),准备一个临时指针，指向链表的首结点，继续遍历，直到慢指针和临时指针相遇，那么相遇时所指向的结点就是环的入口while(fast!=null&&fast.next!=null){//变换快慢指针fast=fast.next.next;slow=slow.next;//判断快慢指针是否相遇if(fast.equals(slow)){temp=first;continue;}//让临时结点变换if(temp!=null){temp=temp.next;//判断临时指针是否和慢指针相遇if(temp.equals(slow)){break;}}}returntemp;}//结点类privatestaticclassNode<T>{//存储数据Titem;//下一个结点Nodenext;publicNode(Titem,Nodenext){this.item=item;this.next=next;}}循环链表循环链表，顾名思义，链表整体要形成一个圆环状。在单向链表中，最后一个结点的指针为null，不指向任何结点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个结点的指针指向头结点即可。约瑟夫问题问题描述︰传说有这样一个故事，在罗马人占领乔塔帕特后，39个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，从而逃过了这场死亡游戏。问题转换︰41个人坐一圈，第一个人编号为1，第二个人编号为2，第n个人编号为n。1.编号为1的人开始从1报数，依次向后，报数为3的那个人退出圈;⒉.自退出那个人开始的下一个人再次从1开始报数，以此类推;3.求出最后退出的那个人的编号。图示：代码实现：publicclassJosephTest{publicstaticvoidmain(String[]args){//解决约瑟夫问题//1.构建循环链表，包含41个结点，分别存储1~41之间的值//用来就首结点Node<Integer>first=null;//用来记录前一个结点Node<Integer>pre=null;for(inti=1;i<=41;i++){//如果是第一个结点if(i==1){first=newNode<>(i,null);pre=first;continue;}//如果不是第一个结点Node<Integer>newNode=newNode<>(i,null);pre.next=newNode;pre=newNode;//如果是最后一个结点，那么需要让最后一个结点的下一个结点变为first,变为循环链表了if(i==41){pre.next=first;}}//2.需要count计数器，模拟报数intcount=0;//3.遍历循环链表//记录每次遍历拿到的结点，默认从首结点开始Node<Integer>n=first;//记录当前结点的上一个结点Node<Integer>before=null;while(n!=n.next){//模拟报数count++;//判断当前报数是不是为3if(count==3){//如果是3，则把当前结点删除调用，打印当前结点，重置count=0，让当前结点n后移before.next=n.next;System.out.print(n.item+",");count=0;n=n.next;}else{//如果不是3，让before变为当前结点，让当前结点后移；before=n;n=n.next;}}//打印最后一个元素System.out.println(n.item);}//结点类privatestaticclassNode<T>{//存储数据Titem;//下一个结点Nodenext;publicNode(Titem,Nodenext){this.item=item;this.next=next;}}}双向链表双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。实现双向链表的API及实现方式跟单向链表很像，就多维护了一个结点而已，这里不过多的去聊，直接贴上代码：importjava.util.Iterator;publicclassTowWayLinkList<T>implementsIterable<T>{//首结点privateNodehead;//最后一个结点privateNodelast;//链表的长度privateintN;//结点类privateclassNode{publicNode(Titem,Nodepre,Nodenext){this.item=item;this.pre=pre;this.next=next;}//存储数据publicTitem;//指向上一个结点publicNodepre;//指向下一个结点publicNodenext;}publicTowWayLinkList(){//初始化头结点和尾结点this.head=newNode(null,null,null);this.last=null;//初始化元素个数this.N=0;}//清空链表publicvoidclear(){this.head.next=null;this.head.pre=null;this.head.item=null;this.last=null;this.N=0;}//获取链表长度publicintlength(){returnN;}//判断链表是否为空publicbooleanisEmpty(){returnN==0;}//获取第一个元素publicTgetFirst(){if(isEmpty()){returnnull;}returnhead.next.item;}//获取最后一个元素publicTgetLast(){if(isEmpty()){returnnull;}returnlast.item;}//插入元素tpublicvoidinsert(Tt){if(isEmpty()){//如果链表为空：//创建新的结点NodenewNode=newNode(t,head,null);//让新结点称为尾结点last=newNode;//让头结点指向尾结点head.next=last;}else{//如果链表不为空NodeoldLast=last;//创建新的结点NodenewNode=newNode(t,oldLast,null);//让当前的尾结点指向新结点oldLast.next=newNode;//让新结点称为尾结点last=newNode;}//元素个数+1N++;}//向指定位置i处插入元素tpublicvoidinsert(inti,Tt){//找到i位置的前一个结点Nodepre=head;for(intindex=0;index<i;index++){pre=pre.next;}//找到i位置的结点Nodecurr=pre.next;//创建新结点NodenewNode=newNode(t,pre,curr);//让i位置的前一个结点的下一个结点变为新结点pre.next=newNode;//让i位置的前一个结点变为新结点curr.pre=newNode;//元素个数+1N++;}//获取指定位置i处的元素publicTget(inti){Noden=head.next;for(intindex=0;index<i;index++){n=n.next;}returnn.item;}//找到元素t在链表中第一次出现的位置publicintindexOf(Tt){Noden=head;for(inti=0;n.next!=null;i++){n=n.next;if(n.next.equals(t)){returni;}}return-1;}//删除位置i处的元素，并返回该元素publicTremove(inti){//找到i位置的前一个结点Nodepre=head;for(intindex=0;index<i;index++){pre=pre.next;}//找到i位置的结点Nodecurr=pre.next;//找到i位置的下一个结点NodenextNode=curr.next;//让i位置的前一个结点的下一个结点变为i位置的下一个结点pre.next=nextNode;//让i位置的下一个结点的上一个结点变为i位置的前一个结点nextNode.pre=pre;//元素的个数-1N--;returncurr.item;}@OverridepublicIterator<T>iterator(){returnnewTIterator();}privateclassTIteratorimplementsIterator{privateNoden;publicTIterator(){this.n=head;}@OverridepublicbooleanhasNext(){returnn.next!=null;}@OverridepublicObjectnext(){n=n.next;returnn.item;}}}链表复杂度分析ge(inti):每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为O(n)；insert(inti,Tt);每一次插入，需要先找到位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n);remove(inti)每一次移除，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)；相比较顺序表，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的，它不需要预先指定存储空间大小，或者在存储过程中涉及到扩容等操作..同时它并没有涉及的元素的交换。相比较顺序表，链表的查询操作性能会比较低。因此，如果我们的程序中查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表。