企业官网建设流程全解析

前言

本文面向编程零基础小白，用生活化案例通俗讲解 Java 中动态数组与链表的核心概念、组成要素与完整实操流程，手把手演示完整可运行代码示例。

一、核心概念

1. 数据结构

“数据结构是计算机存储、组织数据的方式。”官方是这么定义数据结构的。

当有大量同类数据需要保存时，最先考虑的是使用数据结构。
常用的数据结构基本上是数组、链表，或者以数组、链表为基础构建的数据结构功能类。（如哈希表、红黑树等）

“精心选择的数据结构可以带来更高的运行或存储效率。”
在决定使用数据结构时，根据使用场景的不同，使用不同的数据结构可以很大程度上提升效率、节省内存。

2. 动态数组

数组就像一组连续的柜子，只能存同类的数据，每格柜子有一个编号（也就是“下标”）。在使用数组时，存和取都需要通过下标。存数据时，实际上就是为下标处的元素赋值，取数据就是反过来，将一个变量赋值为数组下标位置的数据。

但是数组一旦创建后，大小就固定了，一开始填的是多少就是多少，无法直接改变，何谈“动态”？有的时候没必要执着于直接改变，只要效果是我们想要的，方法具体是什么样的也没什么关系。

要实现数组的扩容可以通过新建一个比原来大些的数组，然后把原来数组每个下标的内容赋值到新数组对应的下标里，再把新数组指向旧数组的对象，就实现了“扩容”的效果。

数组的机制使得它在面对多次随机取数据时游刃有余，直接通过下标找到对应的数据，时间复杂度是 O(1)。但它的机制也使得它在面对扩容需要时必须使用比较间接的方法，没办法直接扩容，需要通过新建数组后复制的方式，时间复杂度是 O(n)，有多少数据 n 就是多少。

3. 链表

链表是由一个一个节点构成的，每个节点会存几个数据。如果是一个基础的单向链表，每个节点会存两个数据，一个是需要储存的数据本身，另一个是指向下一个节点的“地址”，也就是指针。

如果没有指向下一个节点的指针，链表也无法构成，正是每一个节点都指向了它的下一个节点，下一个节点又指向下一个，链表就像锁链一样串了起来。

双向链表则是在原本一个数据加一个指针的基础上，升级成为了一个数据加两个指针，指向下一个节点的指针，与指向上一个节点的指针。

如果要为链表后面添加新的节点，只需要在创建节点后，将最后一个节点的指针指向新创建的节点就行。如果是想插入在两个节点之间，就把上一个节点的指针指向它，再让它的指针指向下一个节点就可以了。

同样的，想要删除最后一个节点的时候，只需要让倒数第二个节点的指针指向 null 就可以了，想要删除中间的某个节点时，也只需要让它的上一个节点指向它的下一个节点就行。

需要取数据时，链表并不存在像数组那样有一个下标，指哪就访问哪里，而是需要从头节点开始，顺着指针一直遍历到指定的位置。一个单向链表有点像俄罗斯套娃那样，必须要一层一层走到指定的位置才能访问到需要的数据。

如果是双向链表，不止可以从头节点开始遍历，也可以从尾节点开始遍历。如果要访问的节点离头节点近，那就从头节点开始，如果要访问的节点离尾节点近，那就从尾节点开始。可以在一定程度上加快访问数据的速度。

链表的机制使得它非常适合应对需要频繁添加或删减数据的情况，每次添加与删减只需要更改节点指针的指向就行，时间复杂度是 O(1)。但链表在访问数据时，因为无法像数组那样直接用下标访问，必须从头节点或尾节点一个个遍历到指定位置，时间复杂度是 O(n)，遍历经过几个节点 n 就是多少。

二、动态数组、链表的组成要素

一、动态数组：

1. 末尾添加方法
   在添加之前会先判断数组是否需要扩容，如果需要扩容就新建一个数组，大小是原数组的2倍大，再将原数组数据遍历赋值到新数组的对应位置中，最后让旧数组对象指向新数组。
   因为每次扩容都使数组大小翻倍，所以数组并非每一个位置都是有效数据，于是需要额外定义一个变量 size 来记录有效数据的长度，避免调用到无效数据。同时，size 变量也是判断是否需要扩容的关键。
   调用方法时需要一个参数 data，将数据保存在最最后一个有效数据的后面，并使 size 增加。

2. 插入添加方法
   这个方法需要两个参数，一个是数据本身（data），另一个是插入添加的位置（index）。
   同样先判断是否需要扩容，随后从后往前遍历数组，将所有数据往后挪一位，直到遍历到 index 的位置，将需要插入的数据赋值到该位置，最后使 size 增加。

3. 删除并返回数据方法
   这个方法需要一个参数 index，代表需要删除的数据的位置。
   它会先保存位置的数据在一个变量里，接着从 index 开始往后遍历，将所有数据往前挪一位，这样就将 index 位置的数据覆盖掉了，达成了删除的效果。
   接着再返回保存了删除位置的数据的变量的数据，最后使 size 减少。

4. 删除第一个匹配数据方法
   这个就简单了，遍历数组，一旦遇到匹配数据就对该数据调用刚刚写的删除方法，再返回结束就行。

5. 删除所有匹配数据方法
   一样遍历数组，遇到匹配数据后调用删除方法，但不返回，继续遍历直到删除所有匹配数据。

6. 获取指定位置数据方法
   这个方法需要一个参数 index，返回 index 位置的数据。

7. 获取数据数量方法
   返回 size。

二、链表：

1. 内部节点类
   这个内部类包含几个变量和一个构造方法，分别是指向下一个的指针（next）、指向上一个的指针（prev）、数据本身（data）和构造方法 Node，用来传参数给 data 变量。

2. 末尾添加方法
   这个方法需要一个参数 data，也就是要存的数据。
   这个方法会先判断链表有没有头节点，如果有，就新建一个节点类的对象，新节点成为新的尾节点，并让曾经的尾节点的 next 指针指向它，也让它的 perv 指针指向曾经的尾节点，它的 next 指向 null（也就是到头了，没有下一个节点了）。
   如果不存在头节点，就让它成为头和尾，next 和 prev 都指向 null，因为它成为了链表的第一个节点，但也是最后一个节点。
   最后使 size 增加。

3. 插入添加方法
   这个方法需要两个参数，分别是插入位置和数据本身。
   首先会和末尾添加一样判断有没有头节点，不过我这里用的是判断链表长度是否为0，效果一样的。
   如果链表长度不是0，那就让插入位置的那个节点的 prev 指向它，并让它的 next 指向插入位置的节点。同时也将插入位置的上一个节点的 next 指向它，它的 prev 指向上一个节点。
   最后使 size 增加。

4. 获取指定位置数据方法
   这个方法需要一个参数，要访问的位置。
   我写的是一个双向链表，所以可以先判断这个位置是离头节点近一些，还是离尾节点近些，然后选择更近的那一边开始遍历，直到找到指定位置并返回数据。

5. 删除并返回指定位置数据方法
   这个方法需要一个参数，要删除的位置。
   同样通过遍历找到指定位置，让它上一个节点的 next 指针指向它的下一个节点，让它的下一个节点的 prev 指针指向它的上一个节点，于是就不再有任何方法访问到它了，返回它的值，然后使 size 减少。

6. 删除第一个匹配数据方法
   这个方法需要一个参数，目标数据。方法会遍历链表找到匹配数据，调用前面写好的删除方法，然后返回。

7. 删除所有匹配数据方法
   和上一个一样，输入一个目标数据，遍历数组，调用删除方法，但在全部删除干净之前不会返回。

8. 链表翻转方法
   让头结点变成尾节点，让每一个节点的 next 指针变成 prev 指针。
   首先从头开始遍历链表，每次让两个指针往下一个节点遍历，同时用两个变量分别保存这两个指针，再把 next 和 prev 的指向对调，然后通过读取对调前保存的指针前往下一个节点，然后做同样的事：留后路、对调、前往下一个……
   最后对调头节点和尾节点。

9. 获取链表长度方法
   返回 size。

三、完整实操案例：

动态数组：

importjava.util.ArrayList;publicclassArray<E>{privateObject[]dataarr;privatestaticintlen=10;privateintsize=0;//自定义动态数组长度publicArray(intlen){dataarr=newObject[len];}//设置默认长度publicArray(){this(len);}//末尾添加publicvoidadd(Edata){//判断是否需要扩容if(size>=dataarr.length){Object[]newArr=newObject[dataarr.length*2];for(inti=0;i<dataarr.length;i++){newArr[i]=dataarr[i];}dataarr=newArr;}dataarr[size]=data;size++;}//插入添加publicvoidadd(intindex,Edata){if(index>size||index<0){return;}if(size>=dataarr.length){Object[]newArr=newObject[dataarr.length*2];for(inti=0;i<size;i++){newArr[i]=dataarr[i];}dataarr=newArr;}for(inti=size-1;i>=index;i--){dataarr[i+1]=dataarr[i];}dataarr[index]=data;size++;}//删除指定位置然后返回它publicEremove(intindex){if(index<0||index>=size){returnnull;}Eremoved=(E)dataarr[index];for(inti=index+1;i<size;i++){dataarr[i-1]=dataarr[i];}size--;returnremoved;}//删除匹配数据publicbooleanremoves(Objectdata){for(inti=0;i<size;i++){if(dataarr[i].equals(data)){remove(i);returntrue;}}returnfalse;}//删除所有匹配数据publicbooleanremoveAll(Objectdata){booleanremoved=false;for(inti=size-1;i>=0;i--){if(dataarr[i].equals(data)){remove(i);removed=true;}}returnremoved;}//获取指定位置数据publicEget(intindex){if(index>=size){returnnull;}Objectobj=dataarr[index];Eresult=(E)obj;returnresult;}//获取数据数量publicintsize(){returnsize;}//用时测试（与官方动态数组对比）publicstaticvoidmain(String[]args){//我的动态数组Array<Integer>list=newArray<>();longstart=System.currentTimeMillis();for(inti=0;i<100000;i++){list.add(i);}longend=System.currentTimeMillis();System.out.println("耗时："+(end-start));//官方动态数组ArrayList<Integer>arrayList=newArrayList<>();start=System.currentTimeMillis();for(inti=0;i<100000;i++){arrayList.add(i);}end=System.currentTimeMillis();System.out.println("耗时："+(end-start));}}

测试结果（单位：毫秒）：

耗时：8 //我的数组 耗时：3 //官方数组

链表

publicclassLinked<E>{privatestaticclassNode<E>{publicEdata;publicNode<E>next;publicNode<E>prev;publicNode(Edata){this.data=data;}}privateNode<E>first;privateNode<E>last;privateintsize;//末尾添加publicvoidadd(Edata){Node<E>newNode=newNode<>(data);if(first==null){first=newNode;last=newNode;first.prev=last;last.next=first;}else{last.next=newNode;newNode.prev=last;newNode.next=first;first.prev=newNode;last=newNode;}size++;}//获取指定位置数据publicEget(intindex){if(index<0||index>=size){returnnull;}Node<E>curr;if(index<size/2){curr=first;for(inti=0;i<index;i++){curr=curr.next;if(curr==null){returnnull;}}}else{curr=last;for(inti=size-1;i>index;i--){curr=curr.prev;if(curr==null){returnnull;}}}returncurr.data;}//插入添加publicvoidadd(intindex,Edata){if(index<0||index>size){return;}Node<E>newNode=newNode<>(data);Node<E>prev=null;Node<E>curr=first;if(size==0){first=newNode;last=newNode;first.prev=last;last.next=first;size++;return;}for(inti=0;i<index;i++){prev=curr;curr=curr.next;}if(prev==null){newNode.prev=last;newNode.next=first;first.prev=newNode;last.next=newNode;first=newNode;}else{if(curr==null){newNode.next=first;}else{newNode.next=curr;curr.prev=newNode;}newNode.prev=prev;prev.next=newNode;if(index==size){first.prev=newNode;last=newNode;}}size++;}//删除并返回指定位置publicEremove(intindex){if(index<0||index>=size){returnnull;}Node<E>curr=first;for(inti=0;i<index;i++){curr=curr.next;}Node<E>prev=curr.prev;Node<E>next=curr.next;if(prev==null){first=next;last.next=first;}else{prev.next=next;}if(next==null){last=prev;first.prev=last;}else{next.prev=prev;}curr.prev=null;curr.next=null;size--;returncurr.data;}//删除匹配数据publicbooleanremoves(Objectdata){Node<E>curr=first;intindex=0;while(curr!=null){if(curr.data.equals(data)){remove(index);returntrue;}curr=curr.next;index++;}returnfalse;}//删除所有匹配数据publicbooleanremoveall(Objectdata){booleanremoved=false;Node<E>curr=first;intindex=0;while(curr!=null){if(curr.data.equals(data)){remove(index);removed=true;index--;}curr=curr.next;index++;}returnremoved;}//链表翻转publicvoidreversal(){if(size==0){return;}Node<E>curr=first;for(inti=0;i<size;i++){Node<E>temp=curr.next;curr.next=curr.prev;curr.prev=temp;curr=temp;}Node<E>temp=first;first=last;last=temp;first.prev=last;last.next=first;}//获取链表长度publicintgetSize(){returnsize;}publicstaticvoidmain(String[]args){Linked<Integer>lin=newLinked<>();lin.add(1);lin.add(2);lin.add(3);intsize=lin.getSize();for(inti=0;i<size;i++)System.out.print(lin.get(i));System.out.println();lin.reversal();size=lin.getSize();for(inti=0;i<size;i++)System.out.print(lin.get(i));System.out.println();lin.add(3,5);size=lin.getSize();for(inti=0;i<size;i++)System.out.print(lin.get(i));System.out.println();lin.add(3,8);size=lin.getSize();for(inti=0;i<size;i++)System.out.print(lin.get(i));System.out.println();lin.add(4,3);size=lin.getSize();for(inti=0;i<size;i++)System.out.print(lin.get(i));System.out.println();lin.removeall(3);size=lin.getSize();for(inti=0;i<size;i++)System.out.print(lin.get(i));System.out.println();}}

四、个人收获总结

这次学习了链表，没想到这个东西真的有点抽象。数组倒是很好理解，用起来也挺顺手，但刚接触链表时，我对“指针”这个概念一只是似懂非懂，一知半解，大概知道是怎么用，但就很难去理解它的本质和原理。

但用多了之后，慢慢地就越来越懂了，最开始我还在想“为什么要用这种这么抽象和麻烦的东西”，不过链接不断地加深，渐渐地就顺手了起来。学习链表让我对数据结构的理解加深了不少，以及指针这个概念，本质上就是存了下一个节点的对象，有点像地址。我一开始搞不懂，为什么写了 curr.next 就可以遍历到下一个节点？实际上是 curr 访问了当前节点的 next 变量，而这个变量里面存了下一个节点的对象，就能“顺藤摸瓜”一样的找过去了