java数据结构之链表LinkedList的使用与实现原理解读诗心博客

一、LinkedList的优缺点　

优点：
- 插入和删除操作较快，只需要修改对应的指针即可
缺点：
- 通过索引查找元素较慢

二、LinkedList与其他数据结构的关系

1.LinkedList与集合等结构的关系

LinkedList与其他集合的关系

2.LinkedList实现的方法

LinkedList实现的接口方法

三、LinkedList的使用及实现原理解读

1.LinkedList的属性

size : 元素个数
first : 链首，链表的第一个节点(Node)
last : 链尾，链表的最后一个节点

链表是由各个节点组成的，下面说探讨一下Node节点的结构(LinkedList实际是一个双向链表)

item : 元素值
next : 当前节点的下一个节点
prev : 当前节点的上一个节点

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

2.LinkedList实例化方法

(1) 链表实例化方法的使用

new LinkedList() : 初始化一个空链表
new LinkedList(Collection c) :通过一个集合来初始化一个链表，将集合的元素转化为链表节点

//1.无参实例化
List<Integer> linkedList = new LinkedList<Integer>();
linkedList.add(5);
linkedList.add(8);
System.out.println(linkedList);  //[5, 8]
//2.通过一个集合来实例化
List<String> courseList = new ArrayList<String>(5);
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
List<String> examinationList = new LinkedList<String>(courseList);
System.out.println(examinationList);  //[JAVA编程, 网络安全, 计算机网络]

(2)链表实例化方法的实现解读

public LinkedList(Collection<? extends E> c) {
    //1.调用无参实例化方法
    this();
    //2.通过addAll方法将集合元素转化为链表节点元素(addAll方法实现在后面讲解)
    addAll(c);
}

3.实现迭代器的方法iterator

(1)iterator的使用

List<String> courseList = new ArrayList<String>(5);
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
//直接引用迭代器，通过iterator方法将返回一个Iterator对象
Iterator<String> iterator = courseList.iterator();
while (iterator.hasNext()) {
    //通过调用next方法不仅可以返回迭代器下一个元素指向的元素，而且还会将迭代器指针向下移动
    System.out.println(iterator.next());  //依次输出：JAVA编程　网络安全　计算机网络
}

(2)iterator的实现解读

public Iterator<E> iterator() {
    //通过listIterator()来实现的
    return listIterator();
}

实际实现listIterator方法的是ListItr类

private class ListItr implements ListIterator<E> {
        //上次返回的节点
        private Node<E> lastReturned;
        //下次迭代的节点
        private Node<E> next;
        //下次迭代的节点索引
        private int nextIndex;
        //期望的修改次数
        private int expectedModCount = modCount;
        //实例化迭代器，需要指定一个索引值(一般是传入0，从第一个元素开始)
        ListItr(int index) {
            // 判断当前索引是否为链表的长度，如果等于链表的长度，表示是第后一个节点，那么它的下一个节点就是null
            //如果索引值不为链表长度，那么通过node方法来获取节点(遍历链表来获取节点)
            /*　------------------------------------------
            //通过索引来获取节点元素
            Node<E> node(int index) {
                //size >> 1是一个右移运算，相当于size / 2 ，即链表的中间位置
                //如果索引值比中间位置小，即在链表中间的左边，那么就从开始位置查找
                if (index < (size >> 1)) {
                    //从链表的开头位置开始遍历
                    Node<E> x = first;
                    //查找到index的前一个节点，它那它前一个节点的next指向的节点即为index的位置所在节点
                    for (int i = 0; i < index; i++)
                        x = x.next;
                    return x;
                } else {
                    //如果索引值比中间位置小，那么索引值在链表中间位置的右边，那么从链表的结束位置开始查找
                    Node<E> x = last;
                    //从结束的位置查找，找到索引值的后一个节点，那么这个节点的前一个指针指向的节点即为index所在的节点
                    for (int i = size - 1; i > index; i--)
                        x = x.prev;
                    return x;
                }
            }
            ---------------------------------------------------*/
            next = (index == size) ? null : node(index);
            //下一个迭代的索引等于指定的索引值
            nextIndex = index;
        }
        public boolean hasNext() {
            //判断下一个迭代的索引值是否小于链表长度，如果大于等于链表长度，就是链表结尾，就没有下一个元素了
            return nextIndex < size;
        }
        public E next() {
        　　 //检查修改次数　
            checkForComodification();
            //检查是否有下一个节点
            if (!hasNext())
                throw new NoSuchElementException();
　　　　　　　//上一次返回节点为下一个节点(因为调用next后就返回了当前next节点)
            lastReturned = next;
            //下一个节点指向下一个节点的下个节点(因为调用next后当前节点就指向了next节点)
            next = next.next;
            //指向下一个节点的索引值增加
            nextIndex++;
            //返回上次返回的节点数据
            return lastReturned.item;
        }
        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();
            //获取上次返回的节点
            Node<E> lastNext = lastReturned.next;
            //删除上次返回的节点(删除节点即为删除节点的数据，修改其前一个节点的和后一个节点的指向)
            /*----------------------------------------------------
            //删除节点的方法说明
             E unlink(Node<E> x) {
                //要删除的节点元素
                final E element = x.item;
                //要删除的节点的下一个节点
                final Node<E> next = x.next;
                //要删除的节点的上一个节点
                final Node<E> prev = x.prev;
                //1.如果它一个节点为null，那么删除的元素就是表头
                if (prev == null) {
                    //因为要删除表头，所以要将表头设置为删除元素的下一个元素
                    first = next;
                } else {
                    //删除的元素不是表头，就将它前一个元素的next指针指向删除元素的下一个节点
                    prev.next = next;
                    //并且将要删除的元素的prev指针指向null
                    x.prev = null;
                }
                //2.如果删除元素的下一个节点为null，那么删除的元素就是表尾
                if (next == null) {
                    //如果要删除表尾，那么要将表尾设置为删除元素的上一个元素节点
                    last = prev;
                } else {
                    //如果要删除的不是表尾，那么就要将删除元素的下一个节点的prev指针指向删除元素的上一个元素节点
                    next.prev = prev;
                    //将删除元素的next指针指向null
                    x.next = null;
                }
                //删除元素节点为null，以便回收空间
                x.item = null;
                //减少元素个数
                size--;
                modCount++;
                return element;
            }
            --------------------------------------------------------*/
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }
        //其他方法不再赘述，只说明最基本的迭代器方法
}

4.ＬinkedList实现Collection接口

(1)contains方法

I.contains方法的使用

作用：检测链表是否包含某个元素
返回值：true|false

List<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
System.out.println(courseList.contains("JAVA编程"));  //true

II.contains方法的实现解读

public boolean contains(Object o) {
    //通过indexOf方法来判断，indexOf是用来判断某个元素在链表中的索引位置，如果没有该元素，则返回　-1
    return indexOf(o) != -1;
}

(2)size方法

I.size方法的使用

作用：返回链表的元素个数
返回值：返回链接元素个数的整数

List<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
System.out.println(courseList.size());   //3

II.size方法的实现解读

public int size() {
    //size属性值一直记录着元素的个数
    return size;
}

(3)isEmpty方法

I.isEmpty方法的使用

作用：判断当前链表是否为空链表

II.isEmpty方法的实现解读

通过size属性是否为0来判断链表是否为空

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

(4)实现toArray方法

I.toArray方法使用

List<String> courseList = new ArrayList<String>(5);
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
String[] courseArr = new String[courseList.size()];
courseList.toArray(courseArr);
for (int i = 0; i< courseArr.length; i++) {
    System.out.println(courseArr[i]);  //依次输出：JAVA编程　　网络安全　计算机网络
}

II.toArray方法实现解读

public <T> T[] toArray(T[] a) {
    //如果数组长度太短，无法容纳链表的内容，则申请一个新的数组空间，将它a指向一个新的数组空间
    if (a.length < size)
        //通过反射机制来实现数组的扩容
        a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
    //遍历链表，将链表的节点赋值给数组相应的元素
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    //如果数组长度大于链表的长度(如果原数组是有值的，而且长度大于链表长度)，则将数组第size位设置为null
    if (a.length > size)
        a[size] = null;
    return a;
}

(5)实现add方法

I.add方法的使用

作用：向链表添加或插入节点
使用方式：
- add(E element) : 在链表结尾添加节点
- add(int index, E element) ：在指定位置添加节点

List<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
courseList.add(2, "计算机组成原理");
System.out.println(courseList);//[JAVA编程, 网络安全, 计算机组成原理, 计算机网络]

II.add方法的实现解读

//在链表结尾添加节点
public boolean add(E e) {
    //调用linkLast方法
    linkLast(e);
    return true;
}
//在指定位置添加节点
public void add(int index, E element) {
    checkPositionIndex(index);
    //如果要插入的索引位置在链表结尾，则在链表结尾添加
    if (index == size)
        /*-------------------------------------------------------
        void linkLast(E e) {
            //1.获取最后一个元素节点
            final Node<E> l = last;
            //2.生成一个新的节点，它的上一个节点为当前链表结尾节点，下一个节点为null
            final Node<E> newNode = new Node<>(l, e, null);
            //3.将新节点作为新的链表结尾节点
            last = newNode;
            //4.如果原结尾节点为null，即原链表是空链表时
            if (l == null)
            　　 //空链表时，指定新节点为首节点
                first = newNode;
            else
                //不为空链表时，将原尾节点的下一个元素指针指向新节点
                l.next = newNode;
            //5.增加链表元素个数
            size++;
            modCount++;
        }
        -------------------------------------------------------*/
        linkLast(element);
    else
        //在某个指定位置添加
        /*----------------------------------------------
        void linkBefore(E e, Node<E> succ) {
            //1.获取在插入的位置原节点的前一个节点
            final Node<E> pred = succ.prev;
            //2.生成新节点，它存储的元素为e,前一个节点指向插入位置的前一个节点，下一个节点指向原插入位置的节点
            final Node<E> newNode = new Node<>(pred, e, succ);
            //3.将原插入位置的节点的prev指针指向新插入的元素节点
            succ.prev = newNode;
            //4.如果原插入位置的前一个节点为null，则原链表为空链表时，指定链表首节点为新插入的节点
            if (pred == null)
                first = newNode;
            else
                //如果原链表不为空链表时，则将原插入位置的前一个节点的next指针指向新插入的节点
                pred.next = newNode;
            //5.增加链表元素个数
            size++;
            modCount++;
        }
        -----------------------------------------------*/
        linkBefore(element, node(index));
}

(6)实现remove方法

I.remove方法的使用

remove(Object o) :通过指定删除的对象来删除
remove(int index):通过指定索引来删除

List<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
courseList.add("计算机组成原理");
courseList.add("C语言编程");
courseList.remove("网络安全");
System.out.println(courseList); //[JAVA编程, 计算机网络, C语言编程]
courseList.remove(2);
System.out.println(courseList);//[JAVA编程, 网络安全, 计算机组成原理, 计算机网络]

II.remove方法的实现解读

//通过节点对象来删除链表节点
public boolean remove(Object o) {
    //如果删除的元素为null
    if (o == null) {
        //从链首开始遍历，依次查找第一个为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)) {
                /*-------------------------------------------------
                //删除节点的方法说明
                 E unlink(Node<E> x) {
                    //要删除的节点元素
                    final E element = x.item;
                    //要删除的节点的下一个节点
                    final Node<E> next = x.next;
                    //要删除的节点的上一个节点
                    final Node<E> prev = x.prev;
                    //1.如果它一个节点为null，那么删除的元素就是表头
                    if (prev == null) {
                        //因为要删除表头，所以要将表头设置为删除元素的下一个元素
                        first = next;
                    } else {
                        //删除的元素不是表头，就将它前一个元素的next指针指向删除元素的下一个节点
                        prev.next = next;
                        //并且将要删除的元素的prev指针指向null
                        x.prev = null;
                    }
                    //2.如果删除元素的下一个节点为null，那么删除的元素就是表尾
                    if (next == null) {
                        //如果要删除表尾，那么要将表尾设置为删除元素的上一个元素节点
                        last = prev;
                    } else {
                        //如果要删除的不是表尾，那么就要将删除元素的下一个节点的prev指针指向删除元素的上一个元素节点
                        next.prev = prev;
                        //将删除元素的next指针指向null
                        x.next = null;
                    }
                    //删除元素节点为null，以便回收空间
                    x.item = null;
                    //减少元素个数
                    size--;
                    modCount++;
                    return element;
                }
                ---------------------------------------------------*/
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
//通过索引删除节点
public E remove(int index) {
    checkElementIndex(index);
　　 /*------------------------------------------------------------
    //通过索引找到节点对象
    Node<E> node(int index) {
        //size >> 1右移运算相当于size / 2
        //1.如果索引值在链表的中间位置的左侧，那么就从链头开始查找
        if (index < (size >> 1)) {
            //2.起始位置即为链首
            Node<E> x = first;
            //3.遍历链表，最后个元素就是查找索引的前一个元素，那么它的next指针指向的就是索引指向的节点
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            //1.如果索引值在中间位置的右侧，从链尾开始查找
            //2.起始位置就是链尾
            Node<E> x = last;
            //3.遍历链表，最后一个元素就是查找索引位置的后一个元素，那的它的prev指针指向的就是索引指向的节点
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    */　
    //1.先通过索引找到要删除的节点对象(node方法)
    //2.再调用unlink删除节点
    return unlink(node(index));
}

(7)实现addAll方法

I.addAll方法的使用

addAll(Collection c):在链表末尾添加节点
addAll(int index, Collection c) : 在指定位置批量插入节点

List<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
courseList.add("计算机组成原理");
courseList.add("C语言编程");
List<String> courseArrList = new ArrayList<String>(2);
courseArrList.add("计算机英语");
courseArrList.add("高等数学");
courseList.addAll(courseArrList);
System.out.println(courseList);    //[JAVA编程, 网络安全, 计算机网络, 计算机组成原理, C语言编程, 计算机英语, 高等数学]
Set<String> courseSet = new HashSet<String>(3);
courseSet.add("线性代数");
courseSet.add("微积分");
courseList.addAll(5, courseSet);
System.out.println(courseList);  //[JAVA编程, 网络安全, 计算机网络, 计算机组成原理, C语言编程, 线性代数, 微积分, 计算机英语, 高等数学]

II.addAll方法的实现解读

//不指定位置时，默认在链表结束添加元素
public boolean addAll(Collection<? extends E> c) {
    //调用在指定位置批量添加元素的方法
    return addAll(size, c);
}
//在指定位置批量添加节点
public boolean addAll(int index, Collection<? extends E> c) {
    //检查索引值的合法性
    checkPositionIndex(index);
    //1.将插入的集合元素转化为数组a
    Object[] a = c.toArray();
    //2.获取数组的长度即插入节点的个数
    int numNew = a.length;
    //3.如果插入的节点个数为0，直接返回
    if (numNew == 0)
        return false;
    //pred用来表示插入元素的prev指针节点,succ表示插入索引的原位置节点
    Node<E> pred, succ;
    //4.如果插入的索引位置和链表个数相等，即在链表结尾添加节点
    if (index == size) {
        //5.如果插入的位置是链表结尾，那么插入位置的原节点是null
        succ = null;
        //6.而且链表插入位置的prev指针就是原链表最后一个节点
        pred = last;
    } else {
        //如果插入位置不是链表结尾，那么根据index值查找到原插入位置的节点
        succ = node(index);
        //插入位置的节点的prev指针就是原插入节点的prev指针
        pred = succ.prev;
    }
    //7.遍历插入的新节点
    for (Object o : a) {
        //8.生成新节点，它对应的元素为e,它的prev指针为pred,next指针为null
        E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        //9.如果prev指针是null则表示原链表是一个空链表，那么将链表的first指针指向插入的节点
        if (pred == null)
            first = newNode;
        else
            //10.如果原链表不是空链表，那么插入位置的next指针就是当前插入的节点
            pred.next = newNode;
        pred = newNode;
    }
    //11.如果插入的位置是原链表结尾
    if (succ == null) {
        //那么last指针指向插入位置的prev指针
        last = pred;
    } else {
        //12.如果插入位置不在原链表结尾，那么插入位置的前一个元素的next指针，指向插入位置的元素,而插入位置的元素节点的prev指针指向插入位置的前一个节点
        pred.next = succ;
        succ.prev = pred;
    }
    //增加链表节点个数
    size += numNew;
    modCount++;
    return true;
}

(8)实现removeAll方法

I.removeAll方法的使用

removeAll(Collection c):批量删除指定集合的节点

List<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
courseList.add("高等数学");
courseList.add("概率论与数理统计");
courseList.add("线性代数");
courseList.add("微积分");
Set<String> mathSet = new HashSet<String>();
mathSet.add("高等数学");
mathSet.add("概率论与数理统计");
mathSet.add("线性代数");
mathSet.add("微积分");
courseList.removeAll(mathSet);
System.out.println(courseList);  //[JAVA编程, 网络安全, 计算机网络]

II.removeAll方法的实现解读

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    //1.获取当前链表的迭代器
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        //2.判断删除的集合中是否有当前迭代器中元素
        if (c.contains(it.next())) {
            //3.调用对应的迭代器对象删除节点
            /*--------------------------------------------------------------
            //实际调用的是AbstractList中的Itr的remove方法
            public void remove() {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();
                try {
                    //调用LinkedList的remove方法
                    AbstractList.this.remove(lastRet);
                    if (lastRet < cursor)
                        cursor--;
                    lastRet = -1;
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException e) {
                    throw new ConcurrentModificationException();
                }
            }
            ---------------------------------------------------------------*/
            it.remove();
            modified = true;
        }
    }
    return modified;
}

(9)实现clear方法

I.clear方法的使用

作用：清空链表

List<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
courseList.clear();
System.out.println(courseList.isEmpty()); //true

II.clear方法的实现解读

public void clear() {
      //1.遍历整个链表，将每个元素存储的元素设置为null，并将它的prev,next指针都指向null
      for (Node<E> x = first; x != null; ) {
          Node<E> next = x.next;
          x.item = null;
          x.next = null;
          x.prev = null;
          x = next;
      }
      //2.将链表的表头和表尾都设置为null
      first = last = null;
      //3.将链表元素个数设置为0
      size = 0;
      modCount++;
}

5.LinkedList实现List接口

(1)set方法

I.set方法的使用

set(int index, E value):为指定索引位置设置新的元素对象

List<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
courseList.set(1, "计算机文化基础");
System.out.println(courseList);  //[JAVA编程, 计算机文化基础, 计算机网络]

II.set方法的实现解读

public E set(int index, E element) {
    checkElementIndex(index);
    //1.通过索引获取到对应的原节点对象,node函数之前已经介绍过，在此不再赘述
    Node<E> x = node(index);
    //2.获取原节点对象的值
    E oldVal = x.item;
    //3.为当前索引对应的元素设置新的值
    x.item = element;
    return oldVal;
}

(2)get方法

I.get方法的使用

get(int index):获取指定索引位置对应的节点

List<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
String tmp = courseList.get(1);
System.out.println(tmp);  //网络安全

II.get方法的实现解读

public E get(int index) {
    checkElementIndex(index);
    //通过node方法查找到节点，再获取节点的item属性值
    return node(index).item;
}

List接口其他方法，在些不再赘述，使用方式与ArrayList基本一致，因为它们都实现了List接口，实现原理，基本上都是通过node方法来获取元素

6.LinkedList实现Queue接口

(1)offer方法

offer即为在队尾添加元素，是使用add方法实现的，和add(E e)是一样的，在此不再赘述

(2)poll方法

I.poll方法的使用：

poll : 弹出队列的第一个元素

LinkedList<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
courseList.add("计算机文化基础");
String first = courseList.poll();
System.out.println(first);      //JAVA编程
System.out.println(courseList); //[网络安全, 计算机网络, 计算机文化基础]

II.poll方法的实现解读：

public E poll() {
    //1.获取队列的第一个元素
    final Node<E> f = first;
    //2.如果队列的第一个元素不为null，那么从队列中将它删除掉
    /*-------------------------------------------------
    //删除第一个元素
    private E unlinkFirst(Node<E> f) {
        final E element = f.item;
        final Node<E> next = f.next;
        //1.删除节点本身
        f.item = null;
        //2.节点的next指针指向null
        f.next = null;
        //3.将队列的头元素节点指向当前头元素的下一个节点
        first = next;
        //4.如果旧头节点的next指针是null，也就是原队列就一个元素
        if (next == null)
            //尾节点为null(本身就一个节点，既是头节点，也是尾节点，删除了，就没了，是个空队列了)
            last = null;
        else
            //还有下一个节点，那么就将原队列的第二个节点的prev指针指向null,第二个节点成为新的头节点
            next.prev = null;
        //5.减少队列的节点个数
        size--;
        modCount++;
        return element;
    }
    ---------------------------------------------------*/
    return (f == null) ? null : unlinkFirst(f);
}

(3)element方法

element方法是获取队列头元素的值，是通过读取first属性来实现的

(4)peek方法

peek是从队列中获取队尾元素的值，是通过获取last的属性来实现的

(5)push方法

I.push的使用

push:在链表开头插入元素节点

LinkedList<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
courseList.push("计算机文化基础");
System.out.println(courseList); //[计算机文化基础, JAVA编程, 网络安全, 计算机网络]

II.push的实现方式

public void push(E e) {
    /*
    ---------------------------------------------
    public void addFirst(E e) {
        linkFirst(e);
    }
    private void linkFirst(E e) {
        //1.获取头节点
        final Node<E> f = first;
        //2.生成新插入的节点
        final Node<E> newNode = new Node<>(null, e, f);
        //3.将链表头指向新插入的节点
        first = newNode;
        //4.如果原链表头是null，即原链表是空链表，那么插入的元素就是唯一的元素节点，链表的尾节点也是新插入的元素节点
        if (f == null)
            last = newNode;
        else
            //如果原链表有节点，那么原表头成为第二个节点，它的prev指针指向新节点
            f.prev = newNode;
        //5.增加链表元素个数
        size++;
        modCount++;
    }
    ---------------------------------------------
    */
    addFirst(e);
}

(6)pop方法

它的功能与poll方法一致，在此不再赘述

7.其他方法的使用及实现

(1)clone方法

I.clone方法的使用：

LinkedList<String> courseList = new LinkedList<String>();
courseList.add("JAVA编程");
courseList.add("网络安全");
courseList.add("计算机网络");
LinkedList<String> cloneCourseList = (LinkedList<String>) courseList.clone();
System.out.println(cloneCourseList); //[JAVA编程, 网络安全, 计算机网络]

II.clone方法实现解读：

public Object clone() {
    /*-----------------------------------------------
    private LinkedList<E> superClone() {
        try {
            //调用基类Object对象clone的方法
            return (LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }
    ------------------------------------------------*/
    //1.对象克隆
    LinkedList<E> clone = superClone();
    //2.将克隆对象的链表头和链表尾都指向null，并且节点个数设置为0,即为一个空表
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;
    //3.遍历原链表对象的节点，依次添加到新克隆对象上
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);
    return clone;
}

java数据结构之链表LinkedList的使用与实现原理解读

一、LinkedList的优缺点

二、LinkedList与其他数据结构的关系

1.LinkedList与集合等结构的关系

2.LinkedList实现的方法

三、LinkedList的使用及实现原理解读

1.LinkedList的属性

2.LinkedList实例化方法

(1) 链表实例化方法的使用

(2)链表实例化方法的实现解读

3.实现迭代器的方法iterator

(1)iterator的使用

(2)iterator的实现解读

4.ＬinkedList实现Collection接口

(1)contains方法

(2)size方法

(3)isEmpty方法

(4)实现toArray方法

(5)实现add方法

(6)实现remove方法

(7)实现addAll方法

(8)实现removeAll方法

(9)实现clear方法

5.LinkedList实现List接口

(1)set方法

(2)get方法

6.LinkedList实现Queue接口

(1)offer方法

(2)poll方法

(3)element方法

(4)peek方法

(5)push方法

(6)pop方法

7.其他方法的使用及实现

(1)clone方法

专题更多...

分类更多...

标签更多...

归档更多...

一、LinkedList的优缺点

二、LinkedList与其他数据结构的关系

1.LinkedList与集合等结构的关系

2.LinkedList实现的方法

三、LinkedList的使用及实现原理解读

1.LinkedList的属性

2.LinkedList实例化方法

(1) 链表实例化方法的使用

(2)链表实例化方法的实现解读

3.实现迭代器的方法iterator

(1)iterator的使用

(2)iterator的实现解读

4.ＬinkedList实现Collection接口

(1)contains方法

(2)size方法

(3)isEmpty方法

(4)实现toArray方法

(5)实现add方法

(6)实现remove方法

(7)实现addAll方法

(8)实现removeAll方法

(9)实现clear方法

5.LinkedList实现List接口

(1)set方法

(2)get方法

6.LinkedList实现Queue接口

(1)offer方法

(2)poll方法

(3)element方法

(4)peek方法

(5)push方法

(6)pop方法

7.其他方法的使用及实现

(1)clone方法

专题 更多...

分类 更多...

标签 更多...

归档 更多...

一、LinkedList的优缺点　

专题更多...

分类更多...

标签更多...

归档更多...