文章详情

登录

短信预约-IT技能 免费直播动态提醒

选择考试省份

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团

请输入下面的图形验证码

提交验证

短信预约提醒成功

一文搞懂线性表(顺序表、链表)

2024-12-03 13:50

关注

本文转载自微信公众号「 bigsai」，作者 bigsai 。转载本文请联系 bigsai公众号。

前言

通过前面数据结构与算法基础知识我么知道了数据结构的一些概念和重要性，那么我们今天总结下线性表相关的内容。当然，我用自己的理解分享给大家。(ps你有混淆是节点还是结点嘛)

其实说实话，可能很多人依然分不清线性表，顺序表，和链表之间的区别和联系!

在Java中，大家都知道List接口类型，这就是逻辑结构，因为他就是封装了一个线性关系的一系列方法和数据。而具体的实现其实就是跟物理结构相关的内容。比如顺序表的内容存储使用数组的，然后一个get，set，add方法都要基于数组来完成,而链表是基于指针的。当我们考虑对象中的数据关系就要考虑指针的属性。指针的指向和value。

下面用一个图来浅析线性表的关系。可能有些不太确切，但是其中可以参考，并且后面也会根据这个图举例。

线性表基本架构

对于一个线性表来说。不管它的具体实现如何，但是它们的方法函数名和实现效果应该一致(即使用方法相同、达成逻辑上效果相同，差别的是运行效率)。线性表的概念与Java的接口/抽象类有那么几分相似。最著名的就是List的Arraylist和LinkedList，List是一种逻辑上的结构，表示这种结构为线性表，而ArrayList，LinkedList更多的是一种物理结构(数组和链表)。

所以基于面向对象的编程思维，我们可以将线性表写成一个接口，而具体实现的顺序表和链表的类可以实现这个线性表的方法，提高程序的可读性，还有一点比较重要的，记得初学数据结构与算法时候实现的线性表都是固定类型(int),随着知识的进步，我们应当采用泛型来实现更合理。至于接口的具体设计如下：

  1. package LinerList; 
  2. public interface ListInterface {     
  3.     void Init(int initsize);//初始化表 
  4.     int length(); 
  5.     boolean isEmpty();//是否为空 
  6.     int ElemIndex(T t);//找到编号 
  7.     T getElem(int index) throws Exception;//根据index获取数据 
  8.     void add(int index,T t) throws Exception;//根据index插入数据 
  9.     void delete(int index) throws Exception; 
  10.     void add(T t) throws Exception;//尾部插入 
  11.     void set(int index,T t) throws Exception; 
  12.     String toString();//转成String输出   
  13. } 

顺序表

顺序表是基于数组实现的，所以所有实现需要基于数组特性。对于顺序表的结构应该有一个存储数据的数组data和有效使用长度length.

还有需要注意的是初始化数组的大小，你可以固定大小，但是笔者为了可用性如果内存不够将扩大二倍。

下面着重讲解一些初学者容易混淆的概念和方法实现。

插入操作

add(int index,T t)

其中index为插入的编号位置，t为插入的数据，插入的流程为：

(1)从后(最后一个有数据位)向前到index依次后移一位，腾出index位置的空间

(2)将待插入数据赋值到index位置上，完成插入操作

可以看得出如果顺序表很长，在靠前的地方如果插入效率比较低(插入时间复杂度为O(n))，如果频繁的插入那么复杂度挺高的。

删除操作

同理，删除也是非常占用资源的。原理和插入类似，删除index位置的操作就是从index+1开始向后依次将数据赋值到前面位置上，具体可以看这张图：

代码实现

这里我实现一个顺序表给大家作为参考学习：

  1. package LinerList; 
  2.  
  3. public class seqlist implements ListInterface { 
  4.     private Object[] date;//数组存放数据 
  5.     private int lenth; 
  6.     public seqlist() {//初始大小默认为10 
  7.         Init(10); 
  8.     } 
  9.  
  10.     public void Init(int initsize) {//初始化 
  11.         this.date=new Object[initsize]; 
  12.         lenth=0;         
  13.     } 
  14.     public int length() {        
  15.         return this.lenth; 
  16.     } 
  17.  
  18.     public boolean isEmpty() {//是否为空 
  19.         if(this.lenth==0) 
  20.             return true; 
  21.         return false; 
  22.     } 
  23.  
  24.      
  25.     public int ElemIndex(T t) { 
  26.         // TODO Auto-generated method stub 
  27.         for(int i=0;i<date.length;i++) 
  28.         { 
  29.             if(date[i].equals(t)) 
  30.             { 
  31.                 return i; 
  32.             } 
  33.         } 
  34.         return -1; 
  35.     } 
  36.  
  37.      
  38.     public T getElem(int index) throws Exception { 
  39.         // TODO Auto-generated method stub 
  40.         if(index<0||index>lenth-1) 
  41.             throw new Exception("数值越界"); 
  42.         return (T) date[index]; 
  43.     } 
  44.  
  45.     public void add(T t) throws Exception {//尾部插入 
  46.          add(lenth,t); 
  47.     } 
  48.  
  49.      
  50.     public void add(int index, T t) throws Exception { 
  51.         if(index<0||index>lenth) 
  52.             throw new Exception("数值越界"); 
  53.         if (lenth==date.length)//扩容 
  54.         { 
  55.             Object newdate[]= new Object[lenth*2]; 
  56.             for(int i=0;i
  57.             { 
  58.                 newdate[i]=date[i]; 
  59.             } 
  60.             date=newdate; 
  61.         } 
  62.         for(int i=lenth-1;i>=index;i--)//后面元素后移动 
  63.         { 
  64.             date[i+1]=date[i]; 
  65.         } 
  66.         date[index]=t;//插入元素 
  67.         lenth++;//顺序表长度+1 
  68.  
  69.     } 
  70.  
  71.     public void delete(int index) throws Exception { 
  72.         if(index<0||index>lenth-1) 
  73.             throw new Exception("数值越界"); 
  74.         for(int i=index;iindex之后元素前移动 
  75.         { 
  76.             date[i]=date[i+1]; 
  77.         } 
  78.         lenth--;//长度-1   
  79.     } 
  80.  
  81.     @Override 
  82.     public void set(int index, T t) throws Exception { 
  83.         if(index<0||index>lenth-1) 
  84.             throw new Exception("数值越界"); 
  85.         date[index]=t; 
  86.     } 
  87.     public String  toString() { 
  88.         String vaString=""; 
  89.         for(int i=0;i
  90.         { 
  91.             vaString+=date[i].toString()+" "; 
  92.         } 
  93.         return vaString; 
  94.  
  95.     } 
  96. } 

链表

学习c/c++的时候链表应该是很多人感觉很绕的东西，这个很大原因可能因为指针，Java虽然不直接使用指针但是我们也要理解指针的原理和运用。链表不同于顺序表(数组)它的结构像一条链一样链接成一个线性结构，而链表中每一个结点都存在不同的地址中，链表你可以理解为它存储了指向结点(区域)的地址，能够通过这个指针找到对应结点。

对于物理存储结构，地址之间的联系是无法更改的，相邻就是相邻。但对于链式存储，下一位的地址是上一个主动记录的，可以进行更改。这就好比亲兄弟从出生就是同姓兄弟，而我们在成长途中最好的朋友可能会由于阶段性发生一些变化!

就如西天取经的唐僧、悟空、八戒、沙和尚。他们本无联系，但结拜为师徒兄弟，你问悟空他的师父他会立马想到唐僧，因为五指山下的约定。

基本结构

对于线性表，我们只需要一个data数组和length就能表示基本信息。而对于链表，我们需要一个node(head头结点)，和length分别表示存储的结点数据和链表长度，这个结点有数据域和指针域。数据域就是存放真实的数据，而指针域就是存放下一个node的指针，其具体结构为：

  1. class node{ 
  2.     T data;//结点的结果 
  3.     node next;//下一个连接的结点 
  4.     public node(){} 
  5.     public node(T data) 
  6.     { 
  7.         this.data=data; 
  8.     } 
  9.     public node(T data, node next) { 
  10.         this.data = data; 
  11.         this.next = next; 
  12.     }  
  13. } 

带头结点链表VS不带头结点链表

有很多人会不清楚带头结点和不带头结点链表的区别，甚至搞不懂什么是带头结点和不带头结点，我给大家阐述一下：

带头结点：head指针始终指向一个结点，这个结点不存储有效值仅仅起到一个标识作用(相当于班主任带学生)

不带头结点：head指针始终指向第一个有效结点，这个结点储存有效数值。

那么带头结点和不带头结点的链表有啥区别呢?

查找上：无大区别，带头结点需要多找一次。

插入上：非第0个位置插入区别不大，不带头结点的插入第0号位置之后需要重新改变head头的指向。

删除上：非第0个位置删除区别不大，不带头结点的删除第0号位置之后需要重新改变head头的指向。

头部删除(带头结点)：带头结点的删除和普通删除一样。直接head.next=head.next.next，这样head.next就直接指向第二个元素了。第一个就被删除了

头部删除(不带头结点)：不带头结点的第一个结点(head)就存储有效数据。不带头结点删除也很简单，直接将head指向链表中第二个node结点就行了。即：head=head.next

总而言之：带头结点通过一个固定的头可以使链表中任意一个结点都同等的插入、删除。而不带头结点的链表在插入、删除第0号位置时候需要特殊处理，最后还要改变head指向。两者区别就是插入删除首位(尤其插入)当然我是建议你以后在使用链表时候尽量用带头结点的链表避免不必要的麻烦。

带头指针VS带尾指针

基本上是个链表都是要有头指针的，那么头尾指针是个啥呢?

头指针： 其实头指针就是链表中head结点，成为头指针。

尾指针： 尾指针就是多一个tail结点的链表，尾指针的好处就是进行尾插入的时候可以直接插在尾指针的后面，然后再改变一下尾指针的顺序即可。

但是带尾指针的单链表如果删除尾的话效率不高，需要枚举整个链表找到tail前面的那个结点进行删除。

插入操作

add(int index,T t)

其中index为插入的编号位置，t为插入的数据，在带头结点的链表中插入在任何位置都是等效的。

加入插入一个结点node，根据index找到插入的前一个结点叫pre。那么操作流程为

  1. node.next=pre.next，将插入结点后面先与链表对应部分联系起来。此时node.next和pre.next一致。
  2. pre.next=node 将node结点插入到链表中。

当然，很多时候链表需要插入在尾部，如果频繁的插入在尾部每次枚举到尾部的话效率可能比较低，可能会借助一个尾指针去实现尾部插入。

删除操作

按照index移除(主要掌握)：delete(int index)

本方法为带头结点普通链表的通用方法(删除尾也一样)，找到该index的前一个结点pre，pre.next=pre.next.next

代码实现

在这里我也实现一个单链表给大家作为参考使用：

  1. package LinerList; 
  2.  
  3. class node{ 
  4.     T data;//结点的结果 
  5.     node next;//下一个连接的结点 
  6.     public node(){} 
  7.     public node(T data) 
  8.     { 
  9.         this.data=data; 
  10.     } 
  11.     public node(T data, node next) { 
  12.         this.data = data; 
  13.         this.next = next; 
  14.     } 
  15.  
  16. } 
  17. public class Linkedlist implements ListInterface{ 
  18.  
  19.     node head; 
  20.     private int length; 
  21.     public Linkedlist() { 
  22.         head=new node(); 
  23.         length=0; 
  24.     } 
  25.     public void Init(int initsize) { 
  26.         head.next=null; 
  27.  
  28.     } 
  29.  
  30.     public int length() { 
  31.         return this.length; 
  32.     } 
  33.  
  34.  
  35.     public boolean isEmpty() { 
  36.         if(length==0)return true; 
  37.         else return false; 
  38.     } 
  39.  
  40.      
  41.     public int ElemIndex(T t) { 
  42.         node team=head.next; 
  43.         int index=0; 
  44.         while(team.next!=null) 
  45.         { 
  46.             if(team.data.equals(t)) 
  47.             { 
  48.                 return index; 
  49.             } 
  50.             index++; 
  51.             team=team.next; 
  52.         } 
  53.         return -1;//如果找不到 
  54.     } 
  55.  
  56.     @Override 
  57.     public T getElem(int index) throws Exception { 
  58.         node team=head.next; 
  59.         if(index<0||index>length-1) 
  60.         { 
  61.             throw new Exception("数值越界"); 
  62.         } 
  63.         for(int i=0;i<index;i++) 
  64.         { 
  65.             team=team.next; 
  66.         } 
  67.         return (T) team.data; 
  68.     } 
  69.  
  70.  
  71.     public void add(T t) throws Exception { 
  72.         add(length,t); 
  73.  
  74.     } 
  75.     //带头结点的插入，第一个和最后一个一样操作 
  76.     public void add(int index, T value) throws Exception { 
  77.         if(index<0||index>length) 
  78.         { 
  79.             throw new Exception("数值越界"); 
  80.         } 
  81.         node team=head;//team 找到当前位置node 
  82.         for(int i=0;i<index;i++) 
  83.         { 
  84.              team=team.next; 
  85.         } 
  86.         nodenode =new node(value);//新建一个node 
  87.         node.next=team.next;//指向index前位置的下一个指针 
  88.         team.next=node;//自己变成index位置     
  89.         length++; 
  90.     } 
  91.  
  92.  
  93.     @Override 
  94.     public void delete(int index) throws Exception { 
  95.         if(index<0||index>length-1) 
  96.         { 
  97.             throw new Exception("数值越界"); 
  98.         } 
  99.         node team=head;//team 找到当前位置node 
  100.         for(int i=0;i<index;i++)//标记team 前一个结点 
  101.         { 
  102.              team=team.next; 
  103.         } 
  104.         //team.next结点就是我们要删除的结点 
  105.         team.next=team.next.next; 
  106.         length--; 
  107.     } 
  108.  
  109.     @Override 
  110.     public void set(int index, T t) throws Exception { 
  111.         // TODO Auto-generated method stub 
  112.         if(index<0||index>length-1) 
  113.         { 
  114.             throw new Exception("数值越界"); 
  115.         } 
  116.         node team=head;//team 找到当前位置node 
  117.         for(int i=0;i<index;i++) 
  118.         { 
  119.              team=team.next; 
  120.         } 
  121.         team.data=t;//将数值赋值，其他不变 
  122.  
  123.     } 
  124.  
  125.     public String toString() { 
  126.         String va=""; 
  127.         node team=head.next; 
  128.         while(team!=null) 
  129.         { 
  130.             va+=team.data+" "; 
  131.             team=team.next; 
  132.         } 
  133.         return va; 
  134.     } 
  135.  
  136. } 

总结

你可能疑问代码能跑起来不，那我来测试一下没问题：

这里的只是简单实现，实现基本方法。链表也只是单链表。完善程度还可以优化。能力有限， 如果有错误或者优化的地方还请大佬指正。

单链表查询速度较慢，因为他需要从头遍历，如果在尾部插入，可以考虑设计带尾指针的链表。而顺序表查询速度虽然快但是插入很费时费力，实际应用根据需求选择!

Java中的Arraylist和LinkedList就是两种方式的代表，不过LinkedList使用双向链表优化，并且JDK也做了大量优化。所以大家不用造轮子，可以直接用，但是手写顺序表、单链表还是很有学习价值的。

 

来源： bigsai内容投诉

免责声明：

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题

  • 2024年上半年信息系统项目管理师第二批次真题及答案解析（完整版）

    难度     813人已做
    查看

  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看

  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看

  • 2024年上半年软考高项第一、二批次真题考点汇总（完整版）

    难度     435人已做
    查看

  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机

一文搞懂线性表(顺序表、链表)

后端开发线性表链表2024-12-03

一文搞定双链表，让你彻底弄懂线性表的链式实现

后端开发单链表双链表2024-11-30

Java线性表的顺序表示及实现

后端开发2024-04-02

C语言线性表顺序表示及实现

后端开发2024-04-02

C语言编程数据结构线性表之顺序表和链表原理分析

后端开发2024-04-02

C语言的线性表之顺序表怎么用

后端开发2023-06-29

Java线性表的顺序表示及实现方法

后端开发2023-07-02

一文搞懂Java正则表达式

后端开发Java正则2024-11-30

顺序存储结构的线性表

后端开发顺序存储2024-12-03

C语言的线性表之顺序表你了解吗

后端开发2024-04-02

C语言线性表中顺序表超详细理解

后端开发2024-04-02

C语言线性表中顺序表的示例分析

后端开发2023-06-29

一起来看看C语言线性表的线性链表

后端开发2024-04-02

Python数据结构之线性顺序表

后端开发python数据2024-12-03

C语言线性顺序表如何实现

后端开发2023-07-02

C++如何实现线性表顺序存储

后端开发2023-07-05

一文搞懂Python中pandas透视表pivot_table功能

后端开发2024-04-02

一文搞懂mysql的分区和分表知识

后端开发2024-04-02

一文搞懂Java正则表达式的使用

后端开发2024-04-02

一文搞懂什么是JMM重排序、内存屏障、顺序一致性

后端开发JMM重排序2024-11-30
位置：首页-资讯-后端开发
咦！没有更多了？去看看其它编程学习网 内容吧
首页课程
资料下载问答资讯