title: 数据结构-线性表：链表
tags: 数据结构,链表
renderNumberedHeading: true
grammar_cjkRuby: true
概述
线性表是由N个元素组成的有序排列，也是最常见的一种数据结构，主要包括：数组 和 链表
链表结构
链表是一种链式存储结构，存储的数据在磁盘上是分开的，只是因为它们之间有一些关联，多个节点之间通过地址进行连接，将其联系在一起就形成了链表。
链表主要分为以下几种：
- 单向链表
- 双向链表
- 循环链表
链表结构分析
单向链表
结构：链表中的每个元素节点中除了存储自身元素外，还存储了下一个节点，用来指向下一个节点。
- 简单实现一个单向链表：
public class Node {
public String data; // 存储自身元素
public Node next; // 存储下一个节点
// 新建一个节点，默认下一个节点为null
public Node(String data) {
this.data = data;
next = null;
}
}
public class SingleChainList {
private int size; // 链表长度
public Node head; // 链表头节点
public SingleChainList() { // 初始化一个空链表
size = 0;
}
public int size() { // 获取链表长度
return size;
}
/**
* 打印单链表的所有值
*/
public void print() {
if (size == 0) {
System.out.println("空列表");
return;
}
Node node = head;
while (node != null) {
System.out.println(node.data);
node = node.next;
}
}
/**
* 在末尾追加一个节点
*/
public void add(Node node) {
if (node == null) {
return;
}
//如果链表为空,那新增的这个node就作为head
if (size == 0) {
head = node; // 头节点指向当前节点
} else { //添加到末尾
Node last = head; // 从头节点开始遍历
while (last.next != null) { // 遍历到最后一个节点
last = last.next;
}
last.next = node;// 加当前节点添加到最后一个节点，即：最后一个节点执向它即可
}
size++;
}
/**
* 在某个位置插入一个节点
*/
public void add(int index, Node node) {
if (index < 0 || index > size) {
throw new RuntimeException("越界");
}
if (node == null) {
return;
}
//插头部
if (index == 0) { // index=0表示插入在头部，即：将当前节点指向头节点，然后将当前节点作为头节点
node.next = head;
head = node;
} else {
Node tempNode = head; // 从头节点开始遍历，找到插入的节点位置，将前一个节点指向当前节点，当前节点指向原前一个节点的下一个节点
for (int i = 0; i < index - 1; i++) {
//取到要被插入的节点的父节点
tempNode = tempNode.next;
}
node.next = tempNode.next;
tempNode.next = node;
}
size++;
}
}
-
单向链表图解
单向链表结构图
双向链表
结构：链表中的每个元素节点中除了存储自身元素外，还存储了下一个节点以及上一个节点，用来指向上一个节点和下一个节点。
- 简单实现一个双向链表
package com.kyrie.utils.dataStructure;
/***
* @project: interface-common
* @package: com.kyrie.utils.dataStructure
* @description: 双向链表
* @author: kyrie
* @mail: 18654169290@163.com
* @createDate: 2021-04-01 23:11
*/
public class DoubleChainList {
class Node {
private Object value; // 自身元素
private Node preNode; // 前一个节点地址
private Node nextNode; // 下一个节点地址
/**
* 新加一个链表节点，此时还未插入到原链表中
*/
public Node(Object value) {
this.value = value;
this.preNode = null;
this.nextNode = null;
}
}
private Node head; // 链表头部
private Node tail; // 链表尾部
private int size;
/**
* 添加节点，默认插入到链表尾部
*/
public void add(Object value) {
addLast(new Node(value));
}
/**
* 添加节点到任意位置
*
* @param index 节点所在下标
* @param value 节点数据
*/
public void add(int index, Object value) {
checkValid(index);
// 1.新增一个节点Node
Node node = new Node(value);
if (index == 0) {
addFirst(node);
} else if (index == size - 1) {
addLast(node);
} else {
Node preNode = head; // 节点插入的前一个Node
Node nextNode = null; // 节点插入的后一个Node
for (int i = 0; i < index - 1; i++) {
preNode = preNode.nextNode;
}
nextNode = preNode.nextNode;
preNode.nextNode = node;
node.preNode = preNode;
nextNode.preNode = node;
node.nextNode = nextNode;
}
size++;
}
/**
* 添加节点到链表首位
*/
public void addFirst(Object value) {
addFirst(new Node(value));
}
/**
* 添加节点到链表首位
*/
public void addFirst(Node node) {
// 2.判断当前链表长度
if (size == 0) {
this.head = node;
this.tail = node;
} else {
Node tempNode = head;
tempNode.preNode = node;
node.nextNode = tempNode;
head = node;
}
size++;
}
/**
* 添加节点到链表尾部
*/
public void addLast(Object value) {
addLast(new Node(value));
}
/**
* 添加节点到链表尾部
*/
public void addLast(Node node) {
// 2.判断当前链表长度
if (size == 0) {
// 当链表为空时，此时插入的节点即为尾部节点，同时当前链表只有一个节点，因此: 头部=尾部
this.tail = node;
this.head = node;
} else {
// 找到原来的尾部节点tempNode
Node tempNode = this.tail;
// 建立向上绑定关系：新node的前一个节点执行原尾部节点
node.preNode = tempNode;
// 建立向下绑定关系：原尾部节点的下一个节点指向新node
tempNode.nextNode = node;
// 更新尾部节点=新node
this.tail = node;
}
size++;
}
/**
* 获取链表指定下标节点的值
*
* @param index 节点下标
*/
public Object get(int index) {
checkValid(index);
Object value;
if (index == 0) {
value = head.value;
} else if (index == size - 1) {
value = tail.value;
} else {
Node currentNode = head;
for (int i = 0; i < index; i++) {
currentNode = currentNode.nextNode;
}
value = currentNode.value;
}
return value;
}
/**
* 移除指定节点
*
* @param index 节点下标
*/
public void remove(int index) {
checkValid(index);
Node node;
if (index == 0) {
node = head.nextNode;
node.preNode = null;
head = node;
} else if (index == size - 1) {
node = tail.preNode;
node.nextNode = null;
tail = node;
} else {
Node preNode = head; // 节点插入的前一个Node
Node nextNode = null; // 节点插入的后一个Node
for (int i = 0; i < index - 1; i++) {
preNode = preNode.nextNode;
}
nextNode = preNode.nextNode;
preNode.nextNode = nextNode;
nextNode.preNode = preNode;
}
size--;
}
/**
* 检查传值是否合法
*
* @param index 节点下标
*/
private void checkValid(int index) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException("size: " + size + ",index: " + index);
}
}
public static void main(String[] args) {
DoubleChainList dChainList = new DoubleChainList();
dChainList.add("123");
dChainList.add("456");
dChainList.add("789");
dChainList.add("abc");
dChainList.add("hahaha");
dChainList.addFirst("firstNode");
dChainList.add(3, "insertNode");
dChainList.remove(0);
System.out.println(dChainList.get(2));
}
}
-
双向链表图解
双向链表图
- Java中双向链表：LinkedList源码分析
LinkedList的双向链表结构
private static class Node<E> {
E item; // 链表节点的自身元素值
Node<E> next; // 链表节点的上一个节点指向
Node<E> prev; // 链表节点的下一个节点指向
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList#addFirst(E e) 方法源码分析
public void addFirst(E e) {
linkFirst(e);
}
/**
* Links e as first element.
*/
private void linkFirst(E e) {
// 首先获取当前在头节点的Node
final Node<E> f = first;
// 创建新添加的Node，因添加到头位置，所以初始化Node时，prev节点指向null，next节点指向原头节点的Node
final Node<E> newNode = new Node<>(null, e, f);
// 当前添加的节点自然是作为链表的头节点
first = newNode;
// 这里是检查原头节点是否为null，为null则说明原链表为空
if (f == null)
last = newNode; // 原链表为空时，当前add的节点，即是头节点，也是尾节点，即:头部=尾部
else
// 原链表不为空时，此时当前add的节点已经作为头节点了，接下来只需要将双向链表的指向关系指定即ok，
// 即：原头节点的上一个节点指向的是当前的节点【本人有个小疑问，虽然是当前节点就是头节点，指向当前节点和指向头节点实际上貌似没啥区别，那么为什么不直接指向头节点呢，，f.prev = first 】
f.prev = newNode;
size++;
modCount++;
}
LinkedList#addLast(E e) 方法源码分析
public void addLast(E e) {
linkLast(e);
}
/**
* Links e as last element.
*/
void linkLast(E e) {
// 首先获取链表尾节点Node
final Node<E> l = last;
// 创建新添加的Node，因添加到尾部，固初始化Node时，上一个节点指向原尾节点，下一个节点指向null
final Node<E> newNode = new Node<>(l, e, null);
// 新添加的Node自然作为尾节点
last = newNode;
// 此处判断当前链表是否为空，l 为 null即表示为空链表，即头部=尾部
if (l == null)
first = newNode;
else
// 设置链表节点的指向关系，原尾节点的下一个节点指向当前新添加的节点
l.next = newNode;
size++;
modCount++;
}
LinkedList#add(int, E) 方法源码分析^[因 LinkedList#add(E) 方法内部调用的也是 addLast 方法，固不再做源码分析，参考addLast源码分析即可。]
public void add(int index, E element) {
// 索引检查，源码在下方贴出，比较简单，不做解释
checkPositionIndex(index);
// 针对链表的添加，插头和插尾属于直接插入法，效率比较高，因此，对于指定索引的add动作，优先判断是否属于头插和尾插
if (index == size)
linkLast(element); // 索引index=size时，表示，在链表最后插入一个节点，直接引用addLast即可
else
linkBefore(element, node(index));
}
/**
* Returns the (non-null) Node at the specified element index.
* 获取指定索引上的Node节点
* 使用二分法提高链表的遍历查找效率，防止全链表遍历
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// index < (size >> 1) :使用二分法判断传入的索引在链表的大致位置，若索引小于链表长度的一半，则表示在链表的做半部分中，反之
if (index < (size >> 1)) {
// 索引在链表的左部分时，从链头开始遍历查找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 索引在链表的右部分时，从链尾开始遍历查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
/**
* 找到原链表指定索引位置处的节点后，再将新Node插入到该节点前面
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 获取原链表索引位置节点的上一个节点
final Node<E> pred = succ.prev;
// 创建新节点，上一个节点指向原节点的上一个节点，下一个节点指向原节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 修改原索引位置节点的指向关系，上一个节点指向当前插入的节点
succ.prev = newNode;
// 若原索引位置节点的上一个节点为null，则说明原索引位置为头节点，因此直接头插新节点
if (pred == null)
first = newNode;
else
// 修改原索引位置节点上一个节点的指向关系，其下一个节点指向当前插入的节点
pred.next = newNode;
size++;
modCount++;
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
LinkedList#getFirst(int, E) 方法源码分析
/**
* 获取链表头节点的值
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
LinkedList#getLast(int, E) 方法源码分析
/**
* 获取链表尾节点的值
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
LinkedList#get(int index) 方法源码分析
/**
* 获取链表指定索引位置节点的值
*/
public E get(int index) {
// 检查插入的链表索引是否越界
checkElementIndex(index);
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
LinkedList#set(int index, E element) 方法源码分析
/**
* 设置链表指定索引位置节点的值
* 设置新值后返回旧值
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
LinkedList#removeFirst() 方法源码分析
/**
* 移除链表表头节点
*/
public E removeFirst() {
// 获取头节点Node
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* Unlinks non-null first node f.
* 移除头部节点后，返回头部节点的元素值element
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 获取头节点的元素值
final E element = f.item;
// 获取头节点的下一个节点Node
final Node<E> next = f.next;
// 清空头节点的元素及节点指向关系【协助JVM垃圾回收】
f.item = null;
f.next = null; // help GC
// 将第二个节点设置为头节点
first = next;
// 此处判断链表是否只包含一个节点，若只包含一个节点，则移除头节点后，头部=尾部=null
if (next == null)
last = null;
else
// 设置第二个节点的前一个节点为null
next.prev = null;
size--;
modCount++;
return element;
}
LinkedList#removeLast() 方法源码分析
/**
* 移除链表表头节点
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* Unlinks non-null last node l.
* 移除尾部节点后，返回尾部节点的元素值element
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
// 获取链表尾节点元素值
final E element = l.item;
// 获取链表尾节点的前一个节点Node
final Node<E> prev = l.prev;
// 清空尾节点的值及引用关系【JVM垃圾回收】
l.item = null;
l.prev = null; // help GC
// 尾节点指向倒数第二个节点
last = prev;
// 此处判断链表是否只存在一个节点，若是，则移除节点后: 头部=尾部=null
if (prev == null)
first = null;
else
// 原链表倒数第二个节点成为尾节点后，设置下一个节点的引用为null
prev.next = null;
size--;
modCount++;
return element;
}
LinkedList#remove(int index)方法源码分析
/**
* 移除链表指定索引位置的节点
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* Unlinks non-null node x.
* 移除指定节点，并返回所移除节点的元素值
*/
E unlink(Node<E> x) {
// assert x != null;
// 获取当前移除节点的元素值
final E element = x.item;
// 获取当前移除节点的前一个节点和后一个节点
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
// 若前一个节点为null,则表示当前移除的节点为头节点，头节点直接指向下一个节点
first = next;
} else {
// 若前一个节点不为null ，则设置prev节点的下一个节点直接引用到next节点，并移除当前节点对前一个节点的引用关系【清空移除节点的引用关系】
prev.next = next;
x.prev = null;
}
if (next == null) {
// 若next节点为null，则表示当前移除的节点为尾节点，即直接设置尾节点指向prev节点
last = prev;
} else {
// 若next节点不为null，则修改next节点前一个节点的引用关系为prev节点，同时移除当前节点对下一个节点的引用关系【清空移除节点的引用关系】
next.prev = prev;
x.next = null;
}
// 清空节点元素【上面移除了当前节点的引用关系，这里再移除元素值，JVM就可以直接进行垃圾回收了】
x.item = null;
size--;
modCount++;
return element;
}
LinkedList#remove()方法源码分析
/**
* 该方法直接引用removeFirst()方法，默认移除头节点
*/
public E remove() {
return removeFirst();
}
LinkedList#remove(Object o)方法源码分析
/**
* 从此列表中删除指定元素的第一个匹配项（如果存在）。
* 如果此列表不包含该元素，则它将保持不变。
* 更正式地说，删除索引最低的元素
* 【移除元素需要遍历整个列表】
*/
public boolean remove(Object o) {
if (o == null) {
// 从头节点开始遍历，移除链表中元素为null的第一个匹配节点，若没有匹配，则链表保持不变
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// 从头节点开始遍历，移除链表中指定元素的第一个匹配节点，若没有匹配，则链表保持不变
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
另外LinkedList中还有以下常用的方法，有兴趣可自行查看源码：
LinkedList#indexOf(Object o) 从表头开始检索链表中指定元素第一次出现的索引
LinkedList#lastIndexOf(Object o) 从表尾开始检索链表中指定元素第一次出现的索引
LinkedList#peek() 检索链表表头节点中的元素值，链表为空会返回null
LinkedList#peekFirst() 检索链表表头节点中的元素值，链表为空会返回null
LinkedList#peekLast() 检索链表表尾节点中的元素值，链表为空会返回null
LinkedList#element() 检索链表表头节点中的元素值,链表为空会抛出NoSuchElementException异常
LinkedList#poll() 检索链表表头节点的元素值并移除表头【弹出表头】,链表为空则返回null
LinkedList#pollFirst() 检索链表表头节点的元素值并移除表头【弹出表头】,链表为空则返回null
LinkedList#pollLast() 检索链表表尾节点的元素值并移除表头【弹出表尾】,链表为空则返回null
LinkedList#offer(E e) 添加指定的元素作为此链表的尾部（最后一个元素）
LinkedList#offerFirst(E e) 在当前链表头部插入指定元素
LinkedList#offerLast(E e) 在当前链表尾部插入指定元素
循环链表
结构：链表中的每个元素节点中除了存储自身元素外，还存储了下一个节点以及上一个节点，用来指向上一个节点和下一个节点。且尾节点的下一个节点【tail】指向了头节点【head】，头节点的上一个节点指向的是尾节点。循环链表分为循环单链表和循环双链表，实际原理与上述的单向链表和双向链表很类似，只是多了一层头部和尾部引用关系，可依据上述单向链表和双向链表代码进行变式实现循环链表，此处不做过多的说明，有兴趣可自行实现。
