本文源码：GitHub·点这里 || GitEE·点这里

一、链表简介

1、链表概念

链表是一种物理存储单元上非间断、非程序的存储构造，数据元素的逻辑程序是通过链表中的指针链接秩序实现的。链表由一系列节点组成，节点能够在运行时动静生成，节点包含两个局部：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

2、根底特点

内存存储

逻辑构造

特点形容

• 物理存储上是无序且不间断的；
• 链表是由多个节点以链式构造组成；
• 逻辑层面上看造成一个有序的链路构造；

链表构造解决数组存储须要事后晓得元素个数的缺点，能够充分利用内存空间，实现灵便的内存动静治理。

二、单向链表

1、根底形容

单向链表是链表的一种，其特点是链表的链接方向是单向的，链表的遍历要从头部开始程序读取；结点形成，head指针指向第一个成为表头结点，终止于最初一个指向NULL的指针。

2、根底操作

增加数据

• 初始化head节点，作为链表的头；
• 批改以后开端节点的next指针；
• 新增加的节点房子在链表开端；

删除数据

遍历找到要删除的节点，把删除节点前个节点的指针指向该删除节点的下个节点；

三、双向链表

1、概念形容

双向链表也叫双链表，是链表的一种，链表的每个数据结点中都有两个指针，别离指向间接后继和间接前驱，从双向链表中的任意一个结点开始，都能够很疾速地拜访它的前驱结点和后继结点，链表构造的应用少数都是结构双向循环链表。

2、根底操作

增加数据

• 遍历找到链表的最初一个节点；
• 批改以后开端节点的next指针；
• 新增加的节点房子在链表开端；
• 增加最新尾节点的prev指针；

删除数据

• 双向链表，基于要删除节点操作即可；
• 操作上图中要删除的Node2节点；
• Node2.prev.next = Node2.next;
• Node2.next.prev = Node2.prev;

通过上述流程的操作，就把链表中一个节点删除，剩下节点再度连接成链式构造。

3、源码剖析

在Java的API中，LinkedList是典型的双向链表构造，上面基于LinkedList源码看双向链表的操作。

根底案例

public class M01_Linked {    public static void main(String[] args) {        List<User> userList = new LinkedList<>() ;        User removeUser = new User(200,"Second") ;        // 增加元素        userList.add(new User(100,"First")) ;        userList.add(removeUser) ;        userList.add(new User(300,"Third")) ;        System.out.println("初始化："+userList);        // 批改元素        userList.get(0).setUserName("Zero");        System.out.println("批改后："+userList);        // 删除元素        userList.remove(removeUser) ;        System.out.println("删除后："+userList);    }}class User {    private Integer userId ;    private String userName ;    public User(Integer userId, String userName) {        this.userId = userId;        this.userName = userName;    }    @Override    public String toString() {        return "User{" +                "userId=" + userId +                ", userName='" + userName + '\'' +                '}';    }    // 省略Get和Set办法}

节点形容

节点三个外围形容：数据，next指针，prev指针。

private static class Node<E> {    E item;         // 数据    Node<E> next;   // 下个指针    Node<E> prev;   // 上个指针    Node(Node<E> prev, E element, Node<E> next) {        this.item = element;        this.next = next;        this.prev = prev;    }}

首位节点解决

基于LinkedList源码，首尾节点形式，针对上图双链表的首位指针特点，这里源码很好了解。

public class LinkedList {    transient Node<E> first;    transient Node<E> last;    // 解决首节点    private void linkFirst(E e) {        final Node<E> f = first;        final Node<E> newNode = new Node<>(null, e, f);        first = newNode;        if (f == null)            last = newNode;        else            f.prev = newNode;    }    // 解决尾节点    void linkLast(E e) {        final Node<E> l = last;        final Node<E> newNode = new Node<>(l, e, null);        last = newNode;        if (l == null)            first = newNode;        else            l.next = newNode;    }}

增加节点

增加节点的办法间接调用linkLast办法，把新节点放到链表的尾部即可。

public boolean add(E e) {    linkLast(e);    return true;}

删除节点

第一步：遍历比照，找到要删除的节点；

public boolean remove(Object o) {    if (o == null) {        for (Node<E> x = first; x != null; x = x.next) {            if (x.item == null) {                unlink(x);                return true;            }        }    } else {        for (Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item)) {                unlink(x);                return true;            }        }    }    return false;}

第二步：移除节点，从新搭建链表构造，并且把以后链表的数据置为null，并返回被移除的节点；

E unlink(Node<E> x) {    final E element = x.item;    final Node<E> next = x.next;    final Node<E> prev = x.prev;    if (prev == null) {        first = next;    } else {        prev.next = next;        x.prev = null;    }    if (next == null) {        last = prev;    } else {        next.prev = prev;        x.next = null;    }    x.item = null;    return element;}

如上就是对Java中LinkedList双链表源码的局部构造剖析，这种代码看多了，总感觉本人写的代码不是Java。

四、环形链表

在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点，这样就造成了环形链表：

环形链表链表的一种构造，特点是表中最初一个结点的指针域指向头结点，整个链表造成一个环。

五、源代码地址

GitHub·地址https://github.com/cicadasmile/model-arithmetic-parentGitEE·地址https://gitee.com/cicadasmile/model-arithmetic-parent

举荐浏览：算法与数据结构