1
import java.util.List;
2
import java.util.LinkedList;
3

4
//某段函数体内
5
{
6
   List<String> newLists=new LinkedList<>();
7
    newLists.add("I am fine!");
8
    newLists.add("You jump I jump");
9
}

1
package Lists1;
2

3
import java.util.NoSuchElementException;
4

5
/**
6
 * SLList 代表一个单向链表，存储泛型数据。
7
 * 经过优化，使用哨兵节点 (sentinel node) 和 last 指针。
8
 * @author Mongxin (Optimized Version)
9
 */
10
public class SLList<T> {
11

12
    // 哨兵节点，不存储实际数据，其 next 指向链表的第一个实际节点
13
    private Node<T> sentinel;
14
    // 指向链表的最后一个实际节点，如果链表为空，则指向 sentinel
15
    private Node<T> last;
16
    private int size;
17

18

19
    /**
20
     * Node 类代表链表中的一个节点。
21
     */
22
    private static class Node<T> {
23
        public T item;     // 节点存储的数据
24
        public Node<T> next; // 指向下一个节点的引用
25

26
        public Node(T i, Node<T> n) {
27
            item = i;
28
            next = n;
29
        }
30
    }
31

32
    /**
33
     * 创建一个空的 SLList。
34
     * 哨兵节点被初始化，last 指向哨兵节点，size 为 0。
35
     */
36
    public SLList() {
37
        sentinel = new Node<>(null, null); // 哨兵节点的值可以是任意，这里用 null
38
        last = sentinel;
39
        size = 0;
40
    }
41

42
    /**
43
     * 创建一个带有一个初始元素 x 的新 SLList。
44
     * @param x 初始元素
45
     */
46
    public SLList(T x) {
47
        sentinel = new Node<>(null, null);
48
        Node<T> newNode = new Node<>(x, null);
49
        sentinel.next = newNode;
50
        last = newNode; // 新节点也是最后一个节点
51
        size = 1;
52
    }
53

54
    /**
55
     * 在链表头部添加元素 x。
56
     * 操作时间复杂度: O(1)。
57
     * @param x 要添加的元素
58
     */
59
    public void addFirst(T x) {
60
        Node<T> newNode = new Node<>(x, sentinel.next);
61
        sentinel.next = newNode;
62
        if (size == 0) { // 如果原链表为空，新添加的节点也是尾节点
63
            last = newNode;
64
        }
65
        size++;
66
    }
67

68
    /**
69
     * 获取链表的第一个元素。
70
     * 操作时间复杂度: O(1)。
71
     * @return 链表的第一个元素
72
     * @throws NoSuchElementException 如果链表为空
73
     */
74
    public T getFirst() {
75
        if (size == 0) {
76
            throw new NoSuchElementException("Cannot get item from an empty list.");
77
        }
78
        return sentinel.next.item;
79
    }
80

81
    /**
82
     * 在链表尾部添加元素。
83
     * Благодаря указателю last, сложность операции: O(1).
84
     * @param item 要添加到链表尾部的元素
85
     */
86
    public void addLast(T item) {
87
        Node<T> newNode = new Node<>(item, null);
88
        last.next = newNode; // 当前的尾节点的 next 指向新节点
89
        last = newNode;      // 更新 last 指针指向新的尾节点
90
        size++;
91
    }
92

93
    /**
94
     * 移除并返回链表的第一个元素。
95
     * 操作时间复杂度: O(1)。
96
     * @return 被移除的第一个元素
97
     * @throws NoSuchElementException 如果链表为空
98
     */
99
    public T removeFirst() {
100
        if (size == 0) {
101
            throw new NoSuchElementException("Cannot removeFirst from an empty list.");
102
        }
103
        T itemToReturn = sentinel.next.item;
104
        sentinel.next = sentinel.next.next;
105
        size--;
106
        if (size == 0) { // 如果移除后链表为空，last 指回 sentinel
107
            last = sentinel;
108
        }
109
        return itemToReturn;
110
    }
111

112
    /**
113
     * 移除并返回链表的最后一个元素。
114
     * 操作时间复杂度: O(N)，因为需要遍历找到倒数第二个节点。
115
     * @return 被移除的最后一个元素
116
     * @throws NoSuchElementException 如果链表为空
117
     */
118
    public T removeLast() {
119
        if (size == 0) {
120
            throw new NoSuchElementException("Cannot removeLast from an empty list.");
121
        }
122

123
        T itemToReturn = last.item;
124

125
        if (size == 1) { // 如果只有一个元素
126
            sentinel.next = null;
127
            last = sentinel;
128
        } else {
129
            Node<T> p = sentinel;
130
            // 遍历直到 p.next 是当前的 last 节点 (即 p 是倒数第二个节点)
131
            while (p.next != last) {
132
                p = p.next;
133
            }
134
            p.next = null; // 移除最后一个节点
135
            last = p;      // 更新 last 指针
136
        }
137
        size--;
138
        return itemToReturn;
139
    }
140

141
    /**
142
     * 返回链表中元素的数量。
143
     * 操作时间复杂度: O(1)。
144
     * @return 链表中元素的数量
145
     */
146
    public int size() {
147
        return this.size;
148
    }
149

150
    /**
151
     * 打印链表中的所有元素。
152
     * 例如: [12, 10, 5]
153
     */
154
    public void print() {
155
        System.out.print("[");
156
        Node<T> p = sentinel.next; // 从第一个实际数据节点开始
157
        while (p != null) {
158
            System.out.print(p.item);
159
            if (p.next != null) {
160
                System.out.print(", ");
161
            }
162
            p = p.next;
163
        }
164
        System.out.println("]");
165
    }
166

167
    /**
168
     * 反转链表。
169
     * 例如: [1, 2, 3] 反转后变为 [3, 2, 1]。
170
     * 操作时间复杂度: O(N)。
171
     */
172
    public void reverse() {
173
        if (size <= 1) {
174
            return; // 空链表或单元素链表无需反转
175
        }
176

177
        Node<T> newLastNode = sentinel.next; // 原来的第一个节点将成为新的最后一个节点
178

179
        Node<T> prev = null;
180
        Node<T> current = sentinel.next;
181
        Node<T> nextNode;
182

183
        while (current != null) {
184
            nextNode = current.next; // 保存下一个节点
185
            current.next = prev;     // 反转当前节点的指针
186
            prev = current;          // prev 前进
187
            current = nextNode;      // current 前进
188
        }
189

190
        sentinel.next = prev; // prev 现在是新的第一个实际节点
191
        last = newLastNode;   // 更新 last 指针
192
        // newLastNode.next 已经在循环中被正确设置为 null
193
    }
194

195

196
    public Object[] toArray() {
197
        Object[] arr = new Object[size];
198
        Node<T> p = sentinel.next;
199
        int i = 0;
200
        while (p != null) {
201
            arr[i++] = p.item;
202
            p = p.next;
203
        }
204
        return arr;
205
    }
206

207
    /**
208
     * 主函数，用于测试 SLList 的功能。
209
     */
210
    public static void main(String[] args) {
211
        System.out.println("--- 测试空链表 ---");
212
        SLList<String> emptyList = new SLList<>();
213
        System.out.print("空链表: ");
214
        emptyList.print(); // 应输出: []
215
        System.out.println("空链表大小: " + emptyList.size()); // 应输出: 0
216
        try {
217
            emptyList.getFirst();
218
        } catch (NoSuchElementException e) {
219
            System.out.println("尝试从空链表获取元素: " + e.getMessage());
220
        }
221
        try {
222
            emptyList.removeFirst();
223
        } catch (NoSuchElementException e) {
224
            System.out.println("尝试从空链表移除第一个元素: " + e.getMessage());
225
        }
226
        try {
227
            emptyList.removeLast();
228
        } catch (NoSuchElementException e) {
229
            System.out.println("尝试从空链表移除最后一个元素: " + e.getMessage());
230
        }
231
    }
232
}