LinkedList数据结构与源码分析

2/10/2017来源:ASP.NET技巧人气:204

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

这里写图片描述 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; } }

这里写图片描述 如果继续在尾部增加节点,效果图如下,此时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++; } }

这里写图片描述 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