数据结构学习:链表

一、什么是链表？

• 熟悉数组的朋友们可能知道:数组是用一块连续内存空间来存储数据,根据下标访问可以达到O(1)
• 链表正相反,用指针串起一块块不连续的内存空间来存储数据
• 链表同数组一样,都为线性表结构,都支持插入、删除、查询等操作
• 链表衍生出单向链表、双向链表、循环链表等结构

二、单向链表代码实现

在这里插入代码片
1

三、双向链表代码实现

在这里插入代码片
1

四、双向链表相比于单向链表的优势?

• 双向链表需要额外的两个空间来存储前继节点和后继节点的地址,支持双向遍历,存储同样多的数据是比单向链表更费时间的
• 很多人说链表适合插入或删除,插入或删除的时间复杂度为O(1),但这种说法是不准确的,比如说删除,不外乎两种情况:给定值删除;给定节点删除,第一种情况不论是单向链表还是双向链表,都要从头遍历找到value等于给定值的结点,然后删除,第二种情况,单向链表还是需要遍历链表,找到待删除节点的前置节点,然后进行删除,时间复杂度为O(n),双向链表因为保存了前置结点的指针,是O(1)操作
• 同样,若是在某个值后插入结点,单向链表和双向链表的时间复杂度都为O(n);若是某个结点后插入结点,单向和双向的时间复杂度都为O(1);若是某个节点前插入结点,双向链表时间复杂度为O(1),单向则为O(n)

五、链表和数组有什么区别?该如何抉择

• 插入、删除、查询等操作,一般情况下,链表和数组的时间复杂度是相反的
• 数组使用的是连续内存空间,CPU在从内存读取数据的时候,会先把数据加载到缓存,方便下次直接访问缓存,而CPU把内存加载到缓存的过程是加载数据块的,数组的连续内存空间地址会一并加载到缓存中,而链表是分散的,对CPU缓存是不友好的
• 数组的空间是大小固定,一经声明就要占用一整块连续内存空间,如果申请过大,可能报内存不足;如果申请过小,后边又需要扩容,而扩容需要把原先数组整个拷贝过去,是非常耗时的,而链表则没有大小的限制,天然的支持动态扩容
• 如果代码对内存的要求比较严苛,可以使用数组,因为链表要额外存储指针,内存消耗翻倍;此外,频繁的插入和删除,还会造成内存碎片

六、链表的其它操作

package LinkedList;

/*
    链表的一些其它操作,包括
    单链表翻转
    链表中环的检测
    有序链表合并
    删除链表中倒数第K个节点
    找到链表的中间节点
 */
public class LinkedListAlgo {
    static class node{
        private  int value;
        private node next;

        public node(int o){
            this.value = o;
        }
    }

    /*
        单链表翻转
        找到next节点和prev节点
     */
    public static node reverse(node p){
        node curr = p;
        node pre = null;
        node next = null;

        while (curr != null){
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }

        return pre;
    }

    /*
        链表中环的检测,检测链表是否为循环链表
        使用快慢指针,快指针先走一步,然后快指针走两步,慢指针走一步,若其中有null,则退出;能相遇,表示其中有环
     */
    public static boolean checkCircle(node p){
        if (p == null) return false;

        node fast = p.next;
        node slow = p;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }

        return false;
    }

    /*
        合并有序链表
        操作和排序两个有序数组一致,比较头结点,小的放入一个新的链表中
     */

    public static node mergeTwoList(node p1,node p2){
        node soldier = new node(0); //哨兵节点,简化操作
        node head = soldier;

        while (p1 != null && p2 != null){
            if (p2.value > p1.value){
                head.next = p1;
                p1 = p1.next;
            }else{
                head.next = p2;
                p2 = p2.next;
            }
            head = head.next;
        }

        if (p1 != null) head.next = p1;
        if (p2 != null) head.next = p2;

        return soldier.next;
    }

    /*
        删除链表中倒数第K个节点
        同样使用快慢指针,快指针先走K步,然后快慢指针同时走,快指针到链表尾的时候,慢指针就到了倒数第K个节点
     */
    public static node deleteKnode(node p,int k){
        node fast = p;
        int i = 1;
        while (fast != null && i < k){
            fast = fast.next;
            i += 1;
        }

        node slow = p;
        node pre = null;
        while (fast != null && fast.next.next != null){
            fast = fast.next;
            slow = slow.next;
        }

        if (pre == null){
            //表明链表中结点数只有k个,倒数第K个为第一个,删除头节点即可
            p = p.next;
        }else{
            pre.next = pre.next.next; //找到前置节点,直接指向下下个元素
        }

        return p;
    }

    /*
        找到链表的中间节点
        同样使用快慢指针法,快慢指针同时从头节点出发,快指针走两步,慢指针走一步,快指针走到尾的时候,慢指针的位置就是中间节点
     */
    public static node findMidNode(node p){
        node fast = p;
        node slow = p;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129