数据结构和算法之旅（二）- 链表
有链接的"数组"。
定义
在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。
可分类为：
- 单向链表：每个元素只知道其下一个元素
- 双向链表：每个元素知道其上一个元素和下一个元素
- 循环链表：通常的链表尾节点tail指向null，而循环链表的tail指向的头结点head
链表内还有一种特殊的节点，称为哨兵(Sentinel)节点，也叫做哑元(Dummy)节点，它不存储数据，通常用作头尾，用来简化边界判断。
性能
随机访问
根据index查找，时间复杂度O(n)，因为需要一个节点next、next找到目标。
插入或删除
- 起始位置：O(1)。
- 结束位置：如果已知tail节点则是O(1)，不知道tail节点则是O(n)。
- 中间位置：根据index查找时间+O(1)。
单向链表之无哨兵节点
talk is cheap, show me the code.
package org.example.datastructure;
import java.util.Iterator;
import java.util.function.Consumer;
/**
* 单向链表 基础实现 无哨兵节点
*/
public class BasicSingleLinkedList implements Iterable {//整体
private Node head = null;//头节点，默认为null
/**
* 内部类关系，对外隐藏实现细节
* 对外部调用者只需要LinkedList即可
* 内部类一半都加上static
* 节点类
*/
private static class Node {//节点
int value;//值
Node next;//下一个节点
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
/**
* 向链表头添加元素
* 多理解！！
*/
public void addFirst(int value) {
//链表为空
// head = new Node(value, null);
//链表非空
//因为head默认为null，所以不需要判断，链表空不空都能能用
head = new Node(value, head);
}
/**
* 向列表尾添加元素
* 先找到尾节点，再添加
*/
public void addLast(int value) {
Node last = findLast();
if (last == null) {
addFirst(value);
return;
}
last.next = new Node(value, null);
}
/**
* 向索引位置插入节点
*
* @param index 索引位置
* @param value 待插入值
*/
public void insert(int index, int value) {
if (index == 0) {
addFirst(value);
return;
}
Node prev = findNode(index - 1);
if (prev == null) {//找不到前一个节点
throw illegalIndex();
}
prev.next = new Node(value, prev.next);
}
/**
* 删除头节点
*/
public void removeFirst() {
if (head == null) {
throw illegalIndex();
}
head = head.next;
}
/**
* 根据索引删除节点
*/
public void remove(int index) {
if (index == 0) {
removeFirst();
return;
}
Node prev = findNode(index - 1);
if (prev == null) {//找不到前一个节点
throw illegalIndex();
}
Node removed = prev.next;
if (removed == null) {
throw illegalIndex();
}
prev.next = removed.next;
}
private static IllegalArgumentException illegalIndex() {
return new IllegalArgumentException("index illegal");
}
/**
* 找到最后一个节点
*/
private Node findLast() {
if (head == null) {
//链表为空，没有最后一个节点
return null;
}
//利用for循环特性获取最后一个节点
Node p;
for (p = head; p.next != null; p = p.next) {
}
return p;
}
/**
* 查询指定位置元素
*/
private Node findNode(int index) {
int i = 0;
//利用for循环特性获取指定index位置节点
for (Node p = head; p != null; p = p.next, i++) {
if (i == index) {
return p;
}
}
return null;
}
/**
* get方法
*/
public int get(int index) {
Node node = findNode(index);
if (node == null) {
throw illegalIndex();
}
return node.value;
}
/**
* 循环1 while
*/
public void loop1(Consumer<Integer> consumer) {
Node pointer = head;//初始值指向头节点
while (pointer != null) {
consumer.accept(pointer.value);//提供给外部的方法
pointer = pointer.next;//指向下一个节点
}
}
/**
* 循环2 for
*/
public void loop2(Consumer<Integer> consumer) {
for (Node pointer = head; pointer != null; pointer = pointer.next) {
consumer.accept(pointer.value);//提供给外部的方法
}
}
/**
* 循环3 iterator
*/
@Override
public Iterator iterator() {
/**
* 匿名内部类 -> 带名字的内部类
* 这个抽取出来的内部类MyIterator，它是不加static的
*
* 当内部类用到了外部类的成员变量时候，就不能加static
* 因为static的意思是不依赖外部类实例的存在，而成员变量是依赖外部类的对象的
*
* 而Node节点类是可以加static的，因为它不依赖外部类的对象的
*
* 内部类能加就加，不能加就不加，建议加static
*/
return new MyIterator();
}
private class MyIterator implements Iterator {
Node pointer = head;//初始值指向头节点
@Override
public boolean hasNext() {//是否有下一个元素
return pointer != null;
}
@Override
public Object next() {//返回当前值，并指向下一个元素
int v = pointer.value;
pointer = pointer.next;
return v;
}
}
}单向链表之含哨兵节点
talk is cheap, show me the code.
package org.example.datastructure;
import java.util.Iterator;
import java.util.function.Consumer;
/**
* 单向链表 优化实现 含哨兵节点
* 带哨兵节点的单向链表可以减少很多边界判断
*/
public class SentinelSinglyLinkedList implements Iterable {
/**
* 头指针指向哨兵节点，哨兵节点值无所谓
*/
private Node head = new Node(111, null);//头节点
/**
* 内部类关系，对外隐藏实现细节
* 对外部调用者只需要LinkedList即可
* 内部类一般都加上static
* 节点类
*/
private static class Node {//节点
int value;//值
Node next;//下一个节点
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
/**
* 加哨兵后修改
* <p>
* 向链表头添加元素
* 多理解！！
*/
public void addFirst(int value) {
//不需要判断链表是否为空，因为链表一定不为空
// //1.链表为空
//// head = new Node(value, null);
// //2.链表非空
// //因为head默认为null，所以不需要判断，链表空不空都能能用
// head = new Node(value, head);
insert(0, value);
}
/**
* 加哨兵后修改
* <p>
* 向列表尾添加元素
* 先找到尾节点，再添加
*/
public void addLast(int value) {
Node last = findLast();
//含哨兵节点，不需要判断链表是否为空，因为链表一定不为空
// if (last == null) {
// addFirst(value);
// return;
// }
last.next = new Node(value, null);
}
/**
* 加哨兵后修改
* <p>
* 向索引位置插入节点
*
* @param index 索引位置
* @param value 待插入值
*/
public void insert(int index, int value) {
// if (index == 0) {
// addFirst(value);
// return;
// }
Node prev = findNode(index - 1);
if (prev == null) {//找不到前一个节点
throw illegalIndex();
}
prev.next = new Node(value, prev.next);
}
/**
* 加哨兵后修改
* <p>
* 删除头节点
*/
public void removeFirst() {
// if (head == null) {
// throw illegalIndex();
// }
// head = head.next;
remove(0);
}
/**
* 加哨兵后修改
* <p>
* 根据索引删除节点
*/
public void remove(int index) {
// if (index == 0) {
// removeFirst();
// return;
// }
Node prev = findNode(index - 1);
if (prev == null) {//找不到前一个节点
throw illegalIndex();
}
Node removed = prev.next;
if (removed == null) {
throw illegalIndex();
}
prev.next = removed.next;
}
private static IllegalArgumentException illegalIndex() {
return new IllegalArgumentException("index illegal");
}
/**
* 加哨兵后修改
* 找到最后一个节点
*/
private Node findLast() {
//含哨兵节点，不需要判断链表是否为空，因为链表一定不为空
// if (head == null) {
// //链表为空，没有最后一个节点
// return null;
// }
Node p;
for (p = head; p.next != null; p = p.next) {
}
return p;
}
/**
* 加哨兵后修改
* <p>
* 查询指定位置元素
*/
private Node findNode(int index) {
int i = -1;
//为什么i=-1？ 因为哨兵节点也占一位。
for (Node p = head; p != null; p = p.next, i++) {
if (i == index) {
return p;
}
}
return null;
}
/**
* get方法
*/
public int get(int index) {
Node node = findNode(index);
if (node == null) {
throw illegalIndex();
}
return node.value;
}
/**
* 加哨兵后修改
* <p>
* 循环1 while
*/
public void loop1(Consumer<Integer> consumer) {
//遍历的起点变了
Node pointer = head.next;//初始值指向头节点
while (pointer != null) {
consumer.accept(pointer.value);//提供给外部的方法
pointer = pointer.next;//指向下一个节点
}
}
/**
* 加哨兵后修改
* <p>
* 循环2 for
*/
public void loop2(Consumer<Integer> consumer) {
for (Node pointer = head.next; pointer != null; pointer = pointer.next) {
consumer.accept(pointer.value);//提供给外部的方法
}
}
/**
* 循环3 iterator
*/
@Override
public Iterator iterator() {
/**
* 匿名内部类 -> 带名字的内部类
* 这个抽取出来的内部类MyIterator，它是不加static的
*
* 当内部类用到了外部类的成员变量时候，就不能加static
* 因为static的意思是不依赖外部类实例的存在，而成员变量是依赖外部类的对象的
*
* 而Node节点类是可以加static的，因为它不依赖外部类的对象的
*
* 内部类能加就加，不能加就不加，建议加static
*/
return new MyIterator();
}
private class MyIterator implements Iterator {
Node pointer = head.next;//初始值指向头节点
@Override
public boolean hasNext() {//是否有下一个元素
return pointer != null;
}
@Override
public Object next() {//返回当前值，并指向下一个元素
int v = pointer.value;
pointer = pointer.next;
return v;
}
}
}双向链表之含哨兵节点
talk is cheap, show me the code.
package org.example.datastructure;
import java.util.Iterator;
/**
* 双向链表 带哨兵节点
* 俩个哨兵节点，一个头哨兵，一个尾哨兵
* 也就是说，链表中至少有俩个节点
* <p>
* 双向链表的优点：从尾部直接能获取最后一个节点
*/
public class DoublyLinkedListSentinel implements Iterable<Integer> {
static class Node {
Node prev;//上一个节点
int value;//值
Node next;//下一个节点
//构造方法 方便初始化
public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
private Node head;//头哨兵
private Node tail;//尾哨兵
public DoublyLinkedListSentinel() {
//头尾节点随便给个值就行
head = new Node(null, 666, null);
tail = new Node(null, 888, null);
head.next = tail;
tail.prev = head;
}
/**
* 根据索引查找节点
*/
private Node findNode(int index) {
int i = -1;//头哨兵也要参与遍历所以从-1开始
for (Node p = head; p != tail; p = p.next, i++) {
if (i == index) {
return p;
}
}
return null;
}
public void addFirst(int value) {
insert(0, value);
}
public void removeFirst() {
remove(0);
}
/**
* 向列表尾添加元素
*/
public void addLast(int value) {
Node last = tail.prev;
Node added = new Node(last, value, tail);
last.next = added;
tail.prev = added;
}
/**
* 删除列表尾元素
*/
public void removeLast() {
Node removed = tail.prev;
if (removed == head) {
throw illegalIndex();
}
Node prev = removed.prev;
prev.next = tail;
tail.prev = prev;
}
/**
* 向索引位置插入节点
*/
public void insert(int index, int value) {
Node prev = findNode(index - 1);
if (prev == null) {
throw illegalIndex();
}
Node next = prev.next;
Node inserted = new Node(prev, value, next);//新节点的上一个节点是prev，下一个节点是next
prev.next = inserted;//prev的下一个节点是inserted
next.prev = inserted;//next的上一个节点是inserted
}
/**
* 删除索引位置的节点
*/
public void remove(int index) {
Node prev = findNode(index - 1);
if (prev == null) {
throw illegalIndex();
}
Node removed = prev.next;
if (removed == tail) {
throw illegalIndex();
}
Node next = removed.next;
prev.next = next;
next.prev = prev;
}
private static IllegalArgumentException illegalIndex() {
return new IllegalArgumentException("index illegal");
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node p = head.next;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public Integer next() {
int v = p.value;
p = p.next;
return v;
}
};
}
}双向环形含哨兵链表
talk is cheap, show me the code.
这个有些特殊，此时哨兵即作为头，也作为尾。
package org.example.datastructure;
import java.util.Iterator;
/**
* 环形双向含哨兵链表
*/
public class RingDoublyLinkedListSentinel implements Iterable<Integer> {
static class Node {
Node prev;
int value;
Node next;
public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
private Node sentinel = new Node(null, 666, null);
public RingDoublyLinkedListSentinel() {
sentinel.next = sentinel;
sentinel.prev = sentinel;
}
/**
* 添加到链表头部
*/
public void addFirst(int value) {
Node a = sentinel;
Node b = sentinel.next;
Node added = new Node(a, value, b);
a.next = added;
b.prev = added;
}
/**
* 添加到链表尾部
*/
public void addLast(int value) {
Node a = sentinel.prev;
Node b = sentinel;
Node added = new Node(a, value, b);
a.next = added;
b.prev = added;
}
/**
* 删除第一个
*/
public void removeFirst() {
Node removed = sentinel.next;
if (removed == sentinel) {
throw new IllegalArgumentException("Illegal argument");
}
Node a = removed.prev;
Node b = removed.next;
a.next = b;
b.prev = a;
}
/**
* 删除最后一个
*/
public void removeLast() {
Node removed = sentinel.prev;
if (removed == sentinel) {
throw new IllegalArgumentException("Illegal argument");
}
Node a = removed.prev;
Node b = removed.next;
a.next = b;
b.prev = a;
}
/**
* 根据值删除节点
*/
public void removeByValue(int value) {
Node removed = findByValue(value);
if (removed == null) {
throw new IllegalArgumentException("Illegal argument");
}
Node a = removed.prev;//前一个节点
Node b = removed.next;//后一个节点
a.next = b;//前一个节点的next指向后一个节点
b.prev = a;//后一个节点的prev指向前一个节点
}
/**
* 根据值找到节点
*/
private Node findByValue(int value) {
Node p = sentinel.next;
while (p != sentinel) {
if (p.value == value) {
return p;
}
p = p.next;
}
return null;
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node pointer = sentinel.next;
@Override
public boolean hasNext() {
return pointer != sentinel;
}
@Override
public Integer next() {
int v = pointer.value;
pointer = pointer.next;
return v;
}
};
}
}单向链表的递归遍历
talk is cheap, show me the code.
import java.util.Iterator;
import java.util.function.Consumer;
/**
* 单向链表 基础实现
* <p>
* ！！！递归遍历！！！
* 它是链表的一种非常重要的遍历方式
*/
public class RecursionLinkedList implements Iterable {//整体
private Node head = null;//头节点，默认为null
/**
* 内部类关系，对外隐藏实现细节
* 对外部调用者只需要LinkedList即可
* 内部类一半都加上static
* 节点类
*/
private static class Node {//节点
int value;//值
Node next;//下一个节点
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
/**
* 向链表头添加元素
* 多理解！！
*/
public void addFirst(int value) {
//1.链表为空
// head = new Node(value, null);
//2.链表非空
//因为head默认为null，所以不需要判断，链表空不空都能能用
head = new Node(value, head);
}
/**
* 向列表尾添加元素
* 先找到尾节点，再添加
*/
public void addLast(int value) {
Node last = findLast();
if (last == null) {
addFirst(value);
return;
}
last.next = new Node(value, null);
}
/**
* 向索引位置插入节点
*
* @param index 索引位置
* @param value 待插入值
*/
public void insert(int index, int value) {
if (index == 0) {
addFirst(value);
return;
}
Node prev = findNode(index - 1);
if (prev == null) {//找不到前一个节点
throw illegalIndex();
}
prev.next = new Node(value, prev.next);
}
/**
* 删除头节点
*/
public void removeFirst() {
if (head == null) {
throw illegalIndex();
}
head = head.next;
}
/**
* 根据索引删除节点
*/
public void remove(int index) {
if (index == 0) {
removeFirst();
return;
}
Node prev = findNode(index - 1);
if (prev == null) {//找不到前一个节点
throw illegalIndex();
}
Node removed = prev.next;
if (removed == null) {
throw illegalIndex();
}
prev.next = removed.next;
}
private static IllegalArgumentException illegalIndex() {
return new IllegalArgumentException("index illegal");
}
/**
* 找到最后一个节点
*/
private Node findLast() {
if (head == null) {
//链表为空，没有最后一个节点
return null;
}
Node p;
for (p = head; p.next != null; p = p.next) {
}
return p;
}
/**
* 查询指定位置元素
*/
private Node findNode(int index) {
int i = 0;
for (Node p = head; p != null; p = p.next, i++) {
if (i == index) {
return p;
}
}
return null;
}
/**
* get方法
*/
public int get(int index) {
Node node = findNode(index);
if (node == null) {
throw illegalIndex();
}
return node.value;
}
/**
* 循环3 iterator
*/ @Override
public Iterator iterator() {
/**
* 匿名内部类 -> 带名字的内部类
* 这个抽取出来的内部类MyIterator，它是不加static的
*
* 当内部类用到了外部类的成员变量时候，就不能加static
* 因为static的意思是不依赖外部类实例的存在，而成员变量是依赖外部类的对象的
*
* 而Node节点类是可以加static的，因为它不依赖外部类的对象的
*
* 内部类能加就加，不能加就不加，建议加static
*/ return new MyIterator();
}
private class MyIterator implements Iterator {
Node pointer = head;//初始值指向头节点
@Override
public boolean hasNext() {//是否有下一个元素
return pointer != null;
}
@Override
public Object next() {//返回当前值，并指向下一个元素
int v = pointer.value;
pointer = pointer.next;
return v;
}
}
private void recursion(Node curr, Consumer<String> before, Consumer<String> after){
if (curr == null) {//递归需要一个终止条件
return;
}
before.accept("before: " + curr.value);
recursion(curr.next, before, after);//这样自己调用自己称为递归
after.accept("after: " + curr.value);
}
public static void main(String[] args) {
RecursionLinkedList list = new RecursionLinkedList();
list.addLast(55);
list.addLast(66);
list.addLast(77);
list.addLast(88);
list.recursion(list.findNode(0),System.out::println, System.out::println);
}
}通过递归方式遍历打印的时候，发现了有趣的现象，不同情况，打印结果却不同 打印在前，递归在后 递归在前，递归在后 俩种情况的呈现方式相差很大，如下图。
下一篇，会详细探讨一下递归，来解释为什么有这种现象。