单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。链表是有序的列表，但是它在内存中是存储如下：

【1】链表是以节点的方式来存储，是链式存储；
【2】每个节点包含data域，next域：指向下一个节点；
【3】如图：发现链表的各个节点不一定是连续存储；
【4】链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定；

一、单链表介绍

【1】一种最简单的结点结构如图所示，它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的结点。因为只有一个指针结点，称为单链表：

【2】链表的第一个结点和最后一个结点，分别称为链表的首结点和尾结点。尾结点的特征是其next引用为空null。链表中每个结点的next引用都相当于一个指针，指向另一个结点，借助这些next引用，我们可以从链表的首结点移动到尾结点。在单链表中通常使用head引用来指向链表的首结点，由head引用可以完成对整个链表中所有节点的访问。

【3】在单链表结构中还需要注意的一点是，由于每个结点的数据域都是一个Object类的对象，因此，每个数据元素并非真正如图中那样，而是在结点中的数据域通过一个Object类的对象引用来指向数据元素的。与数组类似，单链表中的结点也具有一个线性次序，即如果结点 P 的next引用指向结点 S，则 P 就是 S 的直接前驱，S 是 P 的下一个节点。单链表的一个重要特性就是只能通过前驱结点找到下一个结点，而无法从后续结点找到前驱结点。

二、单链表的查询、添加、修改、删除操作

【1】查询操作： 在单链表中进行查找操作，只能从链表的首结点开始，通过每个结点的next引用来一次访问链表中的每个结点以完成相应的查找操作。例如需要在单链表中查找是否包含某个数据元素 e，则方法是使用一个循环变量 p，起始时从单链表的头结点开始，每次循环判断 p所指结点的数据域是否和 e 相同，如果相同则可以返回true，否则让p指向下一个节点，继续循环直到链表中所有结点均被访问，此时 p 为null；后续代码会实现。
【关键操作】： ① 起始条件：p = head；② 结束条件：找到e.equals(p.getData())==true未找到p == null ③ p指向下一个结点：p = p.getNext()；
【缺点】： 逐个比较，频繁移动指针，导致效率低下；

【2】修改操作： 在单链表中修改数据，属于增删改查中最简单的操作，通过传入需要修改的节点对象，从链表的head节点向下遍历，如果修改的节点编号NO等于链表中的某个编号NO则将链表中的节点修改为传入的节点即可。后续代码会实现。

【3】添加操作： 在单链表中数据元素的插入，是通过在链表中插入数据元素所属的结点来完成的。对于链表的不同位置，插入的过程会有细微的差别。中间、末尾的添加过程其实是一样的，关键是在首部添加，会有不同，会改变整个单链表的起始结点。后续代码会实现。 关键操作：以添加中间结点为例：① 指明新结点的后继 s.setNext(p.getNext())；或者 s.next = p.next；② 指明新结点的前驱（其实是指明前驱结点的后继是新结点） p.setNext(s)；或者 p.next = s；
【优缺点】： 添加节点不需要移动元素，只需要修改元素的指针即可，效率高。但是如果需要先查询到添加位置再添加新元素，因为有逐个查询的过程，效率不高。

【4】删除操作： 类似添加操作，创建一个临时节点temp向下遍历，判断其next节点是否等于需要删除的节点。如果等于则将临时的next节点指向next节点的next节点。此时需要删除的节点就没有对象引用，JVM进行垃圾回收GC的时候则会回收此对象。后续代码会实现。

在使用单链表实现线性表的时候，为了使程序更加简洁，我们通常在单链表的最前面添加一个哑元结点，也称为头结点。在头结点中不存储任何实质的数据对象，其next域指向线性表中 0 号元素所在的结点，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便，常用头结点。一个带头结点的单链表实现线性表的结构图如图所示：

三、单链表代码实例

package com.algorithms;
 
/**
 * 模拟单链表
 */
public class SingleLinkedList {
    //创建一个 head节点
    Node head = new Node(0,"");
    //向链表中添加元素,首先根据 no(模拟数组下标） 判断插入的位置
    public void insert(Node n) throws IllegalAccessException {
        //定义一个临时节点 插入、删除时使用
        Node temp = head;
        if(n == null || n.getNo() < 0){
            throw new IllegalAccessException("传入的参数不合法");
        }
        //先判断插入的节点，链表中是否存在
        Node node = get(n.getNo());
        if(node != null){
            System.out.println("该节点链表中已存在，不能插入");
            return;
        }
        //如果当前节点等于null 或者 小于 temp.next 的no说明插入在temp.next前面，temp的后面
        //因为是单链表，所以需要确定插入节点的前一个节点 temp 位置
        while(true){
            if(temp.getNext() ==null || n.getNo() < temp.getNext().getNo()){
                //第一步：现将temp的next复制给新的节点
                n.setNext(temp.getNext());
                //第二步：将temp的next 变量更改为新插入的节点
                temp.setNext(n);
                break;
            }else{
                temp = temp.getNext();
            }
        }
    }
 
    //向链表中查询元素
    public Node get(int index) throws IllegalAccessException {
        //定义一个临时节点 插入、删除时使用
        Node temp = head;
        if(index < 0){
            throw new IllegalAccessException("传入的参数不合法");
        }
        while(true){
            if(temp.getNext() == null){
                System.out.println("链表中不存在no="+index+"的元素");
                return null;
            }
            if(temp.getNext().getNo() == index){
                return temp.getNext();
            }else{
                temp = temp.getNext();
            }
        }
    }
 
    //修改节点  只能修改内容
    public void update(Node n) throws IllegalAccessException {
        //定义一个临时节点 插入、删除时使用
        Node temp = head;
        if(n == null){
          throw new IllegalAccessException("传入的参数不合法");
        }
        while (true){
            if(temp.getNext().getNo() == n.getNo()){
                System.out.println("修改元素成功");
                temp.getNext().setValue(n.getValue());
                break;
            }else{
                temp = temp.getNext();
            }
            if(temp.getNext() == null){
                System.out.println("链表中不存在的元素");
                break;
            }
        }
    }
 
    //删除节点,根据下标删除，根据节点的话其实也是获取下标相同的来删除
    public void remove(int index) throws IllegalAccessException {
        //定义一个临时节点 插入、删除时使用
        Node temp = head;
        if(index < 0){
            throw new IllegalAccessException("传入的参数不合法");
        }
        if(get(index) == null){
            System.out.println("删除的节点链表中不存在");
            return;
        }
        //判断temp的下一个节点是否等于当前节点
        while(true){
            if(temp.getNext().getNo() == index){
                //将Next 的指针移动到下一位
                temp.setNext(temp.getNext().getNext());
                break;
            }else{
                temp = temp.getNext();
            }
            if(temp.getNext() == null){
                System.out.println("删除的节点链表中不存在");
                break;
            }
        }
    }
 
    //查看链表中的信息
    public void list(){
        //定义一个临时节点 插入、删除时使用
        Node temp = head;
        while (temp.getNext() != null){
            System.out.println(temp.getNext().toString());
            temp = temp.getNext();
        }
    }
    //测试代码
    public static void main (String[] args) throws Exception {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        Node first = new Node(1, "First");
        Node second = new Node(2, "Second");
        Node fourth = new Node(4, "Fourth");
 
        //添加
        singleLinkedList.insert(first);
        singleLinkedList.insert(second);
        singleLinkedList.insert(fourth);
 
        //展示
        singleLinkedList.list();
 
        //向链表中添加元素
        Node third = new Node(3, "Third");
        singleLinkedList.insert(third);
        //展示
        /*  如下，有序
            Node{no=1, value='First'}
            Node{no=2, value='Second'}
            Node{no=3, value='Third'}
            Node{no=4, value='Fourth'}
         */
        singleLinkedList.list();
 
        //插入相同元素
        //输出：该节点链表中已存在，不能插入
        singleLinkedList.insert(third);
 
        //修改节点
        third = new Node(3, "Third--update");
        singleLinkedList.update(third);
        //输出：Node{no=3, value='Third--update'}
        singleLinkedList.list();
 
        //删除节点
        singleLinkedList.remove(3);
        singleLinkedList.list();
 
        //获取 3 和 4
        Node node3 = singleLinkedList.get(3);
        Node node4 = singleLinkedList.get(4);
        /* 输出
            null
            Node{no=4, value='Fourth'}
         */
        System.out.println(node3);
        System.out.println(node4);
 
    }
}
class Node{
    //编号，排序的属性，唯一
    private int no;
    private String value;
    //单链表的特点，指向下一个与自己相同的对象
    private Node next;
    public Node(int no,String value){
        this.no=no;
        this.value = value;
    }
 
    public int getNo() {
        return no;
    }
 
    public Node getNext() {
        return next;
    }
 
    public void setNext(Node next) {
        this.next = next;
    }
 
    public void setValue(String value) {
        this.value = value;
    }
 
    public String getValue() {
        return value;
    }
 
    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", value='" + value + '\'' +
                '}';
    }
}

四、双向链表

单向链表的缺点：
【1】单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
【2】单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp，temp是待删除节点的前一 个节点；

与单向链表的区别： 主要却别就是双向列表多了一个向前的指针pre，能够通过当前节点，查看自己的上一个节点。方法的实现与单链表基本相同，就是由原来的只考虑next节点的情况，改变成了需要考虑next和pre两个节点而已；

(adsbygoogle = window.adsbygoogle || []).push({});