LinkedList数据结构与源码分析

2019-11-14 10:03:42

字体：大中小

来源：转载

供稿：网友

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方法

@Overridepublic 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最初的样子

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

这里写图片描述 6. addAll方法可以在指定位置增加集合，另外，该集合可以是自己 7. contains方法需找元素equals那个，LinkedList中的元素允许为空

@Overridepublic 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

上一篇：acm杭电2087-剪花布条

下一篇：R语言利用wordcloud2绘制词云