JDK源码-LinkedList源码

栏目：php教程时间：2015-02-06 09:11:02

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  
      
    
  
            ------分隔线----------------------------