Java语言----LinkedList 和链表的实现

阳光穿透心脏的1/2处 2024-04-20 14:25 83阅读 0赞

**目录**

一.链表概念

二.链表的分类

三.无头单向非循环链表的实现

3.1创建简单链表

3.2 链表基本方法实现

3.3四大基本功能

3.3.1.增加元素结点

3.3.2.查找元素结点

3.3.3.删除元素结点

3.3.4.结点信息修改

四.LinkedList是什么？

五.LinkedList使用方法

总结

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

> ?个人主页：[ tq02的博客\_CSDN博客-C语言,Java,Java数据结构领域博主][tq02_CSDN_-C_Java_Java]  
> ?梦的目标：努力学习，向Java进发，拼搏一切，让自己的未来不会有遗憾。  
> ?欢迎各位→点赞? + 收藏⭐ + 评论?+关注✨  
> 本章讲解内容：**链表** 的讲解
> 
> ![48b44c8bb51a4c12b587a22f8f6c26d1.jpeg][]
> 
> 使用编译器：IDEA

###  ###

## 一.链表概念 ##

> 链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
> 
> **逻辑结构：**
> 
> ![b0f702ca1109492e9a6ccc803fba66e5.png][]
> 
> 注：1、如上图，相当于火车车厢，每一节都相连在一起。
> 
> 2、各个结点连接的方式：通过**地址连接**，在内存当中，相邻结点在内存中不一定相邻。
> 
> 3、所有结点都在 **堆** 中申请出来。
> 
> 4、 每个结点包括两个部分：一个是存储数据元素的**数据域**，另一个是存储下一个结点地址的**指针域**。

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

## 二.链表的分类 ##

>  **1.单向、双向链表**
> 
> ![d0184c0358984cf095ebb4557fb01148.png][]
> 
> 注：无论单向还是双向，都是一个结点存储着下（上）一个结点。

> **2.带头、不带头结点 链表**
> 
> ![02580c9c547e44379042a749c90a3844.png][]
> 
> 注：无头和带头结点的主要区别：有一个起始结点。

> **3.循环、非循环链表** 
> 
> ![c8cf0cd1421d431ca3c8d48edc6041ee.png][]
> 
> 循环链表，就是指：头、尾结点有联系。

在链表结构中，这是主要的链表，但是这些链表种类还可以结合，如：带头双向循环链表、双向循环链表等等。

> 链表的种类很多，但都大同小异，我们主要学习两种链表：
> 
> 1、无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2、无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表

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

## 三.无头单向非循环链表的实现 ##

### 3.1创建简单链表 ###

![d7e0459971e940e68b7c99a7c7bf32e7.png][]

重点：每个结点存储着下一个结点的地址。

**创建链表**代码实现：

public class SingleLinkedList {
    
          static class List{
            
            int item;   //	存储数据
           
            List next;   //	指向下一个结点
            public List(int item) {
                this.item = item;
            }
            public List() {};
        }
    
    //各种链表实现方法
    
    //头插法
    public void addFirst(int data){
    } 
        //尾插法
    public void addLast(int data){
    } 
        //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
    } 
        //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
    return false;
    } 
        //删除第一次出现关键字为key的节点
    public void remove(int key){
    }
    
        //得到单链表的长度
    public int size(){
        return -1;
    }
        //链表的清空
    public void clear() {
    }
        //展示链表
    public void display() {}

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

###  ###

### **3.2 链表基本方法实现** ###

**1.遍历链表元素**

>     public void show() {
>             //这里不是定义了一个节点 这里只是一个引用
>             ListNode cur = head;
>             while (cur != null) {
>                 System.out.print(cur.val+" ");
>                 cur = cur.next;
>             }
>             System.out.println();
>         }

**2.获取链表长度**

>     public int size(){
>             int count = 0;
>             ListNode cur = head;
>             while (cur != null) {
>                 count++;
>                 cur = cur.next;
>             }
>             return count;
>         }

**3.查询数据**

>     public boolean contains(int key){
>             ListNode cur = head;
>             while (cur != null) {
>                 //如果val值 是引用类型  那么这里得用equals来进行比较！！！
>                 if(cur.val == key) {
>                     return true;
>                 }
>                 cur = cur.next;
>             }
>             return false;
>         }

**4.链表的清空**

>     public void clear() {
>             //将所有结点都置空，更为安全
>             while (head != null) {
>                 ListNode headNext = head.next;
>                 head.next = null;
>                 head = headNext;
>             }
>         }

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

###  ###

## 3.3四大基本功能 ##

### 3.3.1 、增加元素结点 ###

>  1.头插法：将新增结点放在链表的头部。
> 
>     public void addFirst(int data){
>             ListNode node = new ListNode(data);
>             node.next = head;
>             head = node;
>         }
> 
> 2.尾插法：将新增结点直接连接在链表的尾部
> 
>     public void addLast(int data){
>             ListNode node = new ListNode(data);
>             if(head == null) {
>                 head = node;
>                 return;
>             }
>             ListNode cur = head;
>             while (cur.next != null) {
>                 cur = cur.next;
>             }
>             //cur 指向的节点就是尾巴节点
>             cur.next = node;
>         }
> 
> 3.选择下标值，添加结点
> 
>     public void addIndex(int index,int data){
>             int len = size();
>             //0、判断index位置的合法性
>             if(index < 0 || index > len) {
>                 throw new IndexOutOfBounds("任意位置插入数据的时候，index位置不合法: "+index);
>             }
>             if(index == 0) {
>                 addFirst(data);
>                 return;
>             }
>             if(index == len) {
>                 addLast(data);
>                 return;
>             }
>             //1、先找到index-1位置的节点
>             ListNode cur = findIndex(index);
>             //2、进行插入
>             ListNode node = new ListNode(data);
>             node.next = cur.next;
>             cur.next = node;
>     }

### 3.3.2.查找元素结点 ###

查找一个元素，返回对应的下标值。

public ListNode findIndex(int index) {
            ListNode cur = head;
            while (index - 1 != 0) {
                cur = cur.next;
                index--;
            }
            return cur;//index-1位置的节点
        }

### 3.3.3.删除元素结点 ###

先找到对应的下标值，然后进行删除。删除方法，前一个结点连接到删除结点的后一个结点。

> ![3d1d387d2ef048bdacc8e78bbf969130.png][]
> 
> 如图，先断开d2与d3的连接，然后d2直接连接d4

代码实现：

//删除第一次出现关键字为key的节点
        public void remove(int key){
            if(head == null) {
                return;
            }
            //当删除结点为头结点
            if(head.val == key) {
                head = head.next;
                return;
            }
            ListNode prev = searchPrev(key); //返回待删除结点的前一个结点
            if(prev == null) {
                System.out.println("没有这个数据！");
                return;
            }
            ListNode del = prev.next;
            prev.next = del.next;
        }
    
        private ListNode searchPrev(int key) {
            ListNode prev = head;
            while (prev.next != null) {
                if(prev.next.val == key) {
                    return prev;
                }else {
                    prev = prev.next;
                }
            }
            return null;
        }

### 3.3.4.结点信息修改 ###

修改指定下标值的结点元素

public void searchPrev(int num,int date) {
            ListNode prev = head;
           for(int i=0;i<num-1;i++) {
                    prev = prev.next;  
            }
            prev.val=date;
        }

##  ##

## 四.LinkedList是什么？ ##

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

![5687bd7a23394845935fe037bfc56b59.png][]

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

## 五.LinkedList使用方法 ##

<table style="width:600px;"> 
 <tbody> 
  <tr> 
   <td style="width:107px;"></td> 
   <td style="width:293px;">方法</td> 
   <td style="width:198px;">解释</td> 
  </tr> 
  <tr> 
   <td colspan="1" style="width:107px;">&nbsp; &nbsp;<strong>构造方法</strong></td> 
   <td style="width:293px;">LinkedList()</td> 
   <td style="width:198px;">&nbsp; &nbsp;无参构造</td> 
  </tr> 
  <tr> 
   <td style="width:293px;">public LinkedList(Collection&lt;? extends E&gt; c)</td> 
   <td style="width:198px;">使用其他集合容器中元素构造List</td> 
  </tr> 
  <tr> 
   <td colspan="1" style="width:107px;">常用方法</td> 
   <td style="width:293px;">boolean add(E e)</td> 
   <td style="width:198px;">尾插e</td> 
  </tr> 
  <tr> 
   <td style="width:293px;">void add(int index,E element)</td> 
   <td style="width:198px;">将e插入到index位置</td> 
  </tr> 
  <tr> 
   <td style="width:293px;">boolean addAII(Collection&lt;? extends E&gt; c)</td> 
   <td style="width:198px;">尾插c中的元素</td> 
  </tr> 
  <tr> 
   <td style="width:293px;">E remove(int index)</td> 
   <td style="width:198px;">删除index位置元素</td> 
  </tr> 
  <tr> 
   <td style="width:293px;">boolean remove(Object o)</td> 
   <td style="width:198px;">删除遇到的第一个o</td> 
  </tr> 
  <tr> 
   <td style="width:293px;">E get( int index)</td> 
   <td style="width:198px;">获取下标index位置元素</td> 
  </tr> 
  <tr> 
   <td style="width:293px;">void clear()</td> 
   <td style="width:198px;">清空</td> 
  </tr> 
 </tbody> 
</table>

## 总结 ##

链表入门很简单，但是却有很多很难的题目，而我们只有将这些题目全部掌握了，对之后的栈、堆等题有更加深刻的知识。

题目推荐：[1、移除链表元素][1] [ 2、反转单链表][2] [3、返回链表中间节点][3]

[4、 合并两个有序链表][4_][ 5、 合并两个有序链表][4_] [ 6. 相交链表][6.] [7、回文链表][7]

[tq02_CSDN_-C_Java_Java]: https://blog.csdn.net/m0_74097410?type=blog
[48b44c8bb51a4c12b587a22f8f6c26d1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/c4bb9f0064f4468da0b27cd94e850d69.jpeg
[b0f702ca1109492e9a6ccc803fba66e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/72937059138a45d2995ca4817b905c43.png
[d0184c0358984cf095ebb4557fb01148.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/e9d79850ba0542c7978926de8b43bc81.png
[02580c9c547e44379042a749c90a3844.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/c22a0d9c7e984d979182c1c44c2808fe.png
[c8cf0cd1421d431ca3c8d48edc6041ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/74985c011b3b4ccd89be2a86b6457b7d.png
[d7e0459971e940e68b7c99a7c7bf32e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/5b94b4526bf3445aa9222293da9d426f.png
[3d1d387d2ef048bdacc8e78bbf969130.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a04368f768814ab9a4c887582322bde4.png
[5687bd7a23394845935fe037bfc56b59.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/fea5b334f5f949478f8a81aa387a16a4.png
[1]: https://leetcode.cn/problems/remove-linked-list-elements/description/
[2]: https://leetcode.cn/problems/reverse-linked-list/description/
[3]: https://leetcode.cn/problems/middle-of-the-linked-list/description/
[4_]: https://leetcode.cn/problems/merge-two-sorted-lists/
[6.]: https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
[7]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking