一：概述
数组是严格的正规军，那么链表就是灵活多变的地下党
链表是一种在物理上非连续、非顺序的数据结构，由若干节点(node) 所组成 单向链表的每一个节点又包含两部分，一部分是存放数据变量的data，另一部分是指向下一节点的指针next.
二：链表的具体说明
<1>链表的基本操作总括
* 链表的基本操作：
* 1. 查找结点
* 在查找元素时，链表不像数组那样可以通过下标快速定位，只能从头结点开始向后一个节点
* 一个一个节点逐一查找
* 例如给出一个链表，需要查找从头节点开始的第3个节点。
* (1) 第一步，将查找的指针定位到头节点
* (2) 第二步：根据头节点的next指针，定位到第2个节点。
* (3) 第三步：根据第2个节点的next指针，定位到第3个节点
* 链表中的数据只能按顺序进行访问，最坏的时间复杂度是O(n)
*
*
* 2. 更新节点
* 如果不考虑查找节点的过程，链表的更新过程会像数组那样简单，
* 直接把旧数据换成新数据即可。
*
* 3 .插入节点
* 与数组类似
* 尾部插入
* 头部插入
* 中间插入
*
* 尾部插入是最简单的一种情况，把最后一个节点的next指针指向新的插入节点即可。
*
* 头部插入，可以分成两个步骤：
* 第一步：把新结点的next指针指向原先的头节点
* 第二步：把新结点变为链表的头节点
*
* 中间插入同样可以分为两个步骤：
* 第一步：新节点的next指针，指向插入位置的节点。
* 第二步：插入位置前置节点的next指针，指向新节点
* 只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑
* 扩容问题
*
* 4. 删除元素
* 链表的删除操作同样分为三种情况：
* 尾部删除
* 头部删除
* 中间删除
*
* 尾部删除是最简单的一种情况，把倒数第二个节点的next指针指向空即可
* 头部删除：也很简单，把链表的头节点设为原先节点的next指针即可
* 中间删除：同样很简单，把删除节点的前置节点的next指针，指向
* 要删除元素的下一个节点即可。
* 这里需要注意的是，许多的高级语言，如JAVA，拥有自动化的
* 垃圾回收机制，所以我们不用刻意的去删除节点，只要没有外部引用指向它们，
* 被删除的节点会自动被回收
*
* 如果不考虑插入、删除操作之前查找元素的过程，只考虑纯粹的插入和删除操作
* 时间复杂度都是O(1)
* */<2>插入元素
// 头节点指针
private Node head;
// 尾节点指针
private Node last;
// 链表的实际长度
private int size;
/**
* @param data :插入元素
* @param index: 插入位置
*/
public void insert(int data, int index) throws Exception {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表的范围");
}
Node insertedNode = new Node(data);
if (size == 0) {
// 空链表
head = insertedNode;
last = insertedNode;
} else if (index == 0) {
// 插入头部
insertedNode.next = head;
head = insertedNode;
} else if (size == index) {
// 插入尾部
insertedNode.next = last;
last = insertedNode;
} else {
//插入中间
Node prevNode = get(index - 1);
insertedNode.next = prevNode.next;
prevNode.next = insertedNode;
}
size++;
}<3>删除元素
// 头节点指针
private Node head;
// 尾节点指针
private Node last;
// 链表的实际长度
private int size;
/**
* 删除链表的元素
*
* @param index: 删除位置
*/
public Node remove(int index) throws Exception {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node removedNode = null;
if (index == 0) {
// 删除头节点
removedNode = head;
head = head.next;
} else if (index == size - 1) {
// 删除尾节点
Node preNode = get(index - 1);
removedNode = preNode.next;
preNode.next = null;
last = preNode;
} else {
// 删除中间节点
Node prevNode = get(index - 1);
Node nextNode = prevNode.next.next;
removedNode = prevNode;
prevNode.next = nextNode;
}
size--;
return removedNode;
}<4>查找元素
// 头节点指针
private Node head;
// 尾节点指针
private Node last;
// 链表的实际长度
private int size;
/**
* 链表查找元素
*
* @param index: 查找的位置
*/
public Node get(int index) throws Exception {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围！");
}
Node temp = head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
}<5>输出，查找节点以及打印
/**
* 输出链表
*/
public void output() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data);
temp = temp.next;
}
}
/**
* 链表节点
*/
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
public static void main(String[] args) throws Exception {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.insert(3,0);
myLinkedList.insert(7,1);
myLinkedList.insert(9,2);
myLinkedList.insert(5,3);
myLinkedList.insert(6,1);
myLinkedList.remove(0);
myLinkedList.output();
}以上是对单链表相关操作的代码实现。为了尾部插入的方便，代码中额外增加了
指向链表尾节点的last
三：链表拓展
<1>链表总结
链表的第一个节点被称为头节点，最后一个节点被称为尾节点，尾节点的next指针指向空
与数组按照下标来随机访问寻找元素不同，对于链表的其中一个节点A，只能根据节点A的
next指针来找到该节点的下一个节点B，再根据节点B得next指针找到下一个节点C
这正如地下党得联络方式一样，一级一级，单线传递
<2>双向链表
双向链表
* 双向链表比单向链表稍微复杂一点，它的每一个节点除了又有data和next指针之外，还拥有指向前
* 置节点的prev指针。
<3>链表的存储方式
链表的存储方式 数组在内存中的存储方式是顺序存储，那么链表在内存中的存储方式则是随机存储
随机存储：数组在内存中的占用了连续完整的存储空间。而链表则采用了见缝插针的方式，链表 的每一个节点分布在内存中的不同位置，依靠next指针关联起来。这样可以灵活的有效利用 零散的碎片空间
<4>数组与链表的性能对比
* 数组 VS 链表
* 数组和链表都属于线性的数据结构
* 数据结构没有绝对的好坏
* 数组和链表各有千秋
* 数组和链表相关操作性能，对比：
* 查找 更新 插入 删除
* 数组 O(1) O(1) O(n) O(n)
* 链表 O(n) O(1) O(1) O(1)
*
* 从表格中可以看出，数组的优势在于能够快速定位元素，
* 对于读操作多、写操作少的场景来说，用数组更合适一些
* 相反地，链表的优势在于能够灵活地进行插入和删除操作
* 如果需要在尾部频繁的插入、删除元素，用链表比较合适
* 一些