文章目录
1、线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2、顺序表
2.1 概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
- 静态顺序表： 使用定长数组存储。
- 动态顺序表： 使用动态开辟的数组存储。
静态顺序表适用于确定知道需要存多少数据的场景。
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用. 相比之下动态顺序表更灵活,根据需要动态的分配空间大小。
2.2 顺序表接口的实现
在实现顺序表接口前我们先把顺序表的成员属性和构造函数完成一下：
public class DATE {
public int[] elem;
public int usedSize;//有效的数据个数
public DATE() {
this.elem = new int[10];//数组初始化为10
}
}
接下来开始实现各个接口的功能
2.2.1 打印顺序表
它的思想很简单，就相当于遍历数组一遍然后输出数组里面的值，而这里是遍历顺序表然后输出顺序表里面的值即可。
//打印顺序表
public void display() {
for(int i=0;i<this.usedSize;i++){
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
2.2.2 在pos位置新增元素
它的思路可以分为以下几个步骤：
1、首先你要判断pos这个位置是否合法
2、如果合法的话，要看这个顺序表是否满了（这可以写个判断方法判断一下），看还能不能放进去元素。如果满了的话可以使用Arrays.copyOf() 对这个顺序表进行扩容。
3、将pos之后的元素依次向后移动。
4、将目标元素data放入pos位置上。
// 在 pos 位置新增元素
import java.util.Arrays;
public void add(int pos, int data) {
//判断位置是否合法
if(pos<0||pos>this.usedSize){
System.out.println("pos位置不合法");
return;
}
//通过isFull()方法的返回值判断这个顺序表是否满了，如果满了则进行扩容
if(isFull())
this.elem= Arrays.copyOf(this.elem,2*this.elem.length);//扩容
//若顺序表没有满，则开始将data放入pos位置上
//注意：在移动数据时，要从后往前移动，因为如果从前往后移动的话，前一个数据
// 会将下一个数据覆盖，导致后面所有的数据都与第一个移动的数据一样。
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() {
//如果有效元素个数和数组长度比较相等的话则返回true，否则返回false
return this.usedSize==this.elem.length;
}
2.2.3 判定是否包含某个元素
它的思想就是：传入要查找的元素，然后在顺序表中的有效元素中依次查找，若元素相等，则说明找到了。
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i <this.usedSize ; i++) {
//让这个元素与顺序表中的有效元素进行比较，如果元素相同的话说明包含了
//这个元素，返回true，否则返回false。
if(this.elem[i]==toFind)
return true;
}
return false;
}
2.2.4 查找某个元素对应的位置
它的思想和判定是否包含某个元素思想一致，只不过若是找的这个元素则返回它的下标。
// 查找某个元素对应的位置
public int search(int toFind) {
for (int i = 0; i <this.usedSize ; i++) {
//让传入的元素和有效元素进行比较，如果找到了这个元素则返回下标即可。
if(this.elem[i]==toFind)
return i;
}
return -1;
}
2.2.5 获取 pos 位置的元素
它的思路为：
1、传入一个位置，判断这个位置是否合法。
2、判断顺序表是否为空（通过isEmpty()方法进行判断）。
3、若位置合法且顺序表不为空则直接返回这个位置上的元素即可。
// 获取 pos 位置的元素
public int getPos(int pos) {
//判断pos位置是否合法
if(pos<0||pos>=this.usedSize){
System.out.println("pos位置不合法！");
return -1;
}
//通过isEmpty()方法返回值判断顺序表是否为空
if(isEmpty()){
System.out.println("顺序表为空！");
return -1;
}
//返回pos位置的元素
return this.elem[pos];
}
//判断这个顺序表是否合法
public boolean isEmpty () {
//若顺序表的有效元素个数为0则说明顺序表为空
return this.usedSize ==0;
}
2.2.6 给 pos 位置的元素设为 value
它的思想和获取 pos 位置的元素思想一致，只不过是当位置合法且顺序表不为空时，直接将value赋值给这个位置覆盖掉原数据即可。
// 给 pos 位置的元素设为 value
public void setPos(int pos, int value) {
//判断pos位置是否合法
if(pos<0||pos>=this.usedSize){
System.out.println("pos位置不合法！");
return ;
}
//通过isEmpty()方法返回值判断顺序表是否为空
if(isEmpty()){
System.out.println("顺序表为空！");
return ;
}
//将pos位置上的元素设为value
this.elem[pos]=value;
}
2.2.7 删除第一次出现的关键字key
首先调用上边已经写好的查找接口判断是否存在这个元素，如果存在的话，就从此数据开始依次将当前数据的下一个数据覆盖当前数据以实现删除功能。
注意： 一定不要忘了有效元素-1！！！
//删除第一次出现的关键字key
public void remove(int toRemove) {
//判断顺序表是否为空
if(isEmpty()){
System.out.println("顺序表为空！");
return ;
}
//调用search方法获得要删除元素的位置
int index=search(toRemove);
//search方法中如果没有找到这个元素则返回-1，所以要进行判断一下
if(index==-1){
System.out.println("没有你要删除的数字");
return ;
}
for (int i = index; i < this.usedSize-1; i++) {
this.elem[i]=this.elem[i+1];//从此数据开始，让当前数据的下一个数据覆盖当前数据以达到删除元素的效果
}
this.usedSize--;//删除一个元素后，有效元素个数减一！！
}
2.2.8 获取顺序表长度
它的思想很简单，直接获取成员属性的有效数据个数usedSize就可以了。
// 获取顺序表的有效数据长度
public int size() {
return this.usedSize;
}
2.2.9 清空顺序表
在这里我们就用最粗暴的办法，直接将有效元素个数清零。（当数组中的元素是基本数据类型时）
// 清空顺序表
public void clear() {
this.usedSize=0;
//当数组中是引用数据类型时
/*for (int i = 0; i < usedSize; i++) {
this.elem[i]= null;
}
this.usedSize=0;*/
}
2.3 顺序表所存在的问题及思考
- 顺序表中间/头部的插入删除，时间复杂度为O(N)。
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
那链表会不会出现这些问题呢？请小伙伴们继续往下看 ? ?
3、链表
3.1 链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向、双向
- 带头、不带头
- 循环、非循环
本文章重点介绍以下两种：
- 无头单向非循环链表： 结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
- 无头双向链表： 在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
3.2 链表的实现
在我们实现链表的接口功能前，我们要先创建两个类，链表类（包含有一个可变的头结点和实现各种功能的接口）和节点类（包含成员属性value和next）。
class ListNode{
public int value;//数据域
public ListNode next;//指针域
public ListNode(int value){
this.value= value;
}
}
public class LinkList {
public ListNode head;//定义链表的头引用
}
下面所写的接口的功能均在链表类中实现。
3.2.1 打印链表
它的思想和打印顺序表思想类似，遍历链表即可，但是需要注意的是： 需要创建一个局部变量cur来代替头结点去遍历，因为头结点在没添加或删除节点之前是固定的，不能让它变来变去的。
//打印链表
public void display(){
ListNode cur=this.head;//创建一个局部变量cur来代替头结点，这样头结点就不会轻易改变了
while(cur!=null){//当节点不为空时遍历单链表，节点为空说明遍历结束
System.out.print(cur.value+" ");
cur=cur.next;//指向下一个节点
}
System.out.println();
}
3.2.2 头插法
所谓头插法就是将一个节点插入到头结点的前面。首先我们要先判断一下头结点是否为空，如果为空的话，那么所创建的新节点就直接为头结点；如若不为空，则先把头结点的地址存放到新节点的next中，然后把新节点置为头结点。（注意： 切不可乱了顺序！！！）
//头插法
public void addFirst(int data){
ListNode node=new ListNode(data);//创建一个新节点并初始化节点的数据
if(this.head==null)//判断头结点是否为空，若为空，则新创建的节点就是头结点
this.head=node;
else{
node.next=this.head;//若头结点不为空，则将头结点的地址存放到新节点的next中
// 然后把新节点置为头结点
this.head=node;
}
}
3.2.3 尾插法
尾插法不同与头插法，尾插法第一次是一定要判断链表是否为空的（也就是判断头结点是否为空），若头节点为空，则要插入的节点就是头结点，若不为空，则引入局部变量cur遍历链表找到最后一个节点，当cur.next为空时，说明找到了最后一个节点，然后让cur中的next指向要插入的节点。
//尾插法
public void addLast(int data){
ListNode node=new ListNode(data);
//尾插的第一次一定要判断头结点是否为空，如果头结点为空，则新节点为头结点
if(this.head==null){
this.head=node;
}
else{
//若头结点不为空，则创建一个局部变量cur来代替头结点进行遍历，找到最后一个节点
ListNode cur=this.head;
while(cur.next!=null){
cur=cur.next;
}
//当变量cur中的next为空时，说明已经遍历结束找到最后一个节点并跳出循环
cur.next=node;//找到最后一个节点后，让最后一个节点中的next设为新节点
}
}
3.2.4 任意位置插入,第一个数据节点为0号下标
首先我们需要先判断一下插入位置是否合理，然后我们如果要在任意位置插入一个节点，则必须要先找到插入位置的前一个节点（因为这是单链表，所以无法直接知道），可再写个方法来实现找到要插入位置的前一个节点。
//只需找到index-1下标即可
public ListNode findIndex(int index){
ListNode cur=this.head;//创建一个局部变量cur代替头结点遍历链表
//当index-1为0时，说明已找到要插入位置的前一个下标
while((index-1)!=0){
cur=cur.next;
index--;//每向后找一个节点，index-1
}
return cur;//返回index的上一个节点
}
//任意位置插入，第一个数据节点为0号下标
public void addIndex(int index,int data){
ListNode node=new ListNode(data);
//判断要插入的位置是否合法
if(index<0||index>size()){
System.out.println("index位置不合法");
return ;
}
//如果要插入的位置为0，则说明是头插，直接调用头插法即可
if(index==0){
addFirst(data);
return;
}
//如果要插入的位置为最后一个元素的位置，则属于是尾插，直接调用尾插法即可
if(index==size()){
addLast(data);
return;
}
//找到要插入位置的前一个位置
ListNode cur=findIndex(index);
node.next=cur.next;//通过上面的查找方法将index位置的前一个节点的下一个节点引用给了新节点的next
cur.next=node;//index位置的前一个节点的下一个节点变成了新节点
}
3.2.5 查找是否包含关键字key是否在单链表当中
传入关键字key，引入局部变量cur遍历链表，如果在遍历过程中遇到和key相同的元素则返回true，否则返回false。
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur=this.head;//引入局部变量cur代替头结点遍历链表
while(cur!=null){
if(cur.value==key)//相等时说明链表中包含了关键字key返回true
return true;
cur=cur.next;//遍历下一个节点
}
//当变量cur为空时，说明遍历结束并跳出循环，链表中没有包含这个关键字，返回false
return false;
}
3.2.6 删除第一次出现关键字为key的节点
首先我们要先判断一下链表是否为空（也就是头节点是否为空），其次我们还要看要删除的key节点是否为头节点，若为头节点，则直接将头结点的引用指向下一个节点，下个节点就成为了头节点；若要删除的key节点不为头节点，则将key节点的前一个节点指向key节点的下一个节点
//找到要删除节点的前一个节点
public ListNode searchPre(int key){
ListNode cur=this.head;
while(cur.next!=null){
//如果某个位置的值和key值相等
if(cur.next.value==key){
//返回那个位置的前一个节点
return cur;
}
//指向下一个节点
cur=cur.next;
}
//当cur.next为空时，说明没有找到要删除的key节点，并且循环结束退出循环
return null;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
//判断链表是否为空
if(this.head==null){
System.out.println("链表为空，无法删除！");
return;
}
//若头结点为要删除的key节点，则头结点的下一个节点直接为头结点
if(this.head.value==key){
this.head=this.head.next;
return ;
}
ListNode pre=searchPre(key);//用pre来接收使用searchPre方法所返回的值
//当值为空时，说明没有要删除的key节点
if(pre==null){
System.out.println("没有你要删除的节点");
return;
}
ListNode suc=pre.next;//suc为后继节点
pre.next=suc.next;//把要删除节点的前一个节点指向要删除节点的后一个节点
}
3.2.7 删除所有值为key的节点
它的思想和删除第一次出现的key节点类似，那个是找到一个要删除的节点就直接跳出循环并返回；而这个是遍历整个链表，直到找到所有要删除的key值后才跳出循环。
//删除所有值为key的节点
public ListNode removeAllKey(int key){
if(this.head==null)
return null;
ListNode pre=this.head;//引用pre变量代替头结点进行遍历
ListNode cur=this.head.next;//引用cur遍历代替头结点的下个节点
while(cur!=null){
//若头结点下个节点的值与所要删除的key值相等
if(cur.value==key){
pre.next= cur.next;//要删除节点的前一个节点指向要删除节点的后一个节点
cur=cur.next;//cur继续往后走，指向下一个节点
}
else{
//若当前位置的节点不是所要删除的key节点，则pre和cur均向后走
pre=cur;
cur=cur.next;
}
}
//最后处理头结点
if(this.head.value==key){
//如果头结点等于要删除的key节点，则它的下一个节点为头结点
this.head=this.head.next;
}
return this.head;//返回头结点
}
3.2.8 获取单链表的长度
引用局部变量cur来遍历链表，并引用一个局部变量count来计数，只要节点不为null，那么count就+1，最后返回的count值就是链表长度了。
//得到单链表的长度
public int size(){
ListNode cur=this.head;
int count=0 ;//引入局部变量count来计数
while(cur!=null){
count++;//当cur不为空时，计数器+1
cur=cur.next;//cur往后走，指向下一个节点
}
return count;//返回链表长度
}
3.2.9 清空链表
首先引用变量curNext来保存头结点的下一个节点，如果不保存的话，那么当将头结点的next置为空时，将找不到头结点的下个节点，那么便无法把其他节点都置为空，也就无法清空链表了。
//置空链表
public void clear(){
//在头结点不为空的情况下
while(this.head!=null){
ListNode curNext=this.head.next;//引用变量curNext来保存头结点的下一个节点
this.head.next=null;//把头结点中的next置为null
this.head=curNext;//把下一个节点置为头结点
}
}
4、顺序表和链表的区别和联系
顺序表：一白遮百丑
白： 空间连续、支持随机访问 。
丑： 1.中间或前面部分的插入删除时间复杂度O(N) 2.增容的代价比较大。
链表：一(胖黑)毁所有
胖黑： 以节点为单位存储，不支持随机访问。
所有： 1.任意位置插入删除时间复杂度为O(1) 2.没有增容问题，插入一个开辟一个空间。
