单链表的简单实现

  1/**
  2 * 一个单链表，及其基本功能实现
  3 *
  4 * @author wangy
  5 * @version 1.0
  6 * @date 2021/6/21 / 22:23
  7 */
  8@SuppressWarnings({ "rawtypes", "unchecked" })
  9public class NodeList<E> {
 10
 11    private Node<E> head;
 12    private Node<E> tail;
 13    private int size;
 14
 15    /*
 16     * 插入头部
 17     * 插入尾部
 18     * 根据index获取元素
 19     * 根据值删除
 20     * 根据index删除
 21     * 反转链表元素
 22     * 判断回文字符串
 23     */
 24
 25    public NodeList() {
 26        this.head = this.tail = null;
 27        this.size = 0;
 28    }
 29
 30    private Node<E> node(E e) {
 31        return new Node<>(e);
 32    }
 33
 34    int size() {
 35        return size;
 36    }
 37
 38    E getHead() {
 39        return head.data;
 40    }
 41
 42    E getTail() {
 43        return tail.data;
 44    }
 45
 46    void insertHead(E e) {
 47        Node<E> p = node(e);
 48        insertHead(p);
 49    }
 50
 51    private void insertHead(Node node) {
 52        node.next = head;
 53        head = node;
 54        if (++size == 1)
 55            tail = head;
 56    }
 57
 58    void insertTail(E e) {
 59        Node<E> p = node(e);
 60        insertTail(p);
 61    }
 62
 63    private void insertTail(Node node) {
 64        tail.next = node;
 65        tail = node;
 66        if (++size == 1)
 67            head = tail;
 68    }
 69
 70    /**
 71     * 在指定位置插入元素, 若index溢出，则自动将元素插入到链表的头部或者尾部。<br>
 72     * 若index&lt;0时插入头部，若index&gt;<code>size</code>时，插入尾部。
 73     * <p>
 74     * 平均时间复杂度 O(n)
 75     *
 76     * @param index 元素插入位置
 77     * @param e     待插入元素
 78     */
 79    void insert(int index, E e) {
 80        Node<E> i = node(e);
 81        if (index <= 0) {
 82            insertHead(i);
 83        } else if (index >= size) {
 84            insertTail(i);
 85        } else {
 86            Node<E> p = head;
 87            while (index > 1) {
 88                p = p.next;
 89                --index;
 90            }
 91            Node<E> next = p.next;
 92            p.next = i;
 93            i.next = next;
 94            ++size;
 95        }
 96    }
 97
 98    E get(int index) {
 99        if (index >= size)
100            throw new IndexOutOfBoundsException("index must >= 0 and < " + size);
101        Node<E> p = head;
102        while (index > 0) {
103            p = p.next;
104            --index;
105        }
106        return p.data;
107    }
108
109    boolean contains(E e) {
110        Node<E> p = head;
111        while (p != null) {
112            if (p.data.equals(e))
113                return true;
114            p = p.next;
115        }
116        return false;
117    }
118
119    /**
120     * 当链表中存在重复元素时，无法准确获取index。 获取的是该元素第一次出现的index。
121     *
122     * @param e element
123     * @return index of first occurrence of element in single linked list.
124     */
125    int getIndex(E e) {
126        Node<E> p = head;
127        int pos = 0;
128        while (p != null) {
129            if (p.data.equals(e))
130                return pos;
131            p = p.next;
132            pos++;
133        }
134        return -1;
135    }
136
137    /**
138     * 移除链表中首次出现的指定元素，若元素不在链表中，则不作处理
139     * <p>
140     * 平均时间复杂度O(n^2)
141     *
142     * @param e 待移除的元素
143     */
144    void remove(E e) {
145        Node<E> p = head;
146        while (p != null) {
147            if (p.data.equals(e)) {
148                remove(p);
149                return;
150            }
151            p = p.next;
152        }
153    }
154
155    /**
156     * remove element by index.
157     * <p>
158     * 时间复杂度 O(n)
159     *
160     * @param index index of element in linked list, Analogous to the index
161     *              semantics of an array.
162     */
163    void remove(int index) {
164        if (index >= size)
165            throw new IndexOutOfBoundsException("index must >= 0 and < " + size);
166        Node<E> del = head;
167        Node<E> l = head;
168        for (int i = 0; i < index; i++) {
169            l = del;
170            del = del.next;
171        }
172        remove(l, del);
173    }
174
175    /**
176     * 删除指定节点
177     * <p>
178     * 平均时间复杂度 O(n)
179     *
180     * @param node 带删除的节点
181     */
182    private void remove(Node node) {
183        Node<E> prev = head;
184        Node<E> curr = head;
185
186        while (!curr.equals(node)) {
187            prev = curr;
188            curr = curr.next;
189            if (curr.equals(tail)) {
190                if (node.equals(curr)) {
191                    break;
192                }
193                return;
194            }
195        }
196        if (curr.equals(head)) {
197            head = prev.next;
198        } else if (curr.equals(tail)) {
199            tail = prev;
200            prev.next = null;
201        } else {
202            prev.next = curr.next;
203        }
204        --size;
205    }
206
207    /**
208     * 快速移除链表中首次出现的元素
209     * <p>
210     * 平均时间复杂度O(n)
211     *
212     * @param e 待删除的元素
213     */
214    void fastRemove(E e) {
215        Node<E> l = null;
216        Node<E> r = head;
217        while (r != null) {
218            if (r.data.equals(e)) {
219                remove(l, r);
220                return;
221            }
222            l = r;
223            r = r.next;
224        }
225    }
226
227    /**
228     * 给定左节点，删除右节点
229     * <p>
230     * 时间复杂度 O(1)
231     *
232     * @param l 左节点
233     * @param r 右节点
234     */
235    private void remove(Node<E> l, Node<E> r) {
236        if (r.equals(head)) {
237            head = r.next;
238        } else if (r.equals(tail)) {
239            tail = l;
240            l.next = null;
241        } else {
242            l.next = r.next;
243        }
244        --size;
245    }
246
247    /**
248     * 反转链表
249     * <p>
250     * 时间复杂度 O(n)
251     */
252    void reverse() {
253        /*
254         * 引入节点，该节点的next总是指向新反转过程中的最新节点；
255         * 当所有的节点遍历完成时，其next指向反转后的head；
256         */
257        Node<E> lead = node(null);
258        lead.next = head;
259        // 从第二个节点开始，反转链表
260        Node<E> cur = head.next;
261        /*
262         * 引入此节点用来记录当前遍历节点的下一个节点，
263         * 避免反转过程中链表"断裂"
264         */
265        Node<E> tmp;
266        while (cur != null) {
267            tmp = cur.next;
268            cur.next = lead.next;
269            lead.next = cur;
270
271            cur = tmp;
272        }
273        head.next = null;
274        tail = head;
275        head = lead.next;
276    }
277
278    /**
279     * 反转head-node节点(不含)之间的元素
280     *
281     * @param node 标记节点
282     */
283    private void reverse(Node<E> node) {
284        if (!contains(node.data))
285            return;
286        Node<E> h = new Node(null);
287        h.next = node;
288        Node<E> cur = head;
289        Node next;
290        while (!cur.equals(node)) {
291            next = cur.next;
292            cur.next = h.next;
293            h.next = cur;
294
295            cur = next;
296        }
297        head = h.next;
298    }
299
300    /**
301     * 判断链表内容是否回文字符串
302     * <p>
303     * 回文字符串，即字符串从左往右和从右往左读是一样的，如【refer】就是回文字符串
304     * <p>
305     * 时间复杂度 O(n)
306     *
307     * @return true yes，false no
308     */
309    boolean isPalindrome() {
310        if (head == null)
311            return false;
312        Node<E> slow = head;
313        Node<E> fast = head;
314        while (fast.next != null && fast.next.next != null) {
315            slow = slow.next;
316            fast = fast.next.next;
317        }
318        // 处理1、2个元素的情形
319        if (slow.equals(fast)) {
320            if (size == 1) {
321                return true;
322            }
323            return head.data.equals(tail.data);
324        }
325        boolean b = false;
326        if (fast.next != null) {
327            // 偶数个元素
328            slow = slow.next;
329            b = true;
330        }
331        // 反转slow节点之前的元素
332        Node<E> rev = slow;
333        reverse(rev);
334        System.out.println("++++++ after reverse ++++++");
335        printAll();
336
337        // 此head和h不一样！链表已被部分反转
338        Node<E> pre = head;
339        try {
340            if (b) {
341                while (slow != null) {
342                    if (slow.data != pre.data)
343                        return false;
344                    slow = slow.next;
345                    pre = pre.next;
346                }
347            } else {
348                while (slow.next != null) {
349                    if (slow.next.data != pre.data)
350                        return false;
351                    slow = slow.next;
352                    pre = pre.next;
353                }
354            }
355        } finally {
356            // 还原链表
357            reverse(rev);
358            System.out.println("++++++ after restore ++++++");
359            printAll();
360        }
361        return true;
362    }
363
364    void printAll() {
365        System.out.print("LinkedList: [");
366        if (size == 1) {
367            System.out.print(getHead() + "/"
368                    + getTail() + "/" + get(0));
369        } else {
370            System.out.print(getHead()
371                    + "(" + getIndex(getHead()) + "), ");
372            for (int i = 1; i < size - 1; i++) {
373                System.out.print(get(i)
374                        + "(" + getIndex(get(i)) + "), ");
375            }
376            System.out.print(getTail()
377                    + "(" + getIndex(getTail()) + ")");
378        }
379        System.out.println("]");
380    }
381
382    static class Node<U> {
383        U data;
384        Node<U> next;
385
386        public Node(U data) {
387            this.data = data;
388            this.next = null;
389        }
390
391        @Override
392        public boolean equals(Object o) {
393            if (this == o)
394                return true;
395            if (o == null || getClass() != o.getClass())
396                return false;
397
398            Node<?> node = (Node<?>) o;
399
400            if (!Objects.equals(data, node.data))
401                return false;
402            return Objects.equals(next, node.next);
403        }
404
405        @Override
406        public int hashCode() {
407            int result = data != null ? data.hashCode() : 0;
408            result = 31 * result + (next != null ? next.hashCode() : 0);
409            return result;
410        }
411
412    }
413
414    public static void main(String[] args) {
415        NodeList<Integer> nl = new NodeList<>();
416        System.out.println("++++++ insert head 10 ++++++");
417        nl.insertHead(10);
418
419        System.out.println("++++++ insert tail 11 ++++++");
420        nl.insertTail(11);
421
422        System.out.println("++++++ insert head 9 ++++++");
423        nl.insertHead(9);
424
425        nl.printAll();
426
427        System.out.println("contains 9? " + nl.contains(9));
428
429        System.out.println("++++++ remove element ++++++");
430        nl.remove(Integer.valueOf(11));
431        nl.printAll();
432
433        nl.fastRemove(10);
434        nl.printAll();
435
436        System.out.println("++++++ insert element ++++++");
437        nl.insert(1, 99);
438        nl.insert(1, 89);
439        nl.insert(1, 79);
440        nl.insert(100, 109);
441        nl.insert(-1, -9);
442        nl.printAll();
443
444        nl.reverse();
445        nl.printAll();
446
447        System.out.println("++++++ judge palindrome ++++++");
448        String[] s = new String[] { "r", "e", "f", "f", "e", "r" };
449        // String[] s = new String[]{"r", "e", "f", "f", "e", "p"};
450        // String[] s = new String[]{"r", "e", "f", "e", "r"};
451        // String[] s = new String[]{"r", "e", "f", "e", "p"};
452        // String[] s = new String[]{"r"};
453        // String[] s = new String[]{"r", "s"};
454        // String[] s = new String[]{"r", "r"};
455        // String[] s = new String[]{"r", "s", "r"};
456        // String[] s = new String[]{"r", "s", "t"};
457
458        NodeList<String> stringNodeList = new NodeList<>();
459        for (String str : s) {
460            stringNodeList.insertHead(str);
461        }
462        stringNodeList.printAll();
463        /*
464         * Node<String> p = stringNodeList.head;
465         * for (int i = 0; i < stringNodeList.size; i++) {
466         * System.out.println(p + " --> " + p.next);
467         * p = p.next;
468         * }
469         */
470        System.out.println(stringNodeList.isPalindrome());
471
472        System.out.println(stringNodeList.get(5));
473        stringNodeList.remove(3);
474        stringNodeList.printAll();
475
476    }
477}