Skip to content

Commit d0155ff

Browse files
hackfengJamhackfengJam
committed
LinkedListStack
1 parent 9282a46 commit d0155ff

File tree

7 files changed

+460
-8
lines changed

7 files changed

+460
-8
lines changed

‎LinkedList/src/LinkedList.java‎

Lines changed: 20 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ public String toString() {
2424
}
2525

2626
private Node head;
27-
int size;
27+
private int size;
2828

2929
public LinkedList() {
3030
head = null;
@@ -72,4 +72,23 @@ public void add(int index, E e) {
7272
public void addLast(E e) {
7373
add(size, e);
7474
}
75+
76+
77+
@Override
78+
public String toString() {
79+
StringBuilder res = new StringBuilder();
80+
81+
// Node cur = dummyHead.next;
82+
// while (cur != null) {
83+
// res.append(cur + "->");
84+
// cur = cur.next;
85+
// }
86+
// res.append("NULL");
87+
for (Node cur = head; cur != null; cur = cur.next) {
88+
res.append(cur + "->");
89+
}
90+
res.append("NULL");
91+
92+
return res.toString();
93+
}
7594
}

‎LinkedList/src/LinkedListDummyHead.java‎

Lines changed: 163 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,163 @@
1+
public class LinkedListDummyHead<E> {
2+
3+
private class Node {
4+
public E e;
5+
public Node next;
6+
7+
public Node(E e, Node next) {
8+
this.e = e;
9+
this.next = next;
10+
}
11+
12+
public Node(E e) {
13+
this(e, null);
14+
}
15+
16+
public Node() {
17+
this(null, null);
18+
}
19+
20+
@Override
21+
public String toString() {
22+
return e.toString();
23+
}
24+
}
25+
26+
private Node dummyHead;
27+
int size;
28+
29+
public LinkedListDummyHead() {
30+
dummyHead = new Node(null, null);
31+
size = 0;
32+
}
33+
34+
// 获取链表中的元素个数
35+
public int getSize() {
36+
return size;
37+
}
38+
39+
40+
public boolean isEmpty() {
41+
return size == 0;
42+
}
43+
44+
public void add(int index, E e) {
45+
if (index < 0 || index > size) {
46+
throw new IllegalArgumentException("Add failed. Illegal index.");
47+
}
48+
Node prev = dummyHead;
49+
for (int i = 0; i < index; i++) {
50+
prev = prev.next;
51+
}
52+
53+
prev.next = new Node(e, prev.next);
54+
size++;
55+
}
56+
57+
// 在链表头添加新的元素e
58+
public void addFirst(E e) {
59+
// Node node = new Node(e);
60+
// node.next = head;
61+
// head = node;
62+
add(0, e);
63+
64+
size++;
65+
}
66+
67+
// 在链表末尾添加新的元素e
68+
public void addLast(E e) {
69+
add(size, e);
70+
}
71+
72+
73+
// 获得链表的第index(0-based)个位置的元素
74+
// 在链表中不是一个常用的操作，练习用
75+
public E get(int index) {
76+
if (index < 0 || index > size) {
77+
throw new IllegalArgumentException("Get failed. Illegal index.");
78+
}
79+
Node cur = dummyHead.next;
80+
for (int i = 0; i < index; i++) {
81+
cur = cur.next;
82+
}
83+
return cur.e;
84+
}
85+
86+
// 获得链表的第一个元素
87+
public E getFirst() {
88+
return get(0);
89+
}
90+
91+
// 获取链表的最后一个元素
92+
public E getLast() {
93+
return get(size - 1);
94+
}
95+
96+
public void set(int index, E e) {
97+
if (index < 0 || index > size) {
98+
throw new IllegalArgumentException("Set failed. Illegal index.");
99+
}
100+
101+
Node cur = dummyHead.next;
102+
for (int i = 0; i < index; i++) {
103+
cur = cur.next;
104+
}
105+
cur.e = e;
106+
}
107+
108+
public boolean contains(E e) {
109+
Node cur = dummyHead.next;
110+
111+
while (cur != null) {
112+
if (cur.e.equals(e)) {
113+
return true;
114+
}
115+
cur = cur.next;
116+
}
117+
return false;
118+
}
119+
120+
// 从链表中删除index(0-based)位置的元素，返回删除的元素
121+
// 在链表中不是一个常用的操作，练习使用: ）
122+
public E remove(int index) {
123+
if (index < 0 || index > size) {
124+
throw new IllegalArgumentException("Remove failed. Illegal index.");
125+
}
126+
Node cur = dummyHead;
127+
for (int i = 0; i < index; i++) {
128+
cur = cur.next;
129+
}
130+
Node retNode = cur.next;
131+
cur.next = retNode.next;
132+
retNode.next = null;
133+
134+
return retNode.e;
135+
}
136+
137+
public E removeFirst() {
138+
return remove(0);
139+
}
140+
141+
public E removeLast() {
142+
return remove(size - 1);
143+
}
144+
145+
@Override
146+
public String toString() {
147+
StringBuilder res = new StringBuilder();
148+
149+
// Node cur = dummyHead.next;
150+
// while (cur != null) {
151+
// res.append(cur + "->");
152+
// cur = cur.next;
153+
// }
154+
// res.append("NULL");
155+
for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
156+
res.append(cur + "->");
157+
}
158+
res.append("NULL");
159+
160+
return res.toString();
161+
}
162+
}
163+

‎LinkedList/src/Main.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,2 +1,22 @@
11
public class Main {
2+
3+
public static void main(String[] args) {
4+
LinkedList<Integer> linkedList = new LinkedList<>();
5+
LinkedListDummyHead<Integer> linkedListDummyHead = new LinkedListDummyHead<>();
6+
7+
for (int i = 0; i < 5; i++) {
8+
linkedList.addFirst(i);
9+
linkedListDummyHead.addFirst(i);
10+
System.out.println("LinkedList: " + linkedList);
11+
System.out.println("linkedListDummyHead: " + linkedListDummyHead);
12+
}
13+
14+
linkedList.add(2, 666);
15+
linkedListDummyHead.add(2, 666);
16+
System.out.println("LinkedList: " + linkedList);
17+
System.out.println("linkedListDummyHead: " + linkedListDummyHead);
18+
19+
linkedListDummyHead.remove(2);
20+
System.out.println(linkedListDummyHead);
21+
}
222
}

‎Stack/src/ArrayStack.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,4 +53,16 @@ public String toString() {
5353
res.append("] top");
5454
return res.toString();
5555
}
56+
57+
public static void main(String[] args) {
58+
ArrayStack<Integer> stack = new ArrayStack<>();
59+
60+
for (int i = 0; i < 5; i++) {
61+
stack.push(i);
62+
System.out.println(stack);
63+
}
64+
65+
stack.pop();
66+
System.out.println(stack);
67+
}
5668
}

0 commit comments

Comments
 (0)