表-List, ArrayList, LinkedList 实现学习笔记
程序员文章站
2022-05-31 08:22:41
...
1. 表的java实现
咱们程序员入门C语言一开始就介绍的
1.1 数组实现
主要就是查询快,删除,插入 时间复杂度O(N),比如删除第一个元素,那么后面的元素就要整体向前移动,而查询就比较简单了时间复杂度O(1)
1.2 链表实现 : 插入删除快,查询较复杂
2. ArrayList 数组实现
预先定义的基本属性
// 默认的容量 private static final int DEFAULT_CAPACITY = 10; // 长度 private int size; // 元素 private E [] items;用数组来保存list里面的元素。
2.1 capacity 容量
capacity 是什么样一个概念:感觉很直观的理解就是一个预先估计的容量,为后面新来的元素有了一个准备,不必每次新添加元素这边都要做扩容处理影响效率(所以ArrayList在空间上这部分是浪费的)。
public void ensureCapacity(int newCapacity){ if ( newCapacity < size) { return; } E [] old = items; items = (E []) new Objects [newCapacity]; for (int i = 0; i < size(); i++) { items [i] = old[i]; } }
2.2 add
public void add (E ele) { add(size(), ele) ; } public void add (int index, E ele) { if ( items.length == size()) { // 扩容机制 jdk 1.5 倍 + 1 ensureCapacity (size() * 2 + 1); } // 插入点,向后移动,后面有位置 for ( int i = size; i > index; i-- ) { items [i] = items [i - 1]; } items[index] = ele; }
2.3 remove
public E remove (int index) { E removeItem = items[index]; // 向前缩进 for ( int i = index; i < size() - 1; i++) { items [i] = items[i - 1]; } size --; return removeItem; }
3.LinkedList 实现
3.1 Node 节点
LinkedList 是双链表来实现的,由节点来构成的,因此我们同时定义了一个节点类Node(内部嵌套)
public class Node<E> { public E data; public Node<E> prev; public Node<E> next; public Node(E data, Node<E> prev, Node<E> next){ this.data = data; this.prev = prev; this.next = next; } }
初始化
public MyLinkedList () { clear(); } public void clear () { beginMarker = new Node<E>(null, null, null); endMarker= new Node<E>(null, beginMarker, null); beginMarker.next = endMarker; size = 0; }
3.2 Node 插入点,删除点
由于链表添加删除,与操作位置上的节点有关系因此操作前要获取位置上的操作节点
public Node<E> getNode (int index){ return getNode(index, 0, size()-1); } public Node<E> getNode (int index, int lower, int upper){ Node<E> p; if(index < lower || index > upper) { throw new IndexOutOfBoundsException(); } // 判断从前开始还是从后开始,减少循环次数 if (index < size()/2) { p = beginMarker; for (int i = 0; i < index; i++){ p = p.next; } }else { p = endMarker; for (int i = size(); i > index; i--) { p = p.prev; } } return p; }
3.3 Node 新增
public void add(int index, E ele){ addBefore( getNode(index, 0, size()), ele); } public void addBefore(Node<E> p, E e){ Node<E> newNode = new Node<E>(e, p.prev, p); p.prev.next = newNode; p.prev = newNode; size ++; }
3.3 Node 删除
public void romove(int index){ romove(getNode(index, 0, size()-1)); } public void romove(Node<E> p){ p.prev.next = p.next; p.next.prev = p.prev; size--; }
4.总结
ArrayList,LinkedList都是非同步的。这点区别于Vector