顺序表（List）可以根据不同的存储方式来以分类，比如说使用数组或使用节点这种数据结构来实现。在Java中，ArrayList就是由数组为基础结构创建的，而LinkList是由节点对象而构成的。由于Array的下标特性，ArrayList查找、更新元素值的性能好；对于LinkLIst，其添加或删除元素的性能好。链表根据功能特点可以分为多种类型，比如说单向链表、双向链表等。今天，我们来介绍如何实现单链表。
- 单链表的结构和元素存储特点：
- 单链表是以节点对象存储元素的，存储方式是链式的（逻辑结构是一个节点指连着并指向下一个节点）。由于对象是可以在内存中任意位置存储的，所以我们可以知道每个元素的存储存储位置并非是连续的。
- 每个节点对象含有数据域和一个节点变量，该节点变量指向下一个节点的存储位置。
- 链表在内存中的实际结构：
- 链表的逻辑结构：
- 在实现单链表前，我们规定：
- 该链表头节点中不存储数据 (这里默认为0)，但是包含指向下一个节点的节点变量。
- 尾节点中的节点变量指向null。那么头结点中的节点变量指向null时，说明该链表不包含任何元素。
- 代码示例：
import com.sun.xml.internal.bind.marshaller.NoEscapeHandler;public class LinkList {
private Node headNode;private int size;public LinkList(){
this.headNode = new Node(0);this.size = 0;}/*** append one element into the linkList's end* @param data, a integer*/public void appendElement(int data){
Node node = new Node(data);Node temp = this.headNode;//如果当前temp的节点变量为null，说明找到了尾节点。while (temp.getNode() != null){
temp = temp.getNode();}temp.setNode(node);++ this.size;}/*** insert a element into the linkList before one node according to the node's index* @param index*/public void insert(int index, int data){
if(index > this.size || index < 1){
System.out.println("Out of boundary.");return;}Node temp = this.headNode;//控制循环，得到index位置节点的前一个节点。for(int i = 1;i < this.size - 1;i ++){
temp = temp.getNode();}//先把新节点指向index位置节点，在把index位置节点的前一个节点指向新节点。Node node = new Node(data);node.setNode(temp.getNode());temp.setNode(node);++ this.size;}/*** delete a element according to the data.* @param data*/public void deleteElement(int data){
if(this.size == 0)return;//辅助节点为当前节点的前一个节点Node assistNode = this.headNode;Node node = assistNode.getNode();while (node.getData() != data){
if(node.getNode() != null){
assistNode = assistNode.getNode();node = node.getNode();}else {
return;}}//把辅助节点指向当前节点的后一个节点assistNode.setNode(node.getNode());node = null;//回收当前节点-- this.size;}/*** print out all nodes' data in oder.*/public void printAllNode(){
Node temp = this.headNode;while (temp.getNode() != null){
//这里先获取下一个节点并赋给temp，避免head节点的data被打印（我们规定headNode不含数据）temp = temp.getNode();System.out.println(temp.toString());}}}class Node{
private int data;private Node node;public Node(int data){
this.data = data;}public void setData(int data) {
this.data = data;}public void setNode(Node node) {
this.node = node;}public int getData() {
return data;}public Node getNode() {
return node;}@Overridepublic String toString() {
return "Node{" +"data=" + data +'}';}
}