list接口
1 package demo1;
2
3 public interface MyList {
4
5 int getSize();//返回线性表中元素的个数
6 boolean isEmpty();//判断线性表是否为空
7 void insert(int i,Object e);//在线性表的i索引值添加元素e
8 boolean contains(Object e);//判断线性表中元素e的索引值
9 int indexOf(Object e);//返回线性表中元素e的索引值
10 Object remove(Object e);//删除线性表第一个与e相同的元素,并返回该元素
11 Object remove(int i);//删除线性表第一个与i相同的元素,并返回该元素
12 Object replace(int i,Object e);//使用元素e代替i,并返回就得元素
13 Object get(int i);//返回索引值为i的元素
14 boolean insertBefore(Object p,Object e);//在线性表元素p前面插入元素e
15 boolean insertAfter(Object p,Object e);//在线性表元素p后面插入元素e
16
17
18 }
通过单向链表实现:
1 package demo1;
2 /**
3 * 通过单向链表实现线性表
4 * @author ASUS
5 *
6 */
7 public class MySingleLink implements MyList {
8
9 private Node head;
10 private int size;
11
12 //返回元素的个数
13 @Override
14 public int getSize() {
15
16 return size;
17 }
18
19 //判断线性表是否为空
20 @Override
21 public boolean isEmpty() {
22
23 return size==0;
24 }
25
26 //在线性表插入元素
27 @Override
28 public void insert(int i, Object e) {
29 //判断索引值是否越界
30 if(i<0||i>size){
31 throw new IndexOutOfBoundsException(i+"越界");
32 }
33 //创建节点
34 Node newNode = new Node(e,null);
35 //头结点为null的情况,链表不存在,刚刚添加的节点就是头结点
36 if(head==null){
37 head = newNode;
38
39 }else{
40 //在0位置插入结点
41 if(i==0){
42 newNode.next=head; //修改新结点next域指向头结点
43 head=newNode; //刚插入的为新的节点
44 }else {
45 //插入结点,先找到i-1的节点
46 Node pNode=head;
47 for(int x=1;x<i;x++){
48 pNode = pNode.next;
49 }
50 //注意,先修改新结点next指针域,再修改i-1的指针域
51 newNode.next=pNode.next;
52 pNode.next=newNode;
53 }
54 }
55 size++;
56
57 //元素个数加0
58 }
59
60 //线性表中是否包含指定的元素
61 @Override
62 public boolean contains(Object e) {
63
64 return indexOf(e)>=0;
65 }
66
67 //返回元素e在线性表中的第一次出现的索引值
68 @Override
69 public int indexOf(Object e) {
70 int i=0; //保存元素e的索引值
71 Node pNode = head;
72 while(pNode !=null){
73 if(e==null && pNode.data==null){
74 return i;
75 }else if(e!=null&&e.equals(pNode.data)){
76 return i;
77 }
78 i++;
79 pNode=pNode.next;
80 }
81
82
83 return -1;
84 }
85
86 //从线性表中删除第一个与e相同的元素
87 @Override
88 public Object remove(Object e) {
89 //找到e第一次出现的索引值
90 int index=indexOf(e);
91 if(index<0){
92 return null; //不存在
93 }
94 return remove(index);
95 }
96
97 //从线性表中删除指定索引的元素
98 @Override
99 public Object remove(int i) {
100 //判断是否越界
101 if(i<0||i>=size){
102 throw new IndexOutOfBoundsException(i+"越界");
103 }
104 Node pNode=head;
105 //删除头结点
106 if(i==0){
107 head=head.next;
108 size--;
109 return pNode.data; //返回删除后的结果
110 }
111 for(int x=1;x<i;x++){
112 pNode =pNode.next;
113 }
114 //
115 Object old=pNode.next.data; //保存删除结点的数据
116 pNode.next=pNode.next.next;
117 size--;
118 return old;
119 }
120
121 //把线性表i索引值得元素替换为e
122 @Override
123 public Object replace(int i, Object e) {
124 //判断是否越界
125 checkIndex(i);
126 Node pNode=getNode(i);
127 Object old = pNode.data;
128 pNode.data=e;
129 return old;
130 }
131 //返回线性表中i索引值得元素
132 @Override
133 public Object get(int i) {
134 checkIndex(i);
135 Node pNode=getNode(i);
136 return pNode.data;
137 }
138 //定义方法,返回线性表i索引的元素
139 private Node getNode(int i){
140 if(i<0||i>=size){
141 return null;
142 }if(i==0){
143 return head;
144 }
145 //找到i结点
146 Node pNode=head;
147 for(int x=i;x<i;x++){
148 pNode=pNode.next;
149
150 }
151 return pNode;
152 }
153 //检查索引值是否越界
154 private void checkIndex(int i){
155 if(i<0||i>size){
156 throw new IndexOutOfBoundsException(i+"越界");
157 }
158 }
159
160 //在指定的元素p前面插入元素e
161 @Override
162 public boolean insertBefore(Object p, Object e) {
163
164 //找p的位置
165 int index=indexOf(p);
166 if(index<0){
167 return false;
168 }
169 insert (index,e);
170 return true;
171 }
172
173
174 //在指定的元素p后面插入元素e
175 @Override
176 public boolean insertAfter(Object p, Object e) {
177 //找p的位置
178 int index =indexOf(p);
179 if(index<0){
180 return false;
181 }
182 insert(index+1,e);
183
184 return true;
185 }
186
187 //重写toString
188 @Override
189 public String toString() {
190 //把链表中各个结点的数据域连接起来
191 StringBuilder sb=new StringBuilder();
192 sb.append("[");
193 Node pNode=head;
194 while(pNode!=null){
195 sb.append(pNode.data);
196 //使用逗号分隔
197 if(pNode.next!=null){
198 sb.append(",");
199
200 }
201 pNode=pNode.next;
202
203 }
204 sb.append("]");
205
206 return sb.toString();
207 }
208
209
210 //定义一个内部类表示单向链表中的节点
211 private class Node{
212
213 Object data;
214 Node next;
215 public Node(Object data, Node next) {
216 super();
217 this.data = data;
218 this.next = next;
219 }
220
221 }
222
223
224 }
测试类:
1 package demo1;
2 /**
3 * 测试单向链表
4 * @author ASUS
5 *
6 */
7 public class MysingleLinkTest {
8
9 public static void main(String[] args) {
10
11 //1.创建链表
12 MySingleLink link=new MySingleLink();
13 //2.判断
14 System.out.println(link.isEmpty());
15 System.out.println(link.getSize());
16 //3.输入元素
17 link.insert(0, "aa");
18 link.insert(0, "bb");
19 link.insert(0, "cc");
20 link.insert(0, "dd");
21
22 //4.直接打印输出
23 System.out.println(link);
24 //5.判断元素是否存在
25 System.out.println(link.indexOf("aa"));
26 System.out.println(link.indexOf("cc"));
27 System.out.println(link.indexOf("xx"));
28 System.out.println(link.contains("cc"));
29 //6.删除结点
30 System.out.println(link.remove("xx"));
31 System.out.println(link.remove("bb"));
32 System.out.println(link);
33 System.out.println(link.remove(0));
34 System.out.println(link);
35 //7.返回元素,元素替换
36 System.out.println(link.get(0));
37 System.out.println(link.replace(0, "CC"));
38 System.out.println(link);
39 //8.在指定元素的前面或后面插入指定的元素
40 link.insertBefore("CC", "前面");
41 link.insertAfter("CC", "后面");
42 System.out.println(link);
43 }
44
45 }
运行截图:
