Java数据结构-LinkedList

痛定思痛。 2022-07-15 04:29 147阅读 0赞

# 内部结构图 #

![这里写图片描述][format_png]

# 实现原理 #

LinkedList内部维护着一个`Node<E>`，其中E为你的类型，`Node<E>`包含着3个属性E item（类型），`Node<E>` next（下一个元素），`Node<E>` prev（上一个元素），每个Node都持有上一个和下一个元素的引用（链表和链尾除外），所以是一个引用链表的结构。  
\#特点  
这种结构在取值的时候由于要算引用，所以比较慢，但是在添加和删除的时候只要把对应的引用替换就可以了，所以添加和删除比较快。

# 常用方法源码 #

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

# remove() #

public E remove(int index) { 
            checkElementIndex(index);//判断下标是否越界
            return unlink(node(index));//引用替换
        }
    E unlink(Node<E> x) { 
            // assert x != null;
            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;
        }

# get(int i) #

public E get(int index) { 
            checkElementIndex(index);//判断数组越界
            return node(index).item;//计算引用位置
        }
    Node<E> node(int index) { 
            // assert isElementIndex(index);
    
            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;
            }
        }

[format_png]: /images/20220715/76f1ce896f8a491c9367c23b4c9e2c2f.png