前言本文面向编程零基础小白用生活化案例通俗讲解 Java 中动态数组与链表的核心概念、组成要素与完整实操流程手把手演示完整可运行代码示例。一、核心概念数据结构“数据结构是计算机存储、组织数据的方式。”官方是这么定义数据结构的。当有大量同类数据需要保存时最先考虑的是使用数据结构。常用的数据结构基本上是数组、链表或者以数组、链表为基础构建的数据结构功能类。如哈希表、红黑树等“精心选择的数据结构可以带来更高的运行或存储效率。”在决定使用数据结构时根据使用场景的不同使用不同的数据结构可以很大程度上提升效率、节省内存。动态数组数组就像一组连续的柜子只能存同类的数据每格柜子有一个编号也就是“下标”。在使用数组时存和取都需要通过下标。存数据时实际上就是为下标处的元素赋值取数据就是反过来将一个变量赋值为数组下标位置的数据。但是数组一旦创建后大小就固定了一开始填的是多少就是多少无法直接改变何谈“动态”有的时候没必要执着于直接改变只要效果是我们想要的方法具体是什么样的也没什么关系。要实现数组的扩容可以通过新建一个比原来大些的数组然后把原来数组每个下标的内容赋值到新数组对应的下标里再把新数组指向旧数组的对象就实现了“扩容”的效果。数组的机制使得它在面对多次随机取数据时游刃有余直接通过下标找到对应的数据时间复杂度是 O(1)。但它的机制也使得它在面对扩容需要时必须使用比较间接的方法没办法直接扩容需要通过新建数组后复制的方式时间复杂度是 O(n)有多少数据 n 就是多少。链表链表是由一个一个节点构成的每个节点会存几个数据。如果是一个基础的单向链表每个节点会存两个数据一个是需要储存的数据本身另一个是指向下一个节点的“地址”也就是指针。如果没有指向下一个节点的指针链表也无法构成正是每一个节点都指向了它的下一个节点下一个节点又指向下一个链表就像锁链一样串了起来。双向链表则是在原本一个数据加一个指针的基础上升级成为了一个数据加两个指针指向下一个节点的指针与指向上一个节点的指针。如果要为链表后面添加新的节点只需要在创建节点后将最后一个节点的指针指向新创建的节点就行。如果是想插入在两个节点之间就把上一个节点的指针指向它再让它的指针指向下一个节点就可以了。同样的想要删除最后一个节点的时候只需要让倒数第二个节点的指针指向 null 就可以了想要删除中间的某个节点时也只需要让它的上一个节点指向它的下一个节点就行。需要取数据时链表并不存在像数组那样有一个下标指哪就访问哪里而是需要从头节点开始顺着指针一直遍历到指定的位置。一个单向链表有点像俄罗斯套娃那样必须要一层一层走到指定的位置才能访问到需要的数据。如果是双向链表不止可以从头节点开始遍历也可以从尾节点开始遍历。如果要访问的节点离头节点近那就从头节点开始如果要访问的节点离尾节点近那就从尾节点开始。可以在一定程度上加快访问数据的速度。链表的机制使得它非常适合应对需要频繁添加或删减数据的情况每次添加与删减只需要更改节点指针的指向就行时间复杂度是 O(1)。但链表在访问数据时因为无法像数组那样直接用下标访问必须从头节点或尾节点一个个遍历到指定位置时间复杂度是 O(n)遍历经过几个节点 n 就是多少。二、动态数组、链表的组成要素一、动态数组末尾添加方法在添加之前会先判断数组是否需要扩容如果需要扩容就新建一个数组大小是原数组的2倍大再将原数组数据遍历赋值到新数组的对应位置中最后让旧数组对象指向新数组。因为每次扩容都使数组大小翻倍所以数组并非每一个位置都是有效数据于是需要额外定义一个变量 size 来记录有效数据的长度避免调用到无效数据。同时size 变量也是判断是否需要扩容的关键。调用方法时需要一个参数 data将数据保存在最最后一个有效数据的后面并使 size 增加。插入添加方法这个方法需要两个参数一个是数据本身data另一个是插入添加的位置index。同样先判断是否需要扩容随后从后往前遍历数组将所有数据往后挪一位直到遍历到 index 的位置将需要插入的数据赋值到该位置最后使 size 增加。删除并返回数据方法这个方法需要一个参数 index代表需要删除的数据的位置。它会先保存位置的数据在一个变量里接着从 index 开始往后遍历将所有数据往前挪一位这样就将 index 位置的数据覆盖掉了达成了删除的效果。接着再返回保存了删除位置的数据的变量的数据最后使 size 减少。删除第一个匹配数据方法这个就简单了遍历数组一旦遇到匹配数据就对该数据调用刚刚写的删除方法再返回结束就行。删除所有匹配数据方法一样遍历数组遇到匹配数据后调用删除方法但不返回继续遍历直到删除所有匹配数据。获取指定位置数据方法这个方法需要一个参数 index返回 index 位置的数据。获取数据数量方法返回 size。二、链表内部节点类这个内部类包含几个变量和一个构造方法分别是指向下一个的指针next、指向上一个的指针prev、数据本身data和构造方法 Node用来传参数给 data 变量。末尾添加方法这个方法需要一个参数 data也就是要存的数据。这个方法会先判断链表有没有头节点如果有就新建一个节点类的对象新节点成为新的尾节点并让曾经的尾节点的 next 指针指向它也让它的 perv 指针指向曾经的尾节点它的 next 指向 null也就是到头了没有下一个节点了。如果不存在头节点就让它成为头和尾next 和 prev 都指向 null因为它成为了链表的第一个节点但也是最后一个节点。最后使 size 增加。插入添加方法这个方法需要两个参数分别是插入位置和数据本身。首先会和末尾添加一样判断有没有头节点不过我这里用的是判断链表长度是否为0效果一样的。如果链表长度不是0那就让插入位置的那个节点的 prev 指向它并让它的 next 指向插入位置的节点。同时也将插入位置的上一个节点的 next 指向它它的 prev 指向上一个节点。最后使 size 增加。获取指定位置数据方法这个方法需要一个参数要访问的位置。我写的是一个双向链表所以可以先判断这个位置是离头节点近一些还是离尾节点近些然后选择更近的那一边开始遍历直到找到指定位置并返回数据。删除并返回指定位置数据方法这个方法需要一个参数要删除的位置。同样通过遍历找到指定位置让它上一个节点的 next 指针指向它的下一个节点让它的下一个节点的 prev 指针指向它的上一个节点于是就不再有任何方法访问到它了返回它的值然后使 size 减少。删除第一个匹配数据方法这个方法需要一个参数目标数据。方法会遍历链表找到匹配数据调用前面写好的删除方法然后返回。删除所有匹配数据方法和上一个一样输入一个目标数据遍历数组调用删除方法但在全部删除干净之前不会返回。链表翻转方法让头结点变成尾节点让每一个节点的 next 指针变成 prev 指针。首先从头开始遍历链表每次让两个指针往下一个节点遍历同时用两个变量分别保存这两个指针再把 next 和 prev 的指向对调然后通过读取对调前保存的指针前往下一个节点然后做同样的事留后路、对调、前往下一个……最后对调头节点和尾节点。获取链表长度方法返回 size。三、完整实操案例动态数组importjava.util.ArrayList;publicclassArrayE{privateObject[]dataarr;privatestaticintlen10;privateintsize0;//自定义动态数组长度publicArray(intlen){dataarrnewObject[len];}//设置默认长度publicArray(){this(len);}//末尾添加publicvoidadd(Edata){//判断是否需要扩容if(sizedataarr.length){Object[]newArrnewObject[dataarr.length*2];for(inti0;idataarr.length;i){newArr[i]dataarr[i];}dataarrnewArr;}dataarr[size]data;size;}//插入添加publicvoidadd(intindex,Edata){if(indexsize||index0){return;}if(sizedataarr.length){Object[]newArrnewObject[dataarr.length*2];for(inti0;isize;i){newArr[i]dataarr[i];}dataarrnewArr;}for(intisize-1;iindex;i--){dataarr[i1]dataarr[i];}dataarr[index]data;size;}//删除指定位置然后返回它publicEremove(intindex){if(index0||indexsize){returnnull;}Eremoved(E)dataarr[index];for(intiindex1;isize;i){dataarr[i-1]dataarr[i];}size--;returnremoved;}//删除匹配数据publicbooleanremoves(Objectdata){for(inti0;isize;i){if(dataarr[i].equals(data)){remove(i);returntrue;}}returnfalse;}//删除所有匹配数据publicbooleanremoveAll(Objectdata){booleanremovedfalse;for(intisize-1;i0;i--){if(dataarr[i].equals(data)){remove(i);removedtrue;}}returnremoved;}//获取指定位置数据publicEget(intindex){if(indexsize){returnnull;}Objectobjdataarr[index];Eresult(E)obj;returnresult;}//获取数据数量publicintsize(){returnsize;}//用时测试与官方动态数组对比publicstaticvoidmain(String[]args){//我的动态数组ArrayIntegerlistnewArray();longstartSystem.currentTimeMillis();for(inti0;i100000;i){list.add(i);}longendSystem.currentTimeMillis();System.out.println(耗时(end-start));//官方动态数组ArrayListIntegerarrayListnewArrayList();startSystem.currentTimeMillis();for(inti0;i100000;i){arrayList.add(i);}endSystem.currentTimeMillis();System.out.println(耗时(end-start));}}测试结果单位毫秒耗时8 //我的数组 耗时3 //官方数组链表publicclassLinkedE{privatestaticclassNodeE{publicEdata;publicNodeEnext;publicNodeEprev;publicNode(Edata){this.datadata;}}privateNodeEfirst;privateNodeElast;privateintsize;//末尾添加publicvoidadd(Edata){NodeEnewNodenewNode(data);if(firstnull){firstnewNode;lastnewNode;first.prevlast;last.nextfirst;}else{last.nextnewNode;newNode.prevlast;newNode.nextfirst;first.prevnewNode;lastnewNode;}size;}//获取指定位置数据publicEget(intindex){if(index0||indexsize){returnnull;}NodeEcurr;if(indexsize/2){currfirst;for(inti0;iindex;i){currcurr.next;if(currnull){returnnull;}}}else{currlast;for(intisize-1;iindex;i--){currcurr.prev;if(currnull){returnnull;}}}returncurr.data;}//插入添加publicvoidadd(intindex,Edata){if(index0||indexsize){return;}NodeEnewNodenewNode(data);NodeEprevnull;NodeEcurrfirst;if(size0){firstnewNode;lastnewNode;first.prevlast;last.nextfirst;size;return;}for(inti0;iindex;i){prevcurr;currcurr.next;}if(prevnull){newNode.prevlast;newNode.nextfirst;first.prevnewNode;last.nextnewNode;firstnewNode;}else{if(currnull){newNode.nextfirst;}else{newNode.nextcurr;curr.prevnewNode;}newNode.prevprev;prev.nextnewNode;if(indexsize){first.prevnewNode;lastnewNode;}}size;}//删除并返回指定位置publicEremove(intindex){if(index0||indexsize){returnnull;}NodeEcurrfirst;for(inti0;iindex;i){currcurr.next;}NodeEprevcurr.prev;NodeEnextcurr.next;if(prevnull){firstnext;last.nextfirst;}else{prev.nextnext;}if(nextnull){lastprev;first.prevlast;}else{next.prevprev;}curr.prevnull;curr.nextnull;size--;returncurr.data;}//删除匹配数据publicbooleanremoves(Objectdata){NodeEcurrfirst;intindex0;while(curr!null){if(curr.data.equals(data)){remove(index);returntrue;}currcurr.next;index;}returnfalse;}//删除所有匹配数据publicbooleanremoveall(Objectdata){booleanremovedfalse;NodeEcurrfirst;intindex0;while(curr!null){if(curr.data.equals(data)){remove(index);removedtrue;index--;}currcurr.next;index;}returnremoved;}//链表翻转publicvoidreversal(){if(size0){return;}NodeEcurrfirst;for(inti0;isize;i){NodeEtempcurr.next;curr.nextcurr.prev;curr.prevtemp;currtemp;}NodeEtempfirst;firstlast;lasttemp;first.prevlast;last.nextfirst;}//获取链表长度publicintgetSize(){returnsize;}publicstaticvoidmain(String[]args){LinkedIntegerlinnewLinked();lin.add(1);lin.add(2);lin.add(3);intsizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();lin.reversal();sizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();lin.add(3,5);sizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();lin.add(3,8);sizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();lin.add(4,3);sizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();lin.removeall(3);sizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();}}四、个人收获总结这次学习了链表没想到这个东西真的有点抽象。数组倒是很好理解用起来也挺顺手但刚接触链表时我对“指针”这个概念一只是似懂非懂一知半解大概知道是怎么用但就很难去理解它的本质和原理。但用多了之后慢慢地就越来越懂了最开始我还在想“为什么要用这种这么抽象和麻烦的东西”不过链接不断地加深渐渐地就顺手了起来。学习链表让我对数据结构的理解加深了不少以及指针这个概念本质上就是存了下一个节点的对象有点像地址。我一开始搞不懂为什么写了 curr.next 就可以遍历到下一个节点实际上是 curr 访问了当前节点的 next 变量而这个变量里面存了下一个节点的对象就能“顺藤摸瓜”一样的找过去了 Java数据结构基础笔记：动态数组、链表
前言本文面向编程零基础小白用生活化案例通俗讲解 Java 中动态数组与链表的核心概念、组成要素与完整实操流程手把手演示完整可运行代码示例。一、核心概念数据结构“数据结构是计算机存储、组织数据的方式。”官方是这么定义数据结构的。当有大量同类数据需要保存时最先考虑的是使用数据结构。常用的数据结构基本上是数组、链表或者以数组、链表为基础构建的数据结构功能类。如哈希表、红黑树等“精心选择的数据结构可以带来更高的运行或存储效率。”在决定使用数据结构时根据使用场景的不同使用不同的数据结构可以很大程度上提升效率、节省内存。动态数组数组就像一组连续的柜子只能存同类的数据每格柜子有一个编号也就是“下标”。在使用数组时存和取都需要通过下标。存数据时实际上就是为下标处的元素赋值取数据就是反过来将一个变量赋值为数组下标位置的数据。但是数组一旦创建后大小就固定了一开始填的是多少就是多少无法直接改变何谈“动态”有的时候没必要执着于直接改变只要效果是我们想要的方法具体是什么样的也没什么关系。要实现数组的扩容可以通过新建一个比原来大些的数组然后把原来数组每个下标的内容赋值到新数组对应的下标里再把新数组指向旧数组的对象就实现了“扩容”的效果。数组的机制使得它在面对多次随机取数据时游刃有余直接通过下标找到对应的数据时间复杂度是 O(1)。但它的机制也使得它在面对扩容需要时必须使用比较间接的方法没办法直接扩容需要通过新建数组后复制的方式时间复杂度是 O(n)有多少数据 n 就是多少。链表链表是由一个一个节点构成的每个节点会存几个数据。如果是一个基础的单向链表每个节点会存两个数据一个是需要储存的数据本身另一个是指向下一个节点的“地址”也就是指针。如果没有指向下一个节点的指针链表也无法构成正是每一个节点都指向了它的下一个节点下一个节点又指向下一个链表就像锁链一样串了起来。双向链表则是在原本一个数据加一个指针的基础上升级成为了一个数据加两个指针指向下一个节点的指针与指向上一个节点的指针。如果要为链表后面添加新的节点只需要在创建节点后将最后一个节点的指针指向新创建的节点就行。如果是想插入在两个节点之间就把上一个节点的指针指向它再让它的指针指向下一个节点就可以了。同样的想要删除最后一个节点的时候只需要让倒数第二个节点的指针指向 null 就可以了想要删除中间的某个节点时也只需要让它的上一个节点指向它的下一个节点就行。需要取数据时链表并不存在像数组那样有一个下标指哪就访问哪里而是需要从头节点开始顺着指针一直遍历到指定的位置。一个单向链表有点像俄罗斯套娃那样必须要一层一层走到指定的位置才能访问到需要的数据。如果是双向链表不止可以从头节点开始遍历也可以从尾节点开始遍历。如果要访问的节点离头节点近那就从头节点开始如果要访问的节点离尾节点近那就从尾节点开始。可以在一定程度上加快访问数据的速度。链表的机制使得它非常适合应对需要频繁添加或删减数据的情况每次添加与删减只需要更改节点指针的指向就行时间复杂度是 O(1)。但链表在访问数据时因为无法像数组那样直接用下标访问必须从头节点或尾节点一个个遍历到指定位置时间复杂度是 O(n)遍历经过几个节点 n 就是多少。二、动态数组、链表的组成要素一、动态数组末尾添加方法在添加之前会先判断数组是否需要扩容如果需要扩容就新建一个数组大小是原数组的2倍大再将原数组数据遍历赋值到新数组的对应位置中最后让旧数组对象指向新数组。因为每次扩容都使数组大小翻倍所以数组并非每一个位置都是有效数据于是需要额外定义一个变量 size 来记录有效数据的长度避免调用到无效数据。同时size 变量也是判断是否需要扩容的关键。调用方法时需要一个参数 data将数据保存在最最后一个有效数据的后面并使 size 增加。插入添加方法这个方法需要两个参数一个是数据本身data另一个是插入添加的位置index。同样先判断是否需要扩容随后从后往前遍历数组将所有数据往后挪一位直到遍历到 index 的位置将需要插入的数据赋值到该位置最后使 size 增加。删除并返回数据方法这个方法需要一个参数 index代表需要删除的数据的位置。它会先保存位置的数据在一个变量里接着从 index 开始往后遍历将所有数据往前挪一位这样就将 index 位置的数据覆盖掉了达成了删除的效果。接着再返回保存了删除位置的数据的变量的数据最后使 size 减少。删除第一个匹配数据方法这个就简单了遍历数组一旦遇到匹配数据就对该数据调用刚刚写的删除方法再返回结束就行。删除所有匹配数据方法一样遍历数组遇到匹配数据后调用删除方法但不返回继续遍历直到删除所有匹配数据。获取指定位置数据方法这个方法需要一个参数 index返回 index 位置的数据。获取数据数量方法返回 size。二、链表内部节点类这个内部类包含几个变量和一个构造方法分别是指向下一个的指针next、指向上一个的指针prev、数据本身data和构造方法 Node用来传参数给 data 变量。末尾添加方法这个方法需要一个参数 data也就是要存的数据。这个方法会先判断链表有没有头节点如果有就新建一个节点类的对象新节点成为新的尾节点并让曾经的尾节点的 next 指针指向它也让它的 perv 指针指向曾经的尾节点它的 next 指向 null也就是到头了没有下一个节点了。如果不存在头节点就让它成为头和尾next 和 prev 都指向 null因为它成为了链表的第一个节点但也是最后一个节点。最后使 size 增加。插入添加方法这个方法需要两个参数分别是插入位置和数据本身。首先会和末尾添加一样判断有没有头节点不过我这里用的是判断链表长度是否为0效果一样的。如果链表长度不是0那就让插入位置的那个节点的 prev 指向它并让它的 next 指向插入位置的节点。同时也将插入位置的上一个节点的 next 指向它它的 prev 指向上一个节点。最后使 size 增加。获取指定位置数据方法这个方法需要一个参数要访问的位置。我写的是一个双向链表所以可以先判断这个位置是离头节点近一些还是离尾节点近些然后选择更近的那一边开始遍历直到找到指定位置并返回数据。删除并返回指定位置数据方法这个方法需要一个参数要删除的位置。同样通过遍历找到指定位置让它上一个节点的 next 指针指向它的下一个节点让它的下一个节点的 prev 指针指向它的上一个节点于是就不再有任何方法访问到它了返回它的值然后使 size 减少。删除第一个匹配数据方法这个方法需要一个参数目标数据。方法会遍历链表找到匹配数据调用前面写好的删除方法然后返回。删除所有匹配数据方法和上一个一样输入一个目标数据遍历数组调用删除方法但在全部删除干净之前不会返回。链表翻转方法让头结点变成尾节点让每一个节点的 next 指针变成 prev 指针。首先从头开始遍历链表每次让两个指针往下一个节点遍历同时用两个变量分别保存这两个指针再把 next 和 prev 的指向对调然后通过读取对调前保存的指针前往下一个节点然后做同样的事留后路、对调、前往下一个……最后对调头节点和尾节点。获取链表长度方法返回 size。三、完整实操案例动态数组importjava.util.ArrayList;publicclassArrayE{privateObject[]dataarr;privatestaticintlen10;privateintsize0;//自定义动态数组长度publicArray(intlen){dataarrnewObject[len];}//设置默认长度publicArray(){this(len);}//末尾添加publicvoidadd(Edata){//判断是否需要扩容if(sizedataarr.length){Object[]newArrnewObject[dataarr.length*2];for(inti0;idataarr.length;i){newArr[i]dataarr[i];}dataarrnewArr;}dataarr[size]data;size;}//插入添加publicvoidadd(intindex,Edata){if(indexsize||index0){return;}if(sizedataarr.length){Object[]newArrnewObject[dataarr.length*2];for(inti0;isize;i){newArr[i]dataarr[i];}dataarrnewArr;}for(intisize-1;iindex;i--){dataarr[i1]dataarr[i];}dataarr[index]data;size;}//删除指定位置然后返回它publicEremove(intindex){if(index0||indexsize){returnnull;}Eremoved(E)dataarr[index];for(intiindex1;isize;i){dataarr[i-1]dataarr[i];}size--;returnremoved;}//删除匹配数据publicbooleanremoves(Objectdata){for(inti0;isize;i){if(dataarr[i].equals(data)){remove(i);returntrue;}}returnfalse;}//删除所有匹配数据publicbooleanremoveAll(Objectdata){booleanremovedfalse;for(intisize-1;i0;i--){if(dataarr[i].equals(data)){remove(i);removedtrue;}}returnremoved;}//获取指定位置数据publicEget(intindex){if(indexsize){returnnull;}Objectobjdataarr[index];Eresult(E)obj;returnresult;}//获取数据数量publicintsize(){returnsize;}//用时测试与官方动态数组对比publicstaticvoidmain(String[]args){//我的动态数组ArrayIntegerlistnewArray();longstartSystem.currentTimeMillis();for(inti0;i100000;i){list.add(i);}longendSystem.currentTimeMillis();System.out.println(耗时(end-start));//官方动态数组ArrayListIntegerarrayListnewArrayList();startSystem.currentTimeMillis();for(inti0;i100000;i){arrayList.add(i);}endSystem.currentTimeMillis();System.out.println(耗时(end-start));}}测试结果单位毫秒耗时8 //我的数组 耗时3 //官方数组链表publicclassLinkedE{privatestaticclassNodeE{publicEdata;publicNodeEnext;publicNodeEprev;publicNode(Edata){this.datadata;}}privateNodeEfirst;privateNodeElast;privateintsize;//末尾添加publicvoidadd(Edata){NodeEnewNodenewNode(data);if(firstnull){firstnewNode;lastnewNode;first.prevlast;last.nextfirst;}else{last.nextnewNode;newNode.prevlast;newNode.nextfirst;first.prevnewNode;lastnewNode;}size;}//获取指定位置数据publicEget(intindex){if(index0||indexsize){returnnull;}NodeEcurr;if(indexsize/2){currfirst;for(inti0;iindex;i){currcurr.next;if(currnull){returnnull;}}}else{currlast;for(intisize-1;iindex;i--){currcurr.prev;if(currnull){returnnull;}}}returncurr.data;}//插入添加publicvoidadd(intindex,Edata){if(index0||indexsize){return;}NodeEnewNodenewNode(data);NodeEprevnull;NodeEcurrfirst;if(size0){firstnewNode;lastnewNode;first.prevlast;last.nextfirst;size;return;}for(inti0;iindex;i){prevcurr;currcurr.next;}if(prevnull){newNode.prevlast;newNode.nextfirst;first.prevnewNode;last.nextnewNode;firstnewNode;}else{if(currnull){newNode.nextfirst;}else{newNode.nextcurr;curr.prevnewNode;}newNode.prevprev;prev.nextnewNode;if(indexsize){first.prevnewNode;lastnewNode;}}size;}//删除并返回指定位置publicEremove(intindex){if(index0||indexsize){returnnull;}NodeEcurrfirst;for(inti0;iindex;i){currcurr.next;}NodeEprevcurr.prev;NodeEnextcurr.next;if(prevnull){firstnext;last.nextfirst;}else{prev.nextnext;}if(nextnull){lastprev;first.prevlast;}else{next.prevprev;}curr.prevnull;curr.nextnull;size--;returncurr.data;}//删除匹配数据publicbooleanremoves(Objectdata){NodeEcurrfirst;intindex0;while(curr!null){if(curr.data.equals(data)){remove(index);returntrue;}currcurr.next;index;}returnfalse;}//删除所有匹配数据publicbooleanremoveall(Objectdata){booleanremovedfalse;NodeEcurrfirst;intindex0;while(curr!null){if(curr.data.equals(data)){remove(index);removedtrue;index--;}currcurr.next;index;}returnremoved;}//链表翻转publicvoidreversal(){if(size0){return;}NodeEcurrfirst;for(inti0;isize;i){NodeEtempcurr.next;curr.nextcurr.prev;curr.prevtemp;currtemp;}NodeEtempfirst;firstlast;lasttemp;first.prevlast;last.nextfirst;}//获取链表长度publicintgetSize(){returnsize;}publicstaticvoidmain(String[]args){LinkedIntegerlinnewLinked();lin.add(1);lin.add(2);lin.add(3);intsizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();lin.reversal();sizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();lin.add(3,5);sizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();lin.add(3,8);sizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();lin.add(4,3);sizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();lin.removeall(3);sizelin.getSize();for(inti0;isize;i)System.out.print(lin.get(i));System.out.println();}}四、个人收获总结这次学习了链表没想到这个东西真的有点抽象。数组倒是很好理解用起来也挺顺手但刚接触链表时我对“指针”这个概念一只是似懂非懂一知半解大概知道是怎么用但就很难去理解它的本质和原理。但用多了之后慢慢地就越来越懂了最开始我还在想“为什么要用这种这么抽象和麻烦的东西”不过链接不断地加深渐渐地就顺手了起来。学习链表让我对数据结构的理解加深了不少以及指针这个概念本质上就是存了下一个节点的对象有点像地址。我一开始搞不懂为什么写了 curr.next 就可以遍历到下一个节点实际上是 curr 访问了当前节点的 next 变量而这个变量里面存了下一个节点的对象就能“顺藤摸瓜”一样的找过去了