Java版-数据结构-链表

####概要

之前我们分别学习了解了动态数组、栈、队列,其实他们的底层都是依托静态数组来实现的、只是通过我们定义的resize方法来动态扩容解决固定容量的问题,那么我们即将学习的链表,它其实是一种真正的动态数据结构。

介绍

链表是一种最简单的动态数据结构,它能够辅助组成其它的数据结构,链表中的元素可存储在内存中的任何地方(不需要连续的内存,这一点和我们的数组具有很大的区别,数组需要连续的内存),链表中的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串接在一起

存储链表的数据的我们一般称为节点(Node),节点一般分为两部分,一部分存储我们真正的数据,而另外一部分存储的是下一个节点的引用地址。

1
2
3
4
class Node{
private E e; // 存储的真正元素
private Node next; // 存储下一个node的引用地址(指向下一个node)
}

比如现在我们将元素A、B、C三个节点添加到链表中,示意图如下:

image-20190327213801994

从图中节点A到节点B之间的箭头代表,节点A指向了节点BNodeA.next = NodeB),因为在实际业务中我们的链表长度不可能是无穷无尽的,基本上都是有限个节点,通常定义链表中的最后一个元素它的next存储的是NULL(空),换句话说,如果在链表中,一个节点的next是空(NULL)的话,那么它一定是最后一个节点(对应我们图中的C节点)。

根据我们上面介绍的链表基本结构,下面我们用代码定义一下链表的基本骨架(这里我们引入了一个虚拟的头结点,下面我们会作说明)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class LinkedList<E> {
/**
* 虚拟的头结点
*/
private Node dummyHead;
/**
* 链表中节点的个数
*/
private int size;

public LinkedList() {
// 创建一个虚拟的头结点
dummyHead = new Node();
}


// 节点定义
private class Node {
// 存储节点的元素
public E e;
// 存储下一个节点的地址
public Node next;

public Node() {

}

public Node(E e) {
this.e = e;
}

public Node(E e, Node next) {
this.e = e;
this.next = next;
}

@Override
public String toString() {
return "Node{" +
"e=" + e +
", next=" + next +
'}';
}
}
}

后面我们对链表的添加节点、删除节点以及查询节点,代码实现都会基于这个基本骨架

向链表中添加节点

思路分析:

一般我们向链表中添加节点,基本思路:找到添加节点位置的前一个节点preNode,然后再改变链表的地址引用;由于链表的第一个节点也就是头结点没有前节点,此时我们为了操作方便,为链表新增了不存储任何元素的一个虚拟的头结点dummyHead(不是必须的,对用户来讲是不可见的),其实链表中真正的第一个节点是节点AdummyHead.next),这样我们就能保证了,链表中存储元素的节点都有前一个节点。

image-20190328144225867

下面我们来看一下,如果现在有一个节点D,我们准备把它插入到节点B的位置,我们需要做哪些操作

第一步:我们首先要找到节点B的前一个节点,也就是节点A

第二步:将新节点D的指向指到节点BNodeD.next = NodeA.next),然后再将节点A的指向,指到节点DNodeA.next = NodeD),这样我们的节点就能串接起来了

image-20190330090951086

代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* 向链表中指定位置插入节点(学习使用,真正插入不会指定索引)
*
* @param index 索引的位置
* @param e 节点元素
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("不是有效的索引");
}

Node prev = dummyHead;

// 找到index位置的前一个节点
for (int i = 0; i < index; i++) {
prev = prev.next;
}

// 新建一个节点,进行挂接
Node node = new Node(e);
node.next = prev.next;
prev.next = node;

size++;
}

链表的遍历

进行链表遍历,我们需要从链表中真正的第一个元素开始,也就是dummyHead.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 获取链表中index位置的元素
*
* @param index 索引的位置
* @return 节点的元素
*/
public E get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("不是有效的索引");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}

修改链表中元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 修改链表中index位置节点的元素
*
* @param index 索引的位置
* @param e 节点的元素
*/
public void set(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("不是有效的索引");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.e = e;
}

查找链表中是否包含某元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 查找链表中是否包含元素e
*
* @param e
* @return
*/
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}

删除链表中的元素

image-20190330093907204

在链表中删除元素,与在链表中添加元素有点类似

第一步:我们首先找到删除节点位置的前一个节点,我们用prev表示,被删除的节点我们用delNode表示

第二步:改变链表的引用地址:prev.next = delNode.next(等同于,将节点在链表中删除)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 删除链表中index位置的节点
*
* @param index
*/
public void remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("不是有效的索引");
}

Node prev = dummyHead;

for (int i = 0; i < index; i++) {
prev = prev.next;
}

Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
}

完整版代码GitHub仓库地址:Java版数据结构-链表 欢迎大家【关注】和【Star

至此笔者已经为大家带来了数据结构:静态数组、动态数组、栈、数组队列、循环队列、链表;接下来,笔者还会一一的实现其它常见的数组结构,大家一起加油!

  • 静态数组
  • 动态数组
  • 数组队列
  • 循环队列
  • 链表
  • 循环链表
  • 二分搜索树
  • 优先队列
  • 线段树
  • 字典树
  • AVL
  • 红黑树
  • 哈希表
  • ….

持续更新中,欢迎大家关注公众号:小白程序之路(whiteontheroad),第一时间获取最新信息!!!


小白程序之路