【Java数据结构】通过Java理解和实现——顺序表和单链表

????线性表

????顺序表

????顺序表概念及结构

????顺序表接口实现（注释非常详细，我????????都能看懂）

????打印顺序表

????在pos位置新增元素

????获取顺序表长度

????判断是否包含某个元素

????查找某个元素对应的位置

????获取pos位置的元素

????给pos位置的元素设为value

????删除第一次出现的数据

????清空顺序表

????顺序表的缺陷

????链表

????链表概念及结构

????无头单向非循环链表接口实现（注释非常详细，我????????都能看懂）

????打印链表

????头插法插入

????尾插法插入

????查找是否包含关键字key在单链表当中

????得到单链表的长度

????任意位置插入,第一个数据节点为0号下标

????删除第一次出现关键字为key的节点

????删除所有值为key的节点

????清空链表

顺序表和链表的区别与联系

顺序表

链表

????线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

????顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

????顺序表概念及结构

顺序表一般可以分为：

静态顺序表：使用定长数组存储。

动态顺序表：使用动态开辟的数组存储。

静态顺序表适用于确定知道需要存多少数据的场景.

静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用

相比之下动态顺序表更灵活, 根据需要动态的分配空间大小.

接下来详细讲解动态顺序表的实现

????顺序表接口实现（注释非常详细，我????????都能看懂）

????打印顺序表

????在pos位置新增元素

这里思路分为以下几个步骤：

• ①判断pos是否合法
• ②判断顺序表满没满（这里还>需要额外写一个判断方法isFull()），满了需要Arrays.copyOf()扩容
• ③pos之后的元素依次向后移动个位置
• ④将目标元素data放入这个pos位置

????获取顺序表长度

????判断是否包含某个元素

????查找某个元素对应的位置

????获取pos位置的元素

????给pos位置的元素设为value

????删除第一次出现的数据

先调用上边已经写好的查找接口判断是否有这个数据，如果有的话，就从此数据开始依次将当前数据的下一个数据覆盖当前数据实现删除功能不要忘了有效元素-1

//删除第一次出现的关键字key
   public void remove(int toRemove) {
       if (-1==this.search(toRemove)){
           System.out.println("没有这个元素");
       }
       else{
           int index = this.search(toRemove);//获得要删除数据的位置（下标）
           for (int i = index ; i<usedSize-1 ; i++)//从此数据开始依次将当前数据的下一个数据覆盖当前数据实现删除功能
         elem[i]=elem[i+1];
           usedSize--;//注意删除一个元素之后，整个顺序表的有效元素也要-1嗷
       }
   }

????清空顺序表

????顺序表的缺陷

1. 顺序表中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

链表会不会存在以上的问题呢？请往下看????????

????链表

????链表概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

链表结构非常多样，以下情况组合起来有8种链表结构：

单向、双向

带头、不带头

循环、非循环

我们重点学习以下两种链表

????无头单向非循环链表接口实现（注释非常详细，我????????都能看懂）

先写两个类，一个是链表类（包含有一个可变的头结点和实现各种功能的接口，因为是无头链表，所以这个头结点是可变的），一个是节点类（成员属性有value和next）

接下来的接口都是写在链表类里的，因为链表是一个对象，我们要实现的就是一个链表对象所有的功能

????打印链表

????头插法插入

????尾插法插入

????查找是否包含关键字key在单链表当中

????得到单链表的长度

????任意位置插入,第一个数据节点为0号下标

//根据传入的index查找前一个节点并返回地址
   public ListNode findIndex(int index){
       ListNode cur = this.head;//引入局部变量遍历至index前一节点
       while (index-1 != 0){//停止条件就是index-1等于0了
       //也就是说遍历到index位置上一个节点了
           cur = cur.next;//向后遍历
           index--;//每向后找一个节点index减1
       }
       return cur;//返回index上一个节点引用
   }
//任意位置插入,第一个数据节点为0号下标
   public void addIndex(int index,int data){//需要创建一个查找index位置前一节点的函数
       if (index > 0 && index < size()) {//判断插入位置是否合法
           ListNode node = new ListNode(data);//创建新节点并初始化节点的data
           node.next = findIndex(index).next;//通过上边写的查找方法将index位置前一节点的下一节点引用赋给新插入节点的next
           findIndex(index).next = node;//将新节点的引用存到查找到的节点的next达到链接效果
       }

       else if (index==0) {//如果插入位置是0，则直接使用头插法插入
           addFirst(data);
           return;
       }

       else if(index==size()) {//如果插入位置是链表长度值，则直接使用尾插法插入
           addLast(data);
           return;
       }
       else
           System.out.println("位置不合法！");
       return;
   }

????删除第一次出现关键字为key的节点

首先判断头结点是否为null（链表是否为空），然后有两种情况
①关键字在头结点：将头结点下一个节点设置为新头结点
②关键字不在头结点：将有关键字的节点的下一节点引用赋给有关键字节点的上一节点的next

//删除第一次出现关键字为key的节点
   public void remove(int key){
       if (this.head == null){//判断链表是否为空
           System.out.println("链表为空，不能删除");
           return;
       }
       ListNode cur = this.head;
       while(cur.next != null){//遍历链表
           if(cur.value == key) {//①关键字在头结点：将头结点下一个节点设置为新头结点
               head = cur.next;
               return;
           }
           else if(cur.next.value == key) {//②关键字不在头结点：将有关键字的节点的下一节点引用赋给有关键字节点的上一节点的next
               cur.next = cur.next.next;
               return;
           }
           cur = cur.next;
       }
       System.out.println("没有你要删除的节点");
   }

????删除所有值为key的节点

和上边删除第一次出现的key类似，只不过return换成了continue，再有就是需要设置一个局部变量size，删除过程进行完之后若删除前设置的size值没发生改变，则说明没有删除节点

????清空链表

顺序表和链表的区别与联系

顺序表

顺序表：一白遮百丑

白：空间连续、支持随机访问

丑：1.中间或前面部分的插入删除时间复杂度O(N) 2.增容的代价比较大。

链表

链表：一(胖黑)毁所有

胖黑：以节点为单位存储，不支持随机访问

所有：1.任意位置插入删除时间复杂度为O(1) 2.没有增容问题，插入一个开辟一个空间。