LinkedList數(shù)據(jù)結(jié)構(gòu)與源碼分析

2019-11-14 10:38:55

字體：大中小

供稿：網(wǎng)友

LinkedList

LinkedList繼承AbstractSequentialList，實(shí)現(xiàn)了接口List，Queue，Deque， Clonealbe， Serializable內(nèi)部有一個(gè)數(shù)據(jù)結(jié)構(gòu)Link用來(lái)表示LinkedList中的一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)保存數(shù)據(jù)信息前后兩個(gè)指針內(nèi)部類LinkIterator，實(shí)現(xiàn)LinkList的雙向遍歷內(nèi)部類ReverseLinkIterator，實(shí)現(xiàn)LinkedList逆向遍歷

LinkedList增加元素

構(gòu)造方法，注意此時(shí)LinkedList的size還是默認(rèn)值0。public LinkedList() { voidLink = new Link<E>(null, null, null); voidLink.PRevious = voidLink; voidLink.next = voidLink; }

這里寫(xiě)圖片描述 2. 在尾部增加元素，該方法比較簡(jiǎn)單, 雖然看上去有兩個(gè)節(jié)點(diǎn)，但是voidLink并不是我們需要的，只是為了方便維護(hù)指針而存在的。所以此時(shí)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; } }

這里寫(xiě)圖片描述如果繼續(xù)在尾部增加節(jié)點(diǎn)，效果圖如下，此時(shí)size == 2 3. 下面看一個(gè)復(fù)雜一點(diǎn)的add方法

@Overridepublic void add(int location, E object) { if (location >= 0 && location <= size) { /**注意這里一定要使用一個(gè)新的指針，后面移動(dòng)的也是這個(gè)新的指針link，一定要在一個(gè)LinkedList的pos==0的元素的前面**/ Link<E> link = voidLink; /**這個(gè)if else 語(yǔ)句主要解決插入位置不在結(jié)尾時(shí) （在結(jié)尾時(shí)，執(zhí)行到else，但是里面的for循環(huán)是不會(huì)執(zhí)行的，其i>location是不滿足的），沿著voidLink的next指針的方向（if語(yǔ)句做的事情），或者沿著voidLink的previous的指針?lè)较?else語(yǔ)句的方向)，找到location的位置，將上一步指向最voidLink的指針link移動(dòng)到指定的位置，這里為了速度，看插入位置離頭部近就從前向后找，離尾部近就從尾部向頭部尋找。*/ 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; } } /**-------------后面的和前面說(shuō)的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方法，回復(fù)成voidLink最初的樣子

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

這里寫(xiě)圖片描述 6. addAll方法可以在指定位置增加集合，另外，該集合可以是自己 7. contains方法需找元素equals那個(gè)，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.返回第一個(gè)元素，返回最后一個(gè)元素方法類似，省略不說(shuō)

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

9.indexOf和lastIndexOf兩個(gè)方法從前向后和從后向前遍歷，找到equals那個(gè)元素，找不到則返回-1

上一篇：寫(xiě)一個(gè)單例的類

下一篇：java反射機(jī)制（2）