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
本文地址:http://com.8s8s.com/it/it15370.htm