5.线性表：顺序表与链表_线性表顺序和链式

目     录

一、线性表的定义

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

三、前驱和后继

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

1、什么是顺序表

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

3、顺序表的建立

4、顺序表的基本操作

五、链表（单链表）

1、什么是链表

2、结点（节点）

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

4、链表的创建

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

---

一、线性表的定义

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

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

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

图 2 数据的"线性"结构

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

图 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。

图 4 前驱和后继

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

1、什么是顺序表

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

图 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所示：

图 6 找到目标元素位置

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

图 7 将插入位置腾出

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

图 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}，各个元素在内存中的存储状态可能是：

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

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

2、结点（节点）

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

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

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

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

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

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

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

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

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

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

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

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博客程序=数据结构(解决存储数据和数据之间关系) + 算法(解决如何访问和处理数据问题)，当数据之间的关系确定后，算法的选择将是影响程序执行效率的关键，通常运用“时间复杂度”和“空间复杂度”来衡量一个算法的运行效率_好的算法的标准https://blog.csdn.net/speedwalkman/article/details/130366560下一篇：

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