Java学习笔记（二）- 手写单向链表SingleLinkedList

学习的最好方式就是写出来

欢迎光临我的个人小窝：http://wsfss.top

今天我们就手撸一个简单版的单向链表实现LinkedList吧，JDk1.8的LinkedList是双向链表实现的，后面会撸个双向链表版本的。

1、当然是先写节点类Node

package com.fss.util;

public class Node<E> {

    // 当前节点元素
    E value;

    // 下一个节点
    Node<E> next;

    public Node(E value, Node<E> next) {
        this.value = value;
        this.next = next;
    }
}

2、实现单向链表的尾部添加元素、下标位置添加元素，移除下标位置元素、获取下标位置元素；需要重写迭代器遍历方法，不然是无法用foreach的

package com.fss.util;

import java.util.*;

public class SingleLinkedList<T> extends AbstractSequentialList<T> {

    // 头节点
    transient Node<T> head = null;

    // 链表长度
    transient int size;

    /**
     * 获取链表长度
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 在链表尾部添加节点
     */
    public boolean add(T t) {
        Node next = new Node(t, null);
        // 头节点不存在时，新节点成为头节点
        if (head == null) {
            head = next;
        } else {
            // 找到最后一个节点
            Node<T> last = last();
            last.next = next;
        }
        size++;
        return true;
    }

    /**
     * 在指定位置插入节点，下标位置前的节点next指向t，t的next指向下标位置的节点
     */
    public T set(int index, T t) {
        checkIndex(index);
        Node<T> newNode = new Node<>(t, null);
        size++;
        // 头部插入节点
        if (index == 0) {
            Node<T> next = head;
            head = newNode;
            newNode.next = next;
            return t;
        }
        // 尾部插入节点
        if (index == size - 1) {
            Node<T> last = last();
            last.next = newNode;
            return t;
        }
        Node<T> cur = head;
        int position = 0;
        while (cur.next != null) {
            // 下标前一节点
            if (++position == index) {
                Node<T> next = cur.next;
                cur.next = newNode;
                newNode.next = next;
            }
            cur = cur.next;
        }
        return t;
    }

    /**
     * 获取指定位置的节点元素
     */
    public T get(int index) {
        checkIndex(index);
        return node(index).value;
    }

    /**
     * 删除指定位置的节点元素，index位置的上一节点next指向index位置的下一节点
     */
    public T remove(int index) {
        checkIndex(index);
        // 如果删除的是头节点
        if (index == 0) {
            head = head.next;
        }
        Node<T> cur = head;
        Node<T> old = null;
        int position = 0;
        while (cur.next != null) {
            if (++position == index) {
                old = cur.next;
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
        size--;
        return old.value;
    }

    /**
     * 查找指定位置的节点
     */
    Node<T> node(int index) {
        checkIndex(index);
        Node<T> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 打印链表信息
     */
    public void print() {
        System.out.println("单向链表的长度为：" + size);
    }

    /**
     * 获取尾部节点
     */
    private Node<T> last() {
        Node<T> last = head;
        while (last.next != null) {
            last = last.next;
        }
        return last;
    }

    /**
     * 检查下标是否越界
     */
    private void checkIndex(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("下标超过链表长度范围");
        }
    }

    @Override
    public ListIterator listIterator(int index) {
        checkIndex(index);
        return new ListItr(index);
    }

    /**
     * 重写迭代器，实现单链表结构的迭代
     * 这里只实现了迭代遍历元素，未实现迭代器的add等操作元素的方法
     */
    private class ListItr implements ListIterator<T> {

        // 上一节点
        private Node<T> lastReturned;

        // 下一节点
        private Node<T> next;

        // 下一节点下标
        private int nextIndex;

        public ListItr(int index) {
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        @Override
        public boolean hasNext() {
            return nextIndex < size;
        }

        @Override
        public T next() {
            if (!hasNext())
                throw new NoSuchElementException();
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.value;
        }

        @Override
        public boolean hasPrevious() {
            return false;
        }

        @Override
        public T previous() {
            if (!hasPrevious())
                throw new NoSuchElementException();
            return null;
        }

        @Override
        public int nextIndex() {
            return nextIndex;
        }

        @Override
        public int previousIndex() {
            return 0;
        }

        @Override
        public void remove() {
        }

        @Override
        public void set(T t) {
        }

        @Override
        public void add(T t) {
        }
    }
}