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

类别:Java 点击:0 评论:0 推荐:

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