链表的实现

例题：https://leetcode-cn.com/problems/design-linked-list/

单链表

成员变量

Node head = null;	//头节点
int size;		//链表大小
or
int index;	//链表索引

内部节点类

class Node{
	int val;	//节点数据，可以用泛型
	Node next;	//指向下一个节点
	public Node(int val){
		this.val = val;
	}
}

插入新的头节点

1. Node node = new Node(val);
2. node.next = head;
3. head = node;

插入新的节点（以在头节点及其下一个节点间插入节点为例）

1. Node node = new Node(val);
2. node.next = head.next;
3. head.next = node;

注意：在头部插入节点的操作和此操作不同，在大多数时候需要为此写一个if进行特殊操作
为了使二者的操作统一，可以利用虚拟头结点 dummyHead ，dummyHead.next 即为
实际头结点 head，这样插入节点的操作就统一了，最后 return dummyHead.next 即可

删除节点

1. 将该节点的上一个节点的next指向该节点的下一个节点或null
2. 其实也就是相当于跳过该节点
3. 删除头结点，只需要将head 下移即可。head = head.next

遍历链表(下标从0开始)

Node node = head;
for(int i = 0; i<size; i++){
	System.out.println(node.val);
	node = node.next;
}

双链表

成员变量

Node head = null;
int index = -1;

内部节点类

class Node{
	int val;	//节点数据，可以用泛型
	Node next = null;	//指向下一个节点
	Node pre = null;		// 指向下一个结点
	public Node(int val){
		this.val = val;
	}
}

插入头节点

// 双链表多一个pre指针，若head为null引用head.pre会空指针异常。所以要判断
if(head != null){
	Node node = new Node(val);
	node.next = head;
	node.pre = null;
	head.pre = node;
}
head = node;

插入节点（非头非尾）

// 假设我在temp结点前面插入一个结点
Node node = new Node(val);
node.next = tmp;	// 先解决的node的两个指针，在解决前后两个结点的指针
node.pre = tmp.pre;
tmp.pre.next = node;
tmp.pre = node;

插入尾节点

// 假设尾节点为tmp
Node node = new Node(val);
node.next = null;
node.pre = tmp;
tmp.next = node;

注意：双链表除了有插入头结点这个特殊情况外，还有插入尾结点这个特殊情况。
此时我们可以利用虚拟头结点和虚拟尾结点来实现双链表插入操作的统一

删除头结点

if(head.next == null){
	head == null;
}else{
	head = head.next;
}

删除结点（非头非尾）

// 假设我要删除node这个结点
node.pre.next = node.next;
node.next.pre = node.pre;

删除尾结点

// 假设node为尾结点
if(node == head){
	head = null;
}else{
	node.pre.next = null;
}

遍历操作和单链表相同，只不过还可以从尾巴遍历回去