Java 容器类一、List 列表

List 列表清单

1.ArrayList 数组列表 – 不安全

1.接口 List、RandomAccess: 可以插入空数据，也支持随机访问

2.基于动态数组 ==> 思考下如下实现种 transient 作用？

transient Object[] elementData 数组
private int size 大小

3.add()

public boolean add(E e) {
	ensureCapacityInternal(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
}
// 先做扩容校验
// 再将值放入尾部，size+1

4.add(index, e) 指定位置添加

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //复制，向后移动
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    elementData[index] = element;
    size++;
}
// 先做扩容校验
// 再进行数据复制，把index空出来插入（插入效率低）

5.扩容也是数组复制过程

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 位操作扩容2倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
// ==> ArrayList 主要消耗是数组扩容，和指定位置插入数据
// ==> 指定大小、减少指定位置插入

4.快速失败：Fail-Fast–modCount 面对并发修改快速失败

5.序列化 Serialize

ArrayList 基于动态数组，并非所有空间都被适用，故用了 transient Object[] elementData

==> 自定义序列化: 只序列化被使用的数据当对象中自定义了 writeObject 和 readObject 方法时，

JVM 会调用这两个自定义方法来实现序列化与反序列化

// 写序列化
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    //只序列化了被使用的数据
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

// 读序列化
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

2.ArrayList 和 Array

ArrayList: 动态数组链表存储对象类型不固定，为Object，如存 int 会自动装箱/拆箱成 Integer

Array: 高效，但长度无法改变只能存储相同类型对象

3.Vector 同步线程安全

1.接口 List RandomAccess, 也是一个动态数组存放数据

2.add() 使用 synchronized 进行了同步写数据，开销较大

// 添加元素 synchronized
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

3.add(index, e) 指定位置添加

public void add(int index, E element) {
    insertElementAt(element, index);
}

// 插入元素 synchronized
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

4.自定义 ArrayList

实现 ArrayList 容量底层 增删改查

boolean add(Object obj)
Object remove(int index)
Object set(int index, Object obj)
Object get(int index)

public class Node {
	private Object data;
	private Node next;
	public Node() {
		super();
	}
	public Node(Object data, Node next) {
		super();
		this.data = data;
		this.next = next;
	}
	public Object getData() {
		return data;
	}
	public void setData(Object data) {
		this.data = data;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
}

5.LinkedList 链表列表 / 链表双向队列

1.接口: List Deque

[Deque] 给定类型的元素进行线性处理 == 双向队列   
1.支持高效插入和删除容器的**头部元**   
2.能够快速地**随机访问**任一个元素

删除、插入效率高 O(1)
查询效率低 O(n/2)

2.底层基于双向链表 ==> jdk1.7/8 后取消了循环，修改为双向链表

谁能告诉我这是为啥呢? – 2020年12月8日

1.底层基于双向链表

3.add() 添加到队列尾

public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
// 每次插入都是移动指针，和 ArrayList 的拷贝数组来说效率要高上不少 
// 时间复杂度 O(1)

4.get() 查询

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
// index 离头近从头遍历，反之亦然
// 时间复杂度 O(n/2) 获取一个节点，效率低

6.自定义LinkedList

自定义考虑哪些问题呢?

==> 考虑这些问题可以更深入的理解如何设计数据结构
参考如下案例,看案例对这些问题是如何回应的,然后可翻看LinkedList源码比对下
链表的头节点是不是单独的一个节点，其值为空其指向为下一个节点；
这个头节点我们可以放数据进去吗？
尾节点是指向最后一个节点的一个节点呢.
还是尾节点只是一个地址变量这个地址变量的内容是最后一个链节的地址
又或者说头节点也是这样一个地址变量指向第一节点的物理内存

public class LinkedList2 {
	private Node head;
	private Node last;
	private int size;
	public LinkedList2(){
		head=new Node();
		last=head;
	}
	public boolean add(Object obj){
		if (head.getData()==null) {
			head.setData(obj);
		}else{
		Node newNode=new Node();
		newNode.setData(obj);
		last.setNext(newNode);
		last=newNode;
		}
		size++;
		return true;
	}
	public Object remove(int index){
		if (index==0) {
			head=head.getNext();
			return null;
		}
		Node before=head;
		for (int i = 0; i < index-1; i++) {
			before=before.getNext();
		}// 注意index;
		Node current=before.getNext();
		before.setNext(current.getNext());
		current.setNext(null);
		return current.getData();
	}
	public String toString(){
		StringBuffer sb=new StringBuffer();
		Node currentNode=head;
		sb.append("[");
		while (currentNode!=null) {
			sb.append(currentNode.getData()+" ");
			currentNode=currentNode.getNext();
		}
		sb.append("]");
		return sb.toString();
	}
}

public class Test {
	public static void main(String[] args) {
		day33.LinkedList2 ll=new day33.LinkedList2();
		ll.add("a");
		ll.add("b");
		ll.add("c");
		ll.add("d");
		ll.add("e");
		ll.add("f");
		System.out.println(ll);
	   ll.remove(2);
	   System.out.println(ll);
	}
}

SortedList 排序列表

TODO 2020年12月8日将来再研究

private Comparator<Element<E>> elementComparator;
private Element<E>[] sorted;

private int[] perm;
private int size;

private final SortHelper helper = new SortHelper();

private final Element<E> tempElement = new Element<>(null, -1);

public Element(E e, int index) {
	this.e = e;
	this.index = index;
}

参考：

文档信息

本文作者：jiushun.cheng
本文链接：https://minipa.github.io/2016/06/21/java-data/
版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）

MiniPa

Java 容器类一、List 列表

List 列表清单

1.ArrayList 数组列表 – 不安全

2.ArrayList 和 Array

3.Vector 同步线程安全

4.自定义 ArrayList

5.LinkedList 链表列表 / 链表双向队列

6.自定义LinkedList

自定义考虑哪些问题呢?

SortedList 排序列表

参考：

文档信息

Search

Table of Contents

Java 容器类 一、List 列表

List 列表清单

1.ArrayList 数组列表 – 不安全

2.ArrayList 和 Array

3.Vector 同步线程安全

4.自定义 ArrayList

5.LinkedList 链表列表 / 链表双向队列

6.自定义LinkedList

自定义考虑哪些问题呢?

SortedList 排序列表

参考：

文档信息

Search

Table of Contents

Java 容器类一、List 列表