Skip to content

Commit 6ffbca8

Browse files
Korben-CHYKorben-CHY
committed
add single linked list by Korben
1 parent 7436f62 commit 6ffbca8

File tree

3 files changed

+258
-18
lines changed

3 files changed

+258
-18
lines changed

‎group20/1107837739/1107837739Learning/src/org/korben/coding/basic/list/KDoubleLinkedList.java

+175
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,175 @@
1+
package org.korben.coding.basic.list;
2+
3+
import java.util.Objects;
4+
5+
/**
6+
* Korben's LinkedList
7+
*
8+
* Created by Korben on 18/02/2017.
9+
*/
10+
public class KDoubleLinkedList<T> implements KList<T> {
11+
12+
private int size;
13+
14+
private Node<T> head;
15+
16+
private Node<T> last;
17+
18+
public KDoubleLinkedList() {
19+
this.head = new Node<>(null);
20+
}
21+
22+
@Override
23+
public int size() {
24+
return this.size;
25+
}
26+
27+
@Override
28+
public boolean isEmpty() {
29+
return this.size == 0;
30+
}
31+
32+
@Override
33+
public boolean contains(Object o) {
34+
Node node = this.head;
35+
while (node.next != null) {
36+
node = node.next;
37+
if (Objects.equals(node.data, o)) {
38+
return true;
39+
}
40+
}
41+
return false;
42+
}
43+
44+
@Override
45+
public Object[] toArray() {
46+
return new Object[0];
47+
}
48+
49+
@Override
50+
public boolean add(T o) {
51+
if (this.last == null) {
52+
this.last = new Node<>(o);
53+
this.last.pre = this.head;
54+
this.head.next = this.last;
55+
} else {
56+
Node<T> oldLast = this.last;
57+
this.last = new Node<>(o);
58+
this.last.pre = oldLast;
59+
oldLast.next = this.last;
60+
}
61+
this.size++;
62+
return true;
63+
}
64+
65+
@Override
66+
public boolean remove(T o) {
67+
Node node = this.head;
68+
while (node.next != null) {
69+
node = node.next;
70+
if (Objects.equals(node.data, o)) {
71+
node.pre.next = node.next;
72+
if (node.next != null) {
73+
node.next.pre = node.pre;
74+
}
75+
this.size--;
76+
return true;
77+
}
78+
}
79+
return false;
80+
}
81+
82+
@Override
83+
public void clear() {
84+
this.head.next = null;
85+
this.last = null;
86+
87+
this.size = 0;
88+
}
89+
90+
@Override
91+
public T get(int index) {
92+
return getNode(index).data;
93+
}
94+
95+
@Override
96+
public T set(int index, T element) {
97+
Node<T> node = getNode(index);
98+
node.data = element;
99+
return element;
100+
}
101+
102+
@Override
103+
public void add(int index, T element) {
104+
if (index <= 0 || index >= this.size) {
105+
throw new IndexOutOfBoundsException();
106+
}
107+
Node<T> node = this.head;
108+
for (int i = 0; i <= index; i++) {
109+
node = node.next;
110+
}
111+
Node<T> pre = node.pre;
112+
Node<T> newNode = new Node<>(element);
113+
pre.next = newNode;
114+
newNode.pre = pre;
115+
newNode.next = node;
116+
node.pre = newNode;
117+
118+
this.size++;
119+
}
120+
121+
@Override
122+
public T remove(int index) {
123+
Node<T> node = getNode(index);
124+
Node<T> pre = node.pre;
125+
Node<T> next = node.next;
126+
pre.next = next;
127+
if (next != null) {
128+
next.pre = pre;
129+
}
130+
131+
this.size--;
132+
return node.data;
133+
}
134+
135+
@Override
136+
public int indexOf(T o) {
137+
Node node = this.head;
138+
int index = 0;
139+
while (node.next != null) {
140+
node = node.next;
141+
if (Objects.equals(node.data, o)) {
142+
return index;
143+
}
144+
index++;
145+
}
146+
return -1;
147+
}
148+
149+
@Override
150+
public KIterator<T> iterator() {
151+
throw new IllegalStateException("方法未实现");
152+
}
153+
154+
private Node<T> getNode(int index) {
155+
if (index < 0 || index >= size) {
156+
throw new IndexOutOfBoundsException();
157+
}
158+
159+
Node<T> node = this.head;
160+
for (int i = 0; i <= index; i++) {
161+
node = node.next;
162+
}
163+
return node;
164+
}
165+
166+
private static class Node<T> {
167+
T data;
168+
Node<T> pre;
169+
Node<T> next;
170+
171+
Node(T data) {
172+
this.data = data;
173+
}
174+
}
175+
}

‎group20/1107837739/1107837739Learning/src/org/korben/coding/basic/list/KLinkedList.java

+80-18
Original file line numberDiff line numberDiff line change
@@ -43,19 +43,17 @@ public boolean contains(Object o) {
4343

4444
@Override
4545
public Object[] toArray() {
46-
return new Object[0];
46+
throw new IllegalStateException("方法未实现");
4747
}
4848

4949
@Override
5050
public boolean add(T o) {
5151
if (this.last == null) {
5252
this.last = new Node<>(o);
53-
this.last.pre = this.head;
5453
this.head.next = this.last;
5554
} else {
5655
Node<T> oldLast = this.last;
5756
this.last = new Node<>(o);
58-
this.last.pre = oldLast;
5957
oldLast.next = this.last;
6058
}
6159
this.size++;
@@ -65,13 +63,12 @@ public boolean add(T o) {
6563
@Override
6664
public boolean remove(T o) {
6765
Node node = this.head;
66+
Node preNode;
6867
while (node.next != null) {
68+
preNode = node;
6969
node = node.next;
7070
if (Objects.equals(node.data, o)) {
71-
node.pre.next = node.next;
72-
if (node.next != null) {
73-
node.next.pre = node.pre;
74-
}
71+
preNode.next = node.next;
7572
this.size--;
7673
return true;
7774
}
@@ -101,30 +98,39 @@ public T set(int index, T element) {
10198

10299
@Override
103100
public void add(int index, T element) {
101+
if (index < 0 || index >= this.size) {
102+
throw new IndexOutOfBoundsException();
103+
}
104+
104105
Node<T> node = this.head;
106+
Node<T> preNode = node;
105107
for (int i = 0; i <= index; i++) {
108+
preNode = node;
106109
node = node.next;
107110
}
108-
Node<T> pre = node.pre;
111+
109112
Node<T> newNode = new Node<>(element);
110-
pre.next = newNode;
111-
newNode.pre = pre;
112113
newNode.next = node;
113-
node.pre = newNode;
114+
preNode.next = newNode;
114115

115116
this.size++;
116117
}
117118

118119
@Override
119120
public T remove(int index) {
120-
Node<T> node = getNode(index);
121-
Node<T> pre = node.pre;
122-
Node<T> next = node.next;
123-
pre.next = next;
124-
if (next != null) {
125-
next.pre = pre;
121+
if (index < 0 || index >= size) {
122+
throw new IndexOutOfBoundsException();
123+
}
124+
125+
Node<T> node = this.head;
126+
Node<T> preNode = this.head;
127+
128+
for (int i = 0; i <= index; i++) {
129+
preNode = node;
130+
node = node.next;
126131
}
127132

133+
preNode.next = node.next;
128134
this.size--;
129135
return node.data;
130136
}
@@ -160,9 +166,65 @@ private Node<T> getNode(int index) {
160166
return node;
161167
}
162168

169+
/**
170+
* 把该链表逆置
171+
* 例如链表为 3->7->10 , 逆置后变为 10->7->3
172+
*/
173+
public void reverse() {
174+
175+
}
176+
177+
/**
178+
* 删除一个单链表的前半部分
179+
* 例如：list = 2->5->7->8 , 删除以后的值为 7->8
180+
* 如果list = 2->5->7->8->10 ,删除以后的值为7,8,10
181+
*/
182+
public void removeFirstHalf() {
183+
184+
}
185+
186+
/**
187+
* 从第i个元素开始， 删除length 个元素 ， 注意i从0开始
188+
*/
189+
public void remove(int i, int length) {
190+
191+
}
192+
193+
/**
194+
* 已知链表中的元素以值递增有序排列，并以单链表作存储结构。
195+
* 从当前链表中中删除在list中出现的元素
196+
*/
197+
198+
public void subtract(KLinkedList list) {
199+
200+
}
201+
202+
/**
203+
* 已知当前链表中的元素以值递增有序排列，并以单链表作存储结构。
204+
* 删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同）
205+
*/
206+
public void removeDuplicateValues() {
207+
208+
}
209+
210+
/**
211+
* 已知链表中的元素以值递增有序排列，并以单链表作存储结构。
212+
* 试写一高效的算法，删除表中所有值大于min且小于max的元素（若表中存在这样的元素）
213+
*/
214+
public void removeRange(int min, int max) {
215+
216+
}
217+
218+
/**
219+
* 假设当前链表和参数list指定的链表均以元素依值递增有序排列（同一表中的元素值各不相同）
220+
* 现要求生成新链表C，其元素为当前链表和list中元素的交集，且表C中的元素有依值递增有序排列
221+
*/
222+
public KLinkedList intersection(KLinkedList list) {
223+
return null;
224+
}
225+
163226
private static class Node<T> {
164227
T data;
165-
Node<T> pre;
166228
Node<T> next;
167229

168230
Node(T data) {

‎group20/1107837739/1107837739Learning/src/org/korben/coding/basic/list/KListTest.java

+3
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,9 @@ public void init() {
2424
// 测试KLinkedList
2525
list = new KLinkedList<>();
2626

27+
//// 测试KDoubleLinkedList
28+
//list = new KDoubleLinkedList<>();
29+
2730
initTestSize = 5;
2831

2932
for (int i = 0; i < initTestSize; i++) {

0 commit comments

Comments
 (0)