LinkedList數據結構與源碼分析

2019-11-14 10:31:54

字體：大中小

來源：轉載

供稿：網友

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

上一篇：4.1串類型的定義

下一篇：1060. Are They Equal (25)