深入理解链表结构和LinkedList源码分析

桃扇骨 2022-01-26 10:15 248阅读 0赞

### 深入理解链表结构和LinkedList源码分析 ###

*   *  链表的概念
     *  LinkedList分析
     *   *  继承的类和接口
         *  特殊的关键字transient
         *  源码关键部分分析
     *  自己实现一个单向链表
     *   *  面试相关

## 链表的概念 ##

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

## LinkedList分析 ##

### 继承的类和接口 ###

extends AbstractSequentialList<E>  implements List<E>, Deque<E>, Cloneable, java.io.Serializable

*  AbstractSequentialList extends AbstractList 继承AbstractList ，AbstractSequentialList 它实现了list 的一些位置相关的操作。
 *  实现List 接口能对它进行队列操作
 *  Deque双端队列，双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两邊进行
 *  Cloneable 覆盖了函数clone()
 *  Serializable 支持序列化，能通过序列化传输数据

### 特殊的关键字transient ###

*  transient：关键字transient 标识的字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。我们知道对象的序列化有很多好处，但是有些信息我们为了信息的安全是不想要实现序列化的，比如支付密码，这是只要在属性上加上transient关键字，则该属性在序列化是就不会序列化；

### 源码关键部分分析 ###

package java.util;
    import java.util.function.Consumer;
    public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    { 
    //当前链表的长度
        transient int size = 0;
    //链表的首节点
        transient Node<E> first;
    
    //链表的尾节点
        transient Node<E> last;
    //构造方法
        public LinkedList() { 
        }
    
    //构造方法
        public LinkedList(Collection<? extends E> c) { 
            this();
            addAll(c);
        }
        //链表的节点定义
        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 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;
            //如果 l 为空，则证明链表为空
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
    	//移除一个节点
    	public boolean remove(Object o) { 
    		//如果移除的节点为null
            if (o == null) { 
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (x.item == null) { 
                        unlink(x);
                        return true;
                    }
                }
            } else { 
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (o.equals(x.item)) { 
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }
    	 E unlink(Node<E> x) { 
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
            //如果prev为空，说明要删除的为首节点
            if (prev == null) { 
                first = next;
            } else { 
                prev.next = next;
                x.prev = null;
            }
            //如果next为空，说明删除的为尾节点
            if (next == null) { 
                last = prev;
            } else { 
                next.prev = prev;
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }
        //检查链表中是否包含一个值
    	public boolean contains(Object o) { 
            return indexOf(o) != -1;
        }
        //查找链表，查到返回位置，否返回-1
        public int indexOf(Object o) { 
            int index = 0;
            if (o == null) { 
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (x.item == null)
                        return index;
                    index++;
                }
            } else { 
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (o.equals(x.item))
                        return index;
                    index++;
                }
            }
            return -1;
        }
        //根据位置，得到一个值
        public E get(int index) { 
        	//检查index是否合法：0<=index<size
            checkElementIndex(index);
            return node(index).item;
        }
    	Node<E> node(int index) { 
    		//折半查找
    		//如果index小于size的一半。则从左开始查找，否则从右边开始查找
            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;
            }
        }
        //向index位置前添加一个节点
        public void add(int index, E element) { 
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
        //后面的不再一一介绍

## 自己实现一个单向链表 ##

代码如下：

package test;
    
    public class SingleList<E> { 
        private static class Node<E> { 
            E item;
            Node<E> next;
            public Node(E item, Node<E> next) { 
                this.item = item;
                this.next = next;
            }
        }
        private Node<E> frist;
        private Node<E> last;
        public int size;
        /** * 向尾部添加一个元素 * * @param e */
        public void add(E e) { 
            lastList(e);
        }
        /** * 在某个位置插入一个元素 * * @param e * @param index */
        public void add(E e, int index) { 
            if (index < 0 || index > size) return;
            if (index == size) { //插入尾部
                lastList(e);
            } else { 
                if (index == 0) { 
                    Node<E> l = frist;
                    Node<E> newNode = new Node<>(e, l);//新的元素在插入位置的前一个位置
                    frist = newNode;
                } else { 
                    Node<E> fNode = node(index - 1);//找到要插入位置的前一个位置
                    Node<E> lNode = fNode.next;
                    Node<E> newNode = new Node<>(e, lNode);
                    fNode.next = newNode;
                }
                size++;
            }
        }
        /** * 删除某个节点 * * @param index */
        public void remove(int index) { 
            unLink(index);
        }
        private void unLink(int index) { 
            if (index < 0 || index > size) return;
            if (index == size) { //删尾部
                Node<E> node = node(index - 1);
                node.next = null;
                last = node;
            } else if (index == 0) { //删头部
                Node<E> l = this.frist;
                frist = l.next;
            } else { 
                Node<E> node = node(index - 1);//要删除的前一个节点
                Node<E> removeNode = node.next;//要删除的节点
                Node<E> lNode = removeNode.next;//要删除的后一个节点
                node.next = lNode;
            }
            size--;
        }
        public void remove(E e) { 
            Node<E> newNode = frist;
            int index = -1;
            for (int i = 0; i < size; i++) { 
                newNode = newNode.next;
                if (e.equals(newNode.item)) { 
                    index = i;
                    break;
                }
            }
            if (index != -1)
                unLink(index);
        }
        private void lastList(E e) { 
            Node<E> newNode = new Node<>(e, null);//一个新的节点
            Node<E> l = last;
            last = newNode;//将最后一个节点赋值
            if (l == null) { 
                frist = newNode;
            } else { 
                l.next = newNode;
            }
            size++;
        }
        /** * 获取节点的某个元素 * * @param index * @return */
        public E get(int index) { 
            if (index < 0 || index > size) { 
                return null;
            }
            return node(index).item;
        }
        public Node<E> node(int index) { 
            Node<E> newNode = frist;
            for (int i = 0; i < index; i++) { 
                newNode = newNode.next;
            }
            return newNode;
        }
        /** * 单链表的逆置 * 第一种方法实现 循环 */
        public void inverse() { 
            Node<E> curr = this.frist;
            Node<E> reve = null;
            while (curr != null) { 
                Node<E> temp = curr;
                curr = curr.next;
                temp.next = reve;
                reve = temp;
            }
            frist = reve;
        }
    }

### 面试相关 ###

长问问题：将一个单链表倒置?  
1.循环法：

/**
         * 单链表的逆置
         * @curr:每次循环的当前节点
         * @reve:每次循环的前一个节点
         */
     public void inverse() {
            Node<E> curr = this.frist;
            Node<E> reve = null;
            while (curr != null) {
                Node<E> temp = curr;
                curr = curr.next;
                temp.next = reve;
                reve = temp;
            }
            frist = reve;
        }

2.递归法：

/** * 递归的方式转置 */
        public Node<T> reverse(Node<T> head) { 
            if (head == null || head.next == null) { 
                return head;
            }
            Node<T> tail = reverse(head.next);
            head.next.next = head;
            head.next = null;
            return tail;
        }
        public void transterReverse() { 
            this.frist = reverse(this.frist);
        }