【数据结构Java版】链表之单链表的实现

Dear 丶 2024-04-03 13:26 95阅读 0赞

**目录**

一、ArrayList的缺陷

二、链表

（1）链表的概念及结构

（2）链表的类型

1.单向or双向

2.带头结点or不带头结点

3.循环or不循环

(2)单链表的实现

1.定义链表

2.遍历链表

3.关于链表的插入、删除操作

三、小结

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

##  一、ArrayList的缺陷 ##

由于ArrayList底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。为之java集合中又引入了LinkedList，即链表结构。

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

## 二、链表 ##

### （1）链表的概念及结构 ###

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

![6990588276224a03af817cf90c00dfc7.png][]

注意点:

1、链式结构在逻辑上是连续的，但是在物理上不一定连续

2、现实中的结点一般都是从堆上申请出来

3、从堆上申请的空间，是按照一定策略来分配的，两次申请的空间可以连续，可以不连续

### （2）链表的类型 ###

#### 1.单向or双向 ####

![0e46de68554949d4a14e69db5df44994.png][]

#### 2.带头结点or不带头结点 ####

![d18bfbbc8b5f4d08976e93492da3fc7b.png][]

#### 3.循环or不循环 ####

![9d8a0c2868664219aa0d114c23b12083.png][]

小贴士：重点掌握两种

1.无头单向非循环链表：

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。这种结构在笔试面试中出现很多。

2.无头双向链表：

在Java的集合框架库中LinkedList底层实现就是无头双向循环链表

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

###  (2)单链表的实现 ###

#### 1.定义链表 ####

>  结点（Node）：装元素的一种结构，至少包含：元素本身、指向下一个结点的线索。
> 
>  当下，我们都是使用头结点来表示一条链表Node head = null;头结点不存在，链表中一个结点都没有，链表中一个元素都没有，即链表是一条空的（empty）链表。
> 
>     // 这里定义的是结点对象，不是链表对象
>     // 我们当前的实现中，结点对象中就两个东西，分别：元素（int）、指向下一个结点对象的线索（引用）
>     public class Node {
>         public int val;     // 元素，类型是 int
>         public Node next;   // 类型是引用，Node 类型的引用：指向一个 Node 对象
>         // next：下一个
>         // 当 next == null 时，代表这个结点是所在链表的最后一个结点
>         
>         //构造方法
>         public Node(int val) {
>             this.val = val;
>             this.next = null;
>         }
>     }

#### 2.遍历链表 ####

> a.按照从前到后的顺序，依次访问链表中的元素 ，打印一条链表（依赖遍历链表中的所有元素）
> 
>  让 cur 指向 head 指向的对象（链表的头结点对象），当cur!=null时，表示链表中当前结点是存在的，用变量elements保存该结点的元素，打印出来，然后改变cur的指向使其指向下一个结点。cur 会经历链表中的每个结点：按照从前往后的顺序，每个结点只会经过一次。
> 
>     public static void printAllElements(Node head){
>         Node cur=heaad;
>         while(cur!=null){
>             int elements=cur.val;
>             System.out.printf(elements);
>             cur=cur.next;
>         }
>     }

> b.统计链表中的元素个数
> 
>  每个结点都会经过一次，所以每个元素都会经过一次，count++ 会被指向元素个数。这里使用for循环，也可以用while循环来表示。
> 
>     private static int sizeOf(Node head){
>         int count=0;
>         for(Node cur=head;cur!=null;cur=cur.next){
>             count++;
>         }
>         return count;
>     }

> c.查找链表中存在的某个元素
> 
>  目前只能做到从前往后遍历，无法做到从后往前遍历（代价很大）。所谓从前到后查找，就是要遍历链表中的每个元素，和 target 进行对比。cur.val==target说明找到了，就是 cur 目前指向的结点中包含和 target 相等的元素。如果走到最后，返回一个特殊的null引用，表示没有找到。
> 
>     private static Node searchElemtents(Node head ,int target){
>         Node cur=head;
>         while(cur!=null){
>             if(cur.val==target){
>                 return cur;
>             }
>             cur=cur.next;
>         }
>         return null;
>     }

> d.查找链表中所有的和某元素相等的结点
> 
>  可以用一个顺序表将所有结点保存下来。当找到符合条件的元素时就使用ArrayList中的add()添加方法，将其加入list中，最后结果返回list。
> 
> ArrayList详解：[http://t.csdn.cn/dieWE][http_t.csdn.cn_dieWE]
> 
>     private static List<Node> searchAllNode(Node head,int target){
>         List <Node> list = new ArrayList <>();
>         for(Node cur = head;cur!=null;cur=cue.next){
>             if(cur.val==target){
>                 list.add(cur);
>             }
>         }
>         return list;
>     }

> e.找到链表从前往后数，第n个结点（元素）的操作
> 
> 1)链表中至少有 3 个结点
> 
>  要想找到第三个结点，cur需要往后走两次。如图所示 ：
> 
> ![9c0d42809df6471694d9260ba2327a02.png][]
> 
> ![c55a48c0604f4f12b1fb97589f8585e9.png][]
> 
>     private static Node findThirdNode (Node head) {
>         Node cur = head;
>         // 向后跳 2 步
>         cur = cur.next;
>         cur = cur.next;
>         return cur;
>     }
> 
> 2)链表中至少有 n 个结点
> 
>  要想找到第n个结点，cur需要往后走n-1次。
> 
>     private static Node findNNode (Node head,int n) {
>         Node cur = head;
>         for(int i=0;i<n-1;i++){
>             cur=cur.next;
>         }
>         return cur;
>     }
> 
> 3)链表的长度可能小于 n
> 
> 此刻 cur 可能是 null，当 cur == null 时，cur.next 就会空指针异常。所以循环条件要多一个cur!=null。
> 
> 两种可能： 
> 
> cur == null：说明链表的长度 < n 
> 
> cur != null，说明，循环了 n - 1 次，找到了第 n 个结点
> 
> 两种情况，都可以通过返回 cur 进行处理
> 
>     private static Node findNNode (Node head,int n) {
>         Node cur = head;
>         for(int i = 0;i<n-1 && cur != null ;i++){
>             cur=cur.next;
>         }
>         return cur;
>     }

> f.找到链表从后往前数，第n个结点（元素）的操作
> 
> 1)找到链表的倒数第1个结点
> 
>  前提条件：链表中至少有 1 个结点
> 
>  最后一个结点的特征就是它指向为空,没有下一个结点。我们就可以将其cur.next!=null作为循环条件。
> 
>     private static Node findLastFirstNode(Node head) {
>             Node cur = head;
>             while (cur.next != null) {
>                 cur = cur.next;
>             }
>             return cur;
>         }
> 
> 2)找到链表的倒数第2个结点
> 
>  前提条件：链表中至少有 2 个结点
> 
>  倒数第二个结点的特征就是它下一个结点的指向为空。我们就可以将其cur.next.next!=null作为循环条件。
> 
>     private static Node findLastSecondNode(Node head) {
>             Node cur = head;
>             while (cur.next.next != null) {
>                 cur = cur.next;
>             }
>             return cur;
>         }
> 
> 3)找到链表的倒数第3个结点
> 
>  前提条件：链表中至少有3个结点
> 
>  同理cur.next.next.next!=null作为循环条件。
> 
>     private static Node finfLastThirdNode(Node head) {
>             Node cur = head;
>             while (cur.next.next.next != null) {
>                 cur = cur.next;
>             }
>             return cur;
>         }

#### 3.关于链表的插入、删除操作 ####

> a.头插、头删
> 
> 头插操作
> 
> 1）头插元素
> 
>  先把元素装入到对应的结点中；将创建出来的新结点和链表中的结点产生关系。
> 
> ![c0199ca155a2454d9bd971128d3fddbb.png][]
> 
>     private static Node headInsertionElement (Node head,int e){
>         Node node=new Node(e);
>         node.next=head;
>         return node;
>     }
> 
> 2）头插结点
> 
>  头插结点就是把指定结点插入单链表头部。
> 
> ![026f70649bce47bfb4476ac07fc93625.png][]
> 
>     private static Node headInsertionNode(Node head,Node node){
>         node.next=head;
>         return node;
>     }
> 
> 头删操作
> 
>  将第一个结点删除，注意链表是空的(empty)，没法删除结点，要抛出异常
> 
> ps:不理解异常操作的小朋友可以看这篇哦 [http://t.csdn.cn/nRUyW][http_t.csdn.cn_nRUyW]
> 
> ![fcd542dfcc604d48950278c5b0bda884.png][]
> 
>     private static Node headDelete(Node head){
>         if(head!=null){
>             throw new RuntimeException("链表是空的，无法进行头删操作");
>         }
>         return head.next;
>     }

> b.尾插、尾删
> 
> 尾插操作
> 
> 1）尾插元素
> 
> ![9494f51e4e6e48529e7479e3807d2a0a.png][]
> 
> ![b0295b39ec6e429085275a3eb8c5841c.png][]
> 
>  把元素放入结点中；分情况处理：一是链表是一个空的链表，没有头结点；二是链表中至少有一个结点。
> 
>     private static Node tailInsertElement(Node head ,int e){
>         Node node=new Node(e);
>         if(head==null){
>             node.next==null;
>             return node;
>         }
>         Node last=head;
>         while(last.next!=null){
>             last=last.next;//找最后一个结点
>         }
>         last.next=node;
>         node.next=null;//这句话可以省略
>         return head;
>     }
> 
> 2）尾插结点
> 
>  尾插结点和尾插元素的思路是一致的，只是少了一步将元素放入新结点中。
> 
>     private static Node tailInsertElement(Node head ,Node node){
>         if(head==null){
>             node.next==null;
>             return node;
>         }
>         Node last=head;
>         while(last.next!=null){
>             last=last.next;//找最后一个结点
>         }
>         last.next=node;
>         node.next=null;//这句话可以省略
>         return head;
>     }
> 
> 尾删操作
> 
>  尾删操作有三种情况：一是空链表；二是只有一个结点；三是至少有两个结点。对于空链表，通过抛出异常进行抱怨。只有一个结点是，可以返回null表示经过删除后，链表变为空链表了。三则需要找到倒数第二个结点，将倒数第二个结点的指向变为null。
> 
> ![b98789e7e95f4d6196bddb5e5f674280.png][]
> 
>     private static Node tailDeleteNode(Node node){
>         if(head==null){//空链表
>             throw new RunTimeException("空链表，不能进行删除");
>         }
>         if(head.next==null){//只有一个结点
>             return null;
>         }
>         Node lastOfLast=head;
>         while(lastOfLast.next.next!=null){//找到倒数第二个结点
>             lastOfLast=lastOfLast.next;
>         }
>         lastOfLast.next=null;//删除最后一个结点
>         return head;
>     }

> c.指定删除、插入
> 
> 1)将e插入到到指定结点之后
> 
>  先找到的 node 的下个结点，记为 nextOfNode；再找到 node 的下一个的下一个结点，记为 nextOfNext；让 node 的 next 指向 下下个结点。
> 
> ![c90ce8402d5a4edd9e8ccc4b07b1ea42.png][]
> 
>     private static void insertElements(Node node,int e){
>         Node newNode = new Node(e);
>         newNode.next=node.next;
>         node.next=newNode;
>     }

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

## 三、小结 ##

无头单链表的概念和操作相较而言是比较简单的，我们需要勤加练习，理解头结点和指向关系。

下面为大家整理了一些单链表的oj题供大家练习理解。

[http://t.csdn.cn/cFe7R][http_t.csdn.cn_cFe7R] [206. 反转链表][206.]

[http://t.csdn.cn/kivkD][http_t.csdn.cn_kivkD] [203. 移除链表元素][203.]

[http://t.csdn.cn/52UNu][http_t.csdn.cn_52UNu] [876. 链表的中间结点][876.]

[http://t.csdn.cn/Fx1XM][http_t.csdn.cn_Fx1XM] [21. 合并两个有序链表][21.]

[http://t.csdn.cn/WxzGm][http_t.csdn.cn_WxzGm] [链表中倒数第k个结点\_牛客题霸\_牛客网][k]

[http://t.csdn.cn/MMwUC][http_t.csdn.cn_MMwUC] [链表分割\_牛客题霸\_牛客网][Link 1]

[http://t.csdn.cn/rN6b4][http_t.csdn.cn_rN6b4] [链表的回文结构\_牛客题霸\_牛客网][Link 2]

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

![5b90dabd8adb488e9b77b7c74bac8d66.png][]

[6990588276224a03af817cf90c00dfc7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/899316bf11d942bc98837fd1dd31c9f9.png
[0e46de68554949d4a14e69db5df44994.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3cfd62bbaaa045759db901e65f975f43.png
[d18bfbbc8b5f4d08976e93492da3fc7b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/15fa26b6b02b424d8059191344808058.png
[9d8a0c2868664219aa0d114c23b12083.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/e9f8d893f286454f8d9d349eb4ec1f0c.png
[http_t.csdn.cn_dieWE]: http://t.csdn.cn/dieWE
[9c0d42809df6471694d9260ba2327a02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b7ce31b7aeaf45e4bb78978bfdbcc656.png
[c55a48c0604f4f12b1fb97589f8585e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f1966b07a2d34423a0198a4234aacdaf.png
[c0199ca155a2454d9bd971128d3fddbb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/51c6d5c191e04aa1a62602276ee93199.png
[026f70649bce47bfb4476ac07fc93625.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a9c35bdb4c1d4cfe875618d5f8d74340.png
[http_t.csdn.cn_nRUyW]: http://t.csdn.cn/nRUyW
[fcd542dfcc604d48950278c5b0bda884.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/38dedc73bbe5488aad8fa25c1acb27f3.png
[9494f51e4e6e48529e7479e3807d2a0a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/ceeb245a6a55429799ff1c761cac2db8.png
[b0295b39ec6e429085275a3eb8c5841c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/defe6b4abf0e48d3ad4c520a9377191a.png
[b98789e7e95f4d6196bddb5e5f674280.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/077f4a8e25f54cf7acdaccc6f53e457f.png
[c90ce8402d5a4edd9e8ccc4b07b1ea42.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/2f3cffa6570246f2a945e0b949f2206c.png
[http_t.csdn.cn_cFe7R]: http://t.csdn.cn/cFe7R
[206.]: https://leetcode.cn/problems/reverse-linked-list/
[http_t.csdn.cn_kivkD]: http://t.csdn.cn/kivkD
[203.]: https://leetcode.cn/problems/remove-linked-list-elements/
[http_t.csdn.cn_52UNu]: http://t.csdn.cn/52UNu
[876.]: https://leetcode.cn/problems/middle-of-the-linked-list/
[http_t.csdn.cn_Fx1XM]: http://t.csdn.cn/Fx1XM
[21.]: https://leetcode.cn/problems/merge-two-sorted-lists/
[http_t.csdn.cn_WxzGm]: http://t.csdn.cn/WxzGm
[k]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[http_t.csdn.cn_MMwUC]: http://t.csdn.cn/MMwUC
[Link 1]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[http_t.csdn.cn_rN6b4]: http://t.csdn.cn/rN6b4
[Link 2]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[5b90dabd8adb488e9b77b7c74bac8d66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f7eadad546be49ef8474d14a7f79a755.png