LinkedList介绍
LinkedList的底层是双向链表，它不仅和ArrayList一样，是List的实现类，同时也是Deque的实现类，也就是说，LInked List实现了List和Deque接口。
- 上述集合框架中，LinkedList没有实现RandomAccess接口，所以不支持随机访问
- LInkedList在删除和插入的操作中，不用移动结点，只需要改变结点的指向就可以，所以效率较高
跟上一章单向链表一样链表（一）——单向链表实现，双向链表也有相应的val数据域和next值，但与单链表不一样的地方是，这里引进了prev值，也就是前驱，next储存的是该结点下一个结点的地址，prev储存的是该链表上一个结点的地址，所以双向链表的结点指向两个方向，这里我将起始结点称为head，末尾结点称为last，分别代表两个末端结尾。在单链表的基础上，实现双向链表就简单的多
定义结点
这里的结点，是通过内部类放在LinkedList内部，用ListNode来表示
public class myLinkedList {
static class ListNode{
public int val;
ListNode prev;//前驱
ListNode next;//后继
public ListNode(int val) {
this.val = val;
}
}
ListNode head;//前面的头
ListNode last;//后面的尾
}
头插法
双向链表实现头插法，其核心就是要改变head对应结点的prev，指向新插入的结点的地址，新插入的结点的next指向head对应结点的地址，最后在将head指向新的结点的位置。考虑特殊情况，当链表为空时插入新的链表时，只需要将head位置指向新插入结点的位置即可，此时last也要指向新插入的结点cur位置。
public void addFirst(int data){
ListNode cur = new ListNode(data);
if(head==null){
last = cur;
}else{
head.prev=cur;
cur.next=head;
}
head=cur;
}
尾插法
由于是双向链表，所以头插法和尾插法的大致逻辑是一样的，只是这里的head用last表示，可以把他看作反向的头插法
//尾插法
public void addLast(int data){
ListNode cur = new ListNode(data);
if(last == null){
last = cur;
head=cur;
}else{
last.next = cur;
cur.prev = last;
last = cur;
}
}
任意位置插入结点
在任意位置插入结点，可以利用上面所写的头插法和尾插法，直接调用他们的函数，来解决特殊情况，其他情况，也就是index不在链表开头和结尾，在链表的中间点位置，此时改变四个值，这时候要找到index位置的前一个结点，通过改变prev和next指向，就可以实现任意位置插入结点
public void addIndex(int index,int data){
ListNode cur = new ListNode(data);
if(index == 0){
addFirst(data);
return;
}
if(index == size()){
addLast(data);
return;
}
ListNode temp = findIndexPre(index);
cur.next = temp.next;
cur.prev = cur;
temp.next = cur;
temp.next.prev = cur;
}
public ListNode findIndexPre(int index){
ListNode preNode = head;
for (int i = 0; i < index-1; i++) {
preNode = preNode.next;
}
return preNode;
}
查找是否包含关键字key是否在单链表当中
要想查看链表中是否包含某个值，只需要遍历一遍链表即可，当然此时从任意一边遍历，理论上都可以
public boolean contains(int key){
ListNode cur = head;
while(cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}
删除第一次出现关键字为key的节点
删除中间位置的结点比较简单只需要
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
但是当删掉的结点时链表的两边，此时如果不进行处理，就会造成空指针异常，cur.prev和cur.next要防止出现异常的情况 如果cur.next != null，也就是删除的结点时last指向的位置，只需要改变删除检点前一个结点的next值就行了。cur.prev.next = cur.next;
public void remove(int key){
ListNode cur = head;
//如果链表为空
if(head == null)return;
if(head.next == null){
if(head.val == key){
head = null;
}
}
//找到符合key的结点
while(cur != null) {
if(cur.val == key){
if(head.val == key){
head = head.next;
return;
}
cur.prev.next = cur.next;
if(cur.next != null)
cur.next.prev = cur.prev;
return;
}
cur = cur.next;
}
System.out.println("找不到val为key的结点");
}
删除所有值为key的节点
public void removeAllKey(int key){
ListNode cur = head;
//如果链表为空
if(head == null)return;
if(head.next == null){
if(head.val == key){
head = null;
}
}
//找到符合key的结点
while(cur != null) {
if(cur.val == key){
if(head.val == key){
head = head.next;
head.prev = null;
}
cur.prev.next = cur.next;
if(cur.next != null)
cur.next.prev = cur.prev;
// return;
}
cur = cur.next;
}
}
得到单链表的长度
public int size(){
ListNode cur = head;int length=0;
while(cur != null){
cur = cur.next;
length++;
}
return length;
}
打印链表
public void display(){
ListNode cur = head;
while(cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
清除链表
清除结点可以直接将head和last置为空就可以实现链表的清除，但是如果想把链表中所有的结点prev和next值置为null，就需要遍历整个链表，此时需要创建一个临时结点，记录当前结点下一个结点的位置，防止cur找不到下一个结点。cur每进一步，就将当前结点的prev和next置为空。
public void clear(){
//head == null; last == null;
ListNode cur = head;
ListNode curNext = head;
while(cur.next != null){
curNext = cur.next;
cur.next = null;
cur.prev = null;
cur = curNext;
}
head = null;
last = null;
}