【数据结构】链表

一、何为链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

三、手写LinkedList

参考JDK中的LinkedList，写法基本一致，仅用于自己学习。

public class LinkedList<E> implements List<E> {

    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

    @Override
    public boolean add(E e) {
        linkLast(e); // 默认尾插
        return false;
    }

    /**
     * 头插法
     * @param e
     */
    private void linkFirst(E e) {
        Node<E> f = first;
        Node<E> newNode = new Node<>(e, null, f);
        first = newNode;
        if (f == null) {
            last = newNode;
        } else {
            f.prev = newNode;
        }
        size++;
    }

    /**
     * 尾插法
     * @param e
     */
    private void linkLast(E e) {
        Node<E> l = last;
        Node<E> newNode = new Node<>(e, l, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    /**
     * 插链操作
     * @param e
     */
    private void unLink(Node<E> e) {
        Node<E> prev = e.prev;
        Node<E> next = e.next;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            e.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            e.next = null;
        }
        e.item = null;
        size--;
    }

    @Override
    public boolean addFirst(E e) {
        linkFirst(e);
        return true;
    }

    @Override
    public boolean addLast(E e) {
        linkLast(e);
        return true;
    }

    @Override
    public void remove(int index) {
        checkElementIndex(index);
        unLink(node(index));
    }

    private E unLinkFirst(Node<E> f) {
        E item = f.item;
        Node<E> next = f.next;
        f.item = null;
        f.next = null;
        first = next;
        if (next == null) {
            last = null;
        } else {
            next.prev = null;
        }
        size--;
        return item;
    }

    private E unLinkLast(Node<E> l) {
        E item = l.item;
        Node<E> prev = l.prev;
        l.item = null;
        l.prev = null;
        last = prev;
        if (prev == null) {
            first = null;
        } else {
            prev.next = null;
        }
        size--;
        return item;
    }

    @Override
    public E remove() { // 默认头删
        return removeFirst();
    }

    @Override
    public E removeFirst() {
        Node<E> f = first;
        if (f == null) {
            return null;
        }
        return unLinkFirst(f);
    }

    private Node<E> node(int index) {
        if (index < size >> 1) {
            Node<E> x = first;
            for(int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw new RuntimeException(outOfBoundsMsg(index));
        }
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    @Override
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    private static class Node<E> {
        E item;
        Node<E> prev;
        Node<E> next;
        public Node(E item, Node<E> prev, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = 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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

四、常见问题

• JDK中LinkedList是双向链表，add方法默认是尾插法，remove方法默认是头删，是实现LRU算法的雏形
• 相比于ArrayList，LinkedList更适用于在首尾部进行插入删除和查询操作。ArrayList的耗时操作主要体现在对元素的拷贝和位移，而LinkedList的耗时操作主要体现在遍历定位和创建节点，因此在不同数据规模下耗时不同，不能简单的认为LinkedList一定比ArrayList插入快。