一、定义
在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。
1.可以分三类为
-
单向链表，每个元素只知道其下一个元素是谁
-
双向链表，每个元素知道其上一个元素和下一个元素
-
循环链表，通常的链表尾节点tail指向的都是null，而循环链表的tail指向的是头节点head
链表内还有一种特殊的节点称为哨兵节点，也叫做哑元(Dummy)节点，它不存储数据，通常用作头尾，用来简化边界判断，如下图所示：
2.性能
随机访问
根据index查找，时间复杂度O(n)
插入或删除
起始位置:O(1)
结束位置：如果已知tail尾节点是O(1)，不知道tail尾节点是O(n)
中间位置：根据index查找时间 + O(1)
二、单向链表的插入、删除、查找示例
1.以下为不带哨兵节点代码
package com.tfq.arithmetic.linkedlist;
import java.util.Iterator;
import java.util.function.Consumer;
/**
* @author: fqtang
* @date: 2024/05/18/19:23
* @description: 单向链表类
*/
public class SingleLinkedList implements Iterable<Integer> {
/**
* 头指针
*/
private Node head = null;
public void addFirst(int value) {
//1.链表为空
// head = new Node(value,null);
//2.链表非空
head = new Node(value, head);
}
/**
* 返回链表第一种方式
*
* @return
*/
public void loop(Consumer<Integer> consumer) {
Node p = head;
while(p != null) {
consumer.accept(p.value);
p = p.next;
}
}
/**
* 返回链表第二种方式
*
* @return
*/
public void loop2(Consumer<Integer> consumer) {
for(Node p = head; p != null; p = p.next) {
consumer.accept(p.value);
}
}
/**
* 返回链表第三种方式
*
* @return
*/
public void loop3() {
recursion(head);
}
/**
* 递归链表
*
* @return
*/
public void recursion(Node curr) {
if(curr == null) {
return;
}
System.out.println(curr.value);
recursion(curr.next);
}
/**
* 返回链表第四种方式
*
* @return
*/
@Override
public Iterator<Integer> iterator() {
//匿名内部类 ->带名字内部类
return new NodeIterator();
}
private Node findLast() {
if(head == null) {//空链表
return null;
}
Node p = head;
while(p.next != null) {
p = p.next;
}
return p;
}
public void addLast(int value) {
Node last = findLast();
if(last == null) {
addFirst(value);
return;
}
last.next = new Node(value, null);
}
private Node findNode(int index) {
int i = 0;
for(Node p = head; p != null; p = p.next, i++) {
if(index == i) {
return p;
}
}
return null;//没找到
}
public int getValue(int index) {
Node node = findNode(index);
if(node == null) {
//抛异常
throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
}
return node.value;
}
/**
* 向索引位置插值
*
* @param index 索引
* @param value 待插入值
*/
public void insert(int index, int value) {
if(index == 0) {//若index=0，则向链表的head添加元素节点
addFirst(value);
return;
}
//找索引的上一个节点
Node prev = findNode(index - 1);
if(prev == null) {//上一个节点没找到
throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
}
prev.next = new Node(value, prev.next);
}
/**
* 删除第一个节点
*/
public void removeFirst() {
if(head == null) {
throw new IllegalArgumentException(String.format("index [%d] 不合法%n", 0));
}
head = head.next;
}
/**
* 根据索引删除指定元素
* @param index 待删除索引
*/
public void remove(int index) {
if(index ==0){
removeFirst();
return;
}
//找到上一个节点
Node prev = findNode(index - 1);
if(prev == null){
throw new IllegalArgumentException(String.format("index-1 [%d] 不合法%n", index));
}
//被删除的节点
Node removed = prev.next;
if(removed == null){
throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
}
//上一个节点指向被删除节点的下一个节点
prev.next = removed.next;
}
/**
* 节点类,单向链表与节点是外部类与内部类，更好隐藏内部类，
* 方便外部调用，不需要外部知道内部实现细节
* 内部类使用了static，则此内部类没有使用外部类的变量。当内部类没有使用外部类的变量时推荐使用static
*/
private static class Node {
/**
* 值
*/
int value;
/**
* 下一个结点指针
*/
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
/**
* 内部类使用了一个外部类的成员变量时在内部类的类名上不能使用static，内部类使用了一个Node
*/
private class NodeIterator implements Iterator<Integer> {
Node p = head;
@Override
public boolean hasNext() {//是否有下一个元素
return p != null;
}
@Override
public Integer next() {//返回当前元素值，并指向下一个元素
int v = p.value;
p = p.next;
return v;
}
}
}
2.以下为代哨兵节点
哨兵用来简化边界判断（简化查找上一个节点和非空判断）简化代码。
package com.tfq.arithmetic.linkedlist;
import java.util.Iterator;
import java.util.function.Consumer;
/**
* @author: fqtang
* @date: 2024/05/18/19:23
* @description: 单向链表类(带哨兵监视)
*/
public class SingleLinkedListSentinel implements Iterable<Integer> {
/**
* 头指针指向哨兵节点
*/
private Node head = new Node(666, null);
public void addFirst(int value) {
insert(0,value);
}
/**
* 返回链表第一种方式
*
* @return
*/
public void loop(Consumer<Integer> consumer) {
Node p = head.next;
while(p != null) {
consumer.accept(p.value);
p = p.next;
}
}
/**
* 返回链表第二种方式
*
* @return
*/
public void loop2(Consumer<Integer> consumer) {
for(Node p = head.next; p != null; p = p.next) {
consumer.accept(p.value);
}
}
/**
* 返回链表第三种方式
*
* @return
*/
@Override
public Iterator<Integer> iterator() {
//匿名内部类 ->带名字内部类
return new NodeIterator();
}
private Node findLast() {
Node p = head;
while(p.next != null) {
p = p.next;
}
return p;
}
public void addLast(int value) {
Node last = findLast();
last.next = new Node(value, null);
}
private Node findNode(int index) {
int i = -1;
for(Node p = head; p != null; p = p.next, i++) {
if(index == i) {
return p;
}
}
return null;//没找到
}
public int getValue(int index) {
Node node = findNode(index);
if(node == null) {
//抛异常
throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
}
return node.value;
}
public void test() {
int i = 0;
for(Node p = head; p != null; p = p.next, i++) {
System.out.println(p.value + "，索引值：" + i);
}
}
/**
* 向索引位置插值
*
* @param index 索引
* @param value 待插入值
*/
public void insert(int index, int value) {
//找索引的上一个节点
Node prev = findNode(index - 1);
if(prev == null) {//上一个节点没找到
throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
}
prev.next = new Node(value, prev.next);
}
/**
* 删除第一个节点
*/
public void removeFirst() {
remove(0);
}
/**
* 根据索引删除指定元素
*
* @param index 待删除索引
*/
public void remove(int index) {
//找到上一个节点
Node prev = findNode(index - 1);
if(prev == null) {
throw new IllegalArgumentException(String.format("index-1 [%d] 不合法%n", index));
}
//被删除的节点
Node removed = prev.next;
if(removed == null) {
throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
}
//上一个节点指向被删除节点的下一个节点
prev.next = removed.next;
}
/**
* 节点类,单向链表与节点是外部类与内部类，更好隐藏内部类，
* 方便外部调用，不需要外部知道内部实现细节
* 内部类使用了static，则此内部类没有使用外部类的变量。当内部类没有使用外部类的变量时推荐使用static
*/
private static class Node {
/**
* 值
*/
int value;
/**
* 下一个结点指针
*/
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
/**
* 内部类使用了一个外部类的成员变量时在内部类的类名上不能使用static，内部类使用了一个Node
*/
private class NodeIterator implements Iterator<Integer> {
Node p = head.next;
@Override
public boolean hasNext() {//是否有下一个元素
return p != null;
}
@Override
public Integer next() {//返回当前元素值，并指向下一个元素
int v = p.value;
p = p.next;
return v;
}
}
}
若要学习双向链表，请查看我下一章节。
