线性表是n个数据元素的有限序列，在存储线性表时，需要存储数据元素和元素之间的关系。根据存储关系的不同，在计算机的物理层面对线性表的表示分为两种形式

1. 顺序存储。线性表的元素可存储在地址连续的内存单元中。此时内存单元中存储的是元素的值，而元素的前后关系通过内存单元地址的前后关系隐式体现。
2. 链式存储。线性表的元素可存储在任意地址的内存单元中。其中，内存单元中存储元素值和用于指向直接后继的信息，元素的关系显式存储在节点中。

顺序存储和链式存储都是线性表的底层基础实现。其中，使用链式存储的线性表可称为链表。

链表分类

从定义可知，链表的核心是存储数据元素和关系的节点。节点的定义采用的递归的方式，其中用于存储关系信息的部分仍是一个节点。

根据节点内存储关系信息的数量的不同，链表可分为

• 单向链表 节点中只存储一个指向后继节点的指针。
  • 若尾节点的后继节点指向了头节点，则称为单向循环链表。
• 双向链表 节点中存储两个指针，分别指向前驱节点和后继节点。
  • 若尾节点和头节点互相指向，则称为双向循环链表。

特点

• 动态性
  在声明链表时，无需指定链表容量。根据需要在运行时创建节点，并将节点添加到链表中。这也是链表的最大特点，解决了顺序存储（数组）因扩容引起的性能下降。
• 不支持随机访问
  由于链表元素的存储地址不连续，获取链表中元素只能通过遍历的方式。

基于链表和数组的特点，可知

• 顺序存储（数组）用于有索引的语义，支持快速查询。
• 链表不适用于有索引的语义，支持动态扩容。

链表的增删改查时间复杂度都是O(n),性能比数组差，若只对表头进行增删查，时间复杂度将为O(1)。结合链表的动态性（没有扩容操作），在特定场景比数组有优势。

虚拟头节点

当没有虚拟头节点时，执行非头节点的插入操作首先使用循环找到目标位置前的节点，然后执行插入操作。但由于头节点没有前置节点，需要单独处理。为了统一处理插入操作，可引入虚拟头节点。初始化链表时，虚拟头节点不存储元素（e为null），也不指向任何元素(next为null)。

	//虚拟头节点.链表成员变量
private Node dummyNode;
//私有类型，外部用户不能访问和修改
private int size;
public LinkedList(){
//初始化虚拟头节点
dummyNode = new Node(null,null);
size = 0;
}

在需要链表中查找某些位置时，需要用到循环操作。在循环之前，需要定义一个游标，指示当前循环到的位置。分以下情况

• 当查找指定位置前一个位置时（有断链操作），此时可以将虚拟头节点赋值给游标，使所有节点的循环处理方式统一

• 当获取的指定位置时，可将虚拟头节点的下一个节点赋值给游标，即真实头节点，使所有节点的循环处理方式统一。

这两种方式是一种统战思路，当然可以直接把虚拟头节点赋值给游标，再增加一些额外处理逻辑（index + 1或结果node.next），代码不优雅。

递归

本质上，将原来的问题，转化未更小的同一问题。

递归使用

1. 求解最基本问题。需要手动处理。找到最基本问题，边界问题。

2. 大问题转化未小问题 难点 使用小问题的答案解决大问题。把小问题当作已知结果

方法的递归调用，代码指令相同，当每次产生的方法执行环境、参数都是新的。注意程序是卡在递归调用的位置，递归调用后面的代码需要等到返回递归调用值之后才能执行。

缺点： 函数调用时间、系统栈空间。数量大时消耗内存空间

链表天然的递归性 头节点后面是一个更短链表 几乎链表所有操作都可以使用递归

实践

在业务类中使用链表

1. 定义内部节点类。节点类的指针数量决定了链表是单向还是双向。
2. 给业务类添加若干个节点类成员变量 。从链表的整体考虑，用节点表示游标数量。譬如只有头节点（一个节点成员变量）、只有头尾节点（两个节点成员变量）等。

public class LinkedList<E> {
/**
* node节点
* 声明为私有内部类
*/
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
//Node(e,null);
this(e,null);
}
public Node(Node node){
this(null,node);
}
@Override
public String toString(){
return e.toString();
}
}
//虚拟头节点
private Node dummyNode;
//私有类型，外部用户不能访问呢修改
private int size;
public LinkedList(){
dummyNode = new Node(null,null);
size = 0;
}
/* public LinkedList(Array array){
new Node(array[])
}*/
public int getSize(){
return
this.size;
}
/**
* 在链表头添加元素
* 添加的是元素值，不是节点
* 节点是辅助实现链表，主要是使用节点递归存储节点之间的关系
* 同时存储值。
* @param e
*/
public void addFirst(E e){
add(0,e);
}
/**
* 在（0-basec）指定位置插入节点
* 思路（基于没有虚拟头节点）：使用循环找到目标位置前的节点，然后执行插入操作
* 注意该思路不适用与头节点，需单独处理
*这不是常用操作，练习笔试用
* @param e
* @param index
*/
public void add(int index,E e){
if(size < index || index < 0){
throw new IllegalArgumentException("参数非法");
}
Node prev = dummyNode;
for (int j = 0; j < index ; j++) {
prev = prev.next;
}
Node node = new Node(e);
//以下两行的顺序很重要
//断开的后半部分要先处理
node.next = prev.next;
prev.next = node;
size++;
}
/**
* 根据索引（o-based）获取元素值
* 链表中不是常用操作，练习用。
* 注意区分，此处查找的是指定位置的元素，而插入节点addIndex()查找的是指定位置前一个位置的元素。
* @param index
* @return
*/
public E get(int index){
if(index < 0 || index > size){
throw new IllegalArgumentException("参数非法");
}
Node n = dummyNode;
for (int i = 0; i < index; i++) {
n = n.next;
}
return n.next.e;
}
public E getFirst(){
return get(0);
}
public E getLast(){
return get(size -1);
}
/**
* 更新元素
* @param index
* @param e
*/
public void set(int index,E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("参数非法");
}
Node n = dummyNode;
for (int i = 0; i < index + 1; i++) {
n = n.next;
}
n.e = e;
}
/**
* 是否存在
* @param e
* @return
*/
public boolean contains(E e){
Node cur = dummyNode.next;
while (cur.next != null){
if(cur.e.equals(e)){
return true;
}
cur = cur.next;
}
return false;
}
public E removeFirst(){
return remove(0);
}
public E removeLast(){
return remove(size - 1);
}
public E remove(int index){
if(index < 0 || index > size){
throw new IllegalArgumentException("参数非法");
}
Node n = dummyNode;
for (int i = 0; i < index; i++) {
n = n.next;
}
Node d = n.next;
n.next = n.next.next;
//移除引用，使其他时候d.next的元素可以被回收
d.next = null;
size--;
return d.e;
}
@Override
public String toString(){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("result:[");
Node cur = dummyNode.next;
while (cur != null){
stringBuilder.append(cur +"->");
cur = cur.next;
}
/* //for方式 作用和while一样
for(Node cur = dummyNode.next; cur != null; cur = cur.next){
stringBuilder.append(cur +"->");
}*/
return
stringBuilder.append("null ] end").toString();
}
}

延申

• 涉及索引时，要提前确认起始索引是0还是1，即0-based or 1-based

最后

以上就是热情白开水为你收集整理的详解链表LinkedList链表分类特点虚拟头节点递归实践延申的全部内容，希望文章能够帮你解决详解链表LinkedList链表分类特点虚拟头节点递归实践延申所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。