1. 定义

数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链表，别名 链式存储结构 或 单链表，用于存储逻辑关系为 “一对一” 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。
物理存储结构
使用链表存储 {1,3,5}，数据的物理存储状态，如图：
image.png
上图无法体现出各数据之间的逻辑关系。对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。如图：
image.png

2. 链表的节点

链表中每个数据的存储都由以下两部分组成：

  1. 数据元素本身，其所在的区域称为数据域；
  2. 指向直接后继元素的指针，所在的区域称为指针域；

image.png
逻辑存储结构
使用链表存储 {1,3,5}，数据存储的逻辑结构为：
image.png
因此，节点会被抽象为一个节点类：

  1.     private static class Node<E> {
  2.         E item;
  3.         Node<E> next;
  5.         Node(LinkedList.Node<E> var1, E var2,) {
  6.             this.item = var2;
  7.             this.next = var1;
  8.         }
  9.     }

3. 链表的数据结构

前面图示的链表结构并不完整。一个完整的链表需要由以下几部分构成：

  1. 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
  2. 节点：链表中的节点又细分为头节点和其他节点；

因此，一个存储 {1,2,3} 的完整链表结构如图：
image.png