前言：
大家好，我是良辰丫🍓🍓🍓，今天我和大家一起了解一下数据结构中的链表，链表，顾名思义是用链子把一个个数据串连起了的，那么链表和顺序表又有什么不同呢？我们慢慢往下看。🚀🚀🚀

🧑个人主页：良辰针不戳
📖所属专栏：java数据结构
🍎励志语句：生活也许会让我们遍体鳞伤，但最终这些伤口会成为我们一辈子的财富。
💦期待大家三连，关注，点赞，收藏。
💌作者能力有限，可能也会出错，欢迎大家指正。
💞愿与君为伴，共探Java汪洋大海。

目录

• 单链表
• • 1.1 单链表的结构
  • 2.2 单链表的基本操作
  • • 2.2.1 头插法
    • 2.2.2 尾插法
    • 2.2.3 任意位置插入
    • 2.2.4 查找是否包含关键字key是否在单链表当中。
    • 2.2.5 删除第一次出现关键字为key的节点
    • 2.2.6 删除所有值为key的节点。
    • 2.2.7 得到单链表的长度
    • 2.2.8 清空单链表
    • 2.2.9 打印单链表

单链表

1.1 单链表的结构

链表由一个个节点串起来，其中节点又包括数据域和指针域，节点如下图所示。

下图为一个简单的单链表图，可能画的不好，嘿嘿嘿，大家见谅哈。其中数据域存放数据，指针域存放下一节点的地址，通过地址就可以间接访问下一节点。

2.2 单链表的基本操作

接下来我们就来搞一下单链表的基本操作，让大家更加深刻的了解链表。一般而言，我们经常使用无头的链表，我们今天就拿无头的链表进行举例。注意我们说的头节点是傀儡节点，就是它不存储链表的数据，只是一个哨兵作用。

2.2.1 头插法

先实例化一个新节点。

新节点与单链表建立联系。

head指向新的头结点。

大家看了上面的单链表头插法是不是感觉没那么难呢？嘿嘿嘿，只要找到了规律，其实一切都不是那么难。现在呢，大家需要记住一个先绑定后面的思想，这样防止前面链条断了无法串连起来链表。

public void addFirst(int data){ListNode listNode = new ListNode(data);listNode.next = head;head = listNode;}

2.2.2 尾插法

• 同样也是先申请一个头结点，注意，数据结构是很严谨的，需要把很多情况都考虑到。
• 头结点为空，说明链表没有元素，插入元素的节点直接成为了头结点。
• 链表尾插法的空间复杂度为O(n)，需要去遍历找到尾巴，才可以进行插入，相比于顺序表，不用担心它的容量不足。

尾节点与新节点进行连接。

public void addLast(int data){ListNode listNode = new ListNode(data);if(head == null) {head = listNode;return;}ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = listNode;}

2.2.3 任意位置插入

• 插入的位置如果不合法，直接抛出异常（但是在牛客网等做题网站不能这样，会被当做错误处理）。
• 在首位置插入元素，直接调用头插法，在尾位置插入元素，直接调用尾插法。
• 如果是在中间进行插入，找到要插入的前一个位置，这里我们用cur进行遍历，先进行右边绑定，然后再连接左边。

public void addIndex(int index,int data)throws ListIndexOutOfException{checkIndex(index);if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}ListNode cur = findIndexSubOne(index);ListNode listNode = new ListNode(data);listNode.next = cur.next;cur.next = listNode;}

private ListNode findIndexSubOne(int index) {ListNode cur = head;int count = 0;while (count != index-1) {cur = cur.next;count++;}return cur;}private void checkIndex(int index) throws ListIndexOutOfException{if(index < 0 || index > size()) {throw new ListIndexOutOfException("index位置不合法");}}

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

这个也是一个简单的遍历，找到关键字，返回true，否则就返回false。

public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}

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

• 如果链表没有数据，直接return。
• 如果头结点的数据与关键字相同，头结点直接后移一位。
• 找到要删除节点的前驱节点，没有要删除的节点返回空。
• 直接cur.next = del.next，有的小伙伴可能会有疑问，一个指令就可以删除嘛。那么它原来的指向呢？就像给变量赋值，cur.next给它赋予了新的指向，del.next或许还指向地址为0x112的节点，但是在访问链表的时候已经访问不到del的节点，如果大家觉得不合适可以把del.next置为空。

 public void remove(int key){if(head == null) {return ;//一个节点都没有}if(head.val == key) {head = head.next;return;}ListNode cur = searchPrev(key);if(cur == null) {return;}ListNode del = cur.next;//要删除的节点cur.next = del.next;}//找到要删除的前驱节点private ListNode searchPrev(int key) {ListNode cur = head;while (cur.next != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;//没有你要删除的节点}

2.2.6 删除所有值为key的节点。

• 删除所有值为key的节点，这里我们使用双指针思想。
• 头结点为空时直接退出，让prev指向头结点，cur指向head.next，然后进行遍历，找到关键字的时候就进行上面的删除操作，如果没有找到，指针后移，直到遍历完链表。

public void removeAllKey(int key){if(head == null) {return;}/*while(head.val == key) {head = head.next;}*/ListNode prev = head;ListNode cur = head.next;while (cur != null) {if(cur.val == key) {prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if(head.val == key) {head = head.next;}}

2.2.7 得到单链表的长度

通过遍历记录单链表长度。

//得到单链表的长度 O(N)public int size(){int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;}

2.2.8 清空单链表

单链表是通过头结点进行遍历的，头结点置为空时就找不到后面的节点了。

 public void clear() {head = null;}

2.2.9 打印单链表

遍历打印单链表。

public void display() {//如果说 把整个链表 遍历完成 那么 就需要 head == null// 如果说 你遍历到链表的尾巴  head.next == nullListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}

后序：
今天的单链表就讲到这里，希望大家有一定的收获，以路为马，不负韶华，朝着新的彼岸前行，加油。💞💞💞