java需要关注的知识点---LinkedList

LinkedList是采用双向链表来存储数据：

LinkedList允许插入null的值
双向链表的结构图：



LinkedList的构造函数：

  public LinkedList() {
        header.next = header.previous = header;
    }

LinkedList在构造函数中初始化双向链表的表头header，指定header的上一个和下一个都是自己。
LinkedList的add方法：

 public boolean add(E e) {
	addBefore(e, header);
        return true;
    }

在进行插入元素的时候，传入插入元素和header.
LinkedList的addBefore方法：

private Entry<E> addBefore(E e, Entry<E> entry) {
	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	size++;
	modCount++;
	return newEntry;
    }

LinkedList插入元素的过程（addBefore方法执行操作的图示）：
刚刚开始：
空head:



插入元素第一个元素e:



插入第二个元素e2:
指针指向：



删除已经失效的指针效果图：



插入第三个元素e3:

指针指向：





删除已经失效的指针效果图：





示图中，的2X1表示的是，指针指向e2，不再指向e,所以该指向不存在。

LinkedList 的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;
    }

删除前：





删除操作：







程序最后设置e.next,e.previous,e.element为null,虚拟机会回收该快 内存。

LinkedList的addFirst方法（在head之后插入元素）。

 public void addFirst(E e) {
	addBefore(e, header.next);
    }

图示：
1：



2：插入后指针效果图：



3：最后效果图：

评论

1 楼 jiasanshou 2011-11-24