LinkedList的原理

古城微笑少年丶 2023-09-24 22:01 101阅读 0赞

### LinkedList的原理 ###

*  LinkedList的原理
 *   *  1.概述
     *  2.含有的属性
     *  3.源码解析
     *  4.其他方法
     *  5.总结

# LinkedList的原理 #

## 1.概述 ##

LinkedList是通过一个双向链表来实现的,它允许插入所有元素,包括null,它是线程不同步的.如图:

![链表][b5f27e7cf9be45d8b48adbe7e321de70.png]

从图中可以看出双向链表每个结点除了数据域之外,还有一个前指针和后指针,分别指向前驱结点和后驱结点(如果有前驱和后驱的话,没有指向null),另外,双向链表还有一个first指针和last指针,分别指向头结点和尾节点.  
[LinkedList集合对元素进行增、查、删操作][LinkedList]

## 2.含有的属性 ##

//链表的节点个数
    transient int size = 0;
    //指向头节点的指针
    transient Node<E> first;
    //指向尾节点的指针
    transient Node<E> last;

## 3.源码解析 ##

图解:

![LinkedList源码解析][LinkedList 1]

对于链表这种数据结构来说,添加元素的操作就是表头\\表位插入元素,或者指定位置插入.源码:

public boolean add(E e) {
        
        linkLast(e);  // 默认调用
        return true;
    }
    
    // 向前添加
    /*
    当向前表头插入一个节点时,可以想到当前节点的前驱一定为null,后继节点是first指针指向的节点,当然也要修改first指针指向新的头结点.还要修改原来的头结点编程第二个节点,所以还要修改原来头结点的前驱指针,指向表头节点
    */
    private void linkFirst(E e) {
        
        final Node<E> f = first;
        // 当前结点的前驱指向null,后继指针原来的头结点
        final Node<E> newNode = new Node<>(null, e, f);
        // 头指针指向新的头结点
        first = newNode;
        // 如果原来有头节点,则更新原来的节点的前驱指针,否则更新尾指针
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        // 元素的个数
        size++;
        // 更改的次数,一般线程安全方面研究它
        modCount++;
    }
    
    // 向后添加
    /*
    当向表尾插入一个节点时,很显然当前节点的后继为null,前驱节点是last指针指向的节点,然后还要修改last指针指向新的尾节点.还要修改原来尾节点的后继指针,使它指向新的尾节点
    */
    void linkLast(E e) {
        
        final Node<E> l = last;
        // 当前结点的前驱指向尾节点,后继指向null
        final Node<E> newNode = new Node<>(l, e, null);
        // 尾指针指向新的尾节点
        last = newNode;
        // 如果原来有尾节点,则更新原来节点的后继指针,否则更新头指针
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        // 元素的个数
        size++;
        // 更改的次数,一般线程安全方面研究它
        modCount++;
    }
    // 指定节点之前插入元素
    /*
    当向指定节点之前插入一个节点时,当前节点的后继为指定节点,后继节点为指定节点的前驱节点,还要修改前驱节点的后继为当前节点,以及后续节点的前驱为当前节点
    */
    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++;
    }
    
    // 私有静态内部类,用来表示链表每个结点的结构
    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;
        }
    }

## 4.其他方法 ##

public E get(int index) {
        
        checkElementIndex(index);
        return node(index).item;
    }
    
    Node<E> node(int index) {
        
        // assert isElementIndex(index);
    	// 长度除以2,判断是离链表头近还是尾近
        // 根据下标是否超过链表长度的一半，来选择从头部开始遍历还是从尾部开始遍历
        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;
        }
    }

## 5.总结 ##

> 1、LinkedList 的底层结构是一个带头/尾指针的双向链表，可以快速的对头/尾节点 进行操作。  
> 2、相比数组，链表的特点就是在指定位置插入和删除元素的效率较高，但是查找的 效率就不如数组那么高了。

下一篇：[LinkedList源码分析][LinkedList 2]

[b5f27e7cf9be45d8b48adbe7e321de70.png]: https://img-blog.csdnimg.cn/b5f27e7cf9be45d8b48adbe7e321de70.png
[LinkedList]: https://blog.csdn.net/itcast_cn/article/details/123800207?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167808785416800226551750%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=167808785416800226551750&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-123800207-null-null.blog_rank_default&utm_term=linklist&spm=1018.2226.3001.4450
[LinkedList 1]: https://img-blog.csdnimg.cn/b1bdb00a01a6443abd4d616dcf14e9fb.png
[LinkedList 2]: https://blog.csdn.net/weixin_43811057/article/details/129624120?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22129624120%22,%22source%22:%22weixin_43811057%22%7D