欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java语言之LinkedList源码分析(jdk1.8)

程序员文章站 2022-06-07 13:35:45
...

1、LinkedList简介

        LinkedList见名知意,他在数据结构中是一个类似于链表的链式存储结构。学习过数据结构的我们都知道链式存储最大的特点有以下

  •   链表长度不受限制(理论上在内存空间允许的情况下链表可以申请无限的长度
  •   插入删除较为方便 (在链表的数据结构上进行增删,相比较数组而言较为方便,不需要像数组一样整体移动元素
  •   索引元素较为麻烦 (链式存储在索引元素时较为麻烦,如果采用遍历方式寻找,有着较高的时间复杂度,当数据较多时链式一般采用采用二叉搜索树的形式进行存储)  

2、LinkedList数据结构

        和普通链表相似,LinkedList中主要是通过记录其信息

    //链表的当前存储长度
	transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
	 //链表的首元素节点
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
	 //链表的尾元素节点
    transient Node<E> last;

         在LinkedList中每个节点元素都是以Node形式储存,在LinkedList中Node以其内部类的形式定义

    //链表中节点元素的数据结构
	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;
        }
    }
        由Node的定义可知,在java的LinkedList中其以一个双向链表的形式存储并使用

3、LinkedList构造方法与核心方法

        构造方法:

    //无参构造方法
	 public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
	 //创建一个链表序列,并将指定集合C中的元素放入链表序列中
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

        add方法:

    //在链表中增加一个元素
	public boolean add(E e) {
		//在没有指定位置的情况下,默认将新增元素放入链表的最后位置
        linkLast(e);
        return true;
    }
	
	//将指定的元素e放入链表的最后位置
	 void linkLast(E e) {
        final Node<E> l = last;
		//存放最后的位置,e节点的前驱为l,后继为null
        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 e)方法

    //在指定的索引位置插入一个元素
	public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
	
	 /**
     * Returns the (non-null) Node at the specified element index.
     */
	 //根据位置信息找出指定的元素
    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;
        }
    }
	
	/**
     * Inserts element e before non-null Node succ.
     */
	 //在一个为空节点succ前插入指定节点e
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        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(int index)

    //获取指定位置的元素
	 public E get(int index) {
		 
        checkElementIndex(index);
		
		//获取指定位置的元素信息,不包含前驱与后继节点位置
        return node(index).item;
    }

        获取首尾元素的值

    //获取首尾节点的元素值
	 public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }


        未完待续.............

        附:以上皆由作者原创,转载请注明出处