既然叫回顾,当然不能仅仅介绍基础,这里主要解析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是判断)的元素。
分享到:
相关推荐
数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与C语言 第3章 栈和队列(共150页).ppt 数据结构与算法 数据结构...
数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与C语言 第3章 栈和队列(共150页).ppt 数据结构与算法 数据结构...
01-001数据结构的概念和基本术语、抽象数据类型的表示与实现 01-002算法设计的要求、算法效率的度量 02-001线性表的类型定义 02-002线性表的顺序表示与实现、线性表的基本操作 02-003单链表的创建与操作、加工型...
数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与C语言 第3章 栈和队列(共150页).ppt 数据结构与算法 数据结构...
数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与C语言 第3章 栈和队列(共150页).ppt 数据结构与算法 数据结构...
数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与C语言 第3章 栈和队列(共150页).ppt 数据结构与算法 数据结构...
数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与C语言 第3章 栈和队列(共150页).ppt 数据结构与算法 数据结构...
数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与C语言 第3章 栈和队列(共150页).ppt 数据结构与算法 数据结构...
数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与C语言 第3章 栈和队列(共150页).ppt 数据结构与算法 数据结构...
数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与C语言 第3章 栈和队列(共150页).ppt 数据结构与算法 数据结构...
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...
道01数据结构和算法绪论. mp402_谈谈算法. mp4 西03_时间复杂度和空间复杂度.mp404_时间复杂度和空间复杂度2.mp405_时间复杂度和空间复杂度3.mp4险06线性表. mp407_线性表2. mp408_线性表3. mp4品09_ 线性表4. mp...
其中包括了线性表、栈和队列、串和数组、树和图等数据结构的操作、排序等,非常适合进阶级的...其中需要的预备知识数学中的集合、对数、递归等的回顾,还有C#语法中的接口和泛型的温习,从而更快的接受数据结构和算法。
本书在简要回顾了基本的C++程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一个...
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...
5.2 线性表数据结构 5.2.1 抽象数据类型linearList 5.2.2 抽象类linearList 5.3 数组描述 5.3.1 描述 5.3.2 变长一维数组 5.3.3 类arrayList 5.3.4 C++迭代器 5.3.5 arrayList的一个迭代器 5.4 vector的描述 5.5 在...
第 三 章栈和队列数据结构与算法计算机科学与技术学院(2021春)第2部分 线性表回顾:线性链表 和 栈1. 线性链表 – 线性表的游标实现2. 双向链表3.
本教程共分为5个部分,第一部分是C语言提高部分,第二部分为C++基础部分,第三部分为C++进阶部分,第四部分为C、C++及数据结构基础部分,第五部分为C_C++与设计模式基础,内容非常详细. 第一部分 C语言提高部分目录...