Skip to content

Commit 47fcc4a

Browse files
author
liuchao
committed
新增双向链表
1 parent cd47f65 commit 47fcc4a

File tree

4 files changed

+254
-0
lines changed

4 files changed

+254
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33

44
## 传送门
55

6+
### [双向链表](https://github.com/chaoaiqi/study/blob/master/java/src/juejin/lc/string/DulLinkList.java)
67
### [KMP算法(基于DFA)](https://github.com/chaoaiqi/study/blob/master/java/src/juejin/lc/string/KMPByDFA.java)
78
### [KMP算法](https://github.com/chaoaiqi/study/blob/master/java/src/juejin/lc/string/KMPArithmetic.java)
89
### [BM启发式算法](https://github.com/chaoaiqi/study/blob/master/java/src/juejin/lc/string/BoyerMoore.java)

‎java/src/juejin/lc/linkedList/DulLinkList.java

Lines changed: 217 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,217 @@
1+
package juejin.lc.linkedList;
2+
3+
/**
4+
* 双向链表
5+
*/
6+
public class DulLinkList {
7+
/**
8+
* 声明一个头结点
9+
*/
10+
private DulNode head;
11+
/**
12+
* 声明一个尾部节点
13+
*/
14+
private DulNode tail;
15+
16+
/**
17+
* 链表数量
18+
*/
19+
private int count;
20+
21+
private DulLinkList() {
22+
head = null;
23+
tail = null;
24+
count = 0;
25+
}
26+
27+
/**
28+
* 添加到链表头部
29+
*
30+
* @param data
31+
*/
32+
private void insertToHead(int data) {
33+
DulNode dulNode = new DulNode(data);
34+
if (count == 0) {
35+
head = dulNode;
36+
tail = dulNode;
37+
} else {
38+
DulNode prev = head;
39+
prev.prev = dulNode;
40+
dulNode.next = head;
41+
head = dulNode;
42+
}
43+
++count;
44+
}
45+
46+
/**
47+
* 添加到链表尾部
48+
*
49+
* @param data
50+
*/
51+
private void insertToTail(int data) {
52+
DulNode dulNode = new DulNode(data);
53+
if (count == 0) {
54+
head = dulNode;
55+
tail = dulNode;
56+
} else {
57+
DulNode next = tail;
58+
dulNode.prev = next;
59+
next.next = dulNode;
60+
tail = dulNode;
61+
}
62+
++count;
63+
}
64+
65+
/**
66+
* 插入指定位置的数据
67+
*
68+
* @param index 索引
69+
* @param data 数据
70+
*/
71+
private void insertByIndex(int index, int data) {
72+
if (index > count) {//放入链表尾部
73+
insertToTail(data);
74+
} else {
75+
DulNode resNode = selectByIndex(index);
76+
if (null != resNode) {
77+
System.out.println("根据index索引所得返回值为：" + resNode.data);
78+
DulNode dulNode = new DulNode(data);
79+
DulNode prev = resNode.prev;
80+
prev.next = dulNode;
81+
dulNode.prev = prev;
82+
dulNode.next = resNode;
83+
resNode.prev = dulNode;
84+
}
85+
}
86+
++count;
87+
}
88+
89+
/**
90+
* 删除链表头部
91+
* @return 返回值
92+
*/
93+
private DulNode deleteHead() {
94+
DulNode p = head;
95+
if (count > 0) {
96+
head = head.next;
97+
head.prev = null;
98+
--count;
99+
}
100+
return p;
101+
}
102+
103+
/**
104+
* 删除链表尾部
105+
* @return 返回值
106+
*/
107+
private DulNode deleteTail() {
108+
DulNode q = tail;
109+
if (count > 0) {
110+
tail = tail.prev;
111+
tail.next = null;
112+
--count;
113+
}
114+
return q;
115+
}
116+
117+
/**
118+
* 删除指定位置的数据
119+
*
120+
* @param index 索引
121+
*/
122+
private void deleteByIndex(int index) {
123+
if (index > count)
124+
return;
125+
//删除这边加了个小技巧，如果是链表头部或者尾部，直接删除，中间值开始查找
126+
if (index == 0) {
127+
deleteHead();
128+
} else if (index == count - 1) {
129+
deleteTail();
130+
} else {
131+
DulNode resNode = selectByIndex(index);
132+
if (null != resNode) {
133+
System.out.println("要删除的元素为：" + resNode.data);
134+
DulNode prev = resNode.prev;
135+
DulNode next = resNode.next;
136+
prev.next = next;
137+
next.prev = prev;
138+
resNode.prev = null;
139+
resNode.next = null;
140+
}
141+
--count;
142+
}
143+
}
144+
145+
/**
146+
* 根据指定索引获取节点
147+
*
148+
* @param index 索引
149+
* @return 返回值
150+
*/
151+
private DulNode selectByIndex(int index) {
152+
if (index > count) return null;
153+
int num = 0;
154+
DulNode dulNode = head;
155+
while (num < index) {
156+
dulNode = dulNode.next;
157+
++num;
158+
}
159+
return dulNode;
160+
}
161+
162+
/**
163+
* 根据指定节点获取下标
164+
*
165+
* @param data 数据
166+
* @return 返回值
167+
*/
168+
private int indexOf(int data) {
169+
int num = 0;
170+
DulNode dulNode = head;
171+
while (num < count && null != dulNode) {
172+
if (data == dulNode.data) {
173+
return num;
174+
}
175+
dulNode = dulNode.next;
176+
++num;
177+
}
178+
return -1;
179+
}
180+
181+
private void printAll() {
182+
DulNode dulNode = head;
183+
while (null != dulNode) {
184+
System.out.print(dulNode.data + " ");
185+
dulNode = dulNode.next;
186+
}
187+
System.out.println();
188+
}
189+
190+
public static void main(String[] args) {
191+
DulLinkList dulLinkList = new DulLinkList();
192+
dulLinkList.insertToHead(3);
193+
dulLinkList.insertToHead(2);
194+
dulLinkList.insertToHead(1);
195+
dulLinkList.insertToTail(5);
196+
dulLinkList.insertToTail(6);
197+
dulLinkList.insertToTail(7);
198+
dulLinkList.insertToTail(8);
199+
dulLinkList.insertToTail(9);
200+
dulLinkList.printAll();
201+
System.out.println("删除头部,并返回");
202+
DulNode resHead = dulLinkList.deleteHead();
203+
System.out.println("返回值：" + resHead.data);
204+
dulLinkList.insertByIndex(3, 4);
205+
dulLinkList.printAll();
206+
System.out.println("删除尾部,并返回");
207+
DulNode resTail = dulLinkList.deleteTail();
208+
System.out.println("返回值：" + resTail.data);
209+
dulLinkList.printAll();
210+
int data = 5;
211+
int res = dulLinkList.indexOf(data);
212+
System.out.println("数据" + data + "的下标 " + (res != -1 ? res : "不存在"));
213+
int delData = 5;
214+
dulLinkList.deleteByIndex(delData);
215+
dulLinkList.printAll();
216+
}
217+
}

‎java/src/juejin/lc/linkedList/DulNode.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package juejin.lc.linkedList;
2+
3+
/**
4+
* 双向链表类
5+
*/
6+
public class DulNode {
7+
/**
8+
* 数据
9+
*/
10+
public int data;
11+
/**
12+
* 前驱节点
13+
*/
14+
public DulNode prev;
15+
/**
16+
* 后继节点
17+
*/
18+
public DulNode next;
19+
20+
private DulNode(){}
21+
/**
22+
* 有参构造方法
23+
*
24+
* @param data 数据
25+
*/
26+
public DulNode(int data) {
27+
this.data = data;
28+
}
29+
}

‎java/src/juejin/lc/tree/TrieTree.java

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package juejin.lc.tree;
2+
3+
/**
4+
* 实现一个字符集，只包含a～z这26个英文字母的Trie树
5+
*/
6+
public class TrieTree {
7+
}

0 commit comments

Comments
 (0)