Skip to content

Commit 26cd941

Browse files
realDuYuanChaorealDuYuanChao
committed
* Update SinglyLinkedList
* Refactor MergeSortedSinglyLinkedList to single file * Create Problem09 and Problem10 in Project Euler
1 parent 3c07927 commit 26cd941

File tree

4 files changed

+236
-116
lines changed

4 files changed

+236
-116
lines changed

‎DataStructures/Lists/MergeSortedSinglyLinkedList.java

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package DataStructures.Lists;
2+
3+
public class MergeSortedSinglyLinkedList extends SinglyLinkedList {
4+
5+
public static void main(String[] args) {
6+
SinglyLinkedList listA = new SinglyLinkedList();
7+
SinglyLinkedList listB = new SinglyLinkedList();
8+
9+
for (int i = 2; i <= 10; i += 2) {
10+
listA.insert(i);
11+
listB.insert(i - 1);
12+
}
13+
assert listA.toString().equals("2->4->6->8->10");
14+
assert listB.toString().equals("1->3->5->7->9");
15+
assert merge(listA, listB).toString().equals("1->2->3->4->5->6->7->8->9->10");
16+
}
17+
18+
/**
19+
* Merge two sorted SingleLinkedList
20+
*
21+
* @param listA the first sorted list
22+
* @param listB the second sored list
23+
* @return merged sorted list
24+
*/
25+
public static SinglyLinkedList merge(SinglyLinkedList listA, SinglyLinkedList listB) {
26+
Node headA = listA.getHead();
27+
Node headB = listB.getHead();
28+
29+
int size = listA.size() + listB.size();
30+
31+
Node head = new Node();
32+
Node tail = head;
33+
while (headA != null && headB != null) {
34+
if (headA.value <= headB.value) {
35+
tail.next = headA;
36+
headA = headA.next;
37+
} else {
38+
tail.next = headB;
39+
headB = headB.next;
40+
}
41+
tail = tail.next;
42+
}
43+
if (headA == null) {
44+
tail.next = headB;
45+
}
46+
if (headB == null) {
47+
tail.next = headA;
48+
}
49+
return new SinglyLinkedList(head.next, size);
50+
}
51+
}

‎DataStructures/Lists/SinglyLinkedList.java

Lines changed: 100 additions & 116 deletions
Original file line numberDiff line numberDiff line change
@@ -18,15 +18,15 @@ public class SinglyLinkedList {
1818
private Node head;
1919

2020
/**
21-
* size of SinglyLinkedList
21+
* Size of SinglyLinkedList
2222
*/
2323
private int size;
2424

2525
/**
26-
* init SinglyLinkedList
26+
* Init SinglyLinkedList
2727
*/
2828
public SinglyLinkedList() {
29-
head = new Node(0);
29+
head = null;
3030
size = 0;
3131
}
3232

@@ -42,87 +42,86 @@ public SinglyLinkedList(Node head, int size) {
4242
}
4343

4444
/**
45-
* This method inserts an element at the head
45+
* Inserts an element at the head of the list
4646
*
47-
* @param x Element to be added
47+
* @param x element to be added
4848
*/
4949
public void insertHead(int x) {
5050
insertNth(x, 0);
5151
}
5252

5353
/**
54-
* insert an element at the tail of list
54+
* Insert an element at the tail of the list
5555
*
56-
* @param data Element to be added
56+
* @param data element to be added
5757
*/
5858
public void insert(int data) {
5959
insertNth(data, size);
6060
}
6161

6262
/**
63-
* Inserts a new node at a specified position
63+
* Inserts a new node at a specified position of the list
6464
*
6565
* @param data data to be stored in a new node
6666
* @param position position at which a new node is to be inserted
6767
*/
6868
public void insertNth(int data, int position) {
6969
checkBounds(position, 0, size);
70-
Node cur = head;
71-
for (int i = 0; i < position; ++i) {
72-
cur = cur.next;
70+
Node newNode = new Node(data);
71+
if (head == null) { /* the list is empty */
72+
head = newNode;
73+
size++;
74+
return;
75+
} else if (position == 0) { /* insert at the head of the list */
76+
newNode.next = head;
77+
head = newNode;
78+
size++;
79+
return;
7380
}
74-
Node node = new Node(data);
75-
node.next = cur.next;
76-
cur.next = node;
77-
size++;
78-
}
79-
80-
/**
81-
* Insert element to list, always sorted
82-
*
83-
* @param data to be inserted
84-
*/
85-
public void insertSorted(int data) {
8681
Node cur = head;
87-
while (cur.next != null && data > cur.next.value) {
82+
for (int i = 0; i < position - 1; ++i) {
8883
cur = cur.next;
8984
}
90-
91-
Node newNode = new Node(data);
9285
newNode.next = cur.next;
9386
cur.next = newNode;
9487
size++;
9588
}
9689

90+
9791
/**
98-
* This method deletes an element at the head
99-
*
100-
* @return The element deleted
92+
* Deletes a node at the head
10193
*/
10294
public void deleteHead() {
10395
deleteNth(0);
10496
}
10597

10698
/**
107-
* This method deletes an element at the tail
99+
* Deletes an element at the tail
108100
*/
109101
public void delete() {
110102
deleteNth(size - 1);
111103
}
112104

113105
/**
114-
* This method deletes an element at Nth position
106+
* Deletes an element at Nth position
115107
*/
116108
public void deleteNth(int position) {
117109
checkBounds(position, 0, size - 1);
110+
if (position == 0) {
111+
Node destroy = head;
112+
head = head.next;
113+
destroy = null; /* clear to let GC do its work */
114+
size--;
115+
return;
116+
}
118117
Node cur = head;
119-
for (int i = 0; i < position; ++i) {
118+
for (int i = 0; i < position - 1; ++i) {
120119
cur = cur.next;
121120
}
122121

123-
//Node destroy = cur.next;
122+
Node destroy = cur.next;
124123
cur.next = cur.next.next;
125-
//destroy = null; // clear to let GC do its work
124+
destroy = null; // clear to let GC do its work
126125

127126
size--;
128127
}
@@ -140,127 +139,112 @@ public void checkBounds(int position, int low, int high) {
140139
}
141140

142141
/**
143-
* clear all nodes in list
142+
* Clear all nodes in the list
144143
*/
145144
public void clear() {
146-
if (size == 0) {
147-
return;
148-
}
149-
Node prev = head.next;
150-
Node cur = prev.next;
145+
Node cur = head;
151146
while (cur != null) {
152-
prev = null; // clear to let GC do its work
153-
prev = cur;
147+
Node prev = cur;
154148
cur = cur.next;
149+
prev = null; // clear to let GC do its work
155150
}
156-
prev = null;
157-
head.next = null;
151+
head = null;
158152
size = 0;
159153
}
160154

161155
/**
162156
* Checks if the list is empty
163157
*
164-
* @return true is list is empty
158+
* @return {@code true} if list is empty, otherwise {@code false}.
165159
*/
166160
public boolean isEmpty() {
167161
return size == 0;
168162
}
169163

170164
/**
171-
* Returns the size of the linked list
165+
* Returns the size of the linked list.
166+
*
167+
* @return the size of the list.
172168
*/
173169
public int size() {
174170
return size;
175171
}
176172

173+
/**
174+
* Get head of the list.
175+
*
176+
* @return head of the list.
177+
*/
178+
public Node getHead() {
179+
return head;
180+
}
181+
182+
/**
183+
* Calculate the count of the list manually
184+
*
185+
* @return count of the list
186+
*/
187+
public int count() {
188+
int count = 0;
189+
Node cur = head;
190+
while (cur != null) {
191+
cur = cur.next;
192+
count++;
193+
}
194+
return count;
195+
}
196+
177197
@Override
178198
public String toString() {
179199
if (size == 0) {
180200
return "";
181201
}
182202
StringBuilder builder = new StringBuilder();
183-
Node cur = head.next;
203+
Node cur = head;
184204
while (cur != null) {
185205
builder.append(cur.value).append("->");
186206
cur = cur.next;
187207
}
188208
return builder.replace(builder.length() - 2, builder.length(), "").toString();
189209
}
190210

191-
/**
192-
* Merge two sorted SingleLinkedList
193-
*
194-
* @param listA the first sorted list
195-
* @param listB the second sored list
196-
* @return merged sorted list
197-
*/
198-
public static SinglyLinkedList merge(SinglyLinkedList listA, SinglyLinkedList listB) {
199-
Node headA = listA.head.next;
200-
Node headB = listB.head.next;
201-
202-
int size = listA.size() + listB.size();
203-
204-
Node head = new Node();
205-
Node tail = head;
206-
while (headA != null && headB != null) {
207-
if (headA.value <= headB.value) {
208-
tail.next = headA;
209-
headA = headA.next;
210-
} else {
211-
tail.next = headB;
212-
headB = headB.next;
213-
}
214-
tail = tail.next;
215-
}
216-
if (headA == null) {
217-
tail.next = headB;
218-
}
219-
if (headB == null) {
220-
tail.next = headA;
221-
}
222-
return new SinglyLinkedList(head, size);
223-
}
224211

225212
/**
226-
* Main method
227-
*
228-
* @param args Command line arguments
213+
* Driver Code
229214
*/
230-
public static void main(String args[]) {
231-
SinglyLinkedList myList = new SinglyLinkedList();
232-
assert myList.isEmpty();
233-
assert myList.toString().equals("");
234-
235-
myList.insertHead(5);
236-
myList.insertHead(7);
237-
myList.insertHead(10);
238-
assert myList.toString().equals("10->7->5");
239-
240-
myList.deleteHead();
241-
assert myList.toString().equals("7->5");
242-
243-
myList.insertNth(11, 2);
244-
assert myList.toString().equals("7->5->11");
245-
246-
myList.deleteNth(1);
247-
assert myList.toString().equals("7->11");
248-
249-
myList.clear();
250-
assert myList.isEmpty();
251-
252-
/* Test MergeTwoSortedLinkedList */
253-
SinglyLinkedList listA = new SinglyLinkedList();
254-
SinglyLinkedList listB = new SinglyLinkedList();
255-
256-
for (int i = 10; i >= 2; i -= 2) {
257-
listA.insertSorted(i);
258-
listB.insertSorted(i - 1);
215+
public static void main(String[] arg) {
216+
SinglyLinkedList list = new SinglyLinkedList();
217+
assert list.isEmpty();
218+
assert list.size() == 0
219+
&& list.count() == 0;
220+
assert list.toString().equals("");
221+
222+
/* Test insert function */
223+
list.insertHead(5);
224+
list.insertHead(7);
225+
list.insertHead(10);
226+
list.insert(3);
227+
list.insertNth(1, 4);
228+
assert list.toString().equals("10->7->5->3->1");
229+
230+
/* Test delete function */
231+
list.deleteHead();
232+
list.deleteNth(1);
233+
list.delete();
234+
assert list.toString().equals("7->3");
235+
236+
assert list.size == 2
237+
&& list.size() == list.count();
238+
239+
list.clear();
240+
assert list.isEmpty();
241+
242+
try {
243+
list.delete();
244+
assert false; /* this should not happen */
245+
} catch (Exception e) {
246+
assert true; /* this should happen */
259247
}
260-
assert listA.toString().equals("2->4->6->8->10");
261-
assert listB.toString().equals("1->3->5->7->9");
262-
assert SinglyLinkedList.merge(listA, listB).toString().equals("1->2->3->4->5->6->7->8->9->10");
263-
264248
}
265249
}
266250

0 commit comments

Comments
 (0)