算法与数据结构回顾--线性表（1）

既然叫回顾，当然不能仅仅介绍基础，这里主要解析java的线性表--List、map、set。

ArrayList

ArrayList的数据结构是由数组实现的，数组的初始化需要定义大小。所以使用ArrayList之前要估计List的大小。太小虽然不会出现溢出的异常，但是因为需要扩容所以浪费了很多资源，太大又浪费空间。

ArrayList初始化源代码：

    public ArrayList(int initialCapacity) {
	super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
	this.elementData = new Object[initialCapacity];
    }

    public ArrayList() {
	this(10);
    }

 扩容代码：

    public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }

可见，ArrayList在容量不足时，就会通过复制数组的方式扩容。这种做法比较浪费资源。

这里的modCount是用来检测iterator操作不一致的，比如在迭代List的同时又修改List，这就是并发问题了，是不允许的。所以要及时抛出ConcurrentModifacationException.如下：

	public static void main(String[] args){
		
		List<String> strings = new ArrayList<String>();
		for(int i=0;i<10;i++){
			strings.add(String.valueOf(i));
		}
		Iterator it = strings.iterator();
		for(int i=0;i < strings.size();i++){
			System.out.println(it.next());
			strings.remove(i);
		}
	}

  检索代码：

    public E get(int index) {
	RangeCheck(index);

	return (E) elementData[index];
    }

 可见检索的效率是非常高的，时间复杂度只为O(1)。但同时发现这个方法不是线程安全的，但同时相对于线程安全的方法，效率高一些。如果先要将ArrayList转换为线程安全的可以使用Collections.synchronizedCollection(strings)。 这个方法是用代理模式，将方法加锁。

删除代码：

    public E remove(int index) {
	RangeCheck(index);

	modCount++;
	E oldValue = (E) elementData[index];

	int numMoved = size - index - 1;
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	elementData[--size] = null; // Let gc do its work

	return oldValue;
    }

 添加代码和这个相差不多，这里就不多说了。这里面的删除时然被删除的元素后面的元素依次向左移动一位。所以时间复杂度是O(n)。同样线程不安全，不建议在删除多的操作上使用ArrayList。

LinkedList：

初始化：

	Entry(E element, Entry<E> next, Entry<E> previous) {
	    this.element = element;
	    this.next = next;
	    this.previous = previous;
	}
    public LinkedList() {
        header.next = header.previous = header;
    }

 从这个代码开来，LinkedList是一个环形双向链表。它有2个头指针一个指向一个指向链表的头部一个指向链表的尾部，这样它就可以找检索路径最短的那一段开始检索。代码如下：

    private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> 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;
    }

 这里使用了nb的位运算，它比正常的除以2运算效率要高。但是检索需要的时间是O（n）.

添加：

    public void add(int index, E element) {
        addBefore(element, (index==size ? header : entry(index)));
    }

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

    private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> 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;
    }

 

添加的时间复杂度是O（n).

删除：

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

 

这里是根据value是不是null来分别区分，如果为null，就删除第一个为null的。如果不为null删除第一个相同（用equal是判断）的元素。