5.线性表：顺序表与链表

比眉伴天荒 2023-10-13 09:41 79阅读 0赞

**目 录**

一、线性表的定义

二、线性表的顺序存储和链式存储

三、前驱和后继

四、顺序表（顺序存储结构）

1、什么是顺序表

2、顺序表与数组的关系和区别

3、顺序表的建立

4、顺序表的基本操作

五、链表（单链表）

1、什么是链表

2、结点（节点）

3、头结点、头指针和首元结点

4、链表的创建

5、链表的基本操作代码示例

--------------------

## 一、线性表的定义 ##

具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表。线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线儿串起来，再存储到物理空间中”。

![30c1150e9d5a4110bc982ba176449010.png][]

图 1 "一对一"逻辑关系的数据

如图 1 所示，这是一组具有“一对一”关系的数据，我们接下来采用线性表将其储存到物理空间中。首先，用“一根线儿”把它们按照顺序“串”起来，如图 2 所示：

![c85d2efef3044c28be055b7cf6d3a925.png][]

图 2 数据的"线性"结构

图 2 中，左侧是“串”起来的数据，右侧是空闲的物理空间。把这“一串儿”数据放置到物理空间，我们可以选择以下两种方式，如图 3 所示。

![43f3617739974b73abc624ffb2117953.png][]

图 3 两种线性存储结构

两种存储方式都可以将数据之间的关系存储起来，从线的一头开始捋，可以依次找到每个数据，且数据的前后位置没有发生改变。像图 3 这样，用一根线将具有“一对一”逻辑关系的数据存储起来，这样的存储方式就称为线性表或者线性存储结构。

## 二、线性表的顺序存储和链式存储 ##

从图 3 不难看出，线性表存储数据的实现方案有两种，分别是：

1、像图 3a) 那样，不破坏数据的前后次序，将它们连续存储在内存空间中，这样的存储方案称为顺序存储结构（简称顺序表）。

2、像图 3b) 那样，将所有数据分散存储在内存中，数据之间的逻辑关系全靠“一根线”维系，这样的存储方案称为链式存储结构（简称链表）。

也就是说，使用线性表存储数据，有两种真正可以落地的存储方案，分别是顺序表和链表。

## 三、前驱和后继 ##

在具有“一对一“逻辑关系的数据集中，每个个体习惯称为数据元素（简称元素）。例如，图 1 显示的这组数据集中，一共有 5 个元素，分别是 1、2、3、4 和 5。

1、某一元素的左侧相邻元素称为该元素的“直接前驱”，此元素左侧的所有元素统称为该元素的“前驱元素”；

2、某一元素的右侧相邻元素称为该元素的“直接后继”，此元素右侧的所有元素统称为该元素的“后继元素”；

以图 1 数据中的元素 3 来说，它的直接前驱是 2 ，此元素的前驱元素有 2 个，分别是 1 和 2；同理，此元素的直接后继是 4 ，后继元素也有 2 个，分别是 4 和 5。

![a1f4886c27264a4ea54bc72305707e58.png][]

图 4 前驱和后继

## 四、顺序表（顺序存储结构） ##

### 1、什么是顺序表 ###

顺序表又称顺序存储结构，是线性表的一种，专门存储逻辑关系为“一对一”的数据。顺序表存储数据的具体实现方案是：将数据全部存储到一整块内存空间中，数据元素之间按照次序挨个存放。举个简单的例子，将 \{1,2,3,4,5\} 这些数据使用顺序表存储，数据最终的存储状态如下图所示：

![a77abd3343754c7daea6e39db26318ae.png][]

图 5 顺序存储结构示意图

### 2、顺序表与数组的关系和区别 ###

1）顺序表，全名顺序存储结构，是线性表的一种。顺序表不仅要求数据在逻辑上是连续的一条直线，还要求用一段物理地址连续的存储单元以次存储表中数据元素，一般情况下采用数组存储。

2）数组是相同数据类型的元素按一定顺序排列的的集合。数组中的元素存储在一个连续性的内存块中，并通过索引来访问。

简单的说，数组是在物理空间中连续存储的相同数据类型的元素的集合。

3）可见：

a. 数组是一种顺序表，但不能说顺序表是数组。就像小学生是学生，那所有的学生都是小学生吗？我们可以用数组实现顺序表，但我们同样可以用数组实现二叉树、队列等结构，因此不能直接认为顺序表就是数组。

b. 数组理解为物理结构，顺序表理解为逻辑结构比较合理。因此，顺序表是在计算机内存中以数组的形式保存的线性表。

c. 在顺序表中我们可以定义表中元素个数、表空间大小等变量，在数组中是没有的。

### 3、顺序表的建立 ###

1）顺序表的组成：

使用顺序表存储数据，除了存储数据本身的值以外，通常还会记录以下两样数据：

（1）顺序表的最大存储容量：顺序表最多可以存储的数据个数。

（2）顺序表的长度：当前顺序表中存储的数据个数。

2）顺序表插入数据原理：往指定位置放元素时，执行如下步骤：

（1）将要插入位置元素以及后续的元素整体向后移动一个位置；

（2）将元素放到腾出来的位置上；

例如，在 \{1,2,3,4,5\} 的第 3 个位置上插入元素 6，实现过程如下：

a. 遍历至顺序表存储第 3 个数据元素的位置，如图6所示：

![3af543258ebf435a889e654c10999812.png][]

图 6 找到目标元素位置

b. 将元素 3、4 和 5 整体向后移动一个位置，如图7所示：

![b304fda2e1b848128fb7eca7b45cfccc.png][]

图 7 将插入位置腾出

c.将新元素 6 放入腾出的位置，如图 3 所示：

![416b0a2390ff4688b8c4d4b4a6d4b2b8.png][]

图 8 插入目标元素

### 4、顺序表的基本操作 ###

在Java语言中，顺序表的建立需要使用数组。

包括操作：

1) 显示顺序表内容

2) 获取 pos 位置的元素

3) 判断空间是否满

4) 插入数据

5) 删除指定位置数据

public class sequenceTableArraysList {
     
             // 定义的数组，用于存储元素
             public int[] sequenceTable;
             // 当前顺序表的存储容量
             public int size ;
             // 当前顺序表中元素个数，也是有效数据长度
             public int usedSize ;
     
             // 构造函数
             public myArraysList(){
                  this.sequenceTable = new int[10];//初始化数组
                  this.size = 10; // 容量是10    
                  this.usedSize = 0; // 初始化是0      
             }
             
             // 1. 显示顺序表内容
             public void display(){
                  // 是否为空
                  if(this.usedSize <= 0){
                       System.out.println("顺序表为空");
                       return -1;
                  }
                  for (int i = 0; i < this.usedSize; i++){
                       System.out.print(this.sequenceTable[i]+" ");
                  }
                  System.out.println();
             }
    
             // 2. 获取 pos 位置的元素
             //判断是否越界
             //判断是否顺序表为空
             //直接返回下标元素
             public int getPos(int pos){
                  if(pos < 0||pos > this.usedSize){
                       System.out.println("pos下标越界");
                       return -1;
                  }
                  if(this.usedSize <= 0){
                       System.out.println("顺序表为空");
                       return -1;
                  }
                  return this.arrary[pos];
     
             }
             // 3.判断空间是否满
             public boolean isFull() {
                  return this.size == this.usedSize;
             }
             // 4.中间插入数据还是在尾部添加新数据
             public void add(int pos,int data){
                  if(pos < 0 || pos > this.usedSize)){//判断是否在顺序表范围内
                       System.out.println("pos不合法");
                       return;
                  }
                  if(isFull()){
                       //判断是否满了，满了的话扩容
                      this.sequenceTable = Arrays.copyOf(this.sequenceTable,this.size*2);
                      this.size = this.size*2;
                  }
                  //判断pos是插入数据还是在尾部添加新数据，注意这是顺序表，中间不存在空元素的情况
                  //从前往后存储
                  if(pos == this.usedSize){ // 尾部添加新数据
                       this.sequenceTable[pos] = data;
                       this.usedSize++;                                                    
                  }else{ // 插入数据
                       for(int i = this.usedSize - 1; i > pos; i--){
                            this.arrary[i+1] = this.arrary[i];//从后往前落动
                       } 
                       this.sequenceTable[pos] = data;  
                       this.usedSize++;            
                  }
             }
             // 5.删除指定位置数据
             public void del(int pos){
                  if(pos < 0 || pos >= this.usedSize)){//判断是否在顺序表范围内
                       System.out.println("pos不合法");
                       return;
                  }
                 
                  //默认数组从前往后存储
                  if(pos == (this.usedSize-1)){ // 尾部删除
                       this.sequenceTable[pos] = 0;
                       this.usedSize--;                                                    
                  }else{ // 中间删除
                       for(int i = pos; i < (this.usedSize -1); i++){
                            this.sequenceTable[i] = this.sequenceTable[i+1];//从后往前移动
                       } 
                       this.sequenceTable[this.usedSize - 1] = 0;
                       this.usedSize--;             
                  }
             }
             
    }

## 五、链表（单链表） ##

### 1、什么是链表 ###

链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。和顺序表不同，使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。例如，使用链表存储 \{1,2,3\}，各个元素在内存中的存储状态可能是：

![84cd2f91b6124357ac78f90ad65db7da.png][]

可以看到，数据不仅没有集中存放，在内存中的存储次序也是混乱的。那么，链表是如何存储数据间逻辑关系的呢？链表存储数据间逻辑关系的实现方案是：为每一个元素配置一个指针，每个元素的指针都指向自己的直接后继元素，如下图所示：

![305efb2cbfe342308af451b5284f050f.png][]

显然，我们只需要记住元素 1 的存储位置，通过它的指针就可以找到元素 2，通过元素 2 的指针就可以找到元素 3，以此类推，各个元素的先后次序一目了然。这样，数据元素随机存储在内存中，通过指针维系数据之间“一对一”的逻辑关系，这样的存储结构就是链表。

### 2、结点（节点） ###

在链表中，每个数据元素都配有一个指针，这意味着，链表上的每个“元素”都长下图这个样子：

![72c8bf229d7344629f1cfd1021e4e280.png][]

数据域用来存储元素的值，指针域用来存放指针。数据结构中，通常将上图这样的整体称为结点。也就是说，链表中实际存放的是一个一个的结点，数据元素存放在各个结点的数据域中。举个简单的例子， \{1,2,3\} 的存储状态用链表表示，如下图所示：

![610706456e8a49ef9e806acca2c816ef.png][]

### 3、头结点、头指针和首元结点 ###

一个完整的链表应该由以下几部分构成：

1）头指针：一个和结点类型相同的指针，它的特点是：永远指向链表中的第一个结点。上文提到过，我们需要记录链表中第一个元素的存储位置，就是用头指针实现。

2）结点：链表中的节点又细分为头结点、首元结点和其它结点：

(1)头结点：某些场景中，为了方便解决问题，会故意在链表的开头放置一个空结点，这样的结点就称为头结点。也就是说，头结点是位于链表开头、数据域为空（不利用）的结点。

(2)首元结点：指的是链表开头第一个存有数据的结点。

(3)其他节点：链表中其他的节点。

也就是说，一个完整的链表是由头指针和诸多个结点构成的。每个链表都必须有头指针，但头结点不是必须的。例如，创建一个包含头结点的链表存储 \{1,2,3\}，如下图所示：

![31117902d53c4ba281c7f44b7a8efac9.png][]

再次强调，头指针永远指向链表中的第一个结点。换句话说，如果链表中包含头结点，那么头指针指向的是头结点，反之头指针指向首元结点。

### 4、链表的创建 ###

在Java语言中，链表的建立需要使用类。一个链表的构建离不开一个个结点的组成，所以构建链表的第一步当然是打基础，建立结点，我们可以创建一个类来实现一个结点的创建，然后通过构造方法赋值的方式来给结点赋值，当然这个引用必须得是这个结点类型的引用，因为我们的链表基本都是通过结点指向下一个结点实现的。

//定义节点类
    class NodeList{
        public int data;
        public NodeList next;
        public NodeList(int num){
            this.data = num;
        }
    }

### 5、链表的基本操作代码示例 ###

包括操作：

1）得到单链表的长度

2）查找是否在单链表当中存在内容为key的节点

3）插入一个节点

(1) 在尾部插入一个节点

(2)在头部插入一个节点

(3)在任意位置插入一个节点

4) 删除一个节点

5) 显示一个链表的内容

6) 清空链表

public class MyLinkedList {
         // 头节点
         public NodeList head;
         // 初始化链表
         public MyLinkedList(int num){
                this.head  = new NodeList(num);
         }
         //1、得到单链表的长度
         //还有更好的方法，就是在MyLinkedList中定义一个记录器，实时记录链表的长度。
         public int size(){
            int count = 0;
            NodeList cur = this.head;
            while(cur != null){
                count++;
                cur = cur.next;
            }
            return count;
         }
         //2. 查找是否在单链表当中存在内容为key的节点
         public boolean contains(int key){
            NodeList cur = this.head;
            while(cur != null){
                if(cur.data s == key){
                    return true;
                }
                cur = cur.next;
            }
            return false;
         }
         //3 插入一个节点
         //3.1 在尾部插入一个节点
         public void addLast(int num){
            NodeList nodeList = new NodeList(num);
            if(this.head == null){
                this.head = nodeList;
            }else{
                NodeList cur = this.head;
                while(cur.next != null){
                    cur = cur.next;
                }//cur == null
                cur.next = nodeList;
            }
        }
        //3.2 在头部插入一个节点
        public void addFirst(int num){
            NodeList nodeList = new NodeList(num);//先建立一个节点
            nodeList.next = this.head;
            this.head = nodeList;
        }
        
         //3.3 在任意位置插入一个节点
         /**
         * 找到index-1位置的节点的地址
         * @param index
         * @return
         */
         public NodeList findIndex(int index){
            NodeList cur = this.head;
            while(index - 1 != 0){
                cur = cur.next;
                index--;
            }
            return cur;
         }
     
         /**
          *
          * @param index 插入位置
          * @param num 插入元素
          *  我们可以先判断然后寻找然后插入
          */
         public void addIndex(int index,int num) {
             if (index < 0 || index > size()) {
                System.out.println("erro");
                return;
             }
             if(index == size()){
                 addFirst(num);
                 return;
             }
             if(index == size()){
                 addLast(num);
                 return;
             }
             NodeList nodeList = new NodeList(num);
             NodeList cur = findIndex(index);
             nodeList.next = cur.next;
             cur.next = nodeList;
         }
         
         //4、删除一个节点
         /**
         * 找到要删除的关键字的前驱
         * @param key
         * @return
         */
         public NodeList searchPerv(int key){
            NodeList cur = this.head;
            while(cur != null){
                if(cur.next.data == key){
                    return cur;
                }//注意是cur.next
                cur = cur.next;
            }
            return null;
        }
        //删除第一次出现关键字为key的节点
        public void remove(int key){
            if(this.head == null){
                System.out.println("erro");
                return;
            }
            // 头节点的内容是否是key
            if(this.head.data == key){
                this.head = this.head.next;
                return;
            }
            NodeList cur = searchPerv(key);
            NodeList del = cur.next;
            cur.next = del.next;
        }
        //5、 显示一个链表的内容
        public void display(){
            NodeList cur = this.head;//cur来遍历链表
            while(cur != null){
                System.out.print(cur.date+" ");
                cur = cur.next;
            }
            System.out.println();
        }
         /**
         * 从指定头节点开始进行打印
         * @param newHead 给定的头节点
         */
         public void display2(NodeList newHead){
              NodeList cur = newHead;
              while(cur != null){
                  System.out.print(cur.date+" ");
                  cur = cur.next;
             }
            System.out.println();
         }
         //6、清空链表
         public void clear(){
            while (this.head != null) {
                NodeList curNext = head.next;
                this.head.next = null;
                this.head = curNext;
            }
        }                
    }

**上一篇：**

[4. 好算法的判断标准: 时间复杂度和空间复杂度\_好的算法的标准\_IT小悟的博客-CSDN博客程序=数据结构(解决存储数据和数据之间关系) + 算法(解决如何访问和处理数据问题)，当数据之间的关系确定后，算法的选择将是影响程序执行效率的关键，通常运用“时间复杂度”和“空间复杂度”来衡量一个算法的运行效率\_好的算法的标准![favicon32.ico][]https://blog.csdn.net/speedwalkman/article/details/130366560][4. _ _IT_-CSDN_ _ _favicon32.ico_https_blog.csdn.net_speedwalkman_article_details_130366560]**下一篇：**

[6.线性表：顺序表和链表的优缺点\_IT小悟的博客-CSDN博客本章节主要介绍顺序表和链表的定义、特点、优点、缺点和适应环境![favicon32.ico][]https://blog.csdn.net/speedwalkman/article/details/131512304][6._IT_-CSDN_favicon32.ico_https_blog.csdn.net_speedwalkman_article_details_131512304]

[30c1150e9d5a4110bc982ba176449010.png]: https://img-blog.csdnimg.cn/30c1150e9d5a4110bc982ba176449010.png
[c85d2efef3044c28be055b7cf6d3a925.png]: https://img-blog.csdnimg.cn/c85d2efef3044c28be055b7cf6d3a925.png
[43f3617739974b73abc624ffb2117953.png]: https://img-blog.csdnimg.cn/43f3617739974b73abc624ffb2117953.png
[a1f4886c27264a4ea54bc72305707e58.png]: https://img-blog.csdnimg.cn/a1f4886c27264a4ea54bc72305707e58.png
[a77abd3343754c7daea6e39db26318ae.png]: https://img-blog.csdnimg.cn/a77abd3343754c7daea6e39db26318ae.png
[3af543258ebf435a889e654c10999812.png]: https://img-blog.csdnimg.cn/3af543258ebf435a889e654c10999812.png
[b304fda2e1b848128fb7eca7b45cfccc.png]: https://img-blog.csdnimg.cn/b304fda2e1b848128fb7eca7b45cfccc.png
[416b0a2390ff4688b8c4d4b4a6d4b2b8.png]: https://img-blog.csdnimg.cn/416b0a2390ff4688b8c4d4b4a6d4b2b8.png
[84cd2f91b6124357ac78f90ad65db7da.png]: https://img-blog.csdnimg.cn/84cd2f91b6124357ac78f90ad65db7da.png
[305efb2cbfe342308af451b5284f050f.png]: https://img-blog.csdnimg.cn/305efb2cbfe342308af451b5284f050f.png
[72c8bf229d7344629f1cfd1021e4e280.png]: https://img-blog.csdnimg.cn/72c8bf229d7344629f1cfd1021e4e280.png
[610706456e8a49ef9e806acca2c816ef.png]: https://img-blog.csdnimg.cn/610706456e8a49ef9e806acca2c816ef.png
[31117902d53c4ba281c7f44b7a8efac9.png]: https://img-blog.csdnimg.cn/31117902d53c4ba281c7f44b7a8efac9.png
[favicon32.ico]: https://g.csdnimg.cn/static/logo/favicon32.ico
[4. _ _IT_-CSDN_ _ _favicon32.ico_https_blog.csdn.net_speedwalkman_article_details_130366560]: https://blog.csdn.net/speedwalkman/article/details/130366560
[6._IT_-CSDN_favicon32.ico_https_blog.csdn.net_speedwalkman_article_details_131512304]: https://blog.csdn.net/speedwalkman/article/details/131512304