Java顺序表和链表如何实现

1. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2. 顺序表

其实就是一个数组。【增删查改】那为什么还有写一个顺序表，直接用数组就好了嘛？不一样，写到类里面 将来就可以 面向对象了。

2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

• 静态顺序表：使用定长数组存储。

• 动态顺序表：使用动态开辟的数组存储。

静态顺序表适用于确定知道需要存多少数据的场景.

静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用.

相比之下动态顺序表更灵活, 根据需要动态的分配空间大小.

2.2 接口实现

我们来实现一个动态顺序表. 以下是需要支持的接口.

这里我们挨个拆解出来：

publicclassMyArrayList{publicint[]elem;publicintusedSize;//有效的数据个数publicMyArrayList(){this.elem=newint[10];}//打印顺序表publicvoiddisplay(){}System.out.println();}//获取顺序表长度publicintsize(){return0;}//在pos位置新增元素publicvoidadd(intpos,intdata){}//判定是否包含某个元素publicbooleancontains(inttoFind){returntrue;}//查找某个元素对应的位置publicintsearch(inttoFind){return-1;}//获取pos位置的元素publicintgetPos(intpos){return-1;}//给pos位置的元素设为valuepublicvoidsetPos(intpos,intvalue){}//删除第一次出现的关键字keypublicvoidremove(inttoRemove){}//清空顺序表publicvoidclear(){}}

这是我们顺序表的基本结构。下面我们就把顺序表的功能一个一个拆解出来：


打印数据表：

publicvoiddisplay(){for(inti=0;i<this.usedSize;i++){System.out.print(this.elem[i]+"");}System.out.println();}

获取顺序表长度：


publicintsize(){returnthis.usedSize;}

publicvoidadd(intpos,intdata){if(pos<0||pos>this.usedSize){System.out.println("pos位置不合法");return;}if(isFull()){this.elem=Arrays.copyOf(this.elem,2*this.elem.length);}for(inti=this.usedSize-1;i>=pos;i--){this.elem[i+1]=this.elem[i];}this.elem[pos]=data;this.usedSize++;}//判断数组元素是否等于有效数据个数publicbooleanisFull(){returnthis.usedSize==this.elem.length;}

publicbooleancontains(inttoFind){for(inti=0;i<this.usedSize;i++){if(this.elem[i]==toFind){returntrue;}}returnfalse;}

publicintsearch(inttoFind){for(inti=0;i<this.usedSize;i++){if(this.elem[i]==toFind){returni;}}return-1;}

publicintgetPos(intpos){if(pos<0||pos>=this.usedSize){System.out.println("pos位置不合法");return-1;//所以这里说明一下,业务上的处理，这里不考虑}if(isEmpty()){System.out.println("顺序表为空！");return-1;}returnthis.elem[pos];}//判断数组链表是否为空publicbooleanisEmpty(){returnthis.usedSize==0;}

publicvoidsetPos(intpos,intvalue){if(pos<0||pos>=this.usedSize){System.out.println("pos位置不合法");return;}if(isEmpty()){System.out.println("顺序表为空！");return;}this.elem[pos]=value;}//判断数组链表是否为空publicbooleanisEmpty(){returnthis.usedSize==0;}

publicvoidremove(inttoRemove){if(isEmpty()){System.out.println("顺序表为空！");return;}intindex=search(toRemove);//index记录删除元素的位置if(index==-1){System.out.println("没有你要删除的数字！");}for(inti=index;i<this.usedSize-1;i++){this.elem[i]=this.elem[i+1];}this.usedSize--;//this.elem[usedSize]=null;引用数组必须这样做才可以删除}

publicvoidclear(){this.usedSize=0;}

2.3 顺序表的问题及思考

1. 顺序表中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考： 如何解决以上问题呢？下面给出了链表的结构来看看。

3. 链表

3.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

实际中链表的结构非常多样，如果按一般来分的话就是四种：

• 单向链表

• 双向链表

• 循环链表

• 双向循环链表

如果细分的话就有以下情况组合起来就有8种链表结构：

• 单向、双向

• 带头、不带头

• 循环、非循环

这八种分别为：

• 单向 带头 循环

• 单向 不带头 循环

• 单向 带头 非循环

• 单向 不带头 非循环

• 双向 带头 循环

• 双向 不带头 循环

• 双向 带头 非循环

• 双向 不带头 非循环

注：上述加粗是我们重点需要学习的！！！

虽然有这么多的链表的结构，但是我们重点掌握两种:

• 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

head：里面存储的就是第一个节点(头节点)的地址

head.next：存储的就是下一个节点的地址

尾结点：它的next域是一个null

• 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

最上面的数字是我们每一个数值自身的地址。

prev：指向前一个元素地址

next：下一个节点地址

data：数据

3.2 链表的实现

3.2.1无头单向非循环链表的实现

上面地址为改结点元素的地址

val：数据域

next：下一个结点的地址

head：里面存储的就是第一个结点(头结点)的地址

head.next：存储的就是下一个结点的地址

无头单向非循环链表实现:

classListNode{publicintval;publicListNodenext;//ListNode储存的是结点类型publicListNode(intval){this.val=val;}}publicclassMyLinkedList{publicListNodehead;//链表的头引用publicvoidcreatList(){ListNodelistNode1=newListNode(12);ListNodelistNode2=newListNode(23);ListNodelistNode3=newListNode(34);ListNodelistNode4=newListNode(45);ListNodelistNode5=newListNode(56);listNode1.next=listNode2;listNode2.next=listNode3;listNode3.next=listNode4;listNode4.next=listNode5;this.head=listNode1;}//查找是否包含关键字key是否在单链表当中publicbooleancontains(intkey){returntrue;}//得到单链表的长度publicintsize(){return-1;}//头插法publicvoidaddFirst(intdata){}//尾插法publicvoidaddLast(intdata){}//任意位置插入,第一个数据节点为0号下标publicbooleanaddIndex(intindex,intdata){returntrue;}//删除第一次出现关键字为key的节点publicvoidremove(intkey){}//删除所有值为key的节点publicListNoderemoveAllKey(intkey){}//打印链表中的所有元素publicvoiddisplay(){}//清除链表中所有元素publicvoidclear(){}}

上面是我们链表的初步结构(未给功能赋相关代码，大家可以复制他们到自己的idea中进行练习，答案在下文中) 这里我们将他们一个一个拿出来实现 并实现！


打印链表中所有元素：

publicvoiddisplay(){ListNodecur=this.head;while(cur!=null){System.out.print(cur.val+"");cur=cur.next;}System.out.println();}

查找是否包含关键字key是否在单链表当中：


publicbooleancontains(intkey){ListNodecur=this.head;while(cur!=null){if(cur.val==key){returntrue;}cur=cur.next;}returnfalse;}

publicintsize(){intcount=0;ListNodecur=this.head;while(cur!=null){count++;cur=cur.next;}returncount;}

publicvoidaddFirst(intdata){ListNodenode=newListNode(data);node.next=this.head;this.head=node;/*if(this.head==null){this.head=node;}else{node.next=this.head;this.head=node;}*/}

publicvoidaddLast(intdata){ListNodenode=newListNode(data);if(this.head==null){this.head=node;}else{ListNodecur=this.head;while(cur.next!=null){cur=cur.next;}cur.next=node;}}

/***找到index-1位置的节点的地址*@paramindex*@return*/publicListNodefindIndex(intindex){ListNodecur=this.head;while(index-1!=0){cur=cur.next;index--;}returncur;}//任意位置插入,第一个数据节点为0号下标publicvoidaddIndex(intindex,intdata){if(index<0||index>size()){System.out.println("index位置不合法！");return;}if(index==0){addFirst(data);return;}if(index==size()){addLast(data);return;}ListNodecur=findIndex(index);ListNodenode=newListNode(data);node.next=cur.next;cur.next=node;}

注意：单向链表找cur时要-1，但双向链表不用 直接返回cur就好


删除第一次出现关键字为key的结点：

/***找到要删除的关键字key的节点*@paramkey*@return*/publicListNodesearchPerv(intkey){ListNodecur=this.head;while(cur.next!=null){if(cur.next.val==key){returncur;}cur=cur.next;}returnnull;}//删除第一次出现关键字为key的节点publicvoidremove(intkey){if(this.head==null){System.out.println("单链表为空");return;}if(this.head.val==key){this.head=this.head.next;return;}ListNodecur=searchPerv(key);if(cur==null){System.out.println("没有你要删除的节点");return;}ListNodedel=cur.next;cur.next=del.next;}

删除所有值为key的结点：


publicListNoderemoveAllKey(intkey){if(this.head==null){returnnull;}ListNodeprev=this.head;ListNodecur=this.head.next;while(cur!=null){if(cur.val==key){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}//最后处理头if(this.head.val==key){this.head=this.head.next;}returnthis.head;}

publicvoidclear(){while(this.head!=null){ListNodecurNext=head.next;head.next=null;head.prev=null;head=curNext;}last=null;}

3.2.2无头双向非循环链表实现：

上面的地址0x888为该结点的地址

val：数据域

prev：上一个结点地址

next：下一个结点地址

head：头结点 一般指向链表的第一个结点

classListNode{publicintval;publicListNodeprev;publicListNodenext;publicListNode(intval){this.val=val;}}publicclassMyLinkedList{publicListNodehead;//指向双向链表的头结点publicListNodelast;//只想双向链表的尾结点//打印链表publicvoiddisplay(){}//得到单链表的长度publicintsize(){return-1;}//查找是否包含关键字key是否在单链表当中publicbooleancontains(intkey){returntrue;}//头插法publicvoidaddFirst(intdata){}//尾插法publicvoidaddLast(intdata){}//删除第一次出现关键字为key的节点publicvoidremove(intkey){}//删除所有值为key的节点publicvoidremoveAllKey(intkey){}//任意位置插入,第一个数据节点为0号下标publicbooleanaddIndex(intindex,intdata){returntrue;}//清空链表publicvoidclear(){}}

上面是我们链表的初步结构(未给功能赋相关代码，大家可以复制他们到自己的idea中进行练习，答案在下文中) 这里我们将他们一个一个拿出来实现 并实现！


打印链表：

publicvoiddisplay(){ListNodecur=this.head;while(cur!=null){System.out.print(cur.val+"");cur=cur.next;}System.out.println();}

得到单链表的长度：


publicintsize(){ListNodecur=this.head;intcount=0;while(cur!=null){count++;cur=cur.next;}returncount;}

publicbooleancontains(intkey){ListNodecur=this.head;while(cur!=null){if(cur.val==key){returntrue;}cur=cur.next;}returnfalse;}

publicvoidaddFirst(intdata){ListNodenode=newListNode(data);if(this.head==null){this.head=node;this.last=node;}else{node.next=this.head;this.head.prev=node;this.head=node;}}

publicvoidaddLast(intdata){ListNodenode=newListNode(data);if(this.head==null){this.head=node;this.last=node;}else{ListNodelastPrev=this.last;this.last.next=node;this.last=this.last.next;this.last.prev=lastPrev;/***两种方法均可*this.last.next=node;*node.prev=this.last;*this.last=node;*/}}

注：第一种方法是先让last等于尾结点 再让他的前驱等于上一个地址 而第二种方法是先使插入的尾结点的前驱等于上一个地址 再使其等于尾结点

删除第一次出现关键字为key的结点:

publicvoidremove(intkey){ListNodecur=this.head;while(cur!=null){if(cur.val==key){if(cur==head){head=head.next;if(head!=null){head.prev=null;}else{last=null;}}elseif(cur==last){last=last.prev;last.next=null;}else{cur.prev.next=cur.next;cur.next.prev=cur.prev;}return;}cur=cur.next;}}

删除所有值为key的结点:

publicvoidremoveAllKey(intkey){ListNodecur=this.head;while(cur!=null){if(cur.val==key){if(cur==head){head=head.next;if(head!=null){head.prev=null;}else{last=null;}}elseif(cur==last){last=last.prev;last.next=null;}else{cur.prev.next=cur.next;cur.next.prev=cur.prev;}//return;}cur=cur.next;}}

注：他和remove的区别就是删除完后是不是直接return返回，如果要删除所有的key值则不return，让cur继续往后面走。

任意位置插入,第一个数据节点为0号下标：

publicvoidaddIndex(intindex,intdata){if(index<0||index>size()){System.out.println("index位置不合法");}if(index==0){addFirst(data);return;}if(index==size()){addLast(data);return;}ListNodecur=searchIndex(index);ListNodenode=newListNode(data);node.next=cur;cur.prev.next=node;node.prev=cur.prev;cur.prev=node;}publicListNodesearchIndex(intindex){ListNodecur=this.head;while(index!=0){cur=cur.next;index--;}returncur;}

思路：先判断 在头位置就头插 在尾位置就尾插 在中间就改变四个位置的值。


注意：单向链表找cur时要-1，但双向链表不用 直接返回cur就好

清空链表：

publicvoidclear(){while(this.head!=null){ListNodecurNext=head.next;head.next=null;head.prev=null;head=curNext;}last=null;}

3.3 链表面试题

3.3.1反转链表：

这里的

cur = this.head;

prev = null;

curNext = cur.next;

publicListNodereverseList(){if(this.head==null){returnnull;}ListNodecur=this.head;ListNodeprev=null;while(cur!=null){ListNodecurNext=cur.next;cur.next=prev;prev=cur;cur=curNext;}returnprev;}

3.3.2找到链表的中间结点：


publicListNodemiddleNode(){if(head==null){returnnull;}ListNodefast=head;ListNodeslow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;if(fast==null){returnslow;}slow=slow.next;}returnslow;}

3.3.3输入一个链表 返回该链表中倒数第k个结点

publicListNodefindKthToTail(ListNodehead,intk){if(k<=0||head==null){returnnull;}ListNodefast=head;ListNodeslow=head;while(k-1!=0){fast=fast.next;if(fast==null){returnnull;}k--;}while(fast.next!=null){fast=fast.next;slow=slow.next;}returnslow;}

3.3.4合并两个链表 并变成有序的

publicstaticListNodemergeTwoLists(ListNodeheadA,ListNodeheadB){ListNodenewHead=newListNode(-1);ListNodetmp=newHead;while(headA!=null&&headB!=null){if(headA.val<headB.val){tmp.next=headA;headA=headA.next;tmp=tmp.next;}else{tmp.next=headB;headB=headB.next;tmp=tmp.next;}}if(headA!=null){tmp.next=headA;}if(headB!=null){tmp.next=headB;}returnnewHead.next;}

最后返回的是傀儡结点的下一个 即newHead.next


3.3.5 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。(即将所有小于x的放在x左边，大于x的放在x右边。且他们本身的排序不可以变)

//按照x和链表中元素的大小来分割链表中的元素publicListNodepartition(intx){ListNodebs=null;ListNodebe=null;ListNodeas=null;ListNodeae=null;ListNodecur=head;while(cur!=null){if(cur.val<x){//1、第一次if(bs==null){bs=cur;be=cur;}else{//2、不是第一次be.next=cur;be=be.next;}}else{//1、第一次if(as==null){as=cur;as=cur;}else{//2、不是第一次ae.next=cur;ae=ae.next;}}cur=cur.next;}//预防第1个段为空if(bs==null){returnas;}be.next=as;//预防第2个段当中的数据，最后一个节点不是空的。if(as!=null){ae.next=null;}returnbe;}

3.3.6 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。(有序的链表中重复的结点一定是紧紧挨在一起的)

publicListNodedeleteDuplication(){ListNodecur=head;ListNodenewHead=newListNode(-1);ListNodetmp=newHead;while(cur!=null){if(cur.next!=null&&cur.val==cur.next.val){while(cur.next!=null&&cur.val==cur.next.val){cur=cur.next;}//多走一步cur=cur.next;}else{tmp.next=cur;tmp=tmp.next;cur=cur.next;}}//防止最后一个结点的值也是重复的tmp.next=null;returnnewHead.next;}

3.3.7 链表的回文结构。

publicbooleanchkPalindrome(ListNodehead){if(head==null){returntrue;}ListNodefast=head;ListNodeslow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}//slow走到了中间位置ListNodecur=slow.next;while(cur!=null){ListNodecurNext=cur.next;cur.next=slow;slow=cur;cur=curNext;}//反转完成while(head!=slow){if(head.val!=slow.val){returnfalse;}else{if(head.next==slow){returntrue;}head=head.next;slow=slow.next;}returntrue;}returntrue;}

3.3.8 输入两个链表，找出它们的第一个公共结点。

他是一个Y字形

publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){if(headA==null||headB==null){returnnull;}ListNodepl=headA;ListNodeps=headB;intlenA=0;intlenB=0;//求lenA的长度while(pl!=null){lenA++;pl=pl.next;}pl=headA;//求lenB的长度while(ps!=null){lenB++;ps=ps.next;}ps=headB;intlen=lenA-lenB;//差值步if(len<0){pl=headB;ps=headA;len=lenB-lenA;}//1、pl永远指向了最长的链表，ps永远指向了最短的链表2、求到了插值len步//pl走差值len步while(len!=0){pl=pl.next;len--;}//同时走直到相遇while(pl!=ps){pl=pl.next;ps=ps.next;}returnpl;}

3.3.9 给定一个链表，判断链表中是否有环。

提问：为啥么fast一次走两步，不走三步？

答：如果链表只有两个元素他们则永远相遇不了(如上图的示例2)，而且走三步的效率没有走两步的效率高。

publicbooleanhasCycle(ListNodehead){if(head==null){returnfalse;}ListNodefast=head;ListNodeslow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){returntrue;}}returnfalse;}

3.3.10 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

publicListNodedetectCycle(ListNodehead){if(head==null){returnnull;}ListNodefast=head;ListNodeslow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){break;}}if(fast==null||fast.next==null){returnnull;}fast=head;while(fast!=slow){fast=fast.next;slow=slow.next;}returnfast;}

4. 顺序表和链表的区别和联系

4.1顺序表和链表的区别

顺序表：一白遮百丑

白：空间连续、支持随机访问

丑：

• 中间或前面部分的插入删除时间复杂度O(N)

• 增容的代价比较大。

链表：一(胖黑)毁所有

胖黑：以节点为单位存储，不支持随机访问

所有：

• 任意位置插入删除时间复杂度为O(1)

• 没有增容问题，插入一个开辟一个空间。

组织：

1、顺序表底层是一个数组，他是一个逻辑上和物理上都是连续的

2、链表是一个由若干结点组成的一个数据结构，逻辑上是连续的 但是在物理上[内存上]是不一定连续的。

操作：

1、顺序表适合，查找相关的操作，因为可以使用下标，直接获取到某个位置的元素

2、链表适合于，频繁的插入和删除操作。此时不需要像顺序表一样，移动元素。链表的插入 只需要修改指向即可。

3、顺序表还有不好的地方，就是你需要看满不满，满了要扩容，扩容了之后，不一定都能放完。所以，他空间上的利用率不高。

4.2数组和链表的区别

链表随用随取 要一个new一个

而数组则不一样 数组是一开始就确定好的

4.3AeeayList和LinkedList的区别

集合框架当中的两个类

集合框架就是将 所有的数据结构，封装成Java自己的类

以后我们要是用到顺序表了 直接使用ArrayList就可以。

以上就是关于“Java顺序表和链表如何实现”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注主机评测网行业资讯频道。

上一篇：Java行为型设计模式之策略模式怎么实现

下一篇：golang的优势是什么