不想说话,自闭中..

数据结构之链表

前言

链表与之前所讲的数据结构有一些不同。
栈与队列是申请一段连续的空间,然后按顺序来存储数据;
链表是一种物理上非连续、非顺序的存储结构,数据元素之间的顺序是通过每个元素的指针来关联的。

链表结构

链表的每一个节点都包含两部分信息:元素数据本身和指向下一个元素地址的指针。
这里写图片描述

链表分为两种类型:单向链表和双向链表。我们平时所说的链表即为单向链表。双向链表,顾名思义,指向两个方向,即它拥有指向上一个节点和指向下一个节点的两个指针。

链表的操作

插入操作

插入操作分为三种情况,分别是头插入、尾插入、中间插入。

头插入

实际上是增加新的节点的方法,然后把新增加的节点的指针指向原来头指针指向的元素,再把头指针指针新增的节点。

这里写图片描述

尾插入

尾插入的操作,也是增加一个指针为空的节点,然后把原尾指针指向节点的指针指向新增加的节点,最后把尾指针指向新增加的节点即可。

这里写图片描述

中间插入

中间插入元素稍微复杂一些。首先增加一个节点,然后把新增加的节点的指针指向插入位置的后一个位置的节点,把插入位置的前一个节点的指针指向新增加的节点即可。

这里写图片描述

删除操作

删除操作也分为三种情况,分别是头删除、尾删除、中间删除。

头删除

删除头元素时,先把头指针指向下一个节点,然后把原头节点的指针置空。

这里写图片描述

尾删除

首先找到链表中倒数第二个元素,然后把尾指针指向这个元素,接着把原倒数第二个元素的尾指针置空。

这里写图片描述

中间删除

首先把要删除的节点的之前一个节点的指针指向要删除的节点的下一个节点,接着把要删除节点的指针置空。

这里写图片描述

代码实现

节点部分代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
* 链结点,相当于是车厢
*/
public class Node {
//数据域
public long data;
//指针域
public Node next;

public Node(long value) {
this.data = value;
}

/**
* 显示方法
*/
public void display() {
System.out.print(data + " ");
}
}

链表代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
* 链表,相当于火车
*/
public class LinkList {
//头结点
private Node first;

public LinkList() {
first = null;
}

/**
* 插入一个结点,在头结点后进行插入
*/
public void insertFirst(long value) {
Node node = new Node(value);
node.next = first;
first = node;
}

/**
* 删除一个结点,在头结点后进行删除
*/
public Node deleteFirst() {
Node tmp = first;
first = tmp.next;
return tmp;
}

/**
* 显示方法
*/
public void display() {
Node current = first;
while(current != null) {
current.display();
current = current.next;
}
System.out.println();
}

/**
* 查找方法
*/
public Node find(long value) {
Node current = first;
while(current.data != value) {
if(current.next == null) {
return null;
}
current = current.next;
}
return current;
}

/**
* 删除方法,根据数据域来进行删除
*/
public Node delete(long value) {
Node current = first;
Node previous = first;
while(current.data != value) {
if(current.next == null) {
return null;
}
previous = current;
current = current.next;
}

if(current == first) {
first = first.next;
} else {
previous.next = current.next;
}
return current;

}
}

测试类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class TestLinkList {
public static void main(String[] args) {
LinkList linkList = new LinkList();
linkList.insertFirst(34);
linkList.insertFirst(23);
linkList.insertFirst(12);
linkList.insertFirst(0);
linkList.insertFirst(-1);

// linkList.display();
//
// linkList.deleteFirst();
// linkList.display();
//
// Node node = linkList.find(23);
// node.display();

Node node1 = linkList.delete(0);
node1.display();
System.out.println();
linkList.display();
}
}