国内最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2
您当前位置：首页 > php开源 > php教程 > JDK源码-LinkedList源码

JDK源码-LinkedList源码

来源：程序员人生   发布时间：2015-02-06 09:11:02 阅读次数：2501次
1，LinkedList：
    ⑴，实现了List接口，允许null元素。LinkedList还为链表开头和结尾提供了操作，所以使用LinekedList可以用作堆栈、列队或双端队列。
    ⑵，LinkedList实现Deque接口，提供了基于队列的先进先出序列的实现。
    ⑶，所有的操作都是依照两重链表来实现的。
    ⑷，操作为非线程安全的，如果多个线程中，存在修改链表结构的操作，则必须保证线程安全。
2，LinkedList继承AbstractSequentialList实现Lise、Deque、Cloneable、Serializable接口。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    ⑴，AbstractSequentialList继承AbstractList，AbstractList属于ArrayList的父类。
    ⑵，Deque继承自Queue，定义了队列接口操作。Queue接口继承Collection接口。
 3，AbstractSequentialList类详解：
    此类提供了List接口的主要实现。
    要实现1个列表，程序猿只需要扩大此类，并提供listIterator和size方法的实现便可。对不可修改的列表，只需要实现迭代器对应的方法便可。
    该类主要方法有：get   set   add  remove  addAll  iterator  listIterator方法。
    其中，get   set   add  remove  addAll方法均是基于 iterator  listIterator方法实现。
public E remove(int index) {
try {
ListIterator<E> e = listIterator(index);
E outCast = e.next();
e.remove();
return outCast;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public E set(int index, E element) {
try {
ListIterator<E> e = listIterator(index);
E oldVal = e.next();
e.set(element);
return oldVal;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
3，LinkedList成员变量：
    ⑴，header：Entry属性的变量。Entry内部类，定义了1个链表的数据结构。
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
 
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
    ⑵，size：LinkedList元素长度。
4，第1类方法，对Entry对象的操作：
    ⑴，addBefore(E e, Entry<E> entry)：增加e元素至entry链表中。
private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);//生成新的Entry对象，Entry对象的前置指向当前entry的前置元素。
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
   插入操作可参考下图：

主要操作触及，new元素的p指向了old元素，所以下1步将old元素的next指向new元素，然后奖new元素的next的p元素指向new元素本身。基本就是单链表的删除操作而已。
 ⑵，remove：链表元素的删除
private E remove(Entry<E> 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;
}
remove操作，则是将e元素的p指向e的next，将e的next的p指向e的p。使
e的p和n都指向为null，将e元素指向为null。
5，第2类方法，构造方法。
public LinkedList()：默许构造函数，初始化链表头。
public LinkedList() {
header.next = header.previous = header;
}
public LinkedList(Collection<? extends E> c)：构造List包括c中所有元素。
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
6，单链表的基本操作：
    ⑴，add：
public boolean add(E e) {
addBefore(e, header);
return true;
}
    ⑵，remove(Object o)：移除对应元素。
public boolean remove(Object o) {
if (o==null) {
for (Entry<E> e = header.next; e != header; e = e.next) {
if (e.element==null) {
remove(e);
return true;
}
}
} else {
for (Entry<E> e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
我们可以看到如果元素为null直接用的==判断相等，否则调用对应对象的equals方法移除。
7，队列方法：
    ⑴.addFirst(E e)：在链表开头增加元素。
public void addFirst(E e) {
addBefore(e, header.next);
}
    ⑵，addLast：在链表末尾增加元素
public void addLast(E e) {
addBefore(e, header);
}
    ⑶，removeFirst：首元素出队。
public E removeLast() {
return remove(header.previous);
}
8，ListIterator：构造适用与LinkedList的迭代器。
private class ListItr implements ListIterator<E>
private Entry<E> lastReturned = header;
private Entry<E> next;
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------

上一篇 libevent学习四

下一篇 离线Web应用Manifest

分享到:
------分隔线----------------------------
为码而活
为码而活
积分：4237
15粉丝
7关注
栏目热点

程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作

声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！

粤ICP备14040726号-1   2015-2020 程序员人生 版权所有

平平安安 备案网站
关闭
程序员人生