链表是一种常见的数据结构，链表是由一连串的结点组成，这个节点就是链结点，每个链结点都由数据域和指针域两局部组成。
应用链表构造能够克服数组构造须要事后晓得数据大小的毛病，链表构造能够充沛利用计算机内存空间，实现灵便的内存动静治理。然而链表失去了数组随机读取的长处，同时链表因为减少了结点的指针域，空间开销比拟大。
链表比拟好的一种了解是：将链表看成一个火车，每个车厢之间都是相互连接的，只有找到火车头，就能够找到具体的车身。链表也是，咱们只关怀它的头。
一 单向链表
1.1 单向链表原理图
单向链表的一个链结点蕴含数据域和下一个链结点的指针。头结点也蕴含数据域和指针域，然而个别为了不便查找，头节点不写数据，最初一个结点的指针指向空。
1.2 实现单向链表的存储等操作
创立一个链结点的实体类
public class Node { // 数据域 public long data; // 指针域 public Node next; public Node(long value){ this.data = value; }}1.2.1 插入一个节点
在头节点后插入一个结点，第一步须要将新插入的结点指向头结点指向的结点，第二部将头结点指向新插入的结点。插入结点只须要扭转一个援用，所以复杂度为O(1)。
public class LinkList { private Node head; /** * 在头节点之后插入一个节点 */ public void insertFirst(long value){ Node node = new Node(value); node.next = head; head = node; }}1.2.2 头结点后删除一个结点
在头结点后删除一个结点，就是让头结点指向这个结点的下一个结点。复杂度也是O(1)。
public Node deleteFirst(){ Node tmp = head; head = tmp.next; return tmp;}1.2.3 依据数据域查找结点
查找须要比对每个结点的数据，实践上查找一个结点均匀须要N/2次，所以复杂度为O(N)。
public Node find(long value){ Node current = head; while (current.data != value){ if(current.next == null){ return null; } current = current.next; } return current;}1.2.4 依据数据与删除结点
查找须要比对每个结点的数据，实践上删除一个结点均匀须要N/2次，所以复杂度为O(N)。
public Node delete(int value){ Node current = head; // 以后结点的前一个结点 Node pre = head; while (current.data != value){ if(current.next == null){ return null; } pre = current; current = current.next; } if(current == head){ head = head.next; }else{ pre.next = current.next; } return current;}二 双端链表
2.1 双端链表原理图
双端链表是在单向链表的根底上，头结点减少了一个尾结点的援用。
2.2 实现双端链表的存储等操作
2.2.1 从头部插入结点
如果链表为空，则设置尾结点就是新增加的结点。复杂度为O(1)。
public class FirstLastLinkList { private Node first; private Node last; /** * 在头结点之后插入一个节点 */ public void insertFirst(long value){ Node node = new Node(value); if(first == null){ last = node; } node.next = first; first = node; }}2.2.2 从尾部插入结点
如果链表为空，则设置头结点为新增加的结点，否则设置尾结点的后一个结点为新增加的结点。复杂度为O(1)。
public void insertLast(long value){ Node node = new Node(value); if(first == null){ first = node; }else{ last.next = node; } last = node;}2.2.3 从头部进行删除
判断头结点是否有下一个结点，如果没有则设置尾结点为null，复杂度为O(1)。
public Node deleteFirst(){ Node tmp = first; if(first.next == null){ last = null; } first = tmp.next; return tmp;}三 双向链表
3.1 双向链表原理图
每个结点除了保留对后一个结点的援用外，还保留着对前一个结点的援用。
3.2 实现双向链表的存储等操作
链结点实体类
public class Node { // 数据域 public long data; // 后一个结点指针域 public Node1 next; // 前一个结点指针域 public Node prev; public Node(long value){ this.data = value; }}3.2.1 从头部插入结点
如果链表为空，则设置尾结点为新增加的结点，如果不为空，还须要设置头结点的前一个结点为新增加的结点。插入结点只须要扭转两个结点的援用，所以复杂度为O(1)。
public class DoubleLinkList { private Node first; private Node last; /** * 在头结点之后插入一个节点 */ public void insertFirst(long value){ Node node = new Node(value); if(first == null){ last = node; } else{ first.prev = node; } node.next = first; first = node; }}3.2.2 从尾部插入结点
如果链表为空，则设置头结点为新增加的结点，否则设置尾结点的后一个结点为新增加的结点。同时设置新增加的结点的前一个结点为尾结点。插入结点只须要扭转1个结点的援用，所以复杂度为O(1)。
public void insertLast(long value){ Node node = new Node(value); if(first == null){ first = node; }else{ last.next = node; node.prev = last; } last = node;}3.2.3 从头部删除结点
判断头结点是否有下一个结点，如果没有则设置尾结点为null，否则设置头结点的下一个结点的prev为null。复杂度也为O(1)。
public Node deleteFirst(){ Node tmp = first; if(first.next == null){ last = null; }else{ first.next.prev = null; } first = tmp.next; return tmp;}3.2.4 从尾部删除结点
如果头结点后没有其余结点，则设置头结点为null，否则设置尾结点的前一个结点的next为null，设置尾结点为前一个结点。复杂度为O(1)。
public Node deleteLast(){ Node tmp = last; if(first.next == null){ first = null; }else{ last.prev.next = null; } last = last.prev; return last;}四 总结
链表蕴含一个头结点和多个结点，头结点蕴含一个援用，这个援用通常叫做first，它指向链表的第一个链结点。结点的next为null，则意味着这个结点时尾结点。与数组相比，链表更适宜做插入、删除操作，而查找操作的复杂度更高。还有一个劣势就是链表不须要初始化内存大小，不会造成内存溢出（数组中插入元素个数超过数组长度）或内存节约（申明的数组长度比理论放的元素长）。
点关注、不迷路
如果感觉文章不错，欢送关注、点赞、珍藏，你们的反对是我创作的能源，感激大家。
如果文章写的有问题，请不要悭吝，欢送留言指出，我会及时核查批改。
如果你还想更加深刻的理解我，能够微信搜寻「Java旅途」进行关注。回复「1024」即可取得学习视频及精美电子书。每天7:30准时推送技术文章，让你的下班路不在孤单，而且每月还有送书流动，助你晋升硬实力！