LinkedList數(shù)據(jù)結(jié)構(gòu)原理
LinkedList底層的數(shù)據(jù)結(jié)構(gòu)是基于雙向循環(huán)鏈表的爆哑，且頭結(jié)點(diǎn)中不存放數(shù)據(jù)洞难；
LinkedList構(gòu)造函數(shù)
transient int size = 0;
transient Link<E> voidLink;
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;
}
}
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
Link是LinkedList的靜態(tài)內(nèi)部類，可以看作節(jié)點(diǎn)類，data用來(lái)存放數(shù)據(jù)队贱，previous與next則分別存放前后節(jié)點(diǎn)的信息色冀；而構(gòu)造函數(shù)中實(shí)際上是作了對(duì)voidLink的初始化操作，也就是對(duì)頭指針的初始化操作柱嫌；
空鏈表的情況應(yīng)該是header節(jié)點(diǎn)的前一節(jié)點(diǎn)和后一節(jié)點(diǎn)均為null锋恬；
1.添加一個(gè)元素到鏈表尾部
public boolean add(E object) {
return addLastImpl(object);
}
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}
從源碼中可以看到，添加元素到鏈表尾實(shí)際上是新new了一個(gè)Link節(jié)點(diǎn)（newLink）;
voidLink實(shí)際上是頭節(jié)點(diǎn)编丘，然后把頭節(jié)點(diǎn)的前結(jié)點(diǎn)指向newLink与学；把原尾結(jié)節(jié)oldLast的后結(jié)點(diǎn)指向newLink；
2.添加一個(gè)元素到鏈表指定位置
public void add(int location, E object) {
if (location >= 0 && location <= size) {
Link<E> 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<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();
}
}
添加到鏈表指定位置嘉抓，會(huì)先遍歷索守，是順向迭代還是反向迭代，找到位置然后再同上添加元素的操作抑片，將節(jié)點(diǎn)指向修改正確卵佛；
3.刪除數(shù)據(jù)
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> 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<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
刪除的節(jié)點(diǎn)對(duì)象是由系統(tǒng)去gc回收的第股；
4.查找數(shù)據(jù)與修改數(shù)據(jù)
為了提高效率楚里，需要根據(jù)獲取的位置判斷是從頭還是從尾開(kāi)始遍歷
5.用LinkedList模似堆棧
addLastImpl(E object)
addFirst(E object)
removeFirstImpl()
removeLast()
在LinekList中封裝了上面四個(gè)方法腺毫，分別添加刪除鏈表頭尾庭砍，對(duì)鏈表的操作進(jìn)行一下封裝和限制就可以模擬堆椨褂眨或者隊(duì)列了芽狗；
public class Test5{
public static void main(String[] args){
Duilie dl = new Duilie();
dl.myAdd("abc1);
dl.myAdd("abc2);
dl.myAdd("abc3);
dl.myAdd("abc4);
while(!dl.isNull()){
System.out.println(dl.myGet());
}
}
}
class Duilie{
private LinkedList link;
public Duilie(){
link = new LinkedList();
}
public void myAdd(Object obj){
//添加到鏈表尾部
link.addLast(obj);
}
public Object myGet(){
//獲取頭部元素
// return link.removeFirst(); 模似隊(duì)列
//獲取尾部元素
return link.removeLast(); //模似堆棧
}
public boolean isNull(){
return link.isEmpty();
}
}
LinkedList總結(jié)
①數(shù)據(jù)存儲(chǔ)是基于雙向鏈表實(shí)現(xiàn)的喉前；
②插入數(shù)據(jù)很快令野。先是在雙向鏈表中找到要插入節(jié)點(diǎn)的位置index焰枢，找到之后蚓峦，再插入一個(gè)新節(jié)點(diǎn)。 雙向鏈表查找index位置的節(jié)點(diǎn)時(shí)医咨，有一個(gè)加速動(dòng)作：若index < 雙向鏈表長(zhǎng)度的1/2枫匾，則從前向后查找; 否則拟淮，從后向前查找干茉；
③刪除數(shù)據(jù)很快。先是在雙向鏈表中找到要插入節(jié)點(diǎn)的位置index很泊，找到之后角虫，進(jìn)行如下操作：node.previous.next = node.next;node.next.previous = node.previous;node = null ，查找節(jié)點(diǎn)過(guò)程和插入一樣委造；
④獲取數(shù)據(jù)很慢戳鹅，需要從頭節(jié)點(diǎn)進(jìn)行查找；
⑤遍歷數(shù)據(jù)很慢昏兆，每次獲取數(shù)據(jù)都需要從頭開(kāi)始枫虏；
