链表(二)——LinkedList(双向链表)的CURD操作的模拟实现

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;//后面的尾
 }
1
2
3
4
5
6
7
8
9
10
11
12
13

头插法

双向链表实现头插法，其核心就是要改变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;

    }
1
2
3
4
5
6
7
8
9
10
11

尾插法

由于是双向链表，所以头插法和尾插法的大致逻辑是一样的，只是这里的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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

任意位置插入结点

在任意位置插入结点，可以利用上面所写的头插法和尾插法，直接调用他们的函数，来解决特殊情况，其他情况，也就是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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

查找是否包含关键字key是否在单链表当中

要想查看链表中是否包含某个值，只需要遍历一遍链表即可，当然此时从任意一边遍历，理论上都可以

    public boolean contains(int key){
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10

删除第一次出现关键字为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的结点");
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

删除所有值为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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

得到单链表的长度

    public int size(){
        ListNode cur = head;int length=0;
        while(cur != null){
            cur = cur.next;
            length++;
        }
        return length;
    }
1
2
3
4
5
6
7
8

打印链表

    public void display(){
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
1
2
3
4
5
6
7
8

清除链表

清除结点可以直接将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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13