提示：如有错误请留下评论，谢谢。
文章目录
前言一、表1. 关于表的一些描述2. 表的常用操作3. 简单的实现4. 数组是表的一种恰当的表现形式，通常来说有以下几个特点⚠️⚠️⚠️⚠️⚠️⚠️
二、链表1. 关于链表的一些描述2. 链表的特点以及和表的不同之处3. remove 方法4. Insert 方法插入一个元素如下图所示。5. 为了解决 3 中提到的问题，双链表诞生了，双链表与单链表不同的是，每个节点还会存储一个指向它在表中前驱节点的链。如下图所示
三、Java 中的应用1. 包含普通数据结构的部分，在Java API中称为 Collections API2. Collection 接口一些重要部分：3. Iterator 接口4. List 接口，ArrayList 类和 LinkedList 类5. 关于ListIterator 接口
总结
前言
熟练掌握数据结构是每个优秀程序员的必修课程，好的数据结构可以大大提高程序的运行效率，可见数据结构的重要性。之后将会陆续补充数据结构的知识点。 这部分将讲解什么是表，以及表在Java中的应用。
提示：以下是本篇文章正文内容，下面案例可供参考
一、表
1. 关于表的一些描述
这里将处理如 A0到 AN-1 的一般表。这个表的大小是 N，通常将大小为 0 的表称为 空表（empty list）Ai 后继是 Ai-1 , Ai-1 的前驱就是 Ai 。Ai 在表中的位置是 i+1。
2. 表的常用操作
printList, makeEmpty。find 返回某一项首次出现的位置。insert 和 remove 一般是表的某个位置插入和删除某个元素。findKth 则返回某个位置上的元素。
3. 简单的实现
int [] arr
= new int [10];
int [] newArr
= new int [arr
.length
* 2];
for (int i
= 0; i
< arr
.length
; i
++)
newArr
[i
] = arr
[i
];
arr
= newArr
;
4. 数组是表的一种恰当的表现形式，通常来说有以下几个特点⚠️⚠️⚠️⚠️⚠️⚠️
数组的实现可以使printList 以线性时间被执行，而fingKth操作则花费常数时间。插入和删除的开销却潜藏着隐藏的巨大开销。当插入或删除数据是表的第一个位置时，则需要将之后的数据都向后移动一个单位，而删除第一个元素，则需要将整个数组前移一个位置，即 O (N)，这是最坏的情况。反之如果操作都发生在表的末端那么开销就是 O（1）。所以在高端插入或删除可以选择表，但是如果是其他位置插入或删除，这种表明显不是一个好的选择。
二、链表
1. 关于链表的一些描述
为了避免插入和删除的线形开销，那么就需要保证表可以不连续存储，否则就会出现整体移动的情况。链表的一般想法如图所示：
链表由一系列节点组成，这些节点不必在内存中相连。每一个节点均含有表元素和到包含该元素后继元的节点的链（link）。我们称为 next 链。最后一个单元的 next 链引用 null。
2. 链表的特点以及和表的不同之处
使用printLins 和 find（x）的操作显然也是线性的，但常数应该比数组实现的大些。findKthe 不如数组实现的效率高；findKth(i) 花费 O(i)的时间，并以这种方式遍历链表而完成。通常来说findKth(2)，findKth(3)，findKth(…)可以通过对链表的一次扫描完成。
3. remove 方法
该方法可以通过修改一个 next 引用来实现，如下图所示，删除 A2： 显然这个效率要比数组实现的效率要高得多。如果删除最后一项有些特殊，因为必须找到指向最后节点的项，把他的next 改成 null，在经典链表中，每个节点均有指向下一节点的链，而拥有指向最后节点的链并不提供最后节点的前驱节点的任何信息。
4. Insert 方法插入一个元素如下图所示。
5. 为了解决 3 中提到的问题，双链表诞生了，双链表与单链表不同的是，每个节点还会存储一个指向它在表中前驱节点的链。如下图所示
三、Java 中的应用
1. 包含普通数据结构的部分，在Java API中称为 Collections API
2. Collection 接口一些重要部分：
public interface Collection <AnyType> extends Iterable<AnyType>
{
int size();
bollean
isEmpty()
void clear();
boolean contains(AnyType x
);
boolean add(AnyType x
);
boolean remove
(AnyType x
);
java
.util
.Iterator
<AnyType> iterator();
}
Collection 接口扩展了 Iterable接口，实现Iterable接口的那些类可以拥有增强的 for 循环，该循环施加于这些类上一观察它们所有项。
3. Iterator 接口
public interface Iterator<AnyType>
{
boolean hasNext();
AnyType
next();
void remove();
}
每次对 next 的调用都给出集合的下一项，hasNext 则用来告诉是否存在下一项
4. List 接口，ArrayList 类和 LinkedList 类
List 接口继承了 Collection 接口，因此它包含 Collection 接口的所有方法，外加其他一些方法。
public interface List<AnyType> extends Collection<AnyType>
{
AnyType
get(int idx
);
AnyType
set(int idx
, AnyType newVal
);
void add(int idx
, Anytype newVal
);
void remove(int idx
);
ListIterator
<AnyType> listIterator(int pos
);
}
List ADT 有两种流行的实现方式，
a. ArrayList 类提供了 List ADT 的一种可增长数组的实现，其优点是对 get 和 set 调用花费常数时间，缺点是对新项的插入和现有项的删除代价昂贵，除非变动是在末端执行。
b. LinkedList 类则提供了List ADT 的双链表实现，使用它的优点在于，新项的插入和现有项的删除开销比较小，前提是变动项位置已知。缺点在于它不容易作为索引，所以get的调用代价昂贵。LinkedList 中提供了一些方法以便提高操作效率：addFirst(), removeFirst(), removeLast等。
c. 对搜索而言，两个都是低效的由于ArrayList可以自动增加数组大小，如果可以提前确定数组大小，那么用ensureCapacity 可以设置一个容量足够大的数组，以避免后边动态扩展。再有，trimToSize 可以在所有 ArrayList 添加操作完成之后使用以避免浪费空间。
d. 一个例子来说明两种实现方式： 现在假设将一个表中 6，5，1，4，2中的偶数删除，那么你该怎么做？最常见的方法是构建一个包含奇数的表，然后清除原表，再把新表拷贝给原表。但是该如何再不拷贝的情况下最大效率的完成这个任务呢？显然对于ArrayList来说，不适合解决这个问题，不过LinkedList却又希望解决这个问题。 解决的第一种办法：
public static void removeEvensVer1
(List
<Integer> lst
)
{
int i
= 0;
while(i
< lst
.size())
if( lst
.get(i
)%2 == 0)
lst
.remove(i
);
else
i
++;
}
在一个ArrayList上前边提到过，remove的效率不是很高，因此该程序花费二次时间。但LinkedList暴露两个问题，首先对get调用效率不高，因此这个方法LinkedList也花费二次时间。 如果不用循环该用迭代器呢？
public static void removeEvensVer2(List
<Integer> lst
)
{
for(Integer x
: lst
)
if(x
% 2 == 0)
lst
.remove(i
);
}
初看貌似没什么问题，但是真正运行时会报错，为什么呢？ ⚠️因为当一项被删除时，由增强for循环所使用的基础迭代器是非法的。 不过上边已经接近更优的方法了，在迭代器找到一个偶数后，我们可以使用该迭代器来删除这个刚看到的值。对于LinkedList来说花费时间变为常数，但是对于 ArrayList而言，花费时间依然是二次，因为需要删除数据。
public static void removeEvensVer3
(List
<Integer> lst
)
{
Interator
<Integer> itr
= lst
.iterator();
while( itr
.hasNext() )
if (itr
.next())
itr
.remove();
}
经过计算，对于拥有400 000数据的操作中，LinkedList花费0.031s, 但是对于 ArrayList却花费了2.5分钟。可见正确的选择数据结构是多么重要。
5. 关于ListIterator 接口
Public
interface ListIterator<AnyType> extends Iterator<AnyType>
{
boolean hasPrevious();
anyType
previous();
void add(AnyType
);
void set(AnyType
);
}
总结
每一个有意义的程序都将至少使用一种这样的数据结构，而栈则在程序中总是要被间接地用到。 需要知道的知识点： 1. 什么是抽象数据类型（abstract data type, ADT）？ 2. 阐述如何有效的执行表操作 3. 栈 ADT 及其在实现递归方面的应用 4. 队列 ADT 机器在操作系统和算法设计中的应用
《数据结构与算法分析–Java 语言描述》
