定义抽象节点类Node:
1 package cn.wzbrilliant.datastructure;
2
3 /**
4 * 节点
5 * @author ice
6 *
7 */
8 public abstract class Node {
9 private Node next;
10
11 public Node(){
12 next=null;
13 }
14
15 public void setNext(Node nextNode){
16 next=nextNode;
17 }
18
19 public Node getNext(){
20 return next;
21 }
22 }
链表类,实现了插入首尾节点、指定位置节点,删除节点、指定位置节点,链表的逆序以及判空操作:
1 package cn.wzbrilliant.datastructure;
2
3 /**
4 * 链表
5 * @author ice
6 *
7 */
8 public class Link {
9
10 protected Node head;
11 protected Node tail;
12 protected int size;
13
14 public Link() {
15 this.head = null;
16 this.tail = null;
17 this.size = 0;
18 }
19
20 public void addAtFirst(Node node){
21 node.setNext(head);
22 head=node;
23 if(size==0)
24 tail=node;
25 size++;
26 }
27
28 public void addAtLast(Node node){
29 if(size==0){
30 head=tail=node;
31 }else{
32 tail.setNext(node);
33 tail=node;
34 }
35 node.setNext(null);
36 size++;
37 }
38
39 public void removeFirst(){
40 if(size==0)
41 throw new RuntimeException("link size is 0...");
42 head=head.getNext();
43 if(size==1){
44 tail.setNext(null);
45 }
46 size--;
47 }
48
49 public void removeLast(){
50 if(size==0)
51 throw new RuntimeException("link size is 0...");
52
53 if(size==1){
54 head=tail=null;
55 size--;
56 return ;
57 }
58
59 Node node=head;
60 while(node.getNext()!=tail){
61 node=node.getNext();
62 }
63 node.setNext(null);
64 tail=node;
65 size--;
66 }
67
68 /**
69 * 队列逆序
70 */
71 public void reverse() {
72 Node preNode, node, tempNode;
73 if (size == 0)
74 return;
75 preNode = head;
76 node = preNode.getNext();
77 preNode.setNext(null);
78 tail = preNode;
79 while (node != null) {
80 tempNode = node.getNext();
81 node.setNext(preNode);
82 preNode = node;
83 node = tempNode;
84 }
85 head = preNode;
86 }
87
88 /**
89 * 在第index个节点后插入newNode
90 *
91 * @param newNode
92 * @param index
93 */
94 public void insert(Node newNode, int index) {
95 if (index < 0 || index > size)
96 throw new RuntimeException("索引错误");
97
98 if (index == 0) {
99 newNode.setNext(head);
100 head = newNode;
101 size++;
102 return;
103 }
104
105 if (index == size) {
106 newNode.setNext(null);
107 tail.setNext(newNode);
108 tail = newNode;
109 size++;
110 return;
111 }
112
113 Node node = head;
114 for (int i = 1; node != null; i++, node = node.getNext()) {
115 if (i == index) {
116 newNode.setNext(node.getNext());
117 node.setNext(newNode);
118 size++;
119 return;
120 }
121 }
122
123 }
124
125 /**
126 * 移除Node节点 Node节点需重写equals()方法
127 *
128 * @param node
129 */
130 public void remove(Node node) {
131 if (node == null || size == 0)
132 throw new RuntimeException("remove error...");
133 for (Node temp = head; temp != null; temp = temp.getNext()) {
134 if (temp == head) {
135 if (temp.equals(node)) {
136 head = head.getNext();
137 size--;
138 continue;
139 }
140 }
141 if (temp.getNext().equals(node)) {
142 temp.setNext(temp.getNext().getNext());
143 size--;
144 }
145
146 }
147 }
148
149 public Node getFirst() {
150 if (size == 0)
151 return null;
152 return head;
153 }
154
155 public Node getLast() {
156 if (size == 0)
157 return null;
158 return tail;
159 }
160
161 public int size() {
162 return size;
163 }
164
165 public boolean isEmpty() {
166 if (size == 0)
167 return true;
168 return false;
169 }
170 }
栈类,实现了入栈、出战、获取栈顶元素以及判空的操作:
1 package cn.wzbrilliant.datastructure;
2
3 /**
4 * 栈
5 * @author ice
6 *
7 */
8 public class Stack {
9 private int size;
10 private Node top;
11
12 public Stack() {
13 size = 0;
14 top = null;
15 }
16
17 public void push(Node node) {
18 node.setNext(top);
19 top = node;
20 size++;
21 }
22
23 public Node pop() {
24 if (top == null)
25 return null;
26 Node node = top;
27 top = top.getNext();
28 size--;
29 return node;
30 }
31
32 public Node top() {
33 return top;
34 }
35
36 public int size() {
37 return size;
38 }
39
40 public boolean isEmpty() {
41 if (size == 0)
42 return true;
43 return false;
44 }
45 }
队列类,实现了入队、出队、判空的操作:
1 package cn.wzbrilliant.datastructure;
2
3 /**
4 * 队列
5 * @author ice
6 *
7 */
8 public class Queue {
9
10 private Node head;
11 private Node tail;
12 private int size;
13
14 public Queue() {
15 this.head = null;
16 this.tail = null;
17 this.size = 0;
18 }
19
20 public void enQueue(Node node) {
21 tail.setNext(node);
22 tail = node;
23 size++;
24 }
25
26 public Node deQueue() {
27 if (size == 0)
28 return null;
29 Node node = head;
30 head = head.getNext();
31 size--;
32 return node;
33 }
34
35 public int size() {
36 return size;
37 }
38
39 public boolean isEmpty() {
40 if (size == 0)
41 return true;
42 return false;
43 }
44
45 }