一、前言

最近在回顾数据结构与算法，有部分的算法题用到了栈的思想，说起栈又不得不说链表了。数组和链表都是线性存储结构的基础，栈和队列都是线性存储结构的应用～

本文主要讲解单链表的基础知识点，做一个简单的入门～如果有错的地方请指正

二、回顾与知新

说起链表，我们先提一下数组吧，跟数组比较一下就很理解链表这种存储结构了。

2.1回顾数组

数组我们无论是C、Java都会学过：

• 数组是一种连续存储线性结构，元素类型相同，大小相等
  

数组的优点：

• 存取速度快
  

数组的缺点：

• 事先必须知道数组的长度
  
• 插入删除元素很慢
  
• 空间通常是有限制的
  
• 需要大块连续的内存块
  
• 插入删除元素的效率很低
  

2.2链表说明

看完了数组，回到我们的链表：

• 链表是离散存储线性结构
  

n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。

链表优点：

• 空间没有限制
  
• 插入删除元素很快
  

链表缺点：

• 存取速度很慢
  

链表相关术语介绍，我还是通过上面那个图来说明吧：

确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推导出来了～

链表又分了好几类：

• 单向链表
  

• 一个节点指向下一个节点
  

• 双向链表
  

• 一个节点有两个指针域
  

• 循环链表
  

• 能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环
  

操作链表要时刻记住的是：

• 节点中指针域指向的就是一个节点了！
  

三、Java实现链表

算法：

• 遍历
  
• 查找
  
• 清空
  
• 销毁
  
• 求长度
  
• 排序
  
• 删除节点
  
• 插入节点
  

首先，我们定义一个类作为节点

• 数据域
  
• 指针域
  

为了操作方便我就直接定义成public了。

public class Node {
    //数据域
    public int data;
    //指针域，指向下一个节点
    public Node next;
    public Node() {
    }
    public Node(int data) {
        this.data = data;
    }
    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
}

3.1创建链表(增加节点)

向链表中插入数据：

• 找到尾节点进行插入
  
• 即使头节点.next为null，不走while循环，也是将头节点与新节点连接的(我已经将head节点初始化过了，因此没必要判断头节点是否为null)～

/**
     * 向链表添加数据
     *
     * @param value 要添加的数据
     */
    public static void addData(int value) {
        //初始化要加入的节点
        Node newNode = new Node(value);
        //临时节点
        Node temp = head;
        // 找到尾节点
        while (temp.next != null) {
            temp = temp.next;
        }
        // 已经包括了头节点.next为null的情况了～
        temp.next = newNode;
    }

3.2遍历链表

上面我们已经编写了增加方法，现在遍历一下看一下是否正确～～～

从首节点开始，不断往后面找，直到后面的节点没有数据：

/**
     * 遍历链表
     *
     * @param head 头节点
     */
    public static void traverse(Node head) {
        //临时节点，从首节点开始
        Node temp = head.next;
        while (temp != null) {
            System.out.println("关注公众号Java3y：" + temp.data);
            //继续下一个
            temp = temp.next;
        }
    }

结果：