LinkedList

LinkedList继承AbstractSequentialList，实现了接口List，Queue，Deque， Clonealbe， Serializable
内部有一个数据结构Link用来表示LinkedList中的一个节点，该节点保存
- 数据信息
- 前后两个指针
内部类LinkIterator，实现LinkList的双向遍历
内部类ReverseLinkIterator，实现LinkedList逆向遍历

LinkedList增加元素

构造方法，注意此时LinkedList的size还是默认值0。

public LinkedList() {
        voidLink = new Link<E>(null, null, null);
        voidLink.previous = voidLink;
        voidLink.next = voidLink;
    }

LinkedList数据结构与源码分析
2. 在尾部增加元素，该方法比较简单, 虽然看上去有两个节点，但是voidLink并不是我们需要的，只是为了方便维护指针而存在的。所以此时size == 1

private boolean addLastImpl(E object) {
        Link<E> oldLast = voidLink.previous; // 1
        Link<E> newLink = new Link<E>(object, oldLast, voidLink); // 2
        voidLink.previous = newLink; // 3
        oldLast.next = newLink; // 4
        size++;
        modCount++;
return true;
    }

private static final class Link<ET> {
        ET data;

Link<ET> previous, next;

Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
            previous = p;
            next = n;
        }
    }

LinkedList数据结构与源码分析
如果继续在尾部增加节点，效果图如下，此时size == 2

3. 下面看一个复杂一点的add方法

@Override
public void add(int location, E object) {
if (location >= 0 && location <= size) {
/**注意这里一定要使用一个新的指针，后面移动的也是这个新的指针link，
 一定要在一个LinkedList的pos==0的元素的前面**/
        Link<E> link = voidLink;
/**这个if else 语句主要解决插入位置不在结尾时
 （在结尾时，执行到else，但是里面的for循环是不会执行的，
 其i>location是不满足的），沿着voidLink的next指针的方向（if语句做的事情），
 或者沿着voidLink的previous的指针方向(else语句的方向)，找到location的位置，
 将上一步指向最voidLink的指针link移动到指定的位置， 这里为了速度，
 看插入位置离头部近就从前向后找，离尾部近就从尾部向头部寻找。*/
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
                link = link.next;
            }
        } else {
for (int i = size; i > location; i--) {
                link = link.previous;
            }
        }


/**-------------后面的和前面说的addLastImpl都一样--------------**/
        Link<E> previous = link.previous;
        Link<E> newLink = new Link<E>(object, previous, link);
        previous.next = newLink;
        link.previous = newLink;
        size++;
        modCount++;
    } else {
throw new IndexOutOfBoundsException();
    }
}

4.在头部增加元素addFirstImpl和addLastImpl类似
5.clear方法，回复成voidLink最初的样子

@Override
public void clear() {
if (size > 0) {
        size = 0;
        voidLink.next = voidLink;
        voidLink.previous = voidLink;
        modCount++;
    }
}

LinkedList数据结构与源码分析
6. addAll方法可以在指定位置增加集合，另外，该集合可以是自己
7. contains方法需找元素equals那个，LinkedList中的元素允许为空

@Override
public boolean contains(Object object) {
Link<E> link = voidLink.next;
if (object != null) {
while (link != voidLink) {
if (object.equals(link.data)) {
return true;
            }
link = link.next;
        }
    } else {
while (link != voidLink) {
if (link.data == null) {
return true;
            }
link = link.next;
        }
    }
return false;
}

8.返回第一个元素，返回最后一个元素方法类似，省略不说

private E getFirstImpl() {
    Link<E> first = voidLink.next;
if (first != voidLink) {
return first.data;
    }
throw new NoSuchElementException();
}

9.indexOf和lastIndexOf两个方法从前向后和从后向前遍历，找到equals那个元素，找不到则返回-1

秒客网

LinkedList数据结构与源码分析

LinkedList

LinkedList增加元素

相关文章