线性表的链式存储结构——链表（超详细图解）
线性表的链式存储结构称为线性链表，简称链表；常见的链表有单链表、循环链表和双向链表。
链表的优点是数据的插入或删除都非常方便，不需要移动大量数据；缺点是设计数据结构是稍显麻烦，并且在查找数据是，无法像顺序表那样可随机读取，必须按顺序找到该数据为止。
链表是用一组任意的存储单元（可以是连续的，也可以是不连续的存储单元）来存储先线性表中的数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻。因此，必须采用附加信息表示数据元素之间的逻辑关系。存储一个数据元素的存储单元称为结点（Node），一个结点至少包含两个部分：结点（数据域，地址域）。
一、单链表的结构
1.单链表的结构
（1）单链表的定义
每个结点只有一个地址域的线性链表称为单链表（Singly Linked List），结点结构如下：
单链表结点（数据域data，后继结点地址域next）
图1 带头结点的空单链表
图2 带头结点的非空单链表
（2）两种单链表
单链表有带头结点和不带头结点两种。
图3 不带头结点的非空单链表
2.不带头结点单链表的插入操作
在不带头结点的单链表中执行插入操作，要分为两种情况。因为头指针head直接指向第一个元素节点，使得在第一个节点前插入元素和在链表的中间位置插入操作步骤有所不同。
（1）在非开始结点前插入一个新结点
如果要在非开始结点ai前插入一个新结点s，可通过以下3个步骤实现：
把插入位置定位在ai的前一个结点ai-1处，假设由变量p引用；是新结点s的指针域指向ai，即s.next=p.next；使p表示的结点ai-1的指针与指向新结点s，即p.next=s。
图4 单链表在非开始结点前插入一个新结点
（2）在开始结点前插入一个新结点
操作步骤：
s.next=head.nexthead.next=s
图5单链表在开始结点前插入一个新结点
3.带头结点单链表的插入操作
头结点的作用：是为了使第一个元素的插入和删除操作与其他元素一样。
带头结点的单链表执行插入操作，则不会向不带头结点那样麻烦，因为在任何位置插入操作都是一样的。实现步骤：
把插入位置定位在ai的前一个结点ai-1处，假设由变量p引用；是新结点s的指针域指向ai，即s.next=p.next；使p表示的结点ai-1的指针与指向新结点s，即p.next=s。
图6 带头结点单链表的插入操作
4.单链表的Java表示
（1）单链表结点类
声明单链表结点类Node
public class Node
public T data; //数据域，存储数据元素
public Node
public Node(T data, Node
this.data = data;
this.next = next;
}
public Node () { //空构造
this(null,null);
}
public String toString(){
return this.data.toString(); //返回结点数据域的描述字符串
}
}
代码说明：
成员变量声明结点构造函数结点数据域的描述字符串
（2）线性表接口
这是线性表的接口类LinearList，封装了线性表对外可以访问的方法。
public Interface LinearList
//接口方法
public T get(int i);
public void set(int i, T t);
public int insert(T t);
public int insert(int i, T t);
public T remove(int i);
public boolean contains(T key);
public int indexOf(T key);
public int size();
public void clear();
public boolean isEmpty();
public void printList();
}
（3）单链表类
声明单链表类SinglyLinkedList
public class SinglyLinkedList
public Node
public SinglyLinkedList() { //构造空单链表
head=new Node
}
//实现接口方法
public T get(int i) { … }
public void set(int i, T t) { … }
public int insert(T t) { … }
public int insert(int i, T t) { … }
public T remove(int i) { … }
public boolean contains(T key) { … }
public int indexOf(T key) { … }
public int size(){ … }
public void clear() { … }
public boolean isEmpty() { … }
public void printList() { … }
}
二、单链表的基本操作
1.尾插法创建单链表
创建只有头结点的单链表；将指向尾结点的指针指向头结点；
图7 尾插法创建单链表
3.从数组中读入数据，由数组中的数据生成一个新结点，将新结点插入表尾；
4.使尾指针指向新的表尾；
重复执行（3）~（4），直到数组中所有数据均插入链表。
代码如下：
public SinglyLinkedList(T[] values) {//构造单链表，由数组提供元素
this(); //创建只有头结点的单链表
Node
for(int i=0;i rear.next=new Node //尾插法，创建结点链接入rear结点之后 rear=rear.next; //rear指向新的尾结点 } } 由于尾指针每次都要从头开始找到要插入的位置，所以尾插法创建单链表的时间复杂度为O(n)。 2.获取值操作 public T get(int i) { //返回元素ai，若i越界，返回null int j=0; Node //遍历单链表，寻找ai for(i=0;p!=null&&j p=p.next; } //若p指向ai，返回其data值 return (i>=0&&p!=null)?p.data:null; } 3.设置值操作 public void set(int i, T t) { //设置元素ai的值，即设置其data域的值为t int j=0; Node for(i=0;p!=null&&j p=p.next; } if(i>=0&&p!=null){ p.data=t; //将ai的data域设置为t } } 4.求表长 public int size() {//返回单链表的长度 int n=0; Node p=this.head.next; while(p!=null){ n++; p=p.next; } return n; } 5.清空 //清空单链表 public void clear(){ this.head.next=null; } 6.判断表空 //判断单链表是否为空 public boolean isEmpty() { return this.head.next==null; } 7.遍历单链表 public void printList() { //遍历单链表 Node p=this.head.next; while(p!=null){ System.out.println(p.data); //输出结点的数据域 p=p.next; //指针后移一个结点 } } 8.单链表的查找 //在单链表查找首次出现的与key相等元素，返回元素位置，若不存在返回-1 public int indexOf(T key) { int i=0; Node p=this.head.next; for(;p!=null;p=p.next){ //遍历单链表 if(p.data.equals(key)){ return i; } i++; } return -1; } //判断单链表中是否包含key元素 public boolean contains(T key) { Node p=this.head.next; for(;p!=null;p=p.next){ //遍历单链表 if(p.data.equals(key)){ return true; } } return false; } 9.单链表的插入 从头结点起，顺着链表查找结点ai-1，使变量p引用ai-1;若找到结点，则创建一个数据域为t的新结点s，并使它的地址域引用结点，即s=new Node 图8 单链表的插入操作 3.使p的地址域引用新结点s，即p.next=s，最后完成插入并返回i的值。 单链表的插入-算法实现 //在顺序表的最后插入元素t，返回t序号 public int insert(T t) { return this.insert(this.size(),t); } // 在插入元素t，若插入成功，返回i，否则返回-1 public int insert(int i, T t) { int j=0; if(t==null) throw new NullPointerException("不能插入空对象！") //抛出空对象异常 Node while(p.next!=null&&j p=p.next; j++; } if(p!=null&&j==i){ //找到结点 Node p.next=s; //在p之后插入新结点 return i; //插入成功，返回i }else{ return -1; /插入失败，返回-1 } } 10.单链表的删除 从头结点起，顺着链表查找结点ai-1，使变量p引用ai-1；若存在，保存待删除结点的数据域，作为返回值用，即T old=p.next.data。 图9 单链表的删除操作 3.使p的地址域引用被删除结点的直接后继结点，即p.next=p.next.next，最后完成删除并返回old。 单链表的删除-算法实现 //删除结点 public T remove(int i) { int j=0; Node while(p.next!=null&&j p=p.next; j++; } if(p.next!=null&&j==i){ //结点存在 T old=p.next.data; //保存待删除结点的数据域 p.next=p.next.next; //删除结点，包括开始、中间和尾结点删除 return old; //返回已删除结点的数据域 }else{ return null; //i越界，返回null } } 时间复杂度：O(n) 三、循环单链表 1.基本概念 循环链表是一种首尾相接的链表。将单链表中的尾结点的next域指向head，则整个链表成为一个环，这样从链表中的任意结点出发都可找到表中其他的结点，这样的单链表称为循环单链表（Circular Singly Linked List）。 2.循环单链表的结构 空表：head.next=head 图10 带头结点的空循环单链表 非空表：rear.next=head 图11 带头结点的非空循环单链表 3.循环单链表的基本操作 带头结点的循环单链表的各种操作的实现算法与带头结点的单链表的实现算法类似，只需将相应算法中 p!=null或p.next!=null 改为 p!=head或p.next!=head 四、双向链表 1.双向链表的结构 空表：head.next==null 图12 带头结点的空双向链表 非空表： p.next.prev==p p.prev.next==p 图13 带头结点的非空双向链表 2.双向链表的结点类 public class DoubleNode public T data; //数据域，存储数据元素 public DoubleNode public DoubleNode(T data, DoubleNode this.data = data; this.prev = prev; this.next = next; } public DoubleNode () { //空构造 this(null,null,null); } public String toString(){ return this.data.toString(); //返回结点数据域的描述字符串 } } 给单链表的每个结点再增加一个指向其直接前驱结点的引用域prev，这样链表中就有两条不同方向的链，此链表称为双向链表（Doubly Linked List）。 3.双向链表的基本操作 （1）双向链表的前插操作 图14 非空双向链表的前插操作 操作步骤： s.prev=p.prev;p.prev.next=s;p.prev=s;s.next=p; 【思考】如果②和③两步操作次序颠倒，会怎样？ （2）双向链表的删除当前结点操作 图15 非空双向链表的删除结点操作 操作步骤： p.prev.next=p.next;p.next.prev=p.prev; 若p是尾结点，即p.next=null。只需完成p.prev.next=null;即可。 五、循环双链表 若双向链表尾结点的next域指向头结点，头结点的prev域指向尾结点，则构成循环双链表（Circular Doubly Linked List）， 图16 循环双向链表