单链表
顺序表与单链表区别
- 顺序表最重要的优点是存储结构与逻辑结构一一对应，这样对于随机存储元素非常有利，但是有两个主要的缺点，一是插入和删除效率低,时间复杂度都是 O(n)。 二是数组一旦创建，它的大小就是不可改变的。
链表的大小是动态的；链表的插入、删除非常高效。
单链表
链表
将逻辑上具有线性关系的数据元素按链式方式存储，就构成链表，这里的链式方式存储，其本质是指利用指针将各个数据元素链接起来。
单链表
单链表使用一个指向后继元素的指针将具有线性关系的各个节点链接起来，并且最后一个节点的后继指针为空指针。每个节点包含两个要素：
- 数据域 节点保存的数据元素（data）
- 指针域 指向后继节点的指针（next）
对于单链表的一个节点，可以简单的用Java描述：
public class Lnode {
public T data;
public Lnode next;
}
在具体的实现单链表时，有两种实现方式：一种是带头节点的单链表；另一种是不带头节点的单链表。
- 带头节点的单链表
头节点： 指向链表的第一个有效节点，头节点本身不包含有效数据，用于对链表的处理。
对于带头节点的单链表我们定义一个头指针指向链表的头节点：
Lnode head;
head 的 data 域一般不用，而 head 的 next 域指向链表的第一个有效节点，如果链表是空链表，则
head.next = null;
- 不带头节点的单链表
对于不带头节点的单链表，只需要一个指向头节点的引用变量 first 即可以对整个链表进行操作，指向头节点的引用变量也称为头指针，头指针是整个链表的入口点。头指针定义：
Lnode first;
其中 first 直接指向第一个有效节点。如果是空链表，则 first = null;
链表面向对象描述
- 链表节点类最基本的数据成员是 data 和 next 。 使用泛型方法来定义链表节点类。链表节点使用泛型，要求泛型类型 T 是必须可比较的，类型 T 要实现Comparable接口。
public class Lnode implements Comparable>{
public T data;
public Lnode next;
public Lnode(T key) {
data = key;
next = null;
}
public Lnode(T key, Lnode next) {
this.data = key;
this.next = next;
}
@Override
public boolean equals(Object o) {
Lnode node = (Lnode) o;
return data.equals(node.data);
}
@Override
public int compareTo(Lnode another) {
Comparable x;
if (data instanceof Comparable){
x = (Comparable) data;
return x.compareTo(another.data);
}
else throw new ClassCastException("类型无法比较");
}
@Override
public String toString() {
return data.toString();
}
}
- 链表类
链表类的定义实际上是链表抽象数据类型的具体实现，下面是单链表类的定义：
- 一般的单链表只需要一个头指针 first 即可以代表整个链表，但是为了链表尾部插入节点的效率更高，增加一个尾指针 last, last 始终指向链表的最后一个节点。（这里所说的指针并不是 C++ 中的指针， java 没有指针 ，这里指的是一个引用变量）
- 数据存储算法
向链表插入元素(按逻辑位置i（0,1,…,n）插入)
分为4种情况：(1).向空链表插入一个新节点； (2).在链表头节点之前插入新节点； (3).在链表中间插入新节点； (4).在链表尾部插入新节点。
前插法：链表的头指针是 first 指针 p 指向链表中间某个节点，要求将值为 x 的节点 s 插入到节点 p 之前。两种情况：（1）节点 p 就是 头节点[ s.next = first; first = s;]；(2)节点 p 是非头节点，这种情况需要循环遍历到 p 的前驱节点 q [ s.next = p; q.next = s]
向链表删除元素
分为3种情况：(1)链表是空链表； (2) 被删除节点是头节点； (3) 被删除节点是链表中间某个节点
- 查找节点
向链表有序插入节点
链表的有序插入：链表 first 现在的节点值是按照升序排列的，现在要将节点 s 插入到 first 中，使得插入节点 s 后，链表中各个节点的值任然是升序有序的。分4种情况：
（1）链表为空；(2)插入节点的值小于头节点的值；(3)插入节点的值大于尾节点的值；(4)插入节点的值处于中间位置
链表排序
插入排序：可以将一个链表分为两部分，已排序链表 s1 和未排序链表 s2，插入排序思路就是从未排序链表中取出头节点（p）, 然后将 p 按有序的方式插入到已排序链表 s1 之中。
链表转换为字符串和数组
/**
* Created by nvgtor on 2016/4/20.
* 单链表类
*/
public class MLinkList extends MAbsList implements Iterable {
//头指针和尾指针
Lnode first, last;
//指向当前节点的迭代器指针
Iterator iterator = null;
public MLinkList() {
first = last = null;
this.iterator = new LinkIterator();
}
/**
* 数据存储
*
* 1. getNode(int i) 返回i号节点的引用，内部使用
* 2. get(int i)
* 3. set(int i, T x)
* 算法时间复杂度：最坏O(n),最好O（1），平均O（n）
*/
protected Lnode getNode(int i){
if (i < 0 || i > length - 1) return null;
if (i == 0) return first;
Lnode p = first;
int j = 0;
while (p != null && j < i){
p = p.next;
j++;
}
return p;
}
@Override
public T get(int i) {
Lnode p = getNode(i);
if (p == null) return null;
else return p.data;
}
@Override
public boolean set(int i, T x) {
Lnode p = getNode(i);
if (p == null) return false;
else {
p.data = x;
return true;
}
}
/**
* 插入算法
* 1. add(int i, T x) 在链表逻辑上的i(0,1,...,n)号位置插入元素x
* 2. add(T key)
* 3.addBack(T x)
* 4.addFront(T x)
*/
@Override
public void add(int i, T x) {
Lnode p, s;
int j = i - 1;
s = new Lnode(x, null);
if (first == null || length == 0){
//向空链表插入节点s
first = s;
last = s;
} else if (j < 0){
//在头节点之前插入节点s
s.next = first;
first = s;
} else if (j >= length - 1){
//在链表尾插入节点s
last.next = s;
last = s;
} else {
//链表中间插入节点s
p = getNode(j);
s.next = p.next;
p.next = s;
}
length++;
}
//重载add(), 在链表尾部插入
public void add(T key){
add(length, key);
}
//将值为x的节点插入尾部
public void addBack(T key){
add(length, key);
}
//将值为x的节点插入头部
public void addFront(T key){
add(0, key);
}
/**
* 单链表删除i节点
* 1.remove(int i)
* 2.removeNode(int i)
* 3.remove()
* 4.removeFront()
* 5.removeBack()
*/
@Override
public T remove(int i) {
//删除i节点
Lnode p = removeNode(i);
if (p != null) return p.data;
else return null;
}
//核心算法: 删除i号节点，内部使用
protected Lnode removeNode(int i){
Lnode p, q;
if (first == null || length == 0) return null;
if (i == 0){
//删除头节点
p = first;
first = first.next;
length = length - 1;
return p;
}
if (i >= 1 && i <= length="" -1){="" 删除中间节点以及尾节点="" p="getNode(i" -="" 1);="" q="p.next;" p.next="q.next;" if="" (q="=" last)="" last="p;" 1;="" return="" q;="" }="" null;="" 删除头节点="" public="" t="" remove(){="" removenode(0).data;="" removefront(){="" 删除尾节点="" removeback(){="" removenode(length="" 1).data;="" **="" *="" 单链表查找算法="" 查找逻辑上在[begin,="" end]范围内是否存在值为="" key="" 的节点，="" 否则返回="" -1="" 1.indexof(int="" begin,="" int="" end,="" key)="" 2.search(t="" 3.contains(t="" @override="" indexof(int="" {="" 查找key="" lnode p = getNode(begin);
int i = begin;
while (p != null && i < end){
if (p.data.equals(key)) return i;
p = p.next;
i++;
}
return -1;
}
//同indexOf, 一般不用， 主要用于实现字典
public T search(T key){
Lnode p = getNode(0);
while (p != null){
if (p.data.equals(key)) return p.data;
p = p.next;
}
return null;
}
//判断链表是否包含key的节点
public boolean contains(T key){
if (indexOf(key) == -1) return false;
else return true;
}
/**
* 单链表有序插入算法
* 1.addSort(T x)
* 2.insertOrder(Lnode s)
*/
//将值为x的节点有序插入链表，调用insertOrder实现
public void addSort(T x){
Lnode s = new Lnode(x, null);
insertOrder(s);
}
//内部使用，有序插入
public void insertOrder(Lnode s){
Lnode p1, p2;
length = length + 1;
if (first == null) {
//空链表插入
first = s;
last = first;
return;
}
if (compare(s, first) < 0){
//插到头节点前
s.next = first;
first = s;
return;
}
if (compare(s, last) > 0){
//插到尾节点后
last.next = s;
last = s;
return;
}
//被插入的节点在 p1 和 p2 之间
p2 = first;
p1 = p2;
while (p2 != null){
if (compare(s, p2) > 0){
p1 = p2;
p2 = p2.next;
} else
break;
}
s.next = p2;
p1.next = s;
return;
}
/**
* 链表排序 插入排序
* 1. sort()
*/
//链表排序
public void sort(){
MLinkList s1 = new MLinkList<>();//有序链表
Lnode p;
p = this.removeNode(0);
while (p != null){
s1.addSort(p.data);
p = this.removeNode(0);
}
this.first = s1.first;
this.last = s1.last;
this.length = s1.length;
}
/**
* 单链表转换为字符串
*/
public String toString(Lnode first) {
String s;
Lnode p;
p = first;
s = "(";
while (p != null){
s = s + p.data.toString();
p = p.next;
}
s = s + ")";
return s;
}
/**
* 单链表转换为数 Object 型数组
*/
public Object[] toArray(){
Object[] a = new Object[length];
Lnode p = first;
for (int i = 0; i < length; i++){
a[i] = p.data;
p = p.next;
}
return a;
}
/**
* 单链表转换为特定类型数组
* 转换为与链表节点值类型相同的数组
*/
public E[] toArray(E[] a){
if (a.length < length){
a = (E[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), length);
int i = 0;
Object[] result = a;
Lnode x = this.first;
for (i = 0; i < length; i++){
result[i] = x.data;
x = x.next;
}
}
if (a.length > length){
a[length] = null;
}
return a;
}
@Override
public void clear() {
//删除整个链表
first = last = null;
length = 0;
}
public void removeAll(){
clear();
}
private int compare(Lnode a, Lnode b){
//比较器，内部使用
return a.compareTo(b);
}
/**
* 链表迭代器 Iterable 接口重写的方法
*
*/
@Override
public Iterator iterator() {
this.iterator = new LinkIterator();
return this.iterator;
}
//内部类 实现迭代器
private class LinkIterator implements Iterator {
private int index = 0;
private Lnode current = first;
@Override
public boolean hasNext() {
return (index != length() && current != null);
}
@Override
public T next() {
T temp = current.data;
current = current.next;
index++;
return temp;
}
public int nextIndex(){
return index++;
}
@Override
public void remove() {
}
}
}
链表迭代器
迭代器概念
迭代器 (Iterator) 是软件设计的一种模式，其一般含义是：提供一种方法处理一个容器 (Container) 对象中各个元素，而又不暴露该容器对象的内部细节。所谓容器就是容纳数据的一种数据结构。
迭代器提供一种方法依次处理容器对象中各个元素，而又无须暴露该对象的内部表示。根据对容器的特点，基本迭代器可以分为三类：
- 单向迭代器(Forward Iterator): 也称前向迭代器，这类迭代器只能沿一个方向单步处理容器数据。
- 双向迭代器 (Bidirectional Iterator): 这类迭代器可以从前、后两个方向单步处理容器数据。
- 随机迭代器 (Random Access Iterator): 这类迭代器能完成上面两类迭代器的工作，它自己独有的特性就是可以像指针那样进行算术运算，而不只是仅仅只有单步向前或向后迭代的功能。
实现一个简单的单向迭代器需要以下几个步骤：
- 对于线性表（顺序表或者链表）类需要实现 Iterable 接口，Iterable 接口只有一个方法 iterator()，这个方法返回一个 Iterator对象。
- 定义一个迭代器类，如 MyIterator 实现 Iterator 接口，重写里面的三个方法。
对于容器类的数据结构，实现了迭代器后，可以使用迭代器进行容器的遍历。
Iterator 和 Iterable
- Iterator
java提供专门的迭代器接口 Iterator ，我们可以对某个容器型数据结构实现该接口以提供标准的 java 的 java 迭代器。源码如下：
public interface Iterator{
boolean hasNext();
E next();
void remove();
}
- Iterable
java 还提供了 Iterable 接口，Iterable 接口实现的功能是“返回”一个迭代器，常用的实现该接口的子接口有： Collection
public interface Iterable{
Iterator iterator();
}
- for each
for each 语法是 java 5.0 后增加的一个循环结构，可以用来处理集合（容器）中的所有元素而不需要明确指定变量的起始值和终止值。
- Iterator 与泛型搭配
Iterator 对集合类中的任何一个实现类，都可以返回这样一个 Iterator 对象，其试用与任何一个类。
因为集合类（List 和 Set 等）可以装入的对象的类型是不确定的，从集合中取出时都是 Object 类型，用时需要进行强制转换，这样会很麻烦。之所以用泛型，就是提前告诉集合确定要装入集合的类型，这样就可以直接使用而不用进行类型转换。
- 链表类 MLinkList 迭代器的实现，代码如上。
循环链表和双链表
循环链表
将单链表最后一个节点的指针域该为存放链表头节点的地址，就使得整个链表构成一个环，又没有增加额外的存储空间，这种链表称为单循环链表（循环链表）。
循环链表与单链表的区别：
- 在建立一个循环链表时，必须使最后一个节点的指针指向表头节点，而不是像单链表那样设置为 null。此种情况还适用于在最后一个节点后面插入一个新的节点。
- 在判断是否到表尾时，通过判断该节点指针域的值是否为表头节点，当指针的值等于表头节点是，说明已经到表尾，而不是像单链表那样判断指针域值是否为 null。
- 实际使用中，为了灵活性，一般使用尾节点的指针 rear 来代表整个链表。因为用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行。
双向链表
双向链表： 双链表的每个节点具有两个指针，其中一个指向节点的前驱，另一个指向节点的后继。
- 节点定义：
public class DoubleNode { public int data; public DoubleNode prior;//前驱 public DoubleNode next;//后继 }
双链表结构具有对称性：
p.prior.next = p = p.next.prior
- 双链表插入运算
插入时仅需指出直接前驱节点 p ,而连接时则必须注意先后次序是：“先右后左”, 连接次序非常重要：
s = new DoubleNode;
s.data = e;
s.next = p.next
p.next.prior = s
p.next = s
s.prior = p
- 双链表删除运算
设要删除的节点为 p , 将其删除时不需要引入新的辅助指针变量，可以直接断开节点的链接关系，如：
p.prior.next = p.next;
p.next.prior = p.prior;
顺序表与链表的比较
顺序存储的优缺点
优点
- 方法简单，各种高级语言中都有数组，容易实现
- 无需为表示结点间的逻辑关系而增加额外的存储开销
- 顺序表具有按元素序号随机访问的特点
缺点
- 在顺序表进行插入、删除操作时，平均移动大约表中一半的元素，n 较大时，效率低下
- 需要预先分配足够大的存储空间，若预先估计过大，则可能会导致顺序表后部大量闲置；如果分配过小，则又会造成溢出。
链表优缺点
链表的优缺点恰好与顺序表相反。在实际中怎样选取存储结构，通常基于以下几点考虑：
基于存储的考虑
对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低。
基于运算的考虑
在顺序表中按序号访问 ai 的时间性能是 O(1)，而链表中按序号访问的时间性能是 O（n），插入和删除操作，当数据量较大表较长时，链表虽然也要找插入位置，但主要是比较操作，而不用移动，从这个角度看链表性能更优。
基于环境的考虑
顺序表容易实现，高级语言都有数组类型，链表基于指针，前者更简单些。