阅读量:1
目录
一、前言
更详细的理论请移步笔者的另一文章
二、实现
2.1 类的创建
双向链表就是在单链表的基础上加上了一个 prev，存放上一个节点的地址
public class MyLinkedList { // 自己实现双向链表 static class ListNode { int val; ListNode prev;//前 ListNode next;//后 public ListNode(int val) { this.val = val; } } ListNode head = null;//头 ListNode last = null;//尾 } 需要什么方法在后续再补充
三、对链表操作实现
3.1 打印链表
可正序打印
也可逆序打印
public void printHead() { //正序打印 ListNode cur = this.head; if (cur == null) { System.out.println("当前链表为空!"); return; } while (cur != null) { System.out.println(cur.val); cur = cur.next; } } public void printLast(){ //逆序打印 ListNode cur = this.last; if(cur == null){ System.out.println("当前链表为空!"); return; } while (cur != null) { System.out.println(cur.val); cur = cur.prev; } }3.2 插入数据
3.2.1 申请新节点
public ListNode buyNode(int data) { // 申请新节点 ListNode newnode = new ListNode(data); return newnode; } 3.2.2 头插
链表为空就让链表的 head 和 last 都等于这个新节点
若链表不为空
原头节点的 prev 保存新插入节点的地址
新插入节点的 next 保存原头节点的地址
新插入节点成为新的头节点
public void addFirst(int data) { //头插 if (this.head == null) { this.head = buyNode(data); this.last = this.head; return; } ListNode newnode = buyNode(data); newnode.next = this.head;//新插入节点的 next 保存原头节点的地址 this.head.prev = newnode;//原头节点的 prev 保存新插入节点的地址 this.head = newnode;//新插入节点成为新的头节点 }测试
public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); linkedList.addFirst(1); linkedList.addFirst(2); linkedList.addFirst(3); linkedList.addFirst(4); linkedList.printHead(); System.out.println("=============="); linkedList.printLast(); }
3.2.3 尾插
链表为空就让链表的 head 和 last 都等于这个新节点
若链表不为空
last.next 保存新插入节点的地址
新插入节点的 prev 保存 last 的地址
新插入节点成为 last
public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); linkedList.addLast(5); linkedList.addLast(6); linkedList.addLast(7); linkedList.addLast(8); linkedList.printHead(); System.out.println("=============="); linkedList.printLast(); }测试
public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); linkedList.addLast(5); linkedList.addLast(6); linkedList.addLast(7); linkedList.addLast(8); linkedList.printHead(); System.out.println("=============="); linkedList.printLast(); }
3.2.4 链表长度
public int size() { //返回链表节点个数 ListNode cur = this.head; int count = 0; while (cur != null) { count++; cur = cur.next; } return count; }3.2.5 任意位置插入
插入时需要检查坐标的合法性
合法区间是[0,size()]
指定位置合法后
新节点的 prev 存储原位置节点 prev 的地址
新节点的 next 存储原位置节点的地址
原位置的 prev 存储为新节点的地址
原位置前一节点的 next 存储为新节点的地址
为方便观察修改一下打印方法
public void printHead() { //正序打印 ListNode cur = this.head; if (cur == null) { System.out.println("当前链表为空!"); return; } while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } } public void printLast() { //逆序打印 ListNode cur = this.last; if (cur == null) { System.out.println("当前链表为空!"); return; } while (cur != null) { System.out.print(cur.val + " "); cur = cur.prev; } }测试
public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); linkedList.addLast(5); linkedList.addLast(6); linkedList.addLast(7); linkedList.addLast(8); linkedList.printHead(); System.out.println(); System.out.println("=========="); linkedList.addAny(1, 99); linkedList.addAny(2, 199); linkedList.addAny(3, 299); linkedList.addAny(0, 122); linkedList.addAny(linkedList.size(), 999); linkedList.printHead(); } 
3.3 删除数据
3.3.1 头删
由于此处是基础数据类型
不需要对节点中存储的数据进行置空
如果存储的是引用数据类型就需要置空
将原头节点置空
头节点的下一个节点成为新的头节点
新的头节点的 prev 需要置空
public void removeFirst() { //头删 if (this.head == null) { System.out.println("当前链表为空！"); return; } ListNode tmp = this.head.next; // this.head.val = null;//由于此处是基础数据类型 不需要对节点中存储的数据进行置空 如果存储的是引用数据类型就需要置空 this.head = null; this.head = tmp; if(this.head == null){ this.last = null; }else { this.head.prev = null;//新的头节点的 prev 需要置空 } } 测试
public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); linkedList.addFirst(1); linkedList.addFirst(2); linkedList.addFirst(3); linkedList.addFirst(4); linkedList.printHead(); linkedList.removeFirst(); System.out.println(); linkedList.printHead(); linkedList.removeFirst(); System.out.println(); linkedList.printHead(); linkedList.removeFirst(); System.out.println(); linkedList.printHead(); linkedList.removeFirst(); System.out.println(); linkedList.printHead(); }
3.3.2 尾删
由于此处是基础数据类型
不需要对节点中存储的数据进行置空
如果存储的是引用数据类型就需要置空
尾节点的前一个节点成为新的尾节点
新的尾节点的 next 需要置空
public void removeLast() { //尾删 if (this.last == null) { System.out.println("当前链表为空！"); return; } // this.last.val = null;由于此处是基础数据类型 不需要对节点中存储的数据进行置空 如果存储的是引用数据类型就需要置空 ListNode tmp = this.last.prev; this.last = null; this.last = tmp; if(this.last == null){ this.head = null; } else { this.last.next = null;//新的尾节点的 next 需要置空 } }测试
public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); linkedList.addFirst(1); linkedList.addFirst(2); linkedList.addFirst(3); linkedList.addFirst(4); linkedList.printHead(); linkedList.removeLast(); System.out.println(); linkedList.printHead(); linkedList.removeLast(); System.out.println(); linkedList.printHead(); linkedList.removeLast(); System.out.println(); linkedList.printHead(); linkedList.removeLast(); System.out.println(); linkedList.printHead(); }
3.3.3 删除指定位置数据
删除时需要检查坐标的合法性
合法区间是[0,size())
将删除位置前节点的 next 保存为删除节点位置后节点的地址
将删除位置后节点的 prev 保存为删除节点位置前节点的地址
public void removeAny(int index) { if (this.head == null) { System.out.println("当前链表为空！"); return; } if (index < 0 && index >= this.size()) { throw new IndexillegalityException("下标不合法！"); } if (index == 0) { removeFirst(); return; } else if (index == size() - 1) { removeLast(); return; } ListNode cur = this.head; while (index != 0) { //找要删除的节点 cur = cur.next; index--; } cur.prev.next = cur.next; cur.next.prev = cur.prev; cur = null; }测试
public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); linkedList.addFirst(1); linkedList.addFirst(2); linkedList.addFirst(3); linkedList.addFirst(4); linkedList.printHead(); System.out.println(); linkedList.removeAny(1); linkedList.printHead(); System.out.println(); linkedList.removeAny(1); linkedList.printHead(); System.out.println(); linkedList.removeAny(1); linkedList.printHead(); System.out.println(); linkedList.removeAny(1); linkedList.printHead(); System.out.println(); }
抛了一个空指针异常
说明在链表只剩下一个节点的时候需要特殊处理
public void removeAny(int index) { if (this.head == null) { System.out.println("当前链表为空！"); return; } if (index < 0 && index >= this.size()) { throw new IndexillegalityException("下标不合法！"); } if (index == 0) { removeFirst(); return; } else if (index == size() - 1) { removeLast(); return; } ListNode cur = this.head; while (index != 0) { //找要删除的节点 cur = cur.next; index--; } if(cur == null ){ //判断是否只有一个节点 //cur在移动后如果等于空，就说明一定只剩下一个节点 this.last = null; this.head = null; }else { cur.prev.next = cur.next; cur.next.prev = cur.prev; cur = null; } } 
3.3.4 删除指定数据
将删除位置前节点的 next 保存为删除节点位置后节点的地址
将删除位置后节点的 prev 保存为删除节点位置前节点的地址
对头和尾做单独处理
public void removeData(int data){ //删除指定数据 if (this.head == null) { System.out.println("当前链表为空！"); return; } ListNode cur = this.head; while (cur != null){ if(cur.val == data){ if(cur == head){ removeFirst(); return; }else if(cur == last){ removeLast(); return; }else { cur.prev.next = cur.next; cur.next.prev = cur.prev; } } cur = cur.next; } System.out.println("当前链表中没有您要删除的数据"); }测试
public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); linkedList.addFirst(1); linkedList.addFirst(2); linkedList.addFirst(3); linkedList.addFirst(4); linkedList.printHead(); System.out.println(); linkedList.removeData(4); linkedList.printHead(); System.out.println(); linkedList.removeData(3); linkedList.printHead(); System.out.println(); linkedList.removeData(2); linkedList.printHead(); System.out.println(); linkedList.removeData(1); linkedList.printHead(); }
3.3.5 删除所有指定数据
将链表中所有节点值等于 data 的节点全部删除
将3.3.4 的方法中进行删除后继续遍历链表
遇到节点值为 data 的继续删除即可
public void removeDataAll(int data){ //删除所有节点值为data的节点 if (this.head == null) { System.out.println("当前链表为空！"); return; } boolean flg = false; ListNode cur = this.head; while (cur != null){ if(cur.val == data){ flg = true; if(cur == head){ removeFirst(); }else if(cur == last){ removeLast(); }else { cur.prev.next = cur.next; cur.next.prev = cur.prev; } } cur = cur.next; } if(!flg){ System.out.println("当前链表中没有您要删除的数据！"); }else { System.out.println("删除成功！"); } }测试
public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); linkedList.addFirst(4); linkedList.addFirst(4); linkedList.addFirst(4); linkedList.addFirst(4); linkedList.addFirst(2); linkedList.addFirst(1); linkedList.addFirst(5); linkedList.addFirst(6); linkedList.addFirst(4); linkedList.printHead(); System.out.println(); linkedList.removeDataAll(4); linkedList.printHead(); System.out.println(); }
3.3.6 删除链表
即将所有节点全部删除
让每个节点的 next ,prev 都置空
public void clear(){ //删除整个链表 if (this.head == null) { System.out.println("当前链表为空！"); return; } ListNode cur = this.head; while (cur!= null){ // cur.val = null;如果是引用数据类型就需要置空 ListNode tmp = cur.next; cur.next = null; cur.prev = null; cur = tmp; } this.head = null; this.last = null; }四、LinkedList
Java 中已经封装好了 LinkedList 类
4.1 什么是 LinkedList
LinkedList 官方文档 https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html
LinkedList 的底层是双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
1. LinkedList 实现了 List接口 2. LinkedList 的底层使用了双向链表 3. LinkedList 没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问 4. LinkedList 的任意位置插入和删除元素时效率比较高，时间复杂度为O(1) 5. LinkedList 比较适合任意位置插入的场景4.2 LinkedList 的使用
4.2.1 LinkedList的构造方法
public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); LinkedList<Number> linkedList2 = new LinkedList<>(); }4.2.2 常用方法
| 方法 | 功能 |
| boolean add(E e) | 尾插 e |
| void add(int index, E element) 将 e 插入到 index 位置 | 将 e 插入到 index 位置 |
| boolean addAll(Collection<? extends E> c) | 尾插 c 中的元素 |
| E remove(int index) | 删除 index 位置元素 |
| 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 的下标 |
| List<E> subList(int fromIndex, int toIndex) | 截取部分 list |
| …… | …… |
这里只说说 addAll 和 subList
public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.add(new Integer(2)); linkedList.add(new Integer(3)); linkedList.add(new Integer(4)); linkedList.add(new Integer(5)); System.out.println(linkedList); List<Integer> list2 = linkedList.subList(1,3); System.out.println(list2); linkedList.set(1,10); System.out.println(list2); }
与 ArrayList 实现的 subList
subList 只是将对应区间的地址截取出来返回
而不是产生新的对象返回
与 ArrayList 实现的 addAll 类似
形参 c 的类型必须是实现了 Collection 接口
且其中存放的数据必须是 E 本身或 E 的子类
public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.add(new Integer(2)); linkedList.add(new Integer(3)); linkedList.add(new Integer(4)); linkedList.add(new Integer(5)); LinkedList<Number> linkedList2 = new LinkedList<>(linkedList); System.out.println(linkedList); System.out.println(linkedList2); }
五、ArrayList和LinkedList的区别
| 不同点 | ArrayList | LinkedList |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 头插 | 需要搬移元素，效率低O(N) | 只需修改引用的指向，时间复杂度为O(1) |
| 插入 | 空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
