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

<>前言

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



<>1. 简介



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

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

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


* 概念说明
概念 说明
数组长度 存放线性表的空间长度（固定不变）
线性表长度 存放线性表数据元素的长度（动态变化）
地址 存储单元的编号
数组下标 第 i 个元素 = 数组下标第 i-1 的位置
<>2.2 对应操作

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

* 操作1：插入


* 操作2： 删除


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

<>2.3 结构优、缺点



<>2.4 应用场景

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

<>2.5 总结



<>3. 链式存储结构

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



*
链表示意图（以单链表为例）


*
存储元素说明示意图



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

<>3.2 单链表

<>3.2.1 定义

每个结点只有1个指针域

<>3.2.2 示意图



<>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结点，生成一个空结点，然后插入



* 删除


*
整表创建


*
整表删除



* 单链表实现
http://blog.csdn.net/chenleixing/article/details/42392283
<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个环
也称单循环链表

* 示意图


<>3.4 双向链表

<>3.4.1 定义

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

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

<>3.4.2 示意图



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



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

<>3.4.4 特点

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

<>3.5 静态链表



<>4. 存储结构对比



<>5. 总结

* 本文主要讲解了数据结构中最基础的线性表
* 下面我将继续对 数据结构，有兴趣可以继续关注Carson_Ho的安卓开发笔记 <https://blog.csdn.net/carson_ho>
<>请帮顶 / 评论点赞！因为你的鼓励是我写作的最大动力！

• « 上一篇：为什么说学人工智能一定要学Python？很多人都不知道Python的强大
• » 下一篇：简单介绍Hyperledger fabric是什么