Java基础数据结构及其实现原理(一)
程序员文章站
2024-02-06 22:59:40
...
Java基础数据结构
Java类库中的基础数据结构
关注的问题:
- 实现的方式 基础的数据结构
- 是否有序 是否为空 是否重复
1, List
ArrayList的实现原理
实现原理:数组,可扩容
基本的特点:
- 查询快
- 增删慢
//无参构造 默认容量是空
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//有参构造
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
添加的实现 基本就是数组的实现方式
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
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++;
}
//主要是动态扩容的实现
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//每次扩容为原来的容量的一半
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);
}
删除的方式1. 指定元素删除2.指定坐标删除
//按照坐标删除
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
//指定元素删除
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//不检测下标直接删除
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
迭代器的使用
待补充
LinkedList的实现原理
实现原理:双向链表
LinkedList | 添加元素 | 删除元素 | 查看元素 |
---|---|---|---|
链表 | add(),set() | remove() | get() |
队列 | offer() | poll() | peek() |
栈 | push() | pop() | - |
插入方法:
public boolean add(E e) {
linkLast(e);
return true;
}
//添加新节点的方式 将新节点前驱-last 后继-null
void linkLast(E e) {
final Node<E> l = last;
//Node(Node<E> prev, E element, Node<E> next)
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
//判断链表是否有元素 有的话添加链表关系
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//添加新节点的方式 前驱null 后继first
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
//判断链表是否有元素 有的话添加关系
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
//按照下标添加
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
//element要插入的节点
//node(index)原来位置的节点
linkBefore(element, node(index));
}
//添加指定节点 在succ前面添加节点
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
//Node(Node<E> prev, E element, Node<E> next)
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
删除方法
//指定对象的删除方法
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//指定下标的删除方法
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//删除链表的操作
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
//说明是链表首位
first = next;
} else {
//链表前驱更改
//节点的前驱节点的后继指向节点的后继
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
//链表后继更改
//节点的后继节点的前驱指向节点的前驱
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
//获取index位置的元素节点
Node<E> node(int index) {
// assert isElementIndex(index);
//双向链表,当节点index比size的一半大,反向搜索;反向正向
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;
}
}
//删除头节点的操作
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
//关键
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
查找方法
//查找下标
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//查找
推荐阅读
-
Java基础数据结构及其实现原理(一)
-
Java并发编程 Synchronized及其实现原理
-
Java并发编程 Synchronized及其实现原理(转)
-
Java并发——Synchronized及其实现原理
-
聊一聊 MySQL 中的事务及其实现原理
-
Java多线程高并发进阶篇(一)-volatile实现原理剖析
-
Java基础之Collections框架Map接口实现类HashMap及其源码分析(1)
-
回顾数据结构(Java版)——写一个简单的循环队列(数组实现)
-
Java并发编程:Synchronized及其实现原理
-
夯实Java基础系列20:从IDE的实现原理聊起,谈谈那些年我们用过的Java命令