浅谈LinkedList – 小飞侠

概述

在这里插入图片描述

LinkedList底层是双向链表结构,实现了List和Queue接口,内部用Node来包装数据,Deque双端队列,继承了Queue接口,在Queue的基础上做了很多的扩展,可以在两端进行插入和删除,使得Deque数据结构非常灵活.

使用方式

List<Integer> list = new LinkedList<>(); //数组使用
Queue<Integer> queue = new LinkedList<>();//队列使用
Deque<Integer> deque = new LinkedList<>();//双端队列使用

成员变量

该节点类都是用transient修饰其原理和ArrayList中Object[]类似,ArrayList中数组的长度是变化的,实际存储时不一定每次都存满,size不一定等于数组长度,用transient修饰,则可以保证序列化实际存储的元素,而不是整个数组,避免时间和空间的浪费

// LinkedList的节点个数
transient int size = 0;

// 头结点
transient Node<E> first;

// 尾结点
transient Node<E> last;

内部类

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;
     }
 }

add()

源码分析

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    // 默认尾插法插入数据
    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++;
    }

add(int index,E element)

    public void add(int index, E element) {
        // 下标检查，判断index >= 0 && index <= size
        checkPositionIndex(index);

        // 如果下标刚好等于size，则直接利用尾插法
        if (index == size)
            linkLast(element);
        else
            // 否则，则在该index前一位置添加，node()为获取对应下标节点
            linkBefore(element, node(index));
    }

	// 获取对应下标的节点
    Node<E> node(int index) {
        // 判断下标是否在链表的前半部分（size右移1位）
        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;
        }
    }

	// 将元素链接到对应节点的前一位置
    void linkBefore(E e, Node<E> succ) {
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

get( ) 获取对应下标位置的元素

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

remove(int index) 删除指定下标的元素

	public E remove(int index) {
        // 下标检查
        checkElementIndex(index);
        // 先获取对应位置节点
        return unlink(node(index));
    }   

    E unlink(Node<E> x) {
        
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

    private E unlinkFirst(Node<E> f) {
        // 获取头结点元素及头结点的下一个节点
        final E element = f.item;
        final Node<E> next = f.next;
        
        // 将数据置空，同时将头结点的后继置空
        f.item = null;
        f.next = null; // help GC
        
        // 将下一个节点变成头结点
        first = next;
         
        // 如果下一个节点为空，说明原来链表中只有一个节点
        if (next == null)
            last = null;
        else
            // 否则，将下一个节点的前驱置空
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

set(int index, E element) 修改制定下标处的元素

    public E set(int index, E element) {
        // 下标检查
        checkElementIndex(index);
        // 获取对应下标节点
        Node<E> x = node(index);
        E oldVal = x.item;
        // 将新值覆盖旧值，并返回旧值
        x.item = element;
        return oldVal;
    }

实现自己的链表

public class MyLinkedList<E> {
    /**
     * LinkedList的节点个数
     */
    int size = 0;

    /**
     * 头节点
     */
    Node<E> first;

    /**
     * 尾节点
     */
    Node<E> last;


    /**
     * 增减元素
     */
    public boolean add(E e) {
        Node<E> l = last;
        Node<E> newNode = new Node<E>(e, l, null);
        last = newNode;
        if (l == null) {
            first = last;
        } else {
            l.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * 根据下标添加元素
     */
    public void add(int index, E e) {
        //判断下标是否合法
        if (index < 0 || index > size) {
            throw new IndexOutOfException();
        }
        //如果下标等于size 则直接调用add（E e）方法进行尾插
        if (index == size) {
            add(e);
        } else {//否则在index前一位进行插入
            //先获取index下标对应的节点
            Node<E> curNode = getNode(index);

            /**
             * 进行插入
             * 获取当前节点之后，获取当前节点之后，将需要插入的元素封装成节点，该节点的next是curNode
             * prev是curNode未插入节点前的节点
             * 创建新的节点封装之后，插入时需要判断curNode.prev是否为null，为null将first指向newNode
             */
            Node<E> preNode = curNode.prev;
            Node<E> newNode = new Node<E>(e, preNode, curNode);
            curNode.prev = newNode;
            if (preNode == null) {
                first = newNode;
            } else {
                preNode.next = newNode;
            }
            size++;

        }
    }

    //根据index查询节点
    private Node<E> getNode(int index) {
        /**
         * 根据下标查询节点的时候充分利用双向链表的结构特点，从中间位置进行双向查找(二分查找)提高检索效率，
         */

        if (index < (size >> 1)) {
            Node<E> curNode = first;
            for (int i = 0; i < index; i++) {
                curNode = curNode.next;

            }
            return curNode;
        } else {
            Node<E> curNode = last;
            for (int i = size - 1; i > index; i--) {
                curNode = curNode.prev;
            }
            return curNode;
        }
    }

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfException();
        }
        return getNode(index).element;
    }

    /**
     * 根据提供元素顺序查询元素下标
     */
    public int indexOf(E e) {
        for (int i = 0; i < size; i++) {
            Node<E> curNode = getNode(i);
            if (e.equals(curNode.element)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * int lastIndexOf(String e);
     */
    public int lastIndexOf(E e) {
        for (int i = size - 1; i >= 0; i--) {
            Node<E> curNode = getNode(i);
            if (e.equals(curNode.element)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 根据index删除节点
     */
    public E remove(int index) {
        //下标检查
        if (index < 0 || index >= size) {
            throw new IndexOutOfException();
        }
        //根据下标得到需要删除的节点

        Node<E> curNode = getNode(index);
        E element = curNode.element;
        Node<E> preNode = curNode.prev;
        Node<E> nextNode = curNode.next;
        if (preNode == null) {
            first = curNode;
        } else {
            preNode.next = nextNode;
            curNode.prev = null;
        }

        if (nextNode == null) {
            last = preNode;
        } else {
            nextNode.prev = preNode;
            nextNode.next = null;
        }
        curNode.element = null;
        size--;
        return element;
    }

    /**
     * 根据元素删除节点
     */
    public boolean remove(Object object) {
        if (object == null) {
            int i = 0;
            for (Node<E> curNode = first; curNode != null; curNode = curNode.next) {
                if (curNode.element == null) {
                    remove(i);
                    return true;
                }
                i++;
            }
        } else {
            int i = 0;
            for (Node<E> curNode = first; curNode != null; curNode = curNode.next) {
                if (object.equals(curNode.element)) {
                    remove(i);
                    return true;
                }
                i++;
            }
        }
        return false;
    }

    /**
     * 修改制定下标处的元素
     */
    public E set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfException();
        }
        Node<E> curNode = getNode(index);
        E oldValue = curNode.element;
        curNode.element = e;
        return oldValue;
    }


    /**
     * 判断是否包含该元素
     */
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            Node<E> curNode = getNode(i);
            if (e.equals(curNode.element)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 清空链表
     * 清空时不能直接将curNode.next = null，需要将当前节点的next保存下来，防止空指针
     **/
    public void clear() {
        for (Node<E> curNode = first; curNode != null; ) {
            Node<E> nextNode = curNode.next;
            curNode.prev = null;
            curNode.element = null;
            curNode.next = null;
            curNode = nextNode;
        }
        first = last = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

class Node<E> {
    E element;
    Node<E> prev;
    Node<E> next;

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

//自定义异常
class IndexOutOfException extends RuntimeException {
    public IndexOutOfException() {
        super();
    }

    public IndexOutOfException(String message) {
        super(message);
    }
}

原文链接：https://blog.csdn.net/supermanman_/article/details/119608528

概述