链表和Java中的LinkedList集合_java用链表的集合

1 Java实现单链表

Java的集合与数据结构的联系息息相关，例如Java中的LinkedList集合底层实现采用的双向链表。Java实现单链表如下：

public class LinkedList<E> {
    /**
     * 头结点和链表长度
     */
    private Node head;
    private int size;

    /**
     * 内部类，用于创建链表结点
     */
    private class Node {
        private E item;
        private Node next;

        public Node() {
        }

        public Node(E item) {
            this.item = item;
        }

        public Node(E item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    /**
     * 链表初始化
     */
    public LinkedList() {
        this.head = new Node();
        this.size = 0;
    }

    /**
     * 链表判空
     * @return
     */
    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 链表头部插入元素
     * @param e
     */
    public void addFirst(E e) {
        add(e, 0);
    }

    /**
     * 链表尾部插入元素
     * @param e
     */
    public void add(E e) {
        add(e, size);
    }

    /**
     * 链表指定位置插入元素
     * @param e
     * @param index
     */
    public void add(E e, int index) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("插入位置错误！");
        if (index == 0 && this.size == 0) {
            Node addNode = new Node(e, null);
            this.head.next = addNode;
            this.size++;
            return;
        }
        Node node = this.head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        Node addNode = new Node(e, null);
        addNode.next = node.next;
        node.next = addNode;
        this.size++;
    }

    /**
     * 删除链表头部元素
     */
    public void removeFirst() {
        remove(0);
    }

    /**
     * 删除链表尾部元素
     */
    public void remove() {
        if (this.isEmpty()) {
            throw new IllegalArgumentException("当前链表为空！");
        }
        remove(size - 1);
    }

    /**
     * 删除链表指定位置元素
     * @param index
     */
    public void remove(int index) {
        if (index < 0 || index > size - 1)
            throw new IllegalArgumentException("删除位置错误！");
        Node node = this.head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        Node nextNode = node.next.next;
        node.next = nextNode;
        this.size--;
    }

    /**
     * 链表是否包含元素e
     * @param e
     * @return
     */
    public boolean contains(E e) {
        Node node = this.head;
        for (int i = 0; i < size; i++) {
            node = node.next;
            if (node.item == e)
                return true;
        }
        return false;
    }

    /**
     * 打印链表
     */
    public void printLinedList() {
        StringBuilder sb = new StringBuilder();
        Node node = this.head;
        for (int i = 0; i < size; i++) {
            node = node.next;
            sb.append(node.item + " ");
        }
        System.out.println("{" + sb.toString().trim() + "}");
    }

    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();

        for (int i = 0; i < 10; i++) {
            if (i % 2 == 0)
                linkedList.add(i, i);
            else
                linkedList.add(i);
        }
        linkedList.printLinedList();

        linkedList.removeFirst();
        linkedList.printLinedList();
        linkedList.remove();
        linkedList.printLinedList();
        linkedList.remove(5);
        linkedList.printLinedList();

        System.out.println(linkedList.contains(5));
    }
}

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

关键点：

• 实现的是带头结点的单链表，注意与不带头结点的实现相区别。
• 易错易混的地方在于：添加元素和删除元素时，边界的确定。

2 Java中的LinkedList集合

Java中的LinkedList集合同时实现了List接口和Deque接口，也即LinkedList可以看作一个顺序容器，又可以看作一个队列(Queue)或栈(Stack)。可以任意添加元素（允许重复），包括NULL值。线程不安全，且没有实现同步。下面来看看LinkdeList的源码：

    transient int size = 0;

    /**
     * 指向第一个节点的指针。
     */
    transient Node<E> first;

    /**
     * 指向最后一个节点的指针。
     */
    transient Node<E> last;

	/**
	 * Node类定义
	 */
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }    
    
    /**
     * 构造一个空列表。
     */
    public LinkedList() {
    }
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

同样定义了一个Node结点，并且分别定义了指向链表头部和尾部的指针。其内部可以采用分别实现了头插法和尾插法：

  /**
     * 链接e作为第一个元素。
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
    
    /**
     * 将指定的元素插入到此列表的开头。
     *
     * @param e 要添加的元素
     */
    public void addFirst(E e) {
        linkFirst(e);
    }
    /**
     * 链接e作为最后一个元素。
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    
    /**
     * 将指定的元素追加到此列表的末尾。
     *
     * 这个方法相当于添加。
     *
     * @param e 要添加的元素
     */
    public void addLast(E e) {
        linkLast(e);
    }
    
    /**
     * 将指定的元素追加到此列表的末尾。
     * 这个方法相当于addLast。
     *
     * @param e 要追加到此列表的元素
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
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

注：它这个实现没有空出一个多余的头结点，值得学习。

3 相关习题

01 链表【PAT B1025】反转链表