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 MyDualLinkedList implements MyList {
8 private Node first; //指向前结点
9 private Node last; //指向尾结点
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 //1.检查索引是否越界
30 checkIndex(i);
31 //2.如果i==0;
32 if(i==0){
33 addFirst(e);
34 }else if(i==size){
35 //3.如果i==size,在尾部添加
36 addLast(e);
37 }else{
38 //4.列表中心添加
39 //找到i结点,在i结点前面插入元素
40 Node pNode=getNode(i);
41 Node PrevNode=pNode.prev;
42 //生成新的结点
43 Node newNode=new Node(e, PrevNode, pNode);
44 //修改前驱结点的后缀
45
46 PrevNode.next=newNode;
47 pNode.prev=newNode;
48 size++;
49
50
51 }
52 }
53
54 //返回索引值对应的结点
55 private Node getNode(int i) {
56 //
57 Node pNode=first;
58 for(int x=0;x<i;x++){
59 pNode=pNode.next;
60 }
61 return pNode;
62 }
63
64
65 //判断链表中是否包含指定的元素e,如果存在返回true
66 @Override
67 public boolean contains(Object e) {
68
69 return indexOf(e)>=0;
70 }
71
72 //判断元素e在链表中第一次出现的位置,如果不存在返回-1
73 @Override
74 public int indexOf(Object e) {
75 int i=0;
76 //依次遍历链表中各个结点,比较结点的元素与指定的e是否一样
77 if(e==null){
78 for(Node pNode=first;pNode!=null;pNode=pNode.next){
79 if(pNode.data==null){
80 return i;
81 }
82 i++;
83 }
84 }else{
85 for(Node pNode=first;pNode!=null;pNode=pNode.next){
86 if(e.equals(pNode.data)){
87 return i;
88 }
89 i++;
90 }
91
92 }
93 return -1;
94 }
95
96 //从链表中删除指定元素,并返回删除元素
97 @Override
98 public Object remove(Object e) {
99 //找到元素e对应的元素
100 int index=indexOf(e);
101 if(index<0){
102 return null;
103 }
104 return remove(index);
105 }
106
107 //从链表中删除指定索引的元素,并返回删除的元素
108 @Override
109 public Object remove(int i) {
110 //判断索引值是否越界
111 checkIndex(i);
112 //找到对应的结点
113 Node pNode=getNode(i);
114 Node prevNode=pNode.prev;
115 Node nextNode=pNode.next;
116 if(prevNode==null){
117 //删除头结点
118 first=nextNode;
119 }else{
120 prevNode.next=nextNode;
121 }
122 if(nextNode==null){
123 //删除尾结点
124 last=prevNode;
125 }else{
126 nextNode.prev=prevNode;
127
128 }
129 size--;
130 return pNode.data;
131 }
132
133 //修改指定索引值得元素
134 @Override
135 public Object replace(int i, Object e) {
136 //检查是否越界
137 checkIndex(i);
138 //找到索引值为i的结点
139 Node pNode=getNode(i);
140 Object old =pNode.data;
141 pNode.data=e;
142
143
144 return old;
145 }
146
147 //返回线性表中i索引值的元素
148 @Override
149 public Object get(int i) {
150 //判断是否越界
151 checkIndex(i);
152 Node pNode=getNode(i);
153 return pNode.data;
154 }
155
156
157 //在指定元素p前面插入元素e
158 @Override
159 public boolean insertBefore(Object p, Object e) {
160 //找到p元素在链表中的位置
161 int index =indexOf(p);
162 if(index<0){
163 return false;
164 }
165 insert(index,e);
166 return true;
167 }
168 //在指定元素p后面插入元素e
169 @Override
170 public boolean insertAfter(Object p, Object e) {
171 int index=indexOf(p);
172 if(index<0){
173 return false;
174 }
175 insert(index+1,e);
176 return true;
177 }
178 //检查索引值是否越界
179 private void checkIndex(int i){
180 if(i<0||i>size){
181 throw new IndexOutOfBoundsException(i+"越界");
182 }
183 }
184
185 @Override
186 public String toString() {
187 //依次遍历各个结点,吧元素转化为字符串
188 StringBuilder sb=new StringBuilder();
189 sb.append("[");
190 for(Node node=first;node!=null;node=node.next){
191 sb.append(node.data);
192 if(node!=last){
193 sb.append(",");
194
195 }
196 }
197 sb.append("]");
198 return sb.toString();
199 }
200 //常用对头结点和尾结点的操作
201 //在头部添加元素
202 public void addFirst(Object e){
203 Node pNode = first;
204 //生成一个新的结点
205 Node newNode=new Node(e,null,first);
206 first = newNode; //修改first指向新的结点
207 if(pNode==null){
208 last=newNode;
209 }else{
210 pNode.prev=newNode;
211 }
212 size++; //元素个数加一
213 }
214 //在尾部添加
215 public void addLast(Object e){
216 Node pNode=last;
217 //生成一个新的结点
218 Node newNode=new Node(e,last,null);
219 if(pNode==null){
220 first=newNode;
221 }else{
222 pNode.next=newNode;
223 }
224 last=newNode;
225 size++;
226 }
227 //删除第一个元素,删除头元素
228 public Object removeFirst(){
229 return remove(0);
230 }
231 //删除最后一个元素,尾元素
232 public Object removeLast(){
233 return remove(size-1);
234 }
235 //返回头元素
236 public Object getFirst(){
237 return get(0);
238 }
239 //返回尾元素
240 public Object getLast(){
241 return get(size-1);
242 }
243
244 //定义一个内部类描述双向列表的结点
245 private class Node{
246 Object data;
247 Node prev; //指向前驱结点
248 Node next; //指向后续结点
249 public Node(Object data, Node prev, Node next) {
250 super();
251 this.data = data;
252 this.prev = prev;
253 this.next = next;
254 }
255
256
257 }
258 }
测试类:
1 package demo1;
2 /**
3 * 测试双向列表
4 * @author ASUS
5 *
6 */
7 public class TestDualLinkedList {
8
9 public static void main(String[] args) {
10 //创建双向列表
11 MyDualLinkedList linkedList=new MyDualLinkedList();
12
13 System.out.println(linkedList.getSize());
14 System.out.println(linkedList.isEmpty());
15
16 linkedList.insert(0,"gg");
17 linkedList.insert(0,"jj");
18 linkedList.insert(1,"dd");
19 linkedList.insert(2,"mm");
20
21 System.out.println(linkedList);
22 System.out.println("-------------------");
23 //测试是否包含某个元素及第一次出现的位置
24 System.out.println(linkedList.indexOf("jj"));
25 System.out.println(linkedList.contains("mm"));
26 System.out.println(linkedList.indexOf("MM"));
27 System.out.println(linkedList.indexOf("xx"));
28 System.out.println(linkedList.indexOf("gg"));
29 System.out.println("-------------------");
30 //删除指定的元素
31 System.out.println(linkedList.remove(1));
32 System.out.println(linkedList);
33 System.out.println(linkedList.remove("mm"));
34 System.out.println(linkedList);
35 System.out.println("-------------------");
36 //替换指定元素
37 System.out.println(linkedList.replace(0, "哈哈"));
38 System.out.println(linkedList);
39 //返回指定元素的
40 System.out.println(linkedList.get(0));
41 System.out.println("-------------------");
42
43 //在指定元素前面加入
44 System.out.println(linkedList.insertBefore("哈哈", "前面"));
45 System.out.println(linkedList);
46 //后面
47 System.out.println(linkedList.insertAfter("哈哈", "后面"));
48 System.out.println(linkedList);
49 System.out.println("--------------------");
50 //头部尾部添加删除返回
51 linkedList.addFirst("头部");
52 linkedList.addLast("尾部");
53 System.out.println(linkedList);
54 System.out.println(linkedList.getFirst());
55 System.out.println(linkedList.getLast());
56 //删除头部尾部
57 linkedList.removeFirst();
58 linkedList.removeLast();
59 System.out.println(linkedList);
60
61 }
62
63}
运行截图:
