单链表定义和表示
- 线性表的链式存储结构的特点是:用一组任意的存储单元存储线性表的数据元素(逻辑上相邻,物理上可以不相邻)。
- 结点:为了表示数据a(i)和其直接后继a(i+1)的逻辑关系的存储映像,它包含两个域:存储数据元素的“数据域”和存储直接后继存储位置的域“指针域”,指针域中存储的信息称为指针或链。
- 单链表:n个节点链结成一个链接即为线性表的链式存储结构。由于链表每个结点只包含一个指针域,又称线性链表或者单链表。
根据链表结点指针个数,指向和连接方式,可将链表分为单链表、循环链表、双向链表、二叉链表,十字链表等。其中单链表、循环链表和双向链表用于实现线性表的链式存储结构,其他形式多用于实现树和图等非线性结构。
单链表的基本操作和实现
单链表的计算长度和获取值域
计算链表长度
public int size() {
SingleNode<E> cur = HEAD_NODE;
int length = 0;
while (cur.next != null) {
++length;
cur = cur.next;
}
return length;
}
获取对应位置的值域
public E get(int index) {
if (index < 0) {
throw new RuntimeException("index 不能小于0");
}
int length = size();
if (index > length) {
throw new RuntimeException("链表长度为" + length + ",可选择位置0-" + (length - 1) + ";当前选择位置是:" + index);
}
SingleNode<E> cur = HEAD_NODE;
int p = 0;
while (cur.next != null && p <= index) {
cur = cur.next;
++p;
}
return cur.value;
}
单链表的插入节点
在某个链表,第n个位置,添加一个某数值e的新结点,即添加此结点到n-1和n位置之间
- 找到节点a(n-1)
- 生成一个新结点
- 将新结点值域设置为e
- 将新结点指针域指向节点a(n)
- 将a(n-1)结点指针域指向新结点
代码如下所示:
//在链表最后添加值
public void add(E e) {
SingleNode<E> cur = HEAD_NODE;
//找到最后一个结点
while (cur.next != null) {
cur = cur.next;
}
//新建结点,设置值域
SingleNode<E> node = new SingleNode<>(e);
//在最后添加新的结点
cur.next = node;
}
//在某个节点添加新数值
public void add(int index, E e) {
if (index < 0) {
throw new RuntimeException("index 不能小于0");
}
int length = size();
if (index > length) {
throw new RuntimeException("链表长度为" + length + ",可选择插入位置0-" + length + ";当前选择插入位置是:" + index);
}
int p = 0;
//HEAD_NODE 为头结点,HEAD_NODE.next 即为0号位置引用
SingleNode<E> cur = HEAD_NODE;
while (cur.next != null && p <= (index - 1)) {
++p;
cur = cur.next;
}
//新建结点,通过构造设置值域
SingleNode<E> node = new SingleNode<>(e);
node.next = cur.next;
cur.next = node;
}
单链表的删除节点
在一个链表中删除n号元素位置的结点,和插入结点差不多
- 找到a(n-1)结点
- 将a(n-1)结点指针域指向a(n)的直接后继结点
代码如下所示:
//根据下标索引删除
public void delete(int index) {
if (index < 0) {
throw new RuntimeException("index 不能小于0");
}
int length = size();
if (index > length - 1) {
throw new RuntimeException("链表长度为" + length + ",可选择删除的位置0-" + (length - 1) + ";当前选择删除的位置是:" + index);
}
int p = 0;
SingleNode<E> cur = HEAD_NODE;
//找到目标结点的前驱结点
while (cur.next != null && p <= (index - 1)) {
++p;
cur = cur.next;
}
if (cur.next != null) {
cur.next = cur.next.next;
}
}
//删除值
public void delete(E e) {
SingleNode<E> cur = HEAD_NODE;
while (cur.next != null) {
if (e.equals(cur.next.value)) {
cur.next = cur.next.next;
return;
}
cur = cur.next;
}
}
前插法创建单链表
前插法创建单链表,每次将新结点逐个插入链表头部,所以线性表(a、b、c、d、e、f、g)前插法创建,读入数据的顺序和线性表的逻辑顺序是相反的
- 创建头结点
- 创建新结点,设置值域
- 将新结点插入表头
//main函数,插入数据创建链表
public static void main(String[] args) throws Exception {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.createFront("g", "f", "e", "d", "c", "b", "a");
//linkedList.createFront1("a","b","c","d","e","f","g");
linkedList.printSelf();
}
//前插法创建单链表
public void createFront(E... values) {
for (int i = 0; i < values.length; i++) {
SingleNode<E> node = new SingleNode<>();
node.value = values[i];
node.next = HEAD_NODE.next;
HEAD_NODE.next = node;
}
}
//或者为了使用方便,可以这么写
public void createFront1(E... values) {
for (int i = values.length - 1; i >= 0; i--) {
SingleNode<E> node = new SingleNode<>();
node.value = values[i];
node.next = HEAD_NODE.next;
HEAD_NODE.next = node;
}
}
后插法创建单链表
后插法是将新结点逐个插入到链表的尾部来创建链表
- 创建一个只有头结点的空链表
- 新增一个尾指针结点r
- 将新结点插入尾结点r之后,再使r指向新的 尾结点
//main函数,创建链表
public static void main(String[] args) throws Exception {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.createLater("a", "b", "c", "d", "e", "f", "g");
linkedList.printSelf();
}
//后插法创建链表
public void createLater(E... values) {
SingleNode<E> r = HEAD_NODE;
for (int i = 0; i < values.length; i++) {
SingleNode<E> node = new SingleNode<>();
node.value = values[i];
node.next = null;
r.next = node;
r = node;
}
}
循环链表
循环链表是另外一种形式的链式存储结构。最明显的特征就是,尾结点指针域指向头结点,整个链表形成一个环。因此,从表中任一结点出发均可找到表中其他节点。如下图所示。类似的还有多重链的循环链表。
双向链表
单链表只有一个指示直接后继的指针域,因此,从某个结点出发只能顺时针向后查询其他节点,如果需要查询直接前驱,则必须从表头指针出发。为了克服单链表这种单向性的缺点,可以利用双向链表。
顾名思义,在双向链表中有两个指针域,一个指向直接后继,一个指向直接前驱,结点结构如下图所示。代码可以如下描述:
public class DoubleLinkList<T> {
private Node<T> HEAD_NODE;
public DoubleLinkList() {
this.HEAD_NODE = new Node<>();
}
//结点实体类
class Node<T>{
Node<T> prior;
Node<T> next;
T data;
}
}
和单链表类似,双向链表也可以有循环表,如下图所示:
其实能熟练掌握单链表的结构和操作,就能够很快熟悉理解双向链表。比如单链表插入一个新结点到指定结点(p)之后需要三步:1. 找到目标位置;2. 新结点的指针域指向目标结点p的直接后继;3. 目标结点p指针域指向新结点即可。双向链表中,每个结点要多出一个指针域,所以在插入和删除的时候需要多处理一个指针域,原理都是一样的,如下做了双向链表的插入和删除操作
双向链表的插入
如上图链表中有A、B、C三个结点(头结点忽略)。要在A和B之间插入新结点F(即在1号位置插入),则需要以下4步
- 找到A结点(0号位置)
- 新结点的两个指针分别指向A和B
- B的前驱结点的指针指向新结点
- A的后继的指针指向新结点
//插入链表指定位置
public void add(int position, T t) {
//计数器,记录当前位置
int index = 0;
Node<T> curNode = HEAD_NODE;
//定位到目标位置的前驱结点,头结点不计算在内
do {
//指定插入位置在当前链表中存在(逻辑上允许插入到链表最后一个结点后)
if (index == position) {
break;
}
++index;
curNode = curNode.next;
} while (curNode.next != null);
if (position == index) {
Node<T> node = new Node<>();
//指定新结点的值域和两个指针域
node.data = t;
node.prior = curNode;
node.next = curNode.next;
if (curNode.next != null) {
//当前结点如果有直接后继,将后继结点的前驱指针指向新结点
curNode.next.prior = node;
}
//当前结点后继的指针指向新结点
curNode.next = node;
return;
}
System.out.println("插入失败,指定的位置不存在");
}
双向链表的删除
理解如何添加一个结点之后,举一反三,删除就很好理解了,如下图如果要删除B结点,则需要A结点后继指针指向C,C结点的前驱指针指向A即可。
public void delete(int position) {
//计数器,记录当前位置
Node<T> curNode = HEAD_NODE;
//找到当前位置的结点
for (int i = 0; i <= position; i++) {
curNode = curNode.next;
if (curNode == null) {
break;
}
}
if (curNode == null || position < 0) {
System.out.println("删除失败,指定的位置不存在");
return;
}
if (curNode.next != null) {
curNode.next.prior = curNode.prior;
}
curNode.prior.next = curNode.next;
curNode.next = null;
curNode.prior = null;
}
链表常见操作
反转单链表
顾名思义,就是将一个单链表头结点指向尾结点,原来的直接后继变成了直接前驱,方法有很多,比如new 一个新的链表,然后插入;还可以在当前链表直接操作,下面举的例子就是在当前链表直接进行反转,代码和示意图如下所示:
//反转链表方法
public void reverseList() {
//链表第一个结点,翻转后成为尾结点,指针域为null
SingleNode<E> p = HEAD_NODE.next;
SingleNode<E> pCur = p.next;
while (pCur != null) {
p.next = pCur.next;
pCur.next = HEAD_NODE.next;
HEAD_NODE.next = pCur;
pCur = p.next;
}
}