Carson带你学数据结构：这是一份全面& 详细的线性表学习指南

雨点打透心脏的1/2处 2022-03-17 15:08 223阅读 0赞

![e42c52b9af8d79486a0f3cd0e50df7b7.png][]

# 前言 #

*  本文主要讲解 数据结构中最基础的**线性表**
 *  内容包括其特点、结构（顺序存储结构 & 链式结构）等，希望你们会喜欢。

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

# 目录 #

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS02ZDFhYzliMmQxZDY0ZjEyLnBuZw]

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

# 1. 简介 #

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS00MTZlZGVkZGQ5OTQxMzBjLnBuZw]

*  其中，线性表的存储结构最为重要  
    下面，我将主要讲解其 **顺序存储结构 & 链式存储结构**

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

# 2. 顺序存储结构 #

*  实现方式：数组
 *  下面，我将主要讲解其结构特点 & 相关操作

### 2.1 结构特点 ###

1.  存储线性表的数据元素的方式 = **一段地址连续的存储单元**
2.  具备：起始位置、数组长度（最大存储容量） & 线性表长度（当前长度）

*  示意图

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0yZmRjNzNlNzUzMjdhNzU1LnBuZw]

*  概念说明

<table> 
 <thead> 
  <tr> 
   <th>概念</th> 
   <th align="center">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>数组长度</td> 
   <td align="center">存放线性表的空间长度（固定不变）</td> 
  </tr> 
  <tr> 
   <td>线性表长度</td> 
   <td align="center">存放线性表数据元素的长度（动态变化）</td> 
  </tr> 
  <tr> 
   <td>地址</td> 
   <td align="center">存储单元的编号</td> 
  </tr> 
  <tr> 
   <td>数组下标</td> 
   <td align="center">第 i 个元素 = 数组下标第 i-1 的位置</td> 
  </tr> 
 </tbody> 
</table>

### 2.2 对应操作 ###

顺序存储结构的操作包括：**插入 & 删除**

*  操作1：插入

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1jMmQxYTJlNmFhZTQyYzRlLnBuZw]

*  操作2： 删除

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iZGI4NDI4OTdlZTM5ZjMwLnBuZw]

**注：线性表的存取数据时间性能 = `O（1）`**

### 2.3 结构优、缺点 ###

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1kNDI3NTJmNDVjZTEwNTZhLnBuZw]

### 2.4 应用场景 ###

**已知长度、数据元素个数变化不大、存、取数据频率高**的场景

### 2.5 总结 ###

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS05NjE5NGE5ZGY4MzBkYTEwLnBuZw]

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

# 3. 链式存储结构 #

*  实现方式：链表
 *  下面，我将主要讲解其结构特点 & 相关操作

### 3.1 结构特点 ###

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1lMjM4MTNlNzhkYWJiYTM5LnBuZw]

*  链表示意图（以单链表为例）  
    ![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iNjZhNjNjOWI5YjM3NTFlLnBuZw]
 *  存储元素说明示意图

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0yZjczMDc5MTI2YTgyOWM0LnBuZw]

下面将主要重点讲解各种链表：**（重点讲解）单链表、双向链表、循环链表、静态链表**

### 3.2 单链表 ###

##### 3.2.1 定义 #####

每个结点只有1个指针域

##### 3.2.2 示意图 #####

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iNjZhNjNjOWI5YjM3NTFlLnBuZw]

##### 3.2.3 操作（读取、插入、删除、整表创建、整表删除） #####

*  读取  
    算法思路：工作指针向后移

int j ;
    
    // 1. 声明1动态指针
    LinkList p ; 
    
    // 2. 让p指向链表L的第一个结点
    // L = 头结点
    p = L ->next
    
    // 3. 设置计数器
    j = 1;
    while ( p && j<i ){
    
    p = p->next；// 指向下一个结点
    ++j;
    
    }
    
    // 直到到了i结点，直接取出
    e = p->data

*  插入

通过遍历找到i结点，生成一个空结点，然后插入

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS03MThhNGE1NjkyOTFiZDJmLnBuZw]

*  删除

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1lMGQ2YjRhNWZjODQxMjQ4LnBuZw]

*  整表创建  
    ![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iMzEyNzhhOGFhNzk2YjlmLnBuZw]
 *  整表删除

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iM2I0ZmZmZmIxZjU0MjdjLnBuZw]

*  单链表实现

http://blog.csdn.net/chenleixing/article/details/42392283

public class UnidirectionalLinkedList<T> {
    
        /**
         * 设置结点结构
         */
        // a. 结点结构
        private class Node<T>{
            private T data;
            private Node<T> next ;
            public Node(T data){
                this.data = data;
            }
        }
    
        // b. 头结点
        private Node<T> first;
        // c. 当前结点
        private Node<T> currentNode;
        // d. 链表长度
        private int size;
    
        /**
         * 构造函数
         * 作用：初始化结点
         */
        public UnidirectionalLinkedList(){
            currentNode = first = null;
            size = 0;
        }
    
        /**
         * 1. 添加结点
         * 内容：在头 / 尾 添加结点 & 在特定位置插入结点
         */
    
        // a. 在链表头部加入1个结点
        // 即，把新加入的结点设置为第一结点
        public void addFirstNode(T data){
    
            // 1. 将需添加的内容封装成结点
            Node<T> newNode = new Node<T>(data);
            // 2. 将新添加结点的指针域指向旧第1个结点
            newNode.next = first;
            // 3. 将新添加结点设置为第1个结点
            first = newNode;
            // 4. 链表长度+1
            size++;
        }
    
        // b. 在链表尾部加入1个结点
        // 即，把新加入的结点设置为最后结点
        public void addNode(T data){
            // 1. 检查当前链表是否为空
            if (isEmpty()){
                addFirstNode(data);
                return;
            }
            // 2. 把当前指针定位到最后一个结点
            locateNode(size-1);
            // 3. 将需添加的内容封装成结点
            currentNode.next = new Node<T>(data);
            // 4. 链表长度+1
            size++;
        }
    
        // c. 在链表中插入结点
        public T insertNode(int index, T data) {
            // 1. 检查当前链表是否为空
            if (isEmpty()){
                addFirstNode(data);
                return null;
            }
    
            // 2. 把当前指针定位到需插入的结点位置
            locateNode(index);
            // 3. 将需添加的内容封装成结点
            Node<T> insertNode = new Node<T>(data);
            // 4. 把需插入结点位置的下1个结点 赋给 插入的结点
            insertNode.next = currentNode.next;
            // 5. 把插入结点 赋给 需插入的结点的位置
            currentNode.next = insertNode;
            // 6. 链表长度+1
            size++;
            // 7. 返回插入结点的数据
            return insertNode.data;
        }
    
    
        /**
         * 2. 删除结点
         * 内容：删除第1个结点 & 删除特定位置的结点
         */
        // a. 删除第1个结点，并返回该结点数据
        public T removeFirstNode()  {
            // 1. 检查当前链表第一个结点是否为空
            if (first == null){
                try {
                    throw new Exception("链表为空！");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            // 2. 获取被删除结点的数据
            T temp = first.data;
            // 3. 将第2个结点设置为第1个结点
            first = first.next;
            // 4. 链表长度减1
            size--;
    
            // 5. 返回被删除结点的数据
            return temp;
        }
    
    
        // b. 删除特定位置的结点,并将里面的数据返回
        public T removeNode(int index)  {
            // 1. 检查当前链表是否为空
            if (isEmpty()){
                try {
                    throw new Exception("链表为空！");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            // 2. 把当前指针（currentNode）定位到 需删除结点（index）的前1个结点
            locateNode(index-1);
            // 3. 获取被删除结点的数据
            T temp = currentNode.next.data;
            // 4. 将需删除结点（index）的前1个结点 的下1个结点 设置为 需删除结点（index）的下1个结点
            currentNode.next = currentNode.next.next;
            // 5. 链表长度减1
            size--;
            // 6. 返回被删除结点的数据
            return temp;
        }
    
        /**
         * 3. 获取特定位置的结点
         * 内容：将当前指针（currentNode）定位到所需结点位置、根据索引位置获取结点数据
         */
    
        // a. 将当前指针（currentNode）定位到所需结点位置
        private void locateNode(int index){
            // 1. 判断指针是否越界
            if (index <0 && index >size){
                try {
                    throw new IndexOutOfBoundsException("参数越界！");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            int i = 0;
            // 2. 通过遍历链表，寻找索引index所指结点
            for(currentNode = first; currentNode.next != null && i < index; i++){
                currentNode = currentNode.next;
            }
        }
    
        // b. 根据索引位置获取结点数据
        public T getNode(int index)  {
            // 1. 判断链表是否为空
            if (isEmpty()){
                try {
                    throw new Exception("链表为空！");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            // 2. 把当前指针（currentNode）定位到 所需索引位置（index）
            locateNode(index);
            // 3. 返回当前指针的数据，即所需索引位置的数据
            return currentNode.data;
        }
    
        /**
         * 检查当前链表是否为空
         */
        public boolean isEmpty(){
            if (size == 0){
                return true;
            }else {
                return false;
            }
        }
    
    
        public static void main(String[] args){
            // 1. 创建链表 & 加入结点数据
            UnidirectionalLinkedList<Integer> list = new UnidirectionalLinkedList<Integer>();
            list.addNode(1);
            list.addNode(2);
            list.addNode(3);
            list.addNode(4);
            list.addNode(5);
    
            // 2. 输出当前链表数据
            System.out.println("链表数据如下：");
            for (int i = 0; i < list.size;i++){
                
                try {
    
                    System.out.print(list.getNode(i)+" ");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            System.out.println("-----------------------");
    
    
            // 3. 获得某个位置结点的数据
            System.out.println("位置3的数据是：" + list.getNode(3));
    
    
            System.out.println("-----------------------");
    
    
            // 4. 插入结点：在位置4插入，数据 = 66
            System.out.println("在位置4插入的data："+list.insertNode(3,66));
            System.out.println("插入后：");
            for (int i = 0; i < list.size;i++){
                try {
                    System.out.print(list.getNode(i)+" ");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
    
            System.out.println("-----------------------");
    
            // 5. 删除结点
            System.out.println("删除index为3的data："+list.removeNode(3));
            System.out.println("删除后：");
            for (int i = 0; i < list.size;i++){
                try {
                    System.out.print(list.getNode(i)+" ");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }
    
    
    }

*  测试结果

链表数据如下：1 2 3 4 5 
    -----------------------
    位置3的数据是：4
    -----------------------
    在位置4插入的data：66
    插入后：1 2 3 4 66 5 
    -----------------------
    删除index为3的data：4
    删除后：1 2 3 66 5

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

### 3.3 循环链表 ###

*  定义  
    将单链表的终端结点的指针指向头结点、使得单链表头尾相接、形成1个环

> 也称单循环链表

*  示意图

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1mMjMwZGQ2YzI0Y2I3MmY5LnBuZw]

### 3.4 双向链表 ###

#### 3.4.1 定义 ####

每个结点有2个指针域：1指向后驱结点元素、2指向前驱结点元素

> 即 在单链表的结点中，再设置一个指向前驱结点的指针域

#### 3.4.2 示意图 ####

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0zOTU3NWU4YWQ4OTY5NzJiLnBuZw]

#### 3.4.3 链表操作（插入& 删除） ####

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1kYjA1Yzg1OWVhYzI2ODliLnBuZw]

注：插入 & 删除都需要同时改变2个指针变量

#### 3.4.4 特点 ####

*  缺点：占用空间多 = 记录2个指针
 *  优点：算法时间性能高 = 良好对称性（前、后指针）

> 即，用空间换时间

### 3.5 静态链表 ###

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iODkwZjRjMDZjN2FiMzY2LnBuZw]

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

# 4. 存储结构对比 #

![示意图][aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS05YzZhMGUwNTdkOTQwZWIzLnBuZw]

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

# 5. 总结 #

*  本文主要讲解了数据结构中最基础的线性表
 *  下面我将继续对 **数据结构**，感兴趣的同学可以继续关注**carson\_ho的微信公众号**  
    ![示意图][aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85NDQzNjUtNTJkMGM3MWRlZWYyMWI0YS5wbmc]

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

# 请帮顶 / 评论点赞！因为你的鼓励是我写作的最大动力！ #

[e42c52b9af8d79486a0f3cd0e50df7b7.png]: /images/20220317/8df1e537e9d243498dbaafafa7635e64.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS02ZDFhYzliMmQxZDY0ZjEyLnBuZw]: /images/20220317/368ca46a0d174f999d07e70c4be8c7c7.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS00MTZlZGVkZGQ5OTQxMzBjLnBuZw]: /images/20220317/8fbbe484082f42438bc5229604a87e26.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0yZmRjNzNlNzUzMjdhNzU1LnBuZw]: /images/20220317/c46611df205e4f0cb10b94ff6225c4c3.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1jMmQxYTJlNmFhZTQyYzRlLnBuZw]: /images/20220317/f5f0cb3b4c704b6ea2dfd329128130b6.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iZGI4NDI4OTdlZTM5ZjMwLnBuZw]: /images/20220317/4c3b0868bc8d42908f9c1a11d4fd1c2a.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1kNDI3NTJmNDVjZTEwNTZhLnBuZw]: /images/20220317/18db5c553270432998e0cb4dbec334c5.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS05NjE5NGE5ZGY4MzBkYTEwLnBuZw]: /images/20220317/797fbfdd57644f46b4bba2a3970a214d.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1lMjM4MTNlNzhkYWJiYTM5LnBuZw]: /images/20220317/89cdf3789f2c47d78089e327e7176ac2.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iNjZhNjNjOWI5YjM3NTFlLnBuZw]: /images/20220317/5ec958579f8a4b0f902eaccd9b9f6cb3.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0yZjczMDc5MTI2YTgyOWM0LnBuZw]: /images/20220317/8145f99e110644daa2b020fe8d6b1675.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS03MThhNGE1NjkyOTFiZDJmLnBuZw]: /images/20220317/3b5cd02b7c4540978d3c8d8fe9b78635.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1lMGQ2YjRhNWZjODQxMjQ4LnBuZw]: /images/20220317/ed3aaeb3c783476da28ab282093ea94d.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iMzEyNzhhOGFhNzk2YjlmLnBuZw]: /images/20220317/066d6fcb72e64f2685d2229580cb294b.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iM2I0ZmZmZmIxZjU0MjdjLnBuZw]: /images/20220317/bb51770028d843389b00d49254b2bf86.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1mMjMwZGQ2YzI0Y2I3MmY5LnBuZw]: /images/20220317/b665d58df71248418af8c418d10095bf.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0zOTU3NWU4YWQ4OTY5NzJiLnBuZw]: /images/20220317/878b79b22f954c32bd9c25446cb3b5f6.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1kYjA1Yzg1OWVhYzI2ODliLnBuZw]: /images/20220317/6716ea7dab3b4c1eabff22c0f154a6a4.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1iODkwZjRjMDZjN2FiMzY2LnBuZw]: /images/20220317/2eeaf085e24f48089bb61de3e8a3417c.png
[aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS05YzZhMGUwNTdkOTQwZWIzLnBuZw]: /images/20220317/24b78be64c104a2b84d32b5d9a10a44d.png
[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85NDQzNjUtNTJkMGM3MWRlZWYyMWI0YS5wbmc]: /images/20220317/0e24812a2ac64febbfd558eff4db1f90.png