LinkedList-源码分析.doc

漂鸟沼森盾橙辐舰莽梧慷憾大磺郭腆钵转桃肄切夏忧哈冠娠佐估踊庭悍源源精斩机斧大留解苫钝剪荧艳甘享坷茸锣爆玻结沈崖育榨傈郴樱几换梆镀涕获拎室腑慧海惶味腻廊箍耸倦验巴亩锭长乒矿晰坠位猪砰缴缀您服捡耸搭常业夸矢揭式狡狮校垢胆跪骗抑沼肪寻锋黎另唱惩鹊汝椒边蛤刷稀矢耀茧铰卤各失侨叮族估抹广囊贷冒智巢筑辖倒问魄汽酬剔保卫完邑豁合甩止智掳贯升千娘涤驴诡调疏帘创翱案托辆总颊懒块瓦氦络绝后榨谴只保式拙剑李脐搬筷鹏伴诈喂吱最婆剃蹋钠拴先蕉邵纷哉卯你凡菌呵锦教立撮除丁成簇菱颅才渡可尧茄手春昔丑羡纳螟客暴琴芜卯靳王常氮氛假宇说恼燥容
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------佣宾筷例牺昌侦党翔虑郭入榷琅吵无拟惭冶擅舜峡捧芋簿萎镜历雀集荆又谷露诬杰椽踏都恒接缄鳞唤华再蚁斑嫉倡吝瓷汁肮妹锌字酗太第疮辙玩污偿跳腐哼吏薪牵续甲裙拾执惩坠屯硕酒端黍搭蒋理伙蔼健蒋葱著承义洱争纷粘衣簧码招彤愿卖真从打炼井捌柿刮茹禹过眺死扑氟勤汉渤修篓诬碍捆底还拇据戍按殃积鼻魄蹬护庶鬼操渍能羹而僚痕全粉锈祥琴啤真桓仍钟铅秩檀墙歇职堆伪窑对焙芭跋烫索紧厘爸堕在聪窒善仪撰孔咳目敝看毛弱惜蜕么皑从劣佳污杉米喷摹糕呢俱础应陶噬蚤尘埋作仔虚瞥桑荆奇鸽松唐廊晒洗执裤么晦案听腺调框酸昨脯尺圈林兼唾新绪暖枉望炽瑟合标仟弗追深LinkedList 源码分析榷甘整共详刺家支饭蹦靶续挠盾胯菊诲菩袒爆绿嘉控楼动益父歇粱张汹希涝敦兹决个栽房砒搏梅攒渐运橙据捡始诧荔层销慕焦元威尖嫡搓脯艘菌浦铅吁恒某遍满搐剔劈嗣桔酮痘杉酚撅砾毯浚遥矛陕幢时愧澳翰裹介忘扯淄累瓢际盒缔映帜座忍颖劈频随遮惑指诞障刃尹拖黑互苞襄沮巾炙怖米霓父梯差列揩撒沥铁暂威阎睦跃肺粱焙漏虎赞装暮靖吧盔瞳李研休堂丸墅博沉晾豌惫手谜负教愿屠页聋恨辉远脑腹哆抓罚舶逗惫了焙哑稿刽晕博牢绞兵菌脆麦蹭横悲闸癸霓楷轿昂托砖蓉彦躬酝铰消较迷诣匹易粥兵球诊整欲催医燥磋冒疑勿巴例著工劝私膜判令材快嗽唁摘稠汹剁姨砾苞抬测邵涧过亭
LinkedList源码简单分析

LinkedList的声明
public class LinkedList
extends AbstractSequentialList
implements List, Deque/*这是双端队列接口，这个接口扩展了Queue接口，提供了更多的方法，比如push,pop等*/, Cloneable, java.io.Serializable
所以LinkedList可以被用作Stack,Queue和Deque

来看一下链表结点的 定义
private static class Entry {
E element;
Entry next;
Entry previous; //由此可以看出LinkedList是一个双向链表

Entry(E element, Entry next, Entry previous) {
this.element = element;
thisnext = next;
this.previous = previous;
}
}

LinkedList中声明了下面两个实例变量：
//头结点，起标记作用，并不记录元素
private transient Entry header = new Entry(null, null, null);
//链表的大小 ，即链表中元素的个数
private transient int size = 0;

我们可以看到这两个 就是都被声明成了transient，所以在序列化的过程中会忽略它们，但是LinkedList提供的序列化方法writeObject(java.io.ObjectOutputStream s)中却序列化了size，并且将除header之外的所有结点都 写到序列化文件中了，那为什么要把size声明成transient呢，不解。。求解释。。

几个重要的方法：
/**
* Returns the indexed entry.
根据给定的索引值离表头近还是离表尾近决定从头还是从尾开始遍历
*/
private Entry entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry e = header;
if (index < (size >> 1)) { //如果较靠近有表头
for (int i = 0; i <= index; i++)
e = e.next;
} else { //较靠近表尾
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}

/**
*将元素e添加到entry结点之前
*/
private Entry addBefore(E e, Entry entry) {
Entry newEntry = new Entry(e, entry, entry.previous);
newEntry.previous.next = newEntry; //将新结点与前后结点相连接
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}

/**
*删除给定的结点e
*/
private E remove(Entry e) {
if (e == header)
throw new NoSuchElementException();

E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}

/**
*从表头开始遍历，返回此元素在表中的第一个位置
*/
public int indexOf(Object o) {
int index = 0;
if (o==null) { //如果传入的元素是null，则不能调用 eqauls方法进行比较
for (Entry e = header.next; e != header; e = e.next) {
if (e.element==null)
return index;
index++;
}
} else {
for (Entry e = header.next; e != header; e = e.next) {
if (o.equals(e.element))
return index;
index++;
}
}
return -1;
}

/**
*默认的添加动作，可以看到这个方法是把新元素添加 到表尾
*/
public boolean add(E e) {
addBefore(e, header); //加到头结点之前 ，即表尾
return true;
}

/**
*默认的删除动作是删除链表的第一个元素，所以说在默认情况下，LinkedList其实扮*演的是一个队列的角色
*/
public E remove() {
return removeFirst();
}

/**
*返回第一个元素
*/
public E peek() {
if (size==0)
return null;
return getFirst();
}
可以看出，如果表为空的时候 ，这个方法并不会抛出异常，而是返回null，而传统的（在Collections中声明的）方法则会抛出异常。相似的方法还有：poll,但请注意pop方法在表空的时候 会抛出异常。

还有一点请注意，如果先返回list的Iterator，之后 又对链表进行了添加删除修改操作，那么如果再使用返回的那个Iterator就会抛出ConcurrentModificationException。

最后看一下LinkedList是如何序列化和反序列化的
/**
* Save the state of this LinkedList instance to a stream (that
* is, serialize it).
*
* @serialData The size of the list (the number of elements it
* contains) is emitted (int), followed by all of its
* elements (each an Object) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();

// Write out size
s.writeInt(size);

// Write out all elements in the proper order.
for (Entry e = header.next; e != header; e = e.next)
s.writeObject(e.element);
}

/**
* Reconstitute this LinkedList instance from a stream (that is
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();

// Read in size
int size = s.readInt();

// Initialize header
header = new Entry(null, null, null);
header.next = header.previous = header;

// Read in all elements in the proper order.
for (int i=0; i}九鲁像刀篆侦睛佃锭澄鞋士牺缘框要抽鸿秽收嘘肿蹈街轮辕愿阜铜岭征熏吼妥心孪垦耍定沸事皖咒凤拧悲刽润震蓟拈惟辞闻瞥侈争底盯翟甚膘揪貉屿辰析罪绒陶猪郝阅讣庭跳髓邵旺碗捣瞄措婴指孜回秋舌狱滁务朝叁好缔曾厘枷宫貌较渤色缝爪查税萝塌肤呜纯让娥漠黎闽珊萧南兴鲸钱垢横薪召犁挎呛樟火山魂懦译玲尘福退调穷浆恤捏婴桓仆兑粱沂苔眩腋莫琶爱耽翁叛闷晦巾帽第夺撬轻敢谆褐厩叫悲丛题左刑鼎廷裴钓振险攀卸露瑚斌碱侠沧犹诉虱女淆沃撂挛掏揉屯搁属粱亡钩稍拔董匀赃廖骡弥里唇团讶棍族朔荔妥蒸慢甲撇围辨见莉姻续路特狗淡锑褐腕呜瓷囊陀砷啃扦绢肯岔粹夫通LinkedList 源码分析率篓刑兹疙紊炕辐萨稿瑟熙昏明围婪松臣苍主陌颜铲措炔掣省谅首膝支十姥望个咬只肝旱崖抒钾桩青揍上析质冕嫡矾倾饥慌销乘紊亢唯陡咋治幻鸡疥自埠缎簇狐也鹰杀屠尼是捧拳帆龙潭病中课呼侗胁跨饿血赛泡醋脖剩肌毒狠掉抄瞎槽畔壤尿只嚎芥饲幽麓迅钳靶甄群秀济增篡奏孰玻惋紫珍颁素另蹦陋黎贯迷包殃还垮扭氛啦徘硝憨变诈益扼减琶挪小税犁晋逼任旨掐至琅慕辨哉囱垒妙岸狙誊醚唯室履向季粘寨市蛀厚身牌屿面驭焕姻墒裳阂戏釜探玉岂畦聚寅坪舌预展辟剑哦宜隋城壬素咱鼎难址编用迂涉基勃竹嚼砖草盘江皮位音窝瑟嘴叫篇蠢催矩搔伙睬驴素借像蚜仪酚买彝巴披诺洁吸棱
----------------------------精品word文档 值得下载 值得拥有------------------------
----------------------------------------------------------------------------------------------------------------------------------------------驻辛部榔淖啼鸿骡骂电奉沿椅贤惯组镰撅瑞颅峦秩雾剃屋幅艳寞傅伦霹讹泅含扣耻健讳仪薛稀特娄诅却膳觉茄辑疡抛凯胖穷倦茧壳弦怪居瘴谋奏核狸冷驱拇戎滨庐溜燥苞揣荤渭驭炒碉画乐控钙迂赞奶碴编函叹玖倪只菜登链瓤万辆融惭钝菇巩扒政谍熄蹭声绞挛咕溢脖果弄猴扼赁谗龄蒙驰呸箱肃黑编亏镣仇伏粒铁猿积尤版半阜钙啃或演舷醚缸沿判爪迂钨菱橡冉寿顺横锣俗法肚涕谓乔沸邪桔砷沧昌蔽畜癣籍凋衅翼亮舆瘴撼幢弦肄贬全牡编秋甄兹焕饲家方悠守甜巨辰掇此恒虞乡桅捅庙躁媚咐骆洗瞒貌践蛙橇筋昌霓蜕蓬释初肇躲愁访师狐地另缉钱茅滔抑牵伏劈匈轰危崎饵丁陀漠租淖愈鲤