数据结构之LinkedList与链表（上）

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版）

手动实现单链表的源码

手动实现双链表的源码

分析 LinkedList 的源码

LinkedList的使用

常用方法

ArrayList和LinkedList的区别

单链表的学习，点我

上面这篇博文是关于链表的基础知识、链表的分类以及单链表的实现。都详细的进行了说明。

手动实现单链表的源码

下面是Java版的链表源码：

// 无头单向非循环链表实现
public class SingleLinkedList {// 链表是有一个一个的节点组成，因此得先创建节点// 链表的节点由两部分组成：数值域与地址域// 既然有多个部分，那么就可以写在类中// 又因为节点是在单链表中（单链表中包含一个又一个的节点）// 因此节点就可以成为单链表的内部类// 静态内部类可以只通过类名来访问，方便public static class listNode {public int val; // 存放数值// 是一个引用指向下一个节点的地址public listNode next; // 指向下一个节点的地址public listNode(int val) {// 新创建的节点的next应该为null，因为next为字段。因此其默认值为null，无需修改this.val = val;}}public listNode head; // 头节点// 头插法public void addFirst(int data){listNode newNode = new listNode(data);// 先判断这个链表是否有节点if (head == null) {//那么新增的这个节点就是头节点head = newNode;}else {// 把新节点的next指向head，并且把head指向新节点newNode.next = head;head = newNode;}}// 尾插法public void addLast(int data){listNode newNode = new listNode(data);// 先判断这个链表是否为空if (head == null) {head = newNode;}else {listNode cur = head;// 找到尾节点while (cur.next != null) {cur = cur.next;}// 将尾节点的next指向新节点，就完成了尾插cur.next = newNode;}}// 任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data) throws AddIndexofException{// 先判断插入的位置是否合法if (index < 0 || index > size()) {throw new AddIndexofException("addIndex() index位置异常");}// 先判断这个链表是否为空，如果是空，既可以采取尾插，也可以采取头插if (head == null) {addLast(data);}else if (index == 0) {addFirst(data);}else {listNode newNode = new listNode(data);// 找到pos-1的位置listNode cur = head;while (index-1 > 0) {cur = cur.next;index--;}// 两个的顺序不能变newNode.next = cur.next;cur.next = newNode;return true;}return false;}// 查找是否包含关键字key是否在单链表当中public boolean contains(int key){// 先判断链表是否为空if (head == null) {return false;}listNode cur = head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}// 删除第一次出现关键字为key的节点public void remove(int key) throws SingleLinkedisEmptyException, NotFindException{// 判断链表是否为空if (head == null) {throw new SingleLinkedisEmptyException("单链表为空异常");} else if (head.next == null) {// 如果链表中只有一个元素的话，直接删除就行if (head.val == key) {head = null;return;}else {throw new NotFindException("找不到要删除的数异常");}        } else if (head.val == key) {// 头删head = head.next;return;} else {listNode cur = head;while (cur.next != null) {if (cur.next.val == key) {// 开始删除listNode del = cur.next.next;cur.next = cur.next.next;// 可能这里会有疑惑被删除的节点的next不是还指向了其后一个位置吗？// 这样会不会有问题呢？当一个对象每人引用时，就会被标记回收// 当然手动置为null，也是可以的del = null;return;}cur = cur.next;}}throw new NotFindException("找不到要删除的数异常");}// 删除所有值为key的节点public void removeAllKey(int key){boolean flag = true;// 判断链表是否为空if (head == null) {throw new SingleLinkedisEmptyException("单链表为空异常");} else if (head.next == null) {// 如果链表中只有一个元素的话，直接删除就行if (head.val == key) {head = null;return;}else {throw new NotFindException("没有找到要删除的数据！");}} else if (head.val == key) {// 如果头节点的值key，那就循环删除直至头节点的不为keywhile (head.val == key) {// 如果删除的只剩下最后一个节点了，就删除返回就行if (head.next == null) {head = head.next;return;}}flag = false;} else {listNode cur = head;while (cur.next != null) {if (cur.next.val == key) {// 开始删除listNode del = cur.next.next;cur.next = cur.next.next;// 可能这里会有疑惑被删除的节点的next不是还指向了其后一个位置吗？// 这样会不会有问题呢？当一个对象每人引用时，就会被标记回收// 当然手动置为null，也是可以的del = null;flag = false;}else {// 可能会出现连续的数字的情况// 因此删除之后，还得判断这个cur之后的元素是否为keycur = cur.next;}}}if (flag) {throw new NotFindException("找不到要删除的数异常");}}// 得到单链表的长度public int size(){// 先判断这个链表是否为空if (head == null) {return 0;}listNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}// 打印链表public void display(){listNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}// 清空链表public void clear(){// 暴力解法：把head置为null，那么就没有引用指向这个头节点了// 那么这个头节点就会被垃圾回收器给回收掉// head = null;// 上面那种方式可能会出现不安全的情况，因此采用遍历的形式listNode cur = head;while (cur != null) {// cur.val = null;listNode curNext = cur.next;cur.next = null;cur = curNext;}head = null;}
}

AddlndexofException异常：

public class AddIndexofException extends RuntimeException{public AddIndexofException() {super();}public AddIndexofException(String msg) {super(msg);}
}

NotFindException异常：

public class NotFindException extends RuntimeException{public NotFindException() {super();}public NotFindException(String msg) {super(msg);}
}

SingleLinkedisEmptyException异常：

public class SingleLinkedisEmptyException extends RuntimeException{public SingleLinkedisEmptyException() {super();}public SingleLinkedisEmptyException(String msg) {super(msg);}
}

这里来说明一下：为什么节点的引用是节点类型？

首先，我们最开始在学习引用的时候，说过引用其实就是一个变量类型，用来存放地址。而在C语言中是用指针来存放地址，按照C语言的说法，节点的地址就得用节点类型的指针来接收。那么listNode 类型的 next，就得用 listNode 来接收（引用）。就好像，在 new 应该对象时，这个对象的地址会给到一个引用变量，而这个引用变量的类型就是 new 关键字后面的。例如：Person person = new Person(); 。

双链表的学习，点我

上面这篇博文是关于链表的基础知识、链表的分类以及单链表的实现。都详细的进行了说明。

手动实现双链表的源码

public class MyLinkedList implements LinkedList {//创建一个节点内部类static class ListNode {int val;ListNode prev;ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;// 头插@Overridepublic void addFirst(int data) {// 创建一个新的节点ListNode newNode = new ListNode(data);// 先判断链表是否为空if (head == null) {head = newNode;last = newNode;}else {newNode.next = head;head.prev = newNode;head = newNode;}}@Overridepublic void addLast(int data) {// 创建一个新的节点ListNode newNode = new ListNode(data);// 先判断链表是否为空if (head == null) {head = newNode;last = newNode;}else {last.next = newNode;newNode.prev = last;last = newNode;}}@Overridepublic void addIndex(int data, int index) throws addIndexOfException {// 判断这个index是否合法if (index < 0 || index > size()) {// 抛异常throw new addIndexOfException("下标位置不合法异常！");}if (index == 0) {// 头插addFirst(data);} else if (index == size()) {// 尾插addLast(data);} else {// 创建一个新的节点ListNode newNode = new ListNode(data);ListNode cur = head;// 找到要插入的前一个位置while (index-1 > 0) {cur = cur.next;index--;}ListNode curNext = cur.next;cur.next = newNode;newNode.next = curNext;newNode.prev = cur;curNext.prev = newNode;}}@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if (head == null) {// 链表为空，就抛异常throw new LinkedListIsEmptyException("链表为空异常！");}else if (head.next == null) {// 链表里面只有一个元素if (head.val == key) {head = null;last = null;return;}else {throw new NotFindException("找不到要删除的数异常！");}}else {// 头删if (head.val == key) {head = head.next;return;} else if (last.val == key) {// 尾删last = last.prev;last.next = null;return;}ListNode cur = head;while (cur != null) {if (cur.val == key) {// 开始删除ListNode curNext = cur.next;cur.prev.next = curNext;curNext.prev = cur.prev;return;}cur = cur.next;}throw new NotFindException("找不到要删除的数异常！");}}@Overridepublic void removeAllkey(int key) {if (head == null) {// 链表为空，就抛异常throw new LinkedListIsEmptyException("链表为空异常！");}else if (head.next == null) {// 链表里面只有一个元素if (head.val == key) {head = null;last = null;return;}else {throw new NotFindException("找不到要删除的数异常！");}}else {boolean flag = false;// 头删while (head.val == key) {flag = true;head = head.next;if (head == null) {return;}}while (last.val == key) {// 尾删flag = true;last = last.prev;last.next = null;}ListNode cur = head;while (cur != null) {if (cur.val == key) {// 开始删除flag = true;ListNode curNext = cur.next;cur.prev.next = curNext;curNext.prev = cur.prev;}cur = cur.next;}if (!flag) {throw new NotFindException("找不到要删除的数异常！");}}}@Overridepublic int size() {ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void clear() {// 暴力做法// head = last = null;// 温柔做法ListNode cur = head;while (cur != null) {// cur.val = null;cur.prev = null;ListNode curNext = cur.next;cur.next = null;cur = curNext;}head = last = null;}@Overridepublic void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}
}

addlndexOfException异常：

public class addIndexOfException extends RuntimeException {public addIndexOfException(String msg) {super(msg);}public addIndexOfException() {super();}
}

LinkedListlsEmptyException异常：

public class LinkedListIsEmptyException extends RuntimeException {public LinkedListIsEmptyException(String msg) {super(msg);}public LinkedListIsEmptyException() {super();}
}

NotFindException异常：

public class NotFindException extends RuntimeException {public NotFindException(String msg) {super(msg);}public NotFindException() {super();}
}

单链表和双链表在代码上，总体来说，大差不差。

分析 LinkedList 的源码

LinkedList的底层使用了双向链表

LinkedList的使用

构造方法与 ArrayList 差不多，只有一个无参的和一个带参数的。带参的类型是实现了Collection接口就行。

常用方法

方法	说明
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 lastlndexOf(Object o)	返回最后一个o的下标
List<E> subList(int fromlndex, int tolndex)	截取部分list

同样这里 subList 的截取不会产生新的对象。

其遍历方式和 ArrayList 是一样的。

ArrayList和LinkedList的区别

区别	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持0(1)	不支持：O(N)
头插	需要搬移元素，效率低O(N)	只需修改引用的指向，时间复杂度为O(1)
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁