【数据结构】顺序表，链表

雨点打透心脏的1/2处 2023-09-27 13:52 139阅读 0赞

> ## 前言 ##
> 
> 小亭子正在努力的学习编程，接下来将开启 javaEE 的学习~~
> 
> 分享的文章都是学习的笔记和感悟，如有不妥之处希望大佬们批评指正~~
> 
> 同时如果本文对你有帮助的话，烦请点赞关注支持一波, 感激不尽~~

**目录**

前言

顺序表

ArrayList

ArrayList的构造

ArrayList的创建方法：

构造方法：

ArrayList常用方法

ArrayList的扩容机制

ArrayList的实现和常用方法的代码演示

ArrayList小结

链表

链表的分类

LinkedList

LinkedList的构造方法

LinkedList的其他常用方法介绍

LinkedList的实现和常用方法的演示

ArrayList和LinkedList的区别

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

线性表：

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...  
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

## 顺序表 ##

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

### ArrayList ###

在集合框架中，ArrayList是一个普通的类，实现了List接口。

![5a08614b235f48689f38049b8ae2ce4d.png][]

> 【说明】  
> 1. ArrayList是以泛型方式  
> 2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问  
> 3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的  
> 4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的  
> 5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList  
> 6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

#### ArrayList的构造 ####

##### ArrayList的创建方法： #####

>     public static void main(String[] args) {
>     // ArrayList创建，推荐写法
>     // 构造一个空的列表
>     List<Integer> list1 = new ArrayList<>();
>     // 构造一个具有10个容量的列表
>     List<Integer> list2 = new ArrayList<>(10);
>     list2.add(1);
>     list2.add(2);
>     list2.add(3);
>     // list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素
>     // list3构造好之后，与list中的元素一致
>     ArrayList<Integer> list3 = new ArrayList<>(list2);
>     
>     }

##### 构造方法： #####

<table> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>解释</td> 
  </tr> 
  <tr> 
   <td>ArrayList()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>ArrayList(Collection&lt;? extends E&gt; c)</td> 
   <td>利用其他 Collection 构建 ArrayList</td> 
  </tr> 
  <tr> 
   <td>ArrayList(int initialCapacity)</td> 
   <td>指定顺序表初始容量</td> 
  </tr> 
 </tbody> 
</table>

##### ArrayList常用方法 #####

<table> 
 <tbody> 
  <tr> 
   <td>boolean add(E e)</td> 
   <td>尾插 e</td> 
  </tr> 
  <tr> 
   <td>void add(int index, E element)</td> 
   <td>将 e 插入到 index 位置</td> 
  </tr> 
  <tr> 
   <td>boolean addAll(Collection&lt;? extends E&gt; c)</td> 
   <td>尾插 c 中的元素</td> 
  </tr> 
  <tr> 
   <td>E remove(int index)</td> 
   <td>删除 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>boolean remove(Object o)</td> 
   <td>删除遇到的第一个 o</td> 
  </tr> 
  <tr> 
   <td>E get(int index)</td> 
   <td>获取下标 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>E set(int index, E element)</td> 
   <td>将下标 index 位置元素设置为 element</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>清空</td> 
  </tr> 
  <tr> 
   <td>boolean contains(Object o)</td> 
   <td>判断 o 是否在线性表中</td> 
  </tr> 
  <tr> 
   <td>int indexOf(Object o)</td> 
   <td>返回第一个 o 所在下标</td> 
  </tr> 
  <tr> 
   <td>int lastIndexOf(Object o)</td> 
   <td>返回最后一个 o 的下标</td> 
  </tr> 
  <tr> 
   <td>List&lt;E&gt; subList(int fromIndex, int toIndex)</td> 
   <td>截取部分 list</td> 
  </tr> 
 </tbody> 
</table>

##### ArrayList的扩容机制 #####

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。

> 扩容的步骤：
> 
> 1. 检测是否真正需要扩容，如果是调用grow准备扩容  
> 2. 预估需要库容的大小初步预估按照1.5倍大小扩容，如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容，真正扩容之前检测是否能扩容成功，防止太大导致扩容失败  
> 3. 使用copyOf进行扩容

> #### ArrayList的实现和常用方法的代码演示 ####
> 
>     public class MyArrayList{
>         public int [] elem;//顺序表相当于一个数组
>         public int usedSize;//有效数据的长度
>         public static  final int DEFAULT_SIZE = 5;
>         private boolean isFull;
>     
>         public MyArrayList(){
>             this.elem = new int [DEFAULT_SIZE];//实例化
>      }
>     
>         /*
>         判断顺序表是否已满
>          */
>         public boolean isFull(){
>             //看有效数据长度是否等于顺序表长度，等于返回true
>             return this.usedSize == this.elem.length;
>         }
>          /*
>           扩容
>           */
>         public void resize(){
>             //Array.copyOf() 用于复制指定的数组内容以达到扩容的目的
>             this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
>         }
>         /*
>         新增数据
>          */
>         public void  add(int data){
>             if(this.isFull){ //判断顺序表空间是否满了，如果满了，执行扩容
>                 resize();
>             }
>             this.elem[this.usedSize] = data ;//插入数据
>             this.usedSize++; // 有效数据长度加1
>         }
>         /*
>         打印顺序表
>          */
>         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;
>          }
>      /*
>      判定是否包含某个元素
>       */
>         public boolean contains (int toFind){
>             for (int i = 0; i < this.usedSize; i++) {
>                 if (this.elem [i] == toFind){
>                     return true;
>                 }
>             }
>             return false;
>         }
>      /*
>      查找某个元素对应的位置
>       */
>         public int indexof(int toFind){
>             for (int i = 0; i < this.usedSize; i++) {
>                 if (this.elem[i] == toFind){
>                     return  i;
>                 }
>             }
>             return -1;//数组没有负数下标
>         }
>     
>         /*
>         在 pos 位置新增元素 O(N)
>          */
>         public void add(int pos,int data){
>             checkIndex(pos);
>             if (isFull()){
>                 resize();
>             }
>             for (int i = usedSize-1; i >= pos; i--) {
>                 elem[i+1] = elem [i];
>                   }
>             elem[pos] = data ;
>             usedSize++;
>         }
>       /*
>       检查add数据的时候，pos是否是合法的
>        */
>         private void checkIndex(int pos) {
>             if (pos < 0|| pos > elem.length)
>             //抛出异常
>             throw new IndexOutOfException
>                     ("位置不合法，请检查位置的合法性");
>         }
>     
>      /*
>       获取 pos 位置的元素
>       */
>         public int get(int pos) {
>             checkGetIndex(pos);
>             return elem[pos];
>         }
>      /*
>      检查取数据时pos的合法性
>       */
>         private void checkGetIndex(int pos) {
>             if(pos < 0 || pos >= usedSize) {  //取数据的时候元素下标可以等于数组有效长度
>                 throw new IndexOutOfException
>                         ("get获取元素的时候，位置不合法，请检查位置的合法性！");
>             }
>         }
>      /*
>      给 pos 位置的元素设为 value
>       */
>         public void set(int pos, int value) {
>             checkIndex(pos);
>             elem[pos] = value;//顺序表的优点就是可以随机存取
>         }
>     
>      /*
>      删除第一次出现的关键字key O(n)
>       */
>         public boolean remove(int toRemove) {
>             int index = indexof(toRemove);// 找到那个元素对应的位置
>             if(index == -1){  // 判断元素位置的合法性，-1不合法
>                 System.out.println("没有这个数据");
>                 return false;
>             }
>             //删除这个元素后，后面的元素要向前移动
>             for (int i = index; i < usedSize-1 ; i++){
>                 elem[i] = elem [i+1];
>             }
>             usedSize--;
>             elem[usedSize] = 0;
>             //最后一个元素的位置要置为空，内置数据类型置为0就行
>             //elem[usedSize] = null;
>             // 如果里面是引用类型 那么此时就需要手动置空
>             return true;
>         }
>          /*
>          清空数据类型
>           */
>         public void  clear(){
>             //直接把有效长度置为0
>             usedSize = 0;
>              /*遍历，把每一个元素都置为空
>            for (int i = 0; i < usedSize; i++) {
>                 elem[i] = null;
>             }
>             usedSize = 0;
>             */
>         }
>         public static void main(String[] args) {
>             MyArrayList myArrayList = new MyArrayList();
>             myArrayList.add(1);
>             myArrayList.add(3);
>             myArrayList.add(5);
>             myArrayList.add(7);
>             myArrayList.display();
>             myArrayList.size();
>             myArrayList.add(3,111);
>             myArrayList.indexof(3);
>             myArrayList.get(1);
>             myArrayList.set(1,99);
>             myArrayList.remove(3);
>             myArrayList.clear();
>             System.out.println("sssssss");
>         }
>     }

## ArrayList小结 ##

> 1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)，所以不适合用在需要频繁删除插入的场景。相反，由于使用的是连续的空间，在知道下标位置的情况下很容易找到目标元素，时间复杂度为O（1），所以更适合用在查找检索的场景。  
> 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。  
> 3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

## 链表 ##

链表是一种由一系列节点组成，每个节点包含数据和一个指向下一个节点的指针。

链表在逻辑上是连续的，在物理空间上可能连续也可能不连续。

![aceb19dff8844056b9a13d7936934fc1.png][]

### 链表的分类 ###

1. 单向或者双向  
![27c5bf4a2b834da8bfc4bc7da88347e3.png][]

单向链表中，每个节点只包含一个指向下一个节点的指针，最后一个节点的指针指向空。

双向链表中，每个节点除了一个指向下一个节点的指针，还包含一个指向前一个节点的指针，提供前后两个方向的遍历。

2. 带头或者不带头

![c1ede999dab24033a3f1f1354e0146d3.png][]

3. 循环或者非循环

![402de247dc0e421ca049e519ed018f14.png][]

> 小结：
> 
> 与数组相比，链表具有一些优点和缺点。链表插入和删除节点的时间复杂度为O(1)，而在数组中插入和删除节点需要移动其他节点，时间复杂度为O(n)。但在链表中访问某个节点的时间复杂度为O(n)，而在数组中的访问时间复杂度为O(1)。
> 
> 因此，链表适合频繁进行插入和删除操作，而数组适合频繁进行访问操作。 链表常用于实现栈、队列和图等数据结构，也用于解决一些特定的问题，如求解约瑟夫问题等。

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

### LinkedList ###

LinkedList的底层是双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。  
![b15fefd68f6c4a019be3142b29bb2c3e.png][]

在集合框架中，LinkedList也实现了List接口，具体如下  
![93441a01c4474d14abefb0ab9f139853.png][]

> 【说明】  
> 1. LinkedList实现了List接口  
> 2. LinkedList的底层使用了双向链表  
> 3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问  
> 4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)  
> 5. LinkedList比较适合任意位置插入的场景

### LinkedList的构造方法 ###

<table> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>解释</td> 
  </tr> 
  <tr> 
   <td>LinkedList()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>public LinkedList(Collection&lt;? extends E&gt; c)</td> 
   <td>使用其他集合容器中元素构造List</td> 
  </tr> 
 </tbody> 
</table>

#### LinkedList的其他常用方法介绍 ####

<table> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>解释</td> 
  </tr> 
  <tr> 
   <td>boolean add(E e)</td> 
   <td>尾插 e</td> 
  </tr> 
  <tr> 
   <td>void add(int index, E element)</td> 
   <td>将 e 插入到 index 位置</td> 
  </tr> 
  <tr> 
   <td>boolean addAll(Collection&lt;? extends E&gt; c)</td> 
   <td>尾插 c 中的元素</td> 
  </tr> 
  <tr> 
   <td>E remove(int index)</td> 
   <td>删除 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>boolean remove(Object o)</td> 
   <td>删除遇到的第一个 o</td> 
  </tr> 
  <tr> 
   <td>E get(int index)</td> 
   <td>获取下标 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>E set(int index, E element)</td> 
   <td>将下标 index 位置元素设置为 element</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>清空</td> 
  </tr> 
  <tr> 
   <td>boolean contains(Object o)</td> 
   <td>判断 o 是否在线性表中</td> 
  </tr> 
  <tr> 
   <td>int indexOf(Object o)</td> 
   <td>返回第一个 o 所在下标</td> 
  </tr> 
  <tr> 
   <td>int lastIndexOf(Object o)</td> 
   <td>返回最后一个 o 的下标</td> 
  </tr> 
  <tr> 
   <td>List&lt;E&gt; subList(int fromIndex, int toIndex)</td> 
   <td>截取部分 list</td> 
  </tr> 
 </tbody> 
</table>

> #### LinkedList的实现和常用方法的演示 ####
> 
>     public class MyLinkedList {
>         public static class ListNode {
>             public int val;
>             public ListNode prev;//前驱
>             public ListNode next;//后继
>             public ListNode(int val) {
>                 this.val = val;
>     } }
>     
>         public ListNode head;
>         public ListNode last;
>      //打印
>         public void display() {
>             ListNode cur = head;
>             while (cur != null) {
>                 System.out.print(cur.val + " ");
>                 cur = cur.next;
>             }
>         }
>      //求链表长度
>         public int size() {
>             ListNode cur = head;
>             int len = 0;
>             while (cur != null) {
>                 len++;
>             }
>             return len;
>         }
>     
>     //查找是否包含关键字key
>         public boolean contains(int key) {
>             ListNode cur = head;
>             while (cur != null) {
>                 if (cur.val == key) {
>                     return true;
>                 }
>                 cur = cur.next;
>             }
>             return false;
>         }
>     //头插法
>         public void addFirst(int data) {
>             ListNode node = new ListNode(data);
>             if (head == null) {
>                 head = node;
>                 last = node;
>             } else {
>                 head.prev = node;
>                 node.next = head;
>                 head = node;
>             }
>         }
>     
>     //尾插法
>         public void addList(int data) {
>             ListNode node = new ListNode(data);
>             if (head == null) {
>                 head = node;
>                 last = node;
>             } else {
>                 node.prev = last;
>                 last.next = node;
>                 last = node;
>             }
>         }
>      //任意位置插入
>         public void addIndex (int index ,int data){
>             if(index < 0 || index > size()){
>                 System.out.println("地址不合法");//此处可以抛出异常
>             }
>             if (index == size()){
>                 addList(data);
>                 return;
>             }
>             ListNode cur = fidIndexSubOne(index);
>             ListNode node = new ListNode(data);
>             node.next = cur ;
>             cur.prev.next = node;
>             node.prev = cur.prev;
>             cur.prev = node;
>         }
>     
>         //查找下标
>         private ListNode fidIndexSubOne(int index) {
>             ListNode cur = head;
>             int count = 0;
>             while (count != index - 1) {
>                 cur = cur.next;
>                 count++;
>             }
>             return cur;
>         }
>     
>         /*
>         删除第一次出现关键字为key的结点
>         特殊情况是删头和删尾
>          */
>         public void remove(int key) {
>             ListNode cur = head;
>             while (cur != null) {
>                 if (cur.val == key) {
>                     //删除的是头结点
>                     if (cur == head){
>                         head = head.next;
>                         //如果只有一个节点
>                         if (head != null) {
>                             head.prev = null;
>                         }
>                     }else {
>                         //中间部分的结点
>                         cur.prev.next = cur.next;
>                         if (cur.next != null){   //不是尾结点
>                             cur.next.prev = null;
>                         }else { //是尾结点
>                             last = last.prev;
>                         }
>                     }
>                         return;
>                 }
>                 cur = cur.next;
>             }
>     
>         }
>         /*
>         删除所有的关键字为key的结点
>         删除第一个的那个最后不return就行
>          */
>         public void removeAllKey(int key) {
>             ListNode cur = head;
>             while (cur != null) {
>                 if (cur.val == key) {
>                     //删除的是头结点
>                     if (cur == head){
>                         head = head.next;
>                         //如果只有一个节点
>                         if (head != null) {
>                             head.prev = null;
>                         }
>                     }else {
>                         //中间部分的结点
>                         cur.prev.next = cur.next;
>                         if (cur.next != null){   //不是尾结点
>                             cur.next.prev = null;
>                         }else { //是尾结点
>                             last = last.prev;
>                         }
>                     }
>     
>                 }
>                 cur = cur.next;
>             }
>     
>         }
>     
>         /*
>         清除
>         解法：遍历链表，把每一个结点的前驱和后继都置为空
>          */
>         public void  clear (){
>             ListNode cur = head ;
>             while (cur != null){
>                 ListNode curNext = cur.next;
>                 cur.prev = null;
>                 cur.next = null;
>                 cur = curNext;
>             }
>             head = null;
>             last = null;
>         }
>     
>     }

## ArrayList和LinkedList的区别 ##

<table> 
 <tbody> 
  <tr> 
   <td>不同点</td> 
   <td>ArrayList</td> 
   <td>LinkedList</td> 
  </tr> 
  <tr> 
   <td>存储空间上</td> 
   <td>物理上一定连续</td> 
   <td>逻辑上连续，但物理上不一定连续</td> 
  </tr> 
  <tr> 
   <td>随机访问</td> 
   <td>支持O(1)</td> 
   <td>不支持：O(N)</td> 
  </tr> 
  <tr> 
   <td>头插</td> 
   <td>需要搬移元素，效率低O(N)</td> 
   <td>只需修改引用的指向，时间复杂度为O(1)</td> 
  </tr> 
  <tr> 
   <td>插入</td> 
   <td>空间不够时需要扩容</td> 
   <td>没有容量的概念</td> 
  </tr> 
  <tr> 
   <td>应用场景</td> 
   <td>元素高效存储+频繁访问</td> 
   <td>任意位置插入和删除频繁</td> 
  </tr> 
 </tbody> 
</table>

[5a08614b235f48689f38049b8ae2ce4d.png]: https://img-blog.csdnimg.cn/5a08614b235f48689f38049b8ae2ce4d.png
[aceb19dff8844056b9a13d7936934fc1.png]: https://img-blog.csdnimg.cn/aceb19dff8844056b9a13d7936934fc1.png
[27c5bf4a2b834da8bfc4bc7da88347e3.png]: https://img-blog.csdnimg.cn/27c5bf4a2b834da8bfc4bc7da88347e3.png
[c1ede999dab24033a3f1f1354e0146d3.png]: https://img-blog.csdnimg.cn/c1ede999dab24033a3f1f1354e0146d3.png
[402de247dc0e421ca049e519ed018f14.png]: https://img-blog.csdnimg.cn/402de247dc0e421ca049e519ed018f14.png
[b15fefd68f6c4a019be3142b29bb2c3e.png]: https://img-blog.csdnimg.cn/b15fefd68f6c4a019be3142b29bb2c3e.png
[93441a01c4474d14abefb0ab9f139853.png]: https://img-blog.csdnimg.cn/93441a01c4474d14abefb0ab9f139853.png