链表和数组之间最大的区别就是，链表不需要一块连续的内存地址，它无需任何的寻址公式来进行下一个元素的寻找，只需要存储对应的引用就可以做到。
数组在进行删除的时候，除非是删除数组尾，否则就需要进行数组的重新整理。在平时开发的时候，可能使用的ArrayList<?>，？一般都可以是Obeject的子类，所以null也可以进行占位，可以不进行重新整理，但是严谨一点的话，理论上是需要进行重新整理的。而链表的特点就是增加和删除。直接对Node的指针进行操作就可以完成。
至于查询方法，如果Array是有序的，那么Array的查询是会比Linked快，如果都不是有序的，需要从头遍历。那么时间复杂度理论上是一致的。
假设我们做个容器进行数据的暂存。Array的特点是，时间天然有序，并且存储时候只需要一个数据的引用就行，但是虚拟内存上需要一块连续的空间。如果使用Linked的话，同样可以做到时间的有序性，但是有个不好的地方就是它存储的数据是 原数据+引用的合集。说白了就是会多一个对象出来，空间上损耗比Array大一点，但是基本无影响。
链表中有几个分类，单链表，双链表，循环链表。
单链表在使用的时候，有个问题就是例如你要删除一个元素，当你遍历到某个元素的时候，你删除了这个元素，但是你已经无法得知之前的节点了，需要重新遍历一遍。当然使用哨兵来存储之前prev节点会是一个很好的选择。在我看链表数据结构的时候，很直观的一个感觉就是链表的重点应该是如何安置哨兵。哨兵的存在可以节约很多的操作，对应的就是空间换时间。
一般手写链表的时候几个地方要注意下：内存泄露，闭环以及指针丢失。
import java.util.LinkedList;
/**
* description: LinkedListDemo
* date: 2020/12/1 8:53
* 单链表练习
* @author: SmartCat
* version: 1.0.0
*/
public class LinkedListDemo<T> {
//头节点
private ScNode<T> head = new ScNode<>(null,null);
//当前结点，默认一开始为头节点
private ScNode<T> cur = head;
//大小
private int size;
//内部类定义节点
static class ScNode<T>{
private T t;
private ScNode next;
public ScNode(T t,ScNode next){
this.t = t;
this.next = next;
}
public ScNode(T t){
this.t = t;
}
@Override
public String toString(){
if (t==null){
return "头节点为空";
}
return t.toString();
}
}
public void add(T t){
ScNode node = new ScNode(t);
cur.next = node;
cur = node;
size++;
}
public void remove(T t){
ScNode scNode = null;
ScNode prev = null;
//空链表则跳出
if (head.next==null){
return;
}
//第一个Node
scNode = head.next;
prev = head;
while (scNode!=null){
if (scNode.t.equals(t)){
prev.next = scNode.next;
size--;
return;
}else {
prev = scNode;
scNode = scNode.next;
}
}
}
public int getSize() {
return size;
}
@Override
public String toString(){
StringBuilder builder = new StringBuilder();
ScNode scNode = head.next;
while (scNode!=null&&scNode.next!=null){
builder.append(scNode.t.toString()).append(" ");
scNode = scNode.next;
}
return builder.toString();
}
public void getCur(){
System.out.println(cur.toString());
}
public void reverse(){
//如果是空链表，无需反转
if (head.next==null){
return;
}
//反转需要三个节点
ScNode prev = this.head;
ScNode cur = prev.next;
head.next = null;
while (cur!=null){
ScNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
this.head = prev;
}
}
public boolean check(){
ScNode scNode1 = this.head;
ScNode scNode2 = this.head;
while (scNode1.next!=null&&scNode2.next.next!=null){
scNode1 = scNode1.next;
scNode2 = scNode2.next.next;
if (scNode1.equals(scNode2)){
return false;
}else {return true;}
}
return false;
}
public static LinkedListDemo<Integer> merge(LinkedListDemo<Integer> list1,LinkedListDemo<Integer> list2){
LinkedListDemo<Integer> list= new LinkedListDemo<>();
if (list1.head.next==null||list2.head.next==null){
return list;
}
ScNode<Integer> node1 = list1.head.next;
ScNode<Integer> node2 = list2.head.next;
ScNode<Integer> node = list.head;
while (node1!=null||node2!=null){
if (node1==null&&node2!=null){
node.next = node2;
node2 = node2.next;
node = node.next;
}
if (node2==null&&node1!=null){
node.next = node1;
node1 = node1.next;
node = node.next;
}if (node1!=null&&node2!=null){
if (node1.t>node2.t){
node.next = node2;
node2 = node2.next;
node = node.next;
}else {
node.next = node1;
node1 = node1.next;
node = node.next;
}
}
}
return list;
}
public static void main(String[] args) {
LinkedListDemo<Integer> demo = new LinkedListDemo<>();
for (int i = 10; i <= 15; i++) {
demo.add(i);
}
System.out.println(demo.toString());
System.out.println("**************");
LinkedListDemo<Integer> demo1 = new LinkedListDemo<>();
for (int i = 5; i <= 15; i++) {
demo1.add(i);
}
System.out.println(demo1.toString());
LinkedListDemo<Integer> linkedListDemo = LinkedListDemo.merge(demo, demo1);
System.out.println(linkedListDemo.toString());
}
}
同样的空间换时间的思想还有：快慢指针思想。至于双链表的提出，使用哨兵可以解决的情况下，为什么还需要存prev节点呢？
我个人认为一个是在多线程的时候，哨兵的争抢过于频繁，另外一个就是因为双链表本身就具有了单链表的功能，只是在存储上会多一个前向指针。所以在不考虑空间浪费的情况下，双链表更通用，覆盖面更广。