分享
 
 
 

源码分析:LinkedList和Java中的指针操作

王朝java/jsp·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

LinkedList类似C语言的双向链表,但是java中没有指针如何实现呢,看完LinkedList

你将对java中的引用类型有更深入的理解。LindedList的声明如下:

public class LinkedList extends AbstractSequentialList implements List, Cloneable, java.io.Serializable

有关AbstractSequentialList:http://blog.csdn.net/treeroot/archive/2004/09/18/108696.aspx

有关List: http://blog.csdn.net/treeroot/archive/2004/09/14/104638.aspx

有关Cloneable:http://blog.csdn.net/treeroot/archive/2004/09/07/96936.aspx

下面分析一下这个链表的实现,这里只重点分析某些方法。

private transient Entry header = new Entry(null, null, null);

private transient int size = 0;

public LinkedList() {

header.next = header.previous = header;

}

header相当于C中的头指针,而且这个头指针不是链表的元素,有关Entry将在下面介绍。

public LinkedList(Collection c) {

this();

addAll(c);

}

public Object getFirst() {

if (size==0)

throw new NoSuchElementException();

return header.next.element;

}

头指针的下一个元素就是第一个元素

public Object getLast() {

if (size==0)

throw new NoSuchElementException();

return header.previous.element;

}

头指针的前一个当然就是最后一个了

public Object removeFirst() {

Object first = header.next.element;

remove(header.next);

return first;

}

public Object removeLast() {

Object last = header.previous.element;

remove(header.previous);

return last;

}

public void addFirst(Object o) {

addBefore(o, header.next);

}

public void addLast(Object o) {

addBefore(o, header);

}

这个方法在链表末尾插入新的元素,功能和add方法一样,这个方法完全是为了对称性(因为有addFirst)

public boolean contains(Object o) {

return indexOf(o) != -1;

}

public int size() {

return size;

}

public boolean add(Object o) {

addBefore(o, header);

return true;

}

public boolean remove(Object o) {

if (o==null) {

for (Entry e = header.next; e != header; e = e.next) {

if (e.element==null) {

remove(e);

return true;

}

}

} else {

for (Entry e = header.next; e != header; e = e.next) {

if (o.equals(e.element)) {

remove(e);

return true;

}

}

}

return false;

}

用过C的人应该感到很熟悉了,这里就是通过指针后移来查找相同的元素,注意这里最多只删除一个

元素,符合List接口中的说明。

public boolean addAll(Collection c) {

return addAll(size, c);

}

public boolean addAll(int index, Collection c) {

int numNew = c.size();

if (numNew==0)

return false;

modCount++;

Entry successor = (index==size ? header : entry(index));

Entry predecessor = successor.previous;

Iterator it = c.iterator();

for (int i=0; i

Entry e = new Entry(it.next(), successor, predecessor);

predecessor.next = e;

predecessor = e;

}

successor.previous = predecessor;

size += numNew;

return true;

}

这里又看到熟悉的面孔了,在数据结构里面的链表中插入元素不就是这样吗?

successor代表后一个指针,就是说插入的数据在他的前面,predecessor代表前一个指针,也就是要插入数据之前的指针。如果对数据结构比较了解的话,应该比较容易理解,这里我可以把代码改一下,但是不能算是优化:

for (int i=0; i

Entry e = new Entry(it.next(), null, predecessor);

predecessor.next = e;

predecessor = e;

}

predecessor.next = successor;

successor.previous = predecessor;

这样修改和原来是一样的,如果Entry有一个这样的构造函数Entry(Object element,Entry previous)那就

好了,那就可以用修改后的代码优化了(并没有多大的价值)。如果可以看明白为什么可以这样修改,那就完全理解了,如果对这种数据结构不熟悉的话,可以画一个链表,然后按代码执行修改你的链表,这个方法很有效的。

public void clear() {

modCount++;

header.next = header.previous = header;

size = 0;

}

public Object get(int index) {

return entry(index).element;

}

public Object set(int index, Object element) {

Entry e = entry(index);

Object oldVal = e.element;

e.element = element;

return oldVal;

}

public void add(int index, Object element) {

addBefore(element, (index==size ? header : entry(index)));

}

public Object remove(int index) {

Entry e = entry(index);

remove(e);

return e.element;

}

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;

}

这个方法返回一个Entry,这里注意注意当index为0时返回的是head.next,不可能返回head。因为index>=0而且

所以循环语句至少要执行一次。这里指针移动进行了优化,因为是一个双向链表,可以朝不同方向移动,size>>2相当于size=size/2

public int indexOf(Object o) {

int index = 0;

if (o==null) {

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;

}

这里唯一注意的就是index++的位置

public int lastIndexOf(Object o) {

int index = size;

if (o==null) {

for (Entry e = header.previous; e != header; e = e.previous) {

index--;

if (e.element==null)

return index;

}

} else {

for (Entry e = header.previous; e != header; e = e.previous) {

index--;

if (o.equals(e.element))

return index;

}

}

return -1;

}

注意index--的位置

public ListIterator listIterator(int index) {

return new ListItr(index);

}

以下是一个私有内部类

private class ListItr implements ListIterator {

private Entry lastReturned = header;

private Entry next;

//调用next()方法的节点

private int nextIndex;

private int expectedModCount = modCount;

ListItr(int index) {

if (index < 0 || index > size)

throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

if (index < (size >> 1)) {

next = header.next;

for (nextIndex=0; nextIndex

next = next.next;

} else {

next = header;

for (nextIndex=size; nextIndex>index; nextIndex--)

next = next.previous;

}

}

public boolean hasNext() {

return nextIndex != size;

}

public Object next() {

checkForComodification();

if (nextIndex == size)

throw new NoSuchElementException();

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.element;

}

public boolean hasPrevious() {

return nextIndex != 0;

}

public Object previous() {

if (nextIndex == 0)

throw new NoSuchElementException();

lastReturned = next = next.previous;

nextIndex--;

checkForComodification();

return lastReturned.element;

}

public int nextIndex() {

return nextIndex;

}

public int previousIndex() {

return nextIndex-1;

}

public void remove() {

checkForComodification();

try {

LinkedList.this.remove(lastReturned);

} catch (NoSuchElementException e) {

throw new IllegalStateException();

}

if (next==lastReturned)//这里表示删除的是调用previous()返回的元素。

next = lastReturned.next;//next被删除,所以next要后移,索引不变。

else

nextIndex--; //删除的是next.previous,所以索引要减1。

lastReturned = header;//这里很重要:1.释放资源。2.不允许连续调用remove。

expectedModCount++;

}

public void set(Object o) {

if (lastReturned == header)

throw new IllegalStateException();

checkForComodification();

lastReturned.element = o;

}

public void add(Object o) {

checkForComodification();

lastReturned = header;

addBefore(o, next);

nextIndex++;

expectedModCount++;

}

final void checkForComodification() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

}

}

以下是Entry的定义:

private static class Entry {

Object element;

Entry next;

Entry previous;

Entry(Object element, Entry next, Entry previous) {

this.element = element;

this.next = next;

this.previous = previous;

}

}

很简单,就是一个双向链表的接点,只有一个构造函数而已,没有其他方法。这里的next和previous不就是一个引用吗?其实不就是一个C里面的指针吗!不过C语言不会处理空指针,直接让操作系统处理了,Java确实抛出一个系统异常NullPointerException,根本不给他破坏系统的机会。

private Entry addBefore(Object o, Entry e) {

Entry newEntry = new Entry(o, e, e.previous);

newEntry.previous.next = newEntry;

newEntry.next.previous = newEntry;

size++;

modCount++;

return newEntry;

}

private void remove(Entry e) {

if (e == header)

throw new NoSuchElementException();

e.previous.next = e.next;

e.next.previous = e.previous;

size--;

modCount++;

}

public Object clone() {

LinkedList clone = null;

try {

clone = (LinkedList)super.clone();

} catch (CloneNotSupportedException e) {

throw new InternalError();

}

// Put clone into "virgin" state

clone.header = new Entry(null, null, null);

clone.header.next = clone.header.previous = clone.header;

clone.size = 0;

clone.modCount = 0;

// Initialize clone with our elements

for (Entry e = header.next; e != header; e = e.next)

clone.add(e.element);

return clone;

}

public Object[] toArray() {

Object[] result = new Object[size];

int i = 0;

for (Entry e = header.next; e != header; e = e.next)

result[i++] = e.element;

return result;

}

}

public Object[] toArray(Object a[]) {

if (a.length < size)

a = (Object[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);

int i = 0;

for (Entry e = header.next; e != header; e = e.next)

a[i++] = e.element;

if (a.length > size)

a[size] = null;

return a;

}

private static final long serialVersionUID = 876323262645176354L;

private synchronized 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);

}

private synchronized 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

add(s.readObject());

}

这里和ArrayList有一个区别就是size被声明为 transient的,因为这里调用的是add方法,这样

size会自动增加,而在ArrayList是直接给数组赋值(效率更高)。

这里比较一下ArrayList和LinkedList:

1.ArrayList是基于数组,LinkedList基于链表实现。

2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。

3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。

4.查找操作indexOf,lastIndexOf,contains等,两者差不多。

这里只是理论上分析,事实上也不一定,比如ArrayList在末尾插入和删除数据就不设计到数据移动,不过还是

有这么个建议:随机访问比较多的话一定要用ArrayList而不是LinkedList,如果需要频繁的插入和删除应该

考虑用LinkedList来提高性能。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有