站长资讯网本篇文章给大家带来了关于java的相关知识，其中主要介绍了关于顺序表和链表的相关内容，顺序表就是一个数组，是用一段物理地址连续的存储单元依次存储数据元素的线性结构，下面一起来看一下，希望对大家有帮助。
程序员必备接口测试调试工具：立即使用
Apipost = Postman + Swagger + Mock + Jmeter
Api设计、调试、文档、自动化测试工具
后端、前端、测试，同时在线协作，内容实时同步
推荐学习：《java视频教程》
1. 线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2. 顺序表
其实就是一个数组。【增删查改】那为什么还有写一个顺序表，直接用数组就好了嘛？不一样，写到类里面 将来就可以 面向对象了。
2.1 概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
- 静态顺序表：使用定长数组存储。
- 动态顺序表：使用动态开辟的数组存储。
静态顺序表适用于确定知道需要存多少数据的场景.
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用.
相比之下动态顺序表更灵活, 根据需要动态的分配空间大小.
2.2 接口实现
我们来实现一个动态顺序表. 以下是需要支持的接口.
这里我们挨个拆解出来：
public class MyArrayList { public int[] elem; public int usedSize;//有效的数据个数 public MyArrayList() { this.elem = new int[10]; } // 打印顺序表public void display() { } System.out.println();}// 获取顺序表长度public int size() { return 0;}// 在 pos 位置新增元素public void add(int pos, int data) {}// 判定是否包含某个元素public boolean contains(int toFind) { return true;}// 查找某个元素对应的位置public int search(int toFind) { return -1;}// 获取 pos 位置的元素public int getPos(int pos) { return -1;}// 给 pos 位置的元素设为 valuepublic void setPos(int pos, int value) {}//删除第一次出现的关键字keypublic void remove(int toRemove) {}// 清空顺序表public void clear() {}}
这是我们顺序表的基本结构。下面我们就把顺序表的功能一个一个拆解出来：
打印数据表：
public void display() { for (int i = 0; i < this.usedSize; i++) { System.out.print(this.elem[i] + " "); } System.out.println();}
获取顺序表长度：
public int size() { return this.usedSize;}
在 pos 位置新增元素：
public void add(int pos, int data) { if(pos < 0 || pos > this.usedSize) { System.out.println("pos 位置不合法"); return; } if(isFull()){ this.elem = Arrays.copyOf(this.elem,2*this.elem.length); } for (int i = this.usedSize-1; i >= pos; i--) { this.elem[i + 1] = this.elem[i]; } this.elem[pos] = data; this.usedSize++;}//判断数组元素是否等于有效数据个数public boolean isFull() { return this.usedSize == this.elem.length;}
判断是否包含某个元素：
public boolean contains(int toFind) { for (int i = 0; i < this.usedSize; i++) { if (this.elem[i] == toFind) { return true; } } return false;}
查找某个元素对应的位置：
public int search(int toFind) { for (int i = 0; i < this.usedSize; i++) { if (this.elem[i] == toFind) { return i; } } return -1;}
获取 pos 位置的元素：
public int getPos(int pos) { if (pos < 0 || pos >= this.usedSize){ System.out.println("pos 位置不合法"); return -1;//所以 这里说明一下,业务上的处理，这里不考虑 } if(isEmpty()) { System.out.println("顺序表为空！"); return -1; } return this.elem[pos];}//判断数组链表是否为空public boolean isEmpty() { return this.usedSize == 0;}
给 pos 位置的元素设为 value：
public void setPos(int pos, int value) { if(pos < 0 || pos >= this.usedSize) { System.out.println("pos 位置不合法"); return; } if(isEmpty()) { System.out.println("顺序表为空！"); return; } this.elem[pos] = value;}//判断数组链表是否为空public boolean isEmpty() { return this.usedSize == 0;}
删除第一次出现的关键字key：
public void remove(int toRemove) { if(isEmpty()) { System.out.println("顺序表为空！"); return; } int index = search(toRemove);//index记录删除元素的位置 if(index == -1) { System.out.println("没有你要删除的数字！"); } for (int i = index; i < this.usedSize - 1; i++) { this.elem[i] = this.elem[i + 1]; } this.usedSize--; //this.elem[usedSize] = null;引用数组必须这样做才可以删除}
清空顺序表：
public void clear() { this.usedSize = 0;}
2.3 顺序表的问题及思考
-
顺序表中间/头部的插入删除，时间复杂度为O(N)
-
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
-
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考： 如何解决以上问题呢？下面给出了链表的结构来看看。
3. 链表
3.1 链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
实际中链表的结构非常多样，如果按一般来分的话就是四种：
-
单向链表
-
双向链表
-
循环链表
-
双向循环链表
如果细分的话就有以下情况组合起来就有8种链表结构：
- 单向、双向
- 带头、不带头
- 循环、非循环
这八种分别为：
-
单向 带头 循环
-
单向 不带头 循环
-
单向 带头 非循环
-
单向 不带头 非循环
-
双向 带头 循环
-
双向 不带头 循环
-
双向 带头 非循环
-
双向 不带头 非循环
注：上述加粗是我们重点需要学习的！！！
虽然有这么多的链表的结构，但是我们重点掌握两种:
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中
