题外话: 篇幅停了一下,特意去看看其他人写的类似的内容;然后发现类似博主喜欢画图,喜欢讲解原理。
(于是我就在想了,理解数据结构的确需要画图,但我的文章写给懂得人看,只配少量图即可,省事儿)
一般性的,都能想到 dummy head 的技巧以及Java中LinkedList(底层是双向(循环)链表)。
Leetcode 返回一个头结点对象,就算返回整个链表了,而我们自己实现一般会 new 一个链表对象实例,然后调用该实例的各类方法来操作整个链表。
之前写的动态数组并非真正动态,因为其内部封装的是一个容量不可变的静态数组。
而这里的链表则是真正的 动态数据结构 (不需要处理固定容量问题,即增删效率高,但由于不知道实际地址/索引,所以也丧失了随机访能力)。
辅助其他数据结构:二分搜索树,AVL/红黑树,它们基于链表实现。
基本构成: 节点 + 指针。
class Node { E e; Node next; }
为了方便或者统一操作,一般会有 Node head,头结点。
之所以用 dummy head 的原因,其实是为了操作简便。(不用也可以,但实现上的写法就...)
有了 dummy head,头结点前面也有节点了,所以整个操作行为是统一的,一致的,不需要再做情况区分。
(下面有案例)
先把实现的框架列一下,大致如下:
package linkedlist; public class LinkedList<E> { //定义一个内部类,作为节点类 private class Node { public E e; public Node next; //便于 LinkedList 访问 public Node(E e, Node next) { this.e = e; this.next = next; } public Node(E e){ this(e, null); } public Node(){ this(null, null); } @Override public String toString() { return e.toString(); } } //操作链表的辅助变量 private int size; private Node head; //头结点 //构造函数 public LinkedList() { head = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } }
然后再来实现其中的增删改查,此时先不设置虚拟头节点。
这里实现的头部添加 (后续再扩展其他添加):
public void addFirst(E e) { /* Node node = new Node(e); node.next = head; head = node; */ //简写 head = new Node(e, head); //维护链表长度 size++; }
在 某个位置 插入元素:
//指定的 index 位置添加元素 (先要找到 index 前一个位置) // index 从 0 ~ size-1 public void add(int index, E e) { // 索引有问题 if (index < 0 || index > size) { //当 index == size 时,表示在末尾添加 throw new IllegalArgumentException("Add Failed, Illegal index"); } if (index == 0) { addFirst(e); } else { Node prev = head; //找到指定位置前一个节点 for (int i = 0; i < index - 1; i++) { prev = prev.next; } //创建一个新节点 /*Node node = new Node(e); node.next = prev.next; prev.next = node;*/ //简写 prev = new Node(e, prev.next); size++; } }
(可以看到上面确实是区分不同的情况了的)
此时在末尾添加元素,即 index = size 的位置添加,直接调用 addLast 即可:
//在末尾添加元素 public void addLast(E e){ add(size, e); }
不着急往后探索,这里先把头节点优化一下,即加入 dummy head,统一整个操作流程。
上面的操作 add
,由于链表头结点 head 并没有前面一个节点,所以插入的时候确实要特殊一些。(如果第一个节点之前有节点,那么整个操作就统一了)
优化方法,在头结点前面添加一个 虚拟节点
,即不存储任意元素的节点。
内部机制,用户(client) 不知道虚拟节点的存在。(只是为了方便逻辑操作)。
构造函数需要修改,初始化 LinkedList 的时候就要创建一个节点
public LinkedList1() { dummyHead = new Node(null, null); size = 0; }
添加元素可以统一用 add,然后让 addFirst 和 addLast 调用 add 方法即可。
//指定的 index 位置添加元素 (先要找到 index 前一个位置) // index 从 0 ~ size-1 public void add(int index, E e) { // 索引有问题 if (index < 0 || index > size) { //当 index == size 时,表示在末尾添加 throw new IllegalArgumentException("Add Failed, Illegal index"); } //因为在实际 index 取值范围内,总能找到相关节点的前一个节点 Node prev = dummyHead; //找 index 之前的节点 for(int i = 0; i < index; i++){ prev = prev.next; } prev = new Node(e, prev.next); size++; } //头部插入 public void addFirst(E e) { add(0, e); } //在末尾添加元素 public void addLast(E e){ add(size, e); }
//获取某元素 public E get(int index) { //先检查索引的合法性 if(index<0 || index > size-1) { throw new IllegalArgumentException("Get Failed, Illegal index"); } // 和前面找 index 节点前一个节点不同(那里是从第一个节点前面的虚拟节点开始) // 这里就要找 index 节点,索引从 dummyHead.next 开始,即真正的第一个节点开始 Node ret = dummyHead.next; for(int i =0; i < index; i++) { ret = ret.next; } return ret.e; }
获取第一个元素,最后一个:
//获取第一个 public E getFirst() { return get(0); } //获取最后一个 public E getLast() { return get(size -1); }
把 index 位置的元素修改为 E。
(找到节点,然后替换里面的元素 e)
public void set(int index, E e) { //先检查索引的合法性 if (index < 0 || index > size - 1) { throw new IllegalArgumentException("Get Failed, Illegal index"); } //找到节点,然后替换里面的元素 Node curr = dummyHead.next; for (int i = 0; i < index; i++) { curr = curr.next; } curr.e = e; }
一直遍历到元素末尾,然后寻找尾巴。
//查找元素 public boolean contains(E e) { Boolean ret = false; //在 size 范围内遍历查找 Node curr = dummyHead.next; /*for(int i=0; i<size; i++){ if(curr.e.equals(e)){ ret = true; break; } curr = curr.next; }*/ //其实可以用 while 循环 (多判断一次 size 位置) while(curr != null) { //当前节点是有效节点 if(curr.e.equals(e)){ ret = true; break; } curr = curr.next; } return ret; }
多种循环的写法:
//打印方法 @Override public String toString() { StringBuilder res = new StringBuilder(); //从头遍历到尾巴 /*Node curr = dummyHead.next; while(curr != null) { res.append(curr + "->"); curr = curr.next; }*/ //简写 for(Node curr = dummyHead.next; curr != null; curr = curr.next) { res.append(curr + "->"); } res.append("null"); return res.toString(); }
简单测试一下:
//测试元素 public static void main(String[] args) { LinkedList1<Integer> linkedlist = new LinkedList1<>(); //放入元素 0, 1, 2, 3, 4 for(int i =0; i < 5; i++) { linkedlist.addFirst(i); //O(1) System.out.println(linkedlist); } System.out.println(linkedlist); //尝试插入一个元素 linkedlist.add(1, 100); // 4, 100, 2, 3, 1, 0, null System.out.println(linkedlist); }
打印结果:
0->null 1->0->null 2->1->0->null 3->2->1->0->null 4->3->2->1->0->null 4->3->2->1->0->null 4->100->3->2->1->0->null
还是要 先找到前一个节点 。(也就是说还是借助虚拟头结点)
简单一句话,然 delNode 和原来的链表脱离。(delNode 置空非必须)
编码实现:
//删除元素 public E remove(int index){ if (index < 0 || index > size - 1) { throw new IllegalArgumentException("Delete Failed, Illegal index"); } //找到相关节点的前一个节点 Node curr = dummyHead; for(int i = 0; i < index; i++) { curr = curr.next; } Node delNode = curr.next; //删除 curr.next = delNode.next; delNode.next = null; //必须维护 size size--; return delNode.e; } //删除第一个节点 public E removeFirst() { return remove(0); } //删除最后一个节点 public E removeLast() { return remove(size-1); } //删除指定元素 public void removeElem(E e) { //从 dummyHead 开始找,找到就删除,否则就不删除 Node curr = dummyHead; boolean found = false; while (curr.next != null) { if (curr.next.e.equals(e)) { found = true; //删除操作 Node delNode = curr.next; curr.next = delNode.next; delNode.next = null; size--; break; } curr = curr.next; } if (!found) { throw new RuntimeException("要删除的元素不存在"); } }
测试一下:
//测试元素 public static void main(String[] args) { LinkedList1<Integer> linkedlist = new LinkedList1<>(); //放入元素 0, 1, 2, 3, 4 for(int i =0; i < 5; i++) { linkedlist.addFirst(i); //O(1) System.out.println(linkedlist); } System.out.println(linkedlist); //尝试插入一个元素 linkedlist.add(1, 100); // 4, 100, 2, 3, 1, 0, null System.out.println(linkedlist); //尝试删除 index = 1 位置的 100 linkedlist.remove(1); System.out.println(linkedlist); //4->3->2->1->0->null //删除最后一个元素 0 linkedlist.removeLast(); System.out.println(linkedlist); //4->3->2->1->null //删除第一个元素 linkedlist.removeFirst(); System.out.println(linkedlist); //3->2->1->null //删除指定元素 linkedlist.removeElem(3); linkedlist.removeElem(1); //linkedlist.removeElem(null); System.out.println(linkedlist); }
链表虽然不移动元素,但是涉及到从前往后找到(检查)相应的位置/元素。
同上。
修改操作: O(n)。
get(), contains(), find() 一律 O(n),因为并不支持随机访问呀。
上面也说了, 如果只在链表头增删时,它的整体复杂度是 O(1) ,这不正好用于栈么?
package stack; import linkedlist.LinkedList1; //这是有 dummy head优化的链表实现 public class LinkedListStack<E> implements Stack<E>{ //链栈内部实际采用链表存储 private LinkedList1<E> list; public LinkedListStack(){ list = new LinkedList1<>(); } @Override public boolean isEmpty() { return list.isEmpty(); } @Override public int getSize() { return list.getSize(); } @Override public E pop() { return list.removeFirst(); } @Override public E peek() { return list.getFirst(); } @Override public void push(E e) { list.addFirst(e); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Stack: top ["); res.append(list); res.append("]"); return res.toString(); } public static void main(String[] args) { LinkedListStack<Integer> stack = new LinkedListStack<>(); //放入元素 0, 1, 2, 3, 4 for(int i =0; i < 5; i++) { stack.push(i); //O(1) System.out.println(stack); } System.out.println(stack); System.out.println(stack.peek()); //弹出一个元素 stack.pop(); System.out.println(stack); } }
测试结果:
Stack: top [0->null] Stack: top [1->0->null] Stack: top [2->1->0->null] Stack: top [3->2->1->0->null] Stack: top [4->3->2->1->0->null] Stack: top [4->3->2->1->0->null] 4 Stack: top [3->2->1->0->null]
和数组实现的栈的不同,数组是在尾巴上插入,可能涉及动态扩容,均摊复杂度是 O(1),而链栈始终就是O(1)。
因为队列涉及头和尾的操作,所以如果用链表,那一般要添加一个尾指针。
因为 head 和 tail 都是指针,所以入队和出队相当于改变指向那么简单,但谁做头谁做尾巴?(相当于 head, tail 指针往哪个方向移动)
如果要删除 tail 元素并不容易(无法做到O(1)),因为删除元素要知道 tail 前面一个元素。但是 tail 增加,则可以直接添加。(head不用管, 它的增删都比较容易)
所以结论显而易见:
此时还需要 dummy head 么,分析上面的 tail, head,显然不需要操作统一了,所以不需要哑结点。
这里就不复用 LinkedList 了,而是专门再在内部实现链式存储。(Node 内部类还是需要的)
//内部采用链式存储的队列 public class LinkedQueue<E> implements Queue<E> { //定义一个内部类,作为节点类 private class Node { public E e; public Node next; //便于 LinkedList 访问 public Node(E e, Node next) { this.e = e; this.next = next; } public Node(E e) { this(e, null); } public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } private Node head, tail; private int size; //构造器 public LinkedQueue() { head = tail = null; size = 0; } @Override public boolean isEmpty() { return size == 0; } @Override public int getSize() { return size; } @Override public E dequeue() { //出队操作,在队首 //没有元素肯定就不能出队 if (isEmpty()) { //或者 head = null throw new IllegalArgumentException("Cannot dequeue from an empty queue"); } //正常出队,提取 head Node retNode = head; //tail,考虑只有一个元素的队列 head = retNode.next; retNode.next = null;//游离对象 //仅在只有一个元素的队列,需要维护 tail if (head == null) { tail = null; } size--; return retNode.e; } @Override public E getFront() { if (isEmpty()) { //或者 head = null throw new IllegalArgumentException("Cannot dequeue from an empty queue"); } return head.e; // 返回队首即可 } @Override public void enqueue(E e) { //入队操作,在尾部操作 if (tail == null) { //说明此时队列是空的,即 tail 和 head 都为空 tail = new Node(e); head = tail; } else { tail.next = new Node(e); tail = tail.next; } size++; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue: front[ "); for(Node curr = head; curr != null; curr = curr.next){ res.append(curr.e + "->"); } res.append("null ] tail"); return res.toString(); } public static void main(String[] args) { LinkedQueue<Integer> queue = new LinkedQueue<>(); //存储 11 个元素看看 for(int i=0; i<11; i++){ queue.enqueue(i); System.out.println(queue); // 在 10 个元素满的时候回扩容 } //出队试试 System.out.println("------出队"); queue.dequeue(); System.out.println(queue); } }
运行结果如下:
Queue: front[ 0->null ] tail Queue: front[ 0->1->null ] tail Queue: front[ 0->1->2->null ] tail Queue: front[ 0->1->2->3->null ] tail Queue: front[ 0->1->2->3->4->null ] tail Queue: front[ 0->1->2->3->4->5->null ] tail Queue: front[ 0->1->2->3->4->5->6->null ] tail Queue: front[ 0->1->2->3->4->5->6->7->null ] tail Queue: front[ 0->1->2->3->4->5->6->7->8->null ] tail Queue: front[ 0->1->2->3->4->5->6->7->8->9->null ] tail Queue: front[ 0->1->2->3->4->5->6->7->8->9->10->null ] tail ------出队 Queue: front[ 1->2->3->4->5->6->7->8->9->10->null ] tail
到这里,单链表基本探究完毕了。
下面说的这些链表其实也很常用,但是个人要去实现的话,就费事儿啊
(除非你是大学教师,或者学生,或者自由作家,有的是时间耐得住寂寞,磨啊)
这个维护代价其实有点大,有点就是节点之间的联系更加方便了。(单链表时也会维护尾指针)
没有对比就没有伤害,要找我前一个节点是吧,直接给你(不要循环了)。其他操作则没有太多变化( 需要头结点优化 )。由于有额外的变量需要维护,所以并不见得简单。
class Node { E e; Node prev, next; }
jdk 中 linkedlist 貌似经过一阵子去环优化,可能,因为不要环效率也不差。
不用画图了,直接认为尾部元素直接指向 dummy head 即可。
此时不需要 tail,因为在 dummyHead 的前面添加一个元素,就相当于在结尾添加元素了。
(引入的环会导致操作有些许变化,比如遍历)
有点儿类似于数据库存储设计中的无限级字段,即某个元素要存储其父元素位置(parentId)。
毕竟还是基础数据结构,没有太复杂;这种 link 的思想用于树(二叉树,多叉树)很平常。
老规矩,代码参考的话,我放在了 gayhub , FYI。