🎉🎉🎉点进来你就是我的人了
博主主页：🙈🙈🙈戳一戳,欢迎大佬指点!
人生格言：当你的才华撑不起你的野心的时候,你就应该静下心来学习!

欢迎志同道合的朋友一起加油喔🦾🦾🦾
目标梦想：进大厂，立志成为一个牛掰的Java程序猿，虽然现在还是一个🐒嘿嘿
谢谢你这么帅气美丽还给我点赞！比个心

目录

一.单向链表的实现

1. MySingleList的大概实现框架

2. addFirst--头插

3. addLast--尾插

4. addIndex--任意位置插入

5. contains--查找是否包含关键字key

6. remove--删除第一次出现的key

7. removeAllkey--删除所有key

8. (1)求单链表的长度；(2)打印单链表；(3)清除单链表

双向链表的简单介绍

二、双向链表的实现

1.基本框架的构建

2.打印链表

3.查找链表长度

4.头插法

5.尾插法

6.任意位置插入

7.查找是否存在关键词key

8.删除第一次出现的关键词key

9.删除所有关键词key

10、清空链表

三. 缺陷与区别（ArrayList&LinkedList）

链表的简单介绍 

链表是一种在物理上非连续的存储结构。在单向链表中，每一个节点都是一个对象，其中包含了数据和引用两部分，通过引用指向下一个节点。这种结构相比线性存储结构要复杂，并且由于增加了指针(引用)域导致内存开销更大，但它不像数组那样需要预先知道数据规模，可以充分利用计算机的内存空间。 

一.单向链表的实现

首先我们和ArrayList一样，将MySingleList单独定义为一个Java文件，然后每一个结点我们将它定义成一个静态内部类，这样就方便我们访问结点的成员，，还是和ArrayList一样，我们再定义一个Test类用来测试我们的单链表，写一个函数可以测试一下

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

1. MySingleList的大概实现框架

public class MySingleList {static class ListNode {public int value;public ListNode next;public ListNode(int value) {this.value = value;}}//简单的创建单链表public void createList() {ListNode listNode1 = new ListNode(23);ListNode listNode2 = new ListNode(22);ListNode listNode3 = new ListNode(23);listNode1.next = listNode2;listNode2.next = listNode3;this.head = listNode1;}public ListNode head;public void addFirst(int data){}public void addLast(int data){}public void addIndex(int index,int data){}public boolean contains(int key){return false;}public void remove(int key){}public void removeAllKey(int key){}public int size(){return -1;}public void display(){}public void clear(){}
}

2. addFirst--头插

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

 头插没啥细节点，以上图做辅助理解，我就不多赘述了，，

3. addLast--尾插

//尾插法public void addLast(int data) {ListNode node = new ListNode(data);//1.链表为空if(this.head == null) {this.head = node;} else {//2.链表不为空ListNode cur = this.head;while(cur.next != null) {cur = cur.next;}cur.next = node;}}

 这里要注意链表为空的时候，只需要将head指向node即可；

4. addIndex--任意位置插入

    public void addIndex(int index,int data) throws MySingleListIndexOutOfException{//1.先检查插入位置是否合法checkAddIndex(index);//2.分两种情况：1.头插 2.中间位置和尾插ListNode node = new ListNode(data);if(this.head == null) {this.head = node;return;}if(index == 0) {addFirst(data);return;}ListNode cur = findAddIndexSubOne(index);node.next = cur.next;cur.next = node;}private void checkAddIndex(int index) {if(index < 0 || index > this.size()) {throw new MySingleListIndexOutOfException("任意位置插入时，index不合法！");}}//找到待插入位置的前一个结点private ListNode findAddIndexSubOne(int index) {ListNode cur = this.head;while(index - 1 != 0) {cur = cur.next;index--;}return cur;}

 任意位置插的注意事项：1.先要判断下标是否合法；2.要分两种情况。

5. contains--查找是否包含关键字key

    public boolean contains(int key) {if(this.head == null) {System.out.println("链表为空！");return false;}ListNode cur = this.head;while(cur != null) {if(cur.value == key) {return true;}cur = cur.next;}return false;}

6. remove--删除第一次出现的key

//删除第一次出现关键字为key的节点public void remove(int key) {//1.判断有无结点if(this.head == null) {System.out.println("链表为空，不能删除！");return;}//2.删第一个if(this.head.value == key) {this.head = this.head.next;return;}//3.删后面的ListNode cur = this.head;cur = removeSubOne(key,cur);if(cur == null) {System.out.println("链表中没有这个元素！");return;}cur.next = cur.next.next;}private ListNode removeSubOne(int key, ListNode cur) {while(cur.next != null) {if(cur.next.value == key) {return cur;}cur = cur.next;}return null;}

 删除函数的注意事项：1.判空  2.分两种情况：删头和删剩下的，

7. removeAllkey--删除所有key

//方法一:时间复杂度O(N^2)
public void removeAllKey1(int key) {//1.判断有无结点if(this.head == null) {System.out.println("链表为空，不能删除！");return;}//处理中间和尾巴ListNode cur = this.head;while(cur != null) {//removeSubOne函数在上一个删除方法里头cur = removeSubOne(key,cur);if(cur != null) {cur.next = cur.next.next;}}//处理头if(this.head.value == key) {this.head = this.head.next;}
}
//方法二:时间复杂度O(N),只遍历一遍链表
public void removeAllKey2(int key){//特殊情况，首结点的值为key的处理情况(这里我们选择处理方式二)//处理方式一，直接将位于链表前面所有值为key的结点删除，更新头结点
//        while(head.value == key) {
//            head = head.next;
//        }if(head == null) {return;}Node pre = head;//前指针Node cur = head.next;//游标while(cur != null) {if(cur.value == key) {//删除当前cur结点pre.next = cur.next;cur = cur.next;}else{//不删除当前cur结点pre = cur;cur = cur.next;}}//处理方式二，在整个链表删除(结点值为key的)完毕后直接将首结点(值为key)更新if(head.value == key) {head= head.next;}
}

方法一:调用前写过的removeSubOne方法

1.如果先处理头，则需要写成循环，因为当链表所有结点都是待删除的情况时，一个if条件语句处理不了

2.while循环里面的条件不能写成cur.next == null，因为removeSubOne函数如果没找到待删除    的结点，它返回的是一个null，如果写成cur.next != null，则可能会报空指针异常

方法二:只遍历一遍链表,时间复杂度O(N)

使用前后指针解决这个问题, 前指针指向值为key的结点的前驱结点, 而后指针用来标识是否某个结点的值为key。

接下来就是几个简单的函数，也很重要，大家都能看得懂：

8. (1)求单链表的长度；(2)打印单链表；(3)清除单链表

    //得到单链表的长度public int size() {ListNode cur = this.head;int count = 0;while(cur != null) {count++;cur = cur.next;}return count;}public void display() {ListNode cur = this.head;while(cur != null) {System.out.print(cur.value+" ");cur = cur.next;}System.out.println();}public void clear() {this.head = null;}

 这里解释一下遍历链表循环的结束条件:(head不能动,否则打印一次就找不到头结点了)

 这里说说清除函数，我这种方式是比较暴力，也可以用温柔的方式：

用cur结点保存head的next，然后将head的val和next不断置为0或空，然后两个"指针"不断往后走

拓展:用递归和栈分别打印链表(栈后面文章有讲) 

//递归打印链表
public void disPlay(ListNode pHead) {if(pHead == null) {return;}if(pHead.next == null) {System.out.println(pHead.val + " ");return;}disPlay(pHead.next);System.out.println(pHead.val + " ");
}
//用栈打印链表
public void disPlay2(ListNode pHead) {Stack<ListNode> stack =new Stack<>();ListNode cur =pHead;while (cur != null) {stack.push(cur);cur =cur.next;}//遍历栈while (!stack.isEmpty()) {ListNode top = stack.pop();System.out.println(top.val + " ");}
}

双向链表的简单介绍

双向链表，顾名思义和单向链表很相似，均为链表，两者之间的操作也十分相近，最明显的不同之处就是双向链表的单个结点带有两个指针域，分别指向前后两个元素。

二、双向链表的实现

1.基本框架的构建

    //实现静态内部类，用于实现结点static class ListNode{public int val;//定义存放头尾结点的域public ListNode next;public ListNode prev;public ListNode(int val){this.val = val;}}

    public ListNode head;public ListNode tail;

      public void display(){ListNode cur = head;while(cur != null){System.out.print(cur.val+" ");cur = cur.next;}}

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

        public void addFirst(int data){//申请一个新的节点ListNode node = new ListNode(data);//当不存在元素时if(head == null){head = node;tail = node;}else{//当存在元素时head.prev = node;node.next = head;head = node;}}

        public void addLast(int data){ListNode node = new ListNode(data);if(head == null){head = node;tail = node;}else{tail.next = node;node.prev = tail;tail = node;}}

        public void addIndex(int index,int data){ListNode node = new ListNode(data);//1.判断index的合法性if(index < 0 || index > size()){System.out.println("index不合法");throw new IndexWrongFulException("index不合法");}//2.判断是头插还是尾插if(index == 0){addFirst(data);return;}if(index == size()){addLast(data);return;}//3.找到index位置的结点地址ListNode cur = find(index);cur.prev.next = node;node.next = cur;node.prev = cur.prev;cur.prev = node;}

public class IndexWrongFulException extends RuntimeException{public IndexWrongFulException(String message) {super(message);}
}

        private ListNode find(int index){ListNode cur = head;while(index != 0){cur = cur.next;index--;}return cur;}

7.查找是否存在关键词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 remove(int key){ListNode cur = head;while(cur != null){//循环寻找 key 的值if(cur.val == key){//当要删除的值是头节点if(cur == head){head = head.next;//判断删除的是不是单独的一个头节点if(head != null){head.prev = null;}else{tail = null;}}else{//一般情况删除cur.prev.next = cur.next;//判断删除的是否为尾部结点if(cur.next != null){cur.next.prev = cur.prev;}else{this.tail = cur.prev;}}return;}cur = cur.next;}}

        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{tail = null;}}else{cur.prev.next = cur.next;if(cur.next != null){cur.next.prev = cur.prev;}else{this.tail = cur.prev;}}}cur = cur.next;}}

        public void clear(){ListNode cur = head;while(cur != null){ListNode curNext = cur.next;cur.next = null;cur.prev = null;cur =curNext;}}