数据结构《LinkeList 双向链表》

LinkeList

LinkeList 的低层是由双向链表结构组成的，所有元素都是存放到单独的节点当中，通过地址引用将节点串联起来
因此在任意位置插入或删除元素时，都不在需要移动元素，效率较高

下面是双向链表的结构图：

在集合框架中，LinkedList也实现了List接口，具体如下：

1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)

LinkeList 的模拟实现

之前模拟过单向链表，所以前三个方法就不画图了，很简单

public class MyLinkedList {
   
    static class ListNode{
   
       public int val;  // 数值
       public ListNode prev;
       public ListNode next;
       // 初始化数值
        public ListNode(int val) {
   
            this.val = val;
        }
    }
    public ListNode head; //标记头节点
    public ListNode tail; //标记尾节点

    //打印双向链表的节点
    public void display(){
   
        ListNode cur = head;
        while (cur != null){
   
            System.out.println(cur.val+" ");
        }
        System.out.println();
    }

    //获取双向链表的长度
    public int size() {
   
        ListNode cur = this.head;
        int count = 0;
        while(cur != null){
   
            count++;
            cur = cur.next;
        }
        return count;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
   
        ListNode cur = this.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
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

头插法

在双向链表的第一个节点的前面里添加一个新的节点

图解：

源代码：

public void addFirst(int data) {
   
        ListNode node = new ListNode(data);
        // 如果链表里没有节点的情况
        if(head == null){
   
            this.head = node;//第一个节点
            this.tail = node;// 最后一个节点
        }else {
   
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

尾插法

在双向链表的最后一个节点的后里添加一个新的节点

图解

源代码：

 public void addLast(int data) {
   
        ListNode node = new ListNode(data);
        // 如果链表里没有节点的情况
        if(this.head == null){
   
            this.head = node;//第一个节点
            this.tail = node;// 最后一个节点
        
1
2
3
4
5
6
7
8