💐 链表的概念与结构

前面讲解了 ArrayList 实现的顺序表，下面讲解线性表的另一种存储结构 链表；

在顺序表中，所有的元素都是在一段地址连续的存储单元上保存的，每个元素挨着每一个元素，通过下标也可以进行访问；但缺点是在非首尾的插入和删除时，需要移动大量的元素，时间复杂度较高；

所以，为了解决这个问题，就衍生出了另一种数据结构——链表

链表：链表是用一段物理地址不连续的存储单元依次存储数据的线性结构；

有n个节点组成，每个节点里面除了存储数值以外，还保存了下一个节点的地址，这样就可以通过地址依次找到对应的下一个节点；

💐链表的介绍

2、有头或者无头链表

3、循环或非循环链表

根据以上三种链表结构又可以组合成一下八种结构：

而最常用的是以上无头单向非循环链表、无头双向链表，下面就针对于两种链表进行详细的剖析！！！

💐链表的模拟实现

要想深刻的理解链表，就要亲手实现一下，这样才能深切的领会到链表他是怎样进行操作的，如何使用的！！！

首先，先思考，如果要实现一个链表的话，都要有哪些功能呢？下面我实现了一个链表功能，我将针对实现的链表每一部分进行一个剖析：

要实现一个链表，首先实现以下几个基础的功能：

1、节点的增加

2、节点的删除

3、数据的查找

4、节点的插入

//无头单向非循环链表实现
public class LinkedList {static class listNode {private int value;//结点中的值private listNode next;//下一个结点的地址public listNode(int value) {this.value = value;}}//创建一个链表public void createList() {ListNode listNode1 = new ListNode(20);ListNode listNode2 = new ListNode(30);ListNode listNode3 = new ListNode(40);ListNode listNode4 = new ListNode(50);ListNode listNode5 = new ListNode(60);listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode4;listNode4.next = listNode5;this.head = listNode1.next;}private listNode head;//第一个结点的地址//头插法public void addHead(int val) {ListNode listNode = new ListNode(val);listNode.next = head;head = listNode;return;      }//尾插法public void addLast() {ListNode listNode = new ListNode(val);ListNode cur = head;while(cur.next != null) {cur = cur.next;}cur.next = listNode;}//任意位置插入public void addIndex() {ListNode listNode = new ListNode(value);if(index == 0) {addHead(value);return;}if(index >figureSize() || index<0) {throw new IndexException("输入下标下标有误");}ListNode cur = head;ListNode pos = checkIndex(cur, index);//定义一个查找前一个节点的方法listNode.next = pos.next;pos.next = listNode;}//查找前一个节点方法public  static  ListNode checkIndex(ListNode cur, int index) {for(int i =0; i<index-1; i++) {cur = cur.next;}return cur;}//查找链表中是否包含查找的值public void contains() {ListNode cur = head;for(int i =0; i<figureSize(); i++) {if(cur.value == key) {System.out.println("链表中包含查找的值");return;}cur = cur.next;}System.out.println("链表中不包含查找的值");}//删除第一次出现的指定的值的结点public void delFirst(int key) {if(head == null) {return;}if(key == head.value) {head = head.next;return;}ListNode cur =  searchVal(key);if(cur == null) {System.out.println("没有您要删除的值");}assert cur != null;ListNode del = cur.next;cur.next = del.next;}//负责查找前一个节点public ListNode searchVal(int key) {ListNode cur = head;for(int i =0; i<figureSize(); i++) {if(key == cur.next.value) {return cur;}cur = cur.next;}return null;}//删除所有值为key的结点public void allPoint(int key) {if(head == null) {return;}ListNode prev = head;ListNode cur = head.next;while(cur != null){if(cur.value == key) {prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}if(head.value == key) {head = head.next;}}}//打印链表public void disPlay() {ListNode cur = head;while(cur != null) {System.out.println(cur.value +" ");cur = cur.next;}}//计算单链表的长度public void figureSize() {int count = 0;ListNode cur = head;while(cur!=null) {count++;cur = cur.next;}return count;}//清空节点public void clear() {head = null;}}

下面对这些功能进行一一的实现：

1、如何创建一个结点

在实现这些功能前，需要先知道如何去写这个结点的代码，下图讲解：


2、创建一个链表

在已经创建好一个结点的基础上，如何创建链表呢，下面来实现一下：

1、头插法

2、尾插法

3、任意位置插入

4、查找链表中是否包含查找的值

5、删除第一次出现的指定的值的结点

6、删除所有值为key的节点

6、清除节点

直接将头节点置为空，因为只要头节点中的地址为空了，那么后面的结点就没有被引用指向了，所以就会被内存回收

💐双向链表

单向链表在使用上有以下几个缺点：

1、在删除和尾插时，时间复杂度较高

2、只能从前向后访问，无法从后向前访问，限制较大

而下面，介绍的双向链表是非常牛掰的，包括以后在实现栈、队列、双向队列等方面，使用双向链表会方便很多，下面先简单介绍一下双向链表：

💐双向链表的模拟实现

如果想要彻底的理解链表的话，我的建议是，自己多模拟实现几遍这个链表，这样可以更加有利于你灵活的去使用，而不是只记住它的方法的功能。

//无头双向链表的实现
public class LinkedList {static class ListNode{private int val;private ListNode next;private ListNode prev;public ListNode(int val) {this.val = val;}}private ListNode head;private ListNode last;//头插法public void addFirst(int val) {ListNode node = new ListNode(val);//情况一：链表中无节点if(head == null) {head = node;last = node;return;}//情况二：链表中无节点node.next = head;head.prev = node;head = node;}//尾插法public void addLast(int val) {ListNode node = new ListNode(val);//情况一：链表中无节点if(head == null && last == null) {head = node;last = node;}//情况二：链表中有节点last.next = node;node.prev = last;last = last.next;}//任意位置插入public void addIndex(int pos,int val) {ListNode node = new ListNode(val);if(pos == 0) {addFirst(val);return;}if(pos == size()) {addLast(val);return;}//寻找要插入节点的位置ListNode cur = searchIndex(pos);cur.prev.next = node;node.next = cur;node.prev = cur.prev;cur.prev = node;}public ListNode searchIndex(int pos) {ListNode cur = head;for(int i =0; i<pos; i++) {cur = cur.next;}return cur;}//查找关键字key是否包含在链表中public void contains(int key) {if(searchKey(key)) {System.out.println("找到了！！！");}else{System.out.println("链表中不包含此数据！！！");}}public boolean searchKey(int key) {ListNode cur = head;while(cur != null && cur.val != key) {cur = cur.next;}if(cur != null) return true;return false;}//删除第一次出现关键字为key的节点public void remove(int key) {ListNode cur = searchFirst(key);if(cur == null) {System.out.println("链表中不包含此数据！！！");}//情况一：头节点为key时if(cur == head) {//只有一个节点时if(head == last) {head = null;last = null;}else {//多个节点时head = head.next;head.prev = null;}}else if(cur == last) {//情况二：尾结点为key时last = last.prev;last.next = null;}else {cur.prev.next = cur.next;cur.next.prev = cur.prev;}}public ListNode searchFirst(int key) {ListNode cur = head;while(cur != null && cur.val != key) {cur = cur.next;}if(cur != null) {return cur;}return null;}//删除所有值为key的节点public void removeAll(int key) {ListNode cur = head;while(cur != null) {cur = searchFirst(key);if(cur == null) {return;}//为头节点时//情况一：头节点为key时if(cur == head) {//只有一个节点时if(head == last) {head = null;last = null;}else {//多个节点时head = head.next;head.prev = null;}}else if(cur == last) {//情况二：尾结点为key时cur.prev.next = null;last = null;}else {cur.prev.next = cur.next;cur.next.prev = cur.prev;}}}//链表的长度public int size() {ListNode cur = head;int size = 0;while(cur != null) {size++;cur = cur.next;}return size;}//打印单链表public void display() {ListNode cur = head;while(cur != null) {System.out.print(cur.val+" ");cur = cur.next;}}//清空链表public void clear() {head = null;last = null;}
}

这里双链表与单链表的模拟非常相似，只要多多注意几种情况即可；

💐链表常用的方法

1、LinkedList的构造方法

方法	解释
LinkedList()	无参构造
public LinkedList(Collection< ? extends E > c)	使用其他集合容器中元素构造List

    public static void main(String[] args) {//使用无参构造方法List<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);//使用list构造LinkedListList<Integer> list2 = new LinkedList<>(list);list2.add(4);System.out.println(list2);}

2、LinkedList的其他方法

方法	解释
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除 index 位置的元素
boolean remove(Object o)	删除遇见的第一个o
E get(int index)	返回 index 位置的元素
E set(int index, E element)	将下标index 位置元素设置为 element
void clear()	清空链表
boolean contains(Object o)	判断 o 是否在链表中
int indexOf(Object o)	返回第一个 o 所在位置的下标
int lastIndexOf(Object o)	返回最后一个 o 位置的下标

以上方法与ArrayList中的使用都是一样的，这里就不再一一列举！

💐链表及顺序表的遍历

1、for循环的方式遍历

2、foreach的方式遍历

3、Iterator迭代器遍历

 public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);//foreach方式遍历for(int x: list) {System.out.print(x+" ");}System.out.println();//Iterator迭代器遍历--正向遍历Iterator<Integer> it = list.iterator();while(it.hasNext()) {System.out.print(it.next()+" ");}System.out.println();//Iterator迭代器反向遍历//因为反向遍历是从后向前遍历，所以需要知道元素个数ListIterator<Integer> it2 = list.listIterator(list.size());while(it2.hasPrevious()) {System.out.print(it2.previous()+" ");}System.out.println();}

💐ArrayList和LinkedList的差异

1、数据结构实现：

​ ArrayList是动态数组的数据结构实现，而LinkedList是双向链表的数据结构实现；

2、随机访问效率：

​ ArrayList比LinkedList在随机访问的时候效率要高，因为LinkedList是线性的数据存储方式，所以需要移 动指针指针从前向后依次查找；

3、增加和删除效率：

​ 在非首尾的增加和删除操作，LinkedList要比ArrayList效率要高，因为ArrayList增删操作时，会导致其他下标的元素进行移动，时间复杂度高；

4、内存空间占用：

​ LinkedList比ArrayList更占用空间，因为LinkedList的节点处了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素；

5、线程安全：

​ ArrayList 和 LinkedList都是不同步的，也就是不保证线程安全；

6、综合来说：

​ 在需要频繁读取聚合中的元素时，更推荐使用ArrayList，而在插入和删除操作较多时，推荐使用LinkedList；

**7、LinkedList的双向链表：**它的每一个节点中都有两个指针，分别指向前驱和后继，所以，从双向链表的任意一个节点开始，都可以很方便的访问它的前驱节点和后继节点；