线性表的链式存储--单链表

Java之线性表的链式存储——单链表

我们都知道，线性表的存储结构分为两种，顺序存储结构和链式存储结构，线性表的分类可以参考下图来学习记忆。今天我们主要来学习一下链式存储结构。

一、链式存储介绍

"链式存储结构，地址可以连续也可以不连续的存储单元存储数据元素"——来自定义。

其实，你可以想象这样一个场景，你想找一个人（他的名字叫小谭）,于是你首先去问 A ， A 说他不知道，但是他说 B 可能知道，并告诉了你 B 在哪里，于是你找到 B ，B 说他不知道，但是他说 C 可能知道，并告诉了你 C 的地址，于是你去找到 C ，C 真的知道小谭在何处。

上面场景其实可以帮助我们去理解链表，其实每一个链表都包含多个节点，节点又包含两个部分，一个是数据域（储存节点含有的信息），一个是指针域（储存下一个节点或者上一个节点的地址），而这个指针域就相当于你去问B，B知道C的地址，这个指针域就是存放的 C 的地址。

链表下面其实又细分了3种：单链表、双向链表和循环链表。今天我们先讲单链表。

二、单链表介绍

什么是单链表呢？单链表就是每一个节点只有一个指针域的链表。如下图所示，就是一个带头节点的单链表。下面我们需要知道什么是头指针，头节点和首元节点。

头指针：指向链表节点的个节点的指针

头节点：指在链表的首元节点之前附设的一个节点

首元节点：指在链表中存储个实际数据元素的节点（比如上图的 a1 节点）

三、单链表的创建

单链表的创建有两种方式，分别是头插法和尾插法。

1、头插法

头插法，顾名思义就是把新元素插入到头部的位置，每次新加的元素都作为链表的个节点。那么头插入法在Java中怎么实现呢。首先我们需要定义一个节点，如下

public class ListNode {
  public int val; //数据域
  public ListNode next;//指针域
}