目录
链表
单向链表
哨兵链表
双向链表
环形链表
链表
链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。
随机访问性能
根据 index 查找，时间复杂度 O(n)
插入或删除性能
- 起始位置：O(1)
- 结束位置：如果已知 tail 尾节点是 O(1)[双向链表]，不知道 tail 尾节点是 O(n)
- 中间位置：根据 index 查找时间 + O(1)
单向链表
单向链表中每个元素只知道下一个节点位置
单向链表的简单实现
public class SinglyLinkList implements Iterable<Integer> {
private Node head = null;
//节点类
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, head);
}
//向链表尾部添加节点
public void addLast(int value) {
Node last = findLast();
if (last == null) {
addFirst(value);
}
last.next = new Node(value, null);
}
private Node findLast() {
if (head.next == null) {
return null;
}
Node p = head;
while (p.next != null) {
p = p.next;
}
return p;
}
//遍历链表
public void loop(Consumer<Integer> consumer) {
Node pointer = head;
while (pointer != null) {
consumer.accept(pointer.value);
pointer = pointer.next;
}
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node pointer = head;
@Override
public boolean hasNext() {
return pointer != null;
}
@Override
public Integer next() {
int value = pointer.value;
pointer = pointer.next;
return value;
}
};
}
// 根据索引查找节点值
private Node findByIndex(int index) {
int i = 0;
for (Node p = head; p != null; p = p.next, i++) {
if (index == i) {
return p;
}
}
return null;
}
public int get(int index) {
Node node = findByIndex(index);
if (node == null) {
throw new IllegalArgumentException("索引超出范围");
}
return node.value;
}
//插入元素
public void insert(int index, int value) {
if (index == 0) {
addFirst(value);
return;
}
//查找索引的上一个节点
Node node = findByIndex(index - 1);
if (node == null) {
throw new IllegalArgumentException("索引超出范围");
}
node.next = new Node(value, node.next);
}
//移除首节点
public void removeFirst() {
if (head==null){
throw new RuntimeException("链表为空。无法移除");
}
head = head.next;
}
//删除指定节点
public void remove(int index){
if (index==0){
removeFirst();
}
//找到要删除的节点的前驱节点
Node node = findByIndex(index - 1);
Node remove = node.next;
if (remove==null){
//要删除的节点位置为空
throw new IllegalArgumentException("索引越界");
}
node.next = remove.next;
}
}这种实现方法有一个弊端，那就是每次添加或是删除元素时都需要进行判断链表是否为空。因此提出了哨兵链表的概念
哨兵链表
所谓哨兵列表，就是头节点不存储数据，只为简化边缘判断使用。
具体代码如下
public class SinglyLinkListSentinel implements Iterable<Integer> {
//头节点指向哨兵节点。值可以随便给
private Node head = new Node(723468, null);
//节点类
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) {
//在链表头部添加节点时，应该在哨兵之后。
insert(0, value);
}
//向链表尾部添加节点
public void addLast(int value) {
Node last = findLast();
last.next = new Node(value, null);
}
private Node findLast() {
Node p = head;
while (p.next != null) {
p = p.next;
}
return p;
}
//遍历链表
public void loop(Consumer<Integer> consumer) {
//从哨兵节点之后的节点开始遍历
Node pointer = head.next;
while (pointer != null) {
consumer.accept(pointer.value);
pointer = pointer.next;
}
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node pointer = head.next;
@Override
public boolean hasNext() {
return pointer != null;
}
@Override
public Integer next() {
int value = pointer.value;
pointer = pointer.next;
return value;
}
};
}
// 根据索引查找节点值
private Node findByIndex(int index) {
//这里设置为-1是排除哨兵节点带来的影响
int i = -1;
for (Node p = head; p != null; p = p.next, i++) {
if (index == i) {
return p;
}
}
return null;
}
public int get(int index) {
Node node = findByIndex(index);
if (node == null) {
throw new IllegalArgumentException("索引超出范围");
}
return node.value;
}
//插入元素
public void insert(int index, int value) {
//查找索引的上一个节点
Node node = findByIndex(index - 1);
if (node == null) {
throw new IllegalArgumentException("索引超出范围");
}
node.next = new Node(value, node.next);
}
//移除首节点
public void removeFirst() {
remove(0);
}
//删除指定节点
public void remove(int index) {
//找到要删除的节点的前驱节点
Node node = findByIndex(index - 1);
Node remove = node.next;
if (remove == null) {
//要删除的节点位置为空
throw new IllegalArgumentException("索引越界");
}
node.next = remove.next;
}
}双向链表
每个元素知道上一个元素与下一个元素的地址
简单实现如下
public class DoublyLinkedListSentinel implements Iterable<Integer>{
//头哨兵
private Node head = new Node(null, null, 0);
//尾哨兵
private Node tail = new Node(null, null, 0);
public DoublyLinkedListSentinel() {
//初始化时，对头尾哨兵进行指定
head.next = tail;
tail.prev = head;
}
private static class Node {
Node prev;
Node next;
int value;
public Node(Node prev, Node next, int value) {
this.prev = prev;
this.next = next;
this.value = value;
}
}
//提供双向链表方法
public Node findByIndex(int index) {
int i = -1;
for (Node p = head; p != tail; p = p.next, i++) {
if (index == i) {
return p;
}
}
return null;
}
//插入首元素
public void addFirst(int value) {
insert(0, value);
}
//插入元素
public void insert(int index, int value) {
Node prev = findByIndex(index - 1);
if (prev == null) {
throw new RuntimeException("下标越界");
}
Node next = prev.next;
Node node = new Node(prev, next, value);
prev.next = node;
next.prev = node;
}
//向尾节点添加
public void addLast(int value){
Node prev = tail.prev;
Node addNode = new Node(prev, tail, value);
prev.next = addNode;
tail.prev = addNode;
}
//删除首节点
public void removeFirst(){
if (head.next==tail){
throw new RuntimeException("链表为空");
}
Node remove = head.next;
Node next = remove.next;
head.next = next;
next.prev = head;
}
//删除元素
public void remove(int index) {
Node prev = findByIndex(index - 1);
if (prev == null) {
throw new RuntimeException("下标越界");
}
Node remove = prev.next;
Node next = remove.next;
if (remove==tail){
throw new RuntimeException("下标越界");
}
prev.next = next;
next.prev = prev;
}
//获取元素
public int get(int index){
Node node = findByIndex(index);
return node.value;
}
//遍历元素
public void loop(Consumer<Integer> consumer) {
Node pointer = head.next;
while (pointer != tail) {
consumer.accept(pointer.value);
pointer = pointer.next;
}
}
//迭代器实现
@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 value = p.value;
p = p.next;
return value;
}
};
}
}环形链表
环形链表的尾节点指向的是头节点head
环形链表我们也可以引入哨兵，空链表时，哨兵既做头节点也做尾节点。
简单实现代码如下
public class DoublyLinkedListSentinelTo implements Iterable<Integer> {
private Node sentinel = new Node(null, null, -1);
public DoublyLinkedListSentinelTo() {
sentinel.prev = sentinel;
sentinel.next = sentinel;
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node p = sentinel.next;
@Override
public boolean hasNext() {
return p != sentinel;
}
@Override
public Integer next() {
int value = p.value;
p = p.next;
return value;
}
};
}
private static class Node {
Node prev;
Node next;
int value;
public Node(Node prev, Node next, int value) {
this.prev = prev;
this.next = next;
this.value = value;
}
}
//提供循环链表的方法
public Node findByIndex(int index) {
int i = 0;
for (Node p = sentinel.next; p != sentinel; i++, p = p.next) {
if (index == i) {
return p;
}
}
return null;
}
public void addFirst(int value) {
Node next = sentinel.next;
Node addNode = new Node(sentinel, next, value);
sentinel.next = addNode;
next.prev = addNode;
}
public void insert(int index, int value) {
if (index == 0) {
addFirst(value);
}
Node prev = findByIndex(index - 1);
if (prev == null) {
throw new RuntimeException("下标越界");
}
Node next = prev.next;
Node insertNode = new Node(prev, next, value);
next.prev = insertNode;
prev.next = insertNode;
}
public void addLast(int value) {
Node prev = sentinel.prev;
Node addNode = new Node(prev, sentinel, value);
prev.next = addNode;
sentinel.prev = addNode;
}
//删除第一个节点
public void removeFirst() {
Node remove = sentinel.next;
if (remove == sentinel) {
throw new RuntimeException("下标越界");
}
Node next = remove.next;
sentinel.next = next;
next.prev = sentinel;
}
//删除最后一个节点
public void removeLast() {
Node remove = sentinel.prev;
if (remove == sentinel) {
throw new RuntimeException("下标越界");
}
Node prev = remove.prev;
prev.next = sentinel;
sentinel.prev = prev;
}
//删除指定删除节点
public void remove(int index) {
if (index == 0) {
removeFirst();
}
Node prev = findByIndex(index - 1);
Node remove = prev.next;
if (remove == sentinel) {
throw new RuntimeException("下标越界");
}
Node next = remove.next;
prev.next = next;
next.prev = prev;
}
//遍历节点
public void loop(Consumer<Integer> consumer) {
for (Node p = sentinel.next; p != sentinel; p = p.next) {
consumer.accept(p.value);
}
}
}
