linkedlist java 实现_Java LinkedList 实现原理
LinkedList 大家都不陌生，來看看他的實現原理，首先聲明，他是一個雙鏈條，即previous，next
/**
* Constructs a new empty instance of {@code LinkedList}.
*/
public LinkedList() {
voidLink = new Link(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}默認無參構造方法中，新建了一個空節點，他的previous,next都 指向他自己。另外一個構造方法：
/**
* Constructs a new instance of {@code LinkedList} that holds all of the
* elements contained in the specified {@code collection}. The order of the
* elements in this new {@code LinkedList} will be determined by the
* iteration order of {@code collection}.
*
* @param collection
* the collection of elements to add.
*/
public LinkedList(Collection extends E> collection) {
this();
addAll(collection);
}默認添加節點的位置是在最后：
/**
* Adds the specified object at the end of this {@code LinkedList}.
*
* @param object
* the object to add.
* @return always true
*/
@Override
public boolean add(E object) {
return addLastImpl(object);
}
private boolean addLastImpl(E object) {
Link oldLast = voidLink.previous;
Link newLink = new Link(object, oldLast, voidLink);
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}其中鏈條的設置順序為：
1.先設置新添加的節點的previous,next
2.然后設置老節點的next,和空節點的previous,完成節點鏈條的設置值。
3.總大小自增，修改次數自增
屬性modCount的作用在于：
private class SimpleListIterator implements Iterator {
int pos = -1;
int expectedModCount;
int lastPosition = -1;
SimpleListIterator() {
expectedModCount = modCount;
}
public boolean hasNext() {
return pos + 1 < size();
}
public E next() {
if (expectedModCount == modCount) {
try {
E result = get(pos + 1);
lastPosition = ++pos;
return result;
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
throw new ConcurrentModificationException();
}
public void remove() {
if (this.lastPosition == -1) {
throw new IllegalStateException();
}
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
try {
AbstractList.this.remove(lastPosition);
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
expectedModCount = modCount;
if (pos == lastPosition) {
pos--;
}
lastPosition = -1;
}
} 當你在遍歷整個list列表數據時，如果異步線程修改了這個列表的數據時，這個list遍歷過程能夠及時的拋錯并退出當前的遍歷，可以很好的保護數據讀取的一致性。
如果我們要移除一部分數據時：
/**
* Removes the object at the specified location from this {@code LinkedList}.
*
* @param location
* the index of the object to remove
* @return the removed object
* @throws IndexOutOfBoundsException
* if {@code location < 0 || location >= size()}
*/
@Override
public E remove(int location) {
if (location >= 0 && location < size) {
Link link = voidLink;
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;
}
}
Link previous = link.previous;
Link next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}移除數據相對比較簡單：
1.定位移除節點的位置
2.上一節點的next 設值
3.下一節點的previous 設值
相關的方法：?removeFirstImpl，removeLastImpl
其中里面有一個關鍵字：
總結
以上是生活随笔為你收集整理的linkedlist java 实现_Java LinkedList 实现原理的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java soap envelope_如
- 下一篇： 成都两年JAVA工程师_成都Java工程