haohao

数据结构与算法(Java 实现)之线性表(二)

Markdown

因为我们的言语表达了我们的想法,而我们的想法创造了我们的生活。


本篇简单介绍一下单链表,单循环链表和双向循环链表。链表是线性表的核心内容,单链表可以很方便地构成栈和队列。

单链表节点

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
/**
* Created by HaohaoChang on 2017/9/9.
*/
public class Node {
Object data; // 数据元素
Node next; // 下一节点的对象引用
public Node(Node nextval) { // 用于头结点的构造函数
next = nextval;
}
public Node(Object obj, Node nextval) { // 用于下一节点的构造函数
data = obj;
next = nextval;
}
public Object getElement() {
return data;
}
public Node getNext() {
return next;
}
public void setElement(Object data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return data.toString();
}
}

单链表

单链表

本篇的单链表是带头结点的单链表。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
* Created by HaohaoChang on 2017/9/9.
* 单链表
* | a0 | next | --> | a1 | next | --> | a2 | next | --> ... --> | an | null |
* 时间复杂度O(n)
*/
public class SingleLinkedList implements List {
Node head; // 头指针
Node current; // 当前节点位置
int size; // 数据元素个数
public SingleLinkedList() {
head = current = new Node(null);
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public void insert(int index, Object o) throws IllegalArgumentException {
if (index < 0 || index > size) {
throw new IllegalStateException("参数错误");
}
locate(index - 1);
current.setNext(new Node(o, current.next));
size ++;
System.out.println("insert node : " + o);
}
@Override
public Object delete(int index) throws IllegalArgumentException {
if (size == 0) {
throw new IllegalArgumentException("链表已空,没有元素可以删除");
}
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("参数错误");
}
locate(index - 1);
Object o = current.next.getElement();
current.setNext(current.next.next);
size --;
System.out.println("delete node : " + o);
return o;
}
@Override
public Object getData(int index) {
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("参数错误");
}
locate(index);
return current.getElement();
}
@Override
public boolean isEmpty() {
return size == 0;
}
public void locate(int index) throws IllegalArgumentException { // 定位
if (index < -1 || index > size - 1) {
throw new IllegalArgumentException("参数错误");
}
if (index == -1) {
current = head;
return;
}
current = head.next;
int j = 0;
while (current != null && j < index) {
current = current.next;
j++;
}
}
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.insert(0, "Android");
singleLinkedList.insert(1, "iOS");
singleLinkedList.insert(2, "React Native");
singleLinkedList.insert(3, "Kotlin");
singleLinkedList.delete(0);
System.out.println(singleLinkedList.size());
}

运行输出:

1
2
3
4
5
6
insert node : Android
insert node : iOS
insert node : React Native
insert node : Kotlin
delete node : Android
3

单循环链表

单循环链表

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/**
* Created by HaohaoChang on 2017/9/22.
*/
public class SingleCirLinkedList implements List{
Node head;
Node current;
int size;
public SingleCirLinkedList() {
head = current = new Node(null);
head.setNext(head);
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public void insert(int index, Object o) throws IllegalArgumentException {
if (index < 0 || index > size) {
throw new IllegalArgumentException("参数错误");
}
locate(index - 1);
current.setNext(new Node(o, current.getNext()));
size ++;
}
@Override
public Object delete(int index) throws IllegalArgumentException {
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("参数错误");
}
locate(index - 1);
Object o = current.getNext().getElement();
System.out.println("delete : " + o);
current.setNext(current.getNext().getNext());
size --;
return o;
}
@Override
public Object getData(int index) throws IllegalArgumentException{
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("参数错误");
}
locate(index - 1);
return current.getNext().getElement();
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
if (size == 0) {
return "null";
}
StringBuilder stringBuilder = new StringBuilder();
Node p = head.getNext();
while (p != head) {
stringBuilder.append(p.getElement()).append("\n");
p = p.getNext();
}
return stringBuilder.toString();
}
/**
* index 取值范围 -1 至 size - 2 需要考虑 0 -1 这两种特殊情况
*/
private void locate(int index) throws IllegalArgumentException {
if (index < -1) {
throw new IllegalArgumentException("参数错误");
}
if (index == -1) {
current = head;
return;
}
int j = 0;
current = head.getNext();
while (current != head && j < index) {
current = current.getNext();
j++;
}
}
public static void main(String[] args) {
SingleCirLinkedList cirLinkedList = new SingleCirLinkedList();
cirLinkedList.insert(0, "Android");
cirLinkedList.insert(1, "iOS");
cirLinkedList.insert(2, "Kotlin");
System.out.println(cirLinkedList.getData(0));
System.out.println(cirLinkedList.getData(1));
System.out.println(cirLinkedList.getData(2));
cirLinkedList.delete(1);
System.out.println(cirLinkedList.toString());
}
}

运行输出:

1
2
3
4
5
6
Android
iOS
Kotlin
delete : iOS
Android
Kotlin

双向循环链表

双向循环链表节点

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
/**
* Created by HaohaoChang on 2017/9/25.
* 双向链表的节点
*/
public class DulNode {
Object element;
DulNode prior; // 直接前驱指针
DulNode next; // 直接后继指针
public DulNode() {
}
public DulNode(Object element, DulNode prior, DulNode next) {
this.element = element;
this.prior = prior;
this.next = next;
}
public Object getElement() {
return element;
}
public DulNode getPrior() {
return prior;
}
public DulNode getNext() {
return next;
}
public void setElement(Object element) {
this.element = element;
}
public void setPrior(DulNode prior) {
this.prior = prior;
}
public void setNext(DulNode next) {
this.next = next;
}
}

双向循环链表

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/**
* Created by HaohaoChang on 2017/9/25.
*/
public class CirDulLinkedList implements List {
DulNode head; // 头结点
int size;
public CirDulLinkedList() {
// 初始化头结点
head = new DulNode();
head.setPrior(head);
head.setNext(head);
head.setElement(null);
}
@Override
public int size() {
return size;
}
@Override
public void insert(int index, Object o) throws IllegalArgumentException {
if (index < 0 || index > size) {
throw new IllegalArgumentException("参数错误");
}
if (index == size) { // 特殊情况,在尾部直接添加节点
add(o);
} else {
DulNode p = search(index);
DulNode s = p.getPrior();
DulNode newNode = new DulNode(o, s, p);
s.setNext(newNode);
p.setPrior(newNode);
size++;
}
}
@Override
public Object delete(int index) throws IllegalArgumentException {
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("参数错误");
}
DulNode p = search(index);
Object o = p.getElement();
DulNode s = p.getPrior();
s.setNext(p.getNext());
p.getNext().setPrior(s);
size--;
System.out.println("CirDulLinkedList.delete : " + o);
return o;
}
@Override
public Object getData(int index) throws IllegalArgumentException {
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("参数错误");
}
return search(index).getElement();
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() throws IllegalStateException {
if (size == 0) {
throw new IllegalStateException("链表为空");
}
StringBuilder stringBuilder = new StringBuilder();
DulNode p = head.getNext();
while (p != head) {
stringBuilder.append(p.getElement()).append("\n");
p = p.getNext();
}
return stringBuilder.toString();
}
/**
* 直接在链表尾部添加节点
*/
private void add(Object o) {
DulNode rear = head.getPrior();
DulNode newNode = new DulNode(o, rear, head);
rear.setNext(newNode);
head.setPrior(newNode);
size++;
}
// 按照位置查找节点
private DulNode search(int index) throws IllegalArgumentException {
DulNode p = null;
if (index > size / 2) {
// 位于链表的后半部分,反向查询
p = head.getPrior();
for (int i = size - 1; i > index; i--) {
p = p.getPrior();
}
} else {
// 位于链表的前半部分,正向查询
p = head.getNext();
for (int i = 0; i < index; i++) {
p = p.getNext();
}
}
return p;
}
public static void main(String[] args) {
CirDulLinkedList cirDulLinkedList = new CirDulLinkedList();
cirDulLinkedList.insert(0, "Android");
cirDulLinkedList.insert(1, "iOS");
cirDulLinkedList.insert(2, "Kotlin");
cirDulLinkedList.add("ReactNative");
System.out.println(cirDulLinkedList.toString());
cirDulLinkedList.delete(2);
System.out.println(cirDulLinkedList.toString());
}
}



联系我

Wechat ID

公众号

生活不止于眼前的苟且, 还有诗和远方的田野