Java顺序表和链表如何实现

这篇“Java顺序表和链表如何实现”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“Java顺序表和链表如何实现”文章吧。线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。其实就是一个数组。【增删查改】那为什么还有写一个顺序表，直接用数组就好了嘛？不一样，写到类里面将来就可以面向对象了。顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般可以分为：静态顺序表：使用定长数组存储。动态顺序表：使用动态开辟的数组存储。静态顺序表适用于确定知道需要存多少数据的场景.静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用.相比之下动态顺序表更灵活, 根据需要动态的分配空间大小.我们来实现一个动态顺序表. 以下是需要支持的接口.这里我们挨个拆解出来：


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
获取顺序表长度：


publicintsize(){
returnthis.usedSize;}
在 pos 位置新增元素：


publicvoidadd(intpos,intdata){
if(posthis.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
查找某个元素对应的位置：


publicintsearch(inttoFind){
for(inti=0;i
获取 pos 位置的元素：


publicintgetPos(intpos){
if(p免费云主机域名os=this.usedSize){
System.out.println("pos位置不合法");
return-1;//所以这里说明一下,业务上的处理，这里不考虑
}
if(isEmpty()){
System.out.println("顺序表为空！");
return-1;
}
returnthis.elem[pos];}//判断数组链表是否为空publicbooleanisEmpty(){
returnthis.usedSize==0;}
给 pos 位置的元素设为 value：


publicvoidsetPos(intpos,intvalue){
if(pos=this.usedSize){
System.out.println("pos位置不合法");
return;
}
if(isEmpty()){
System.out.println("顺序表为空！");
return;
}
this.elem[pos]=value;}//判断数组链表是否为空publicbooleanisEmpty(){
returnthis.usedSize==0;}
删除第一次出现的关键字key：


publicvoidremove(inttoRemove){
if(isEmpty()){
System.out.println("顺序表为空！");
return;
}
intindex=search(toRemove);//index记录删除元素的位置
if(index==-1){
System.out.println("没有你要删除的数字！");
}
for(inti=index;i
清空顺序表：


publicvoidclear(){
this.usedSize=0;}

获取顺序表长度：
在 pos 位置新增元素：
判断是否包含某个元素：
查找某个元素对应的位置：
获取 pos 位置的元素：
给 pos 位置的元素设为 value：
删除第一次出现的关键字key：
清空顺序表：
顺序表中间/头部的插入删除，时间复杂度为O(N)增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。思考： 如何解决以上问题呢？下面给出了链表的结构来看看。链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。实际中链表的结构非常多样，如果按一般来分的话就是四种：单向链表双向链表循环链表双向循环链表如果细分的话就有以下情况组合起来就有8种链表结构：单向、双向带头、不带头循环、非循环这八种分别为：单向带头循环单向不带头循环单向带头非循环单向不带头非循环双向带头循环双向不带头循环双向带头非循环双向不带头非循环注：上述加粗是我们重点需要学习的！！！虽然有这么多的链表的结构，但是我们重点掌握两种:无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。head：里面存储的就是第一个节点(头节点)的地址head.next：存储的就是下一个节点的地址尾结点：它的next域是一个null无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。最上面的数字是我们每一个数值自身的地址。prev：指向前一个元素地址next：下一个节点地址data：数据上面地址为改结点元素的地址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中进行练习，答案在下文中) 这里我们将他们一个一个拿出来实现 并实现！

上面是我们链表的初步结构(未给功能赋相关代码，大家可以复制他们到自己的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;
}}
任意位置插入,第一个数据结点为0号下标(插入到index后面一个位置)：

查找是否包含关键字key是否在单链表当中：
得到单链表的长度：
头插法(一定要记住绑定位置时一定要先绑定后面的数据避免后面数据丢失)：
尾插法：
任意位置插入,第一个数据结点为0号下标(插入到index后面一个位置)：


/**
*找到index-1位置的节点的地址
*@paramindex
*@return
*/publicListNodefindIndex(intindex){
ListNodecur=this.head;
while(index-1!=0){
cur=cur.next;
index--;
}
returncur;}//任意位置插入,第一个数据节点为0号下标publicvoidaddIndex(intindex,intdata){
if(indexsize()){
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就好

注意：单向链表找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;}

删除所有值为key的结点：
清空链表中所有元素：
上面的地址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中进行练习，答案在下文中) 这里我们将他们一个一个拿出来实现 并实现！

上面是我们链表的初步结构(未给功能赋相关代码，大家可以复制他们到自己的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;}
查找是否包含关键字key是否在单链表当中:


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;
*/
}}

得到单链表的长度：
查找是否包含关键字key是否在单链表当中:
头插法：
尾插法：
注：第一种方法是先让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(indexsize()){
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;}

这里的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找到链表的中间结点：

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;}


publicListNodefindKthToTail(ListNodehead,intk){
if(k


publicstaticListNodemergeTwoLists(ListNodeheadA,ListNodeheadB){
ListNodenewHead=newListNode(-1);
ListNodetmp=newHead;
while(headA!=null&&headB!=null){
if(headA.val最后返回的是傀儡结点的下一个 即newHead.next

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


//按照x和链表中元素的大小来分割链表中的元素publicListNodepartition(intx){
ListNodebs=null;
ListNodebe=null;
ListNodeas=null;
ListNodeae=null;
ListNodecur=head;
while(cur!=null){
if(cur.val


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;}


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;}

他是一个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

提问：为啥么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;}


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;}

顺序表：一白遮百丑白：空间连续、支持随机访问丑：中间或前面部分的插入删除时间复杂度O(N)增容的代价比较大。链表：一(胖黑)毁所有胖黑：以节点为单位存储，不支持随机访问所有：任意位置插入删除时间复杂度为O(1)没有增容问题，插入一个开辟一个空间。组织：1、顺序表底层是一个数组，他是一个逻辑上和物理上都是连续的2、链表是一个由若干结点组成的一个数据结构，逻辑上是连续的但是在物理上[内存上]是不一定连续的。操作：1、顺序表适合，查找相关的操作，因为可以使用下标，直接获取到某个位置的元素2、链表适合于，频繁的插入和删除操作。此时不需要像顺序表一样，移动元素。链表的插入只需要修改指向即可。3、顺序表还有不好的地方，就是你需要看满不满，满了要扩容，扩容了之后，不一定都能放完。所以，他空间上的利用率不高。链表随用随取要一个new一个而数组则不一样数组是一开始就确定好的集合框架当中的两个类集合框架就是将所有的数据结构，封装成Java自己的类以后我们要是用到顺序表了直接使用ArrayList就可以。以上就是关于“Java顺序表和链表如何实现”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注百云主机行业资讯频道。

相关推荐: Vue $nextTick能获取到最新Dom的原因是什么

这篇文章主要介绍“Vue$nextTick能获取到最新Dom的原因是什么”，在日常操作中，相信很多人在Vue$nextTick能获取到最新Dom的原因是什么问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Vue$nextTick能…

免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。