java容器类详解--LinkedList

时间：2022-12-15 18:48:18

LinkedList的主要特点是它实现了List,Deque,可以作为堆栈,队列,双端队列,以及链表
内部维护了一个内部类Entry

//私有静态内部类,笔者个人认为class前面加不加静态属性,影响不大
private static class Entry<E> {
    E element;
    Entry<E> next;
    Entry<E> previous;
//构造器中传入元素本身的引用,以及下一个、上一个元素的引用
    Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
    }
    }

链表的最后一个元素的下一个元素就是header,header的前一个元素就是链表的最后一个元素,这样就形成了环形链表了。注意:LinkedList的index是从0开始,并且不算header在内
LinkedList的增删改查都是围绕这一串链表进行的操作

添加单个元素:LinkedList中的添加单个元素都是调用的同一个方法addBefore() 

private Entry<E> addBefore(E e, Entry<E> entry) {
//先组装好即将添加的元素
    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
//将原来的链路打断,接入新的元素
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
/** 
 modCount表示这个链表发生结构性的变化的次数,在调用listIterator()遍历元素的时候(生成的ListItr
 对象会记录当时的LInkedList的modCount),如果在遍历的同事,调用LinkedList的增加和删除方法
 modCount发生改变就会抛出ConcurrentModificationException 
 */
    modCount++;
return newEntry;
    }

添加一个集合:在指定索引位置添加集合addAll(int index, Collection

public boolean addAll(int index, Collection<? extends E> c) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
        Object[] a = c.toArray();
int numNew = a.length;
if (numNew==0)
return false;
    modCount++;
//保存下一个元素的引用
        Entry<E> successor = (index==size ? header : entry(index));
//保存上一个元素的引用
        Entry<E> predecessor = successor.previous;
for (int i=0; i<numNew; i++) {
            Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
//将predecessor中的"下一个元素引用"改为新元素
            predecessor.next = e;
//将前一个元素向后移一位
            predecessor = e;
        }
//循环结束之后将后一个元素的"前一个元素"由最开始的previous改为最后的predecessor
        successor.previous = predecessor;

        size += numNew;
return true;
    }

删除元素:所有的删除方法都是调用的它的一个私有方法

private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();

        E result = e.element;
//打断链条,重新接上新的元素
    e.previous.next = e.next;
    e.next.previous = e.previous;
//置为null,等待gc回收
        e.next = e.previous = null;
        e.element = null;
    size--;
    modCount++;
return result;
    }

根据索引查找元素:entry(int index)

private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
        Entry<E> e = header;
//由于链表的特性,遍历元素时要根据上一个元素才能得到下一个元素,所以程序先将index与size的一半进行判断,减少遍历的次数

if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
for (int i = size; i > index; i--)
                e = e.previous;
        }
return e;
    }

修改元素和查询元素的方法比较简单,这里就不一一列举。
因为linkedList可以作为队列/双端队列使用,可以使用offer()、poll()等一系列对链表的头尾元素的操作方式。
对于普通的实现了Iterator接口的类来说,仅仅之后单向迭代,而LinkedList比较特殊,它的listIterator()方法会返回一个它的内部类,这个内部类实现Iterator,并扩展了向前迭代的功能,在每次next()执行时,会保存上一次的元素。
虽然LinkedList中的listIterator()和listIterator(int index)是两个方法,其实listIterator()是abstractList中的方法,然后调用了其同类方法listIterator(int index) 因为LinkedList重写了listIterator(),所以还是调用的是LinkedList中的listIterator方法。

虽然是链表结构,插入元素和删除元素比较快,但是在插入和删除元素之前需要定位元素,只能从头/尾挨个遍历,这样效率就比较慢,特别是操作链表中间的元素的时候。
标签：

相关文章