学习完了集合容器,模仿实现了一个LinkedList.Jdk中的LinkedList是一个双向链表,增删改效率比较高,因为比较方便的获取前驱结点.
现在模仿使用的是单向链表.   现在贴上代码. 如有错误,请指正.

接口文件如下:

1. /**
   
2. * <p>Title: ILinearList.java</p>
   
3. * <p>Copyright: Copyright (c) 2015</p>
   
4. * @author possible
   
5. * @version 1.0
   
6. */
   
7. package com.dt.linearlist;
   
8. 
   
9. public interface ILinearList<T> {
   
10. //        /**
    
11. //         * 初始化线性表
    
12. //         *
    
13. //         * @return 返回线性表引用
    
14. //         */
    
15. //        public T initList();
    
16. 
    
17.         /**
    
18.          * 删除线性表
    
19.          *
    
20.          * @return 返回true 销毁成功 false失败
    
21.          */
    
22.         public void destoryList();
    
23. 
    
24.         /**
    
25.          * 判断线性表是否为空
    
26.          *
    
27.          * @return true 链表为空. false 链表不为空
    
28.          */
    
29.         public boolean isEmpty();
    
30. 
    
31.         /**
    
32.          * 线性表长度
    
33.          *
    
34.          * @return 链表长度
    
35.          */
    
36.         public int length();
    
37. 
    
38.         /**
    
39.          * 获取指定索引线性表结点
    
40.          *
    
41.          * @param index
    
42.          *            获取index位置的元素
    
43.          * @return 返回元素 T
    
44.          */
    
45.         public T get(int index);
    
46. 
    
47.         /**
    
48.          * 在指定位置插入元素
    
49.          *
    
50.          * @param i
    
51.          *            插入位置的索引
    
52.          * @param t
    
53.          *            插入的元素
    
54.          * @return true 插入成功, false 插入失败
    
55.          */
    
56.         public boolean add(int index, T t);
    
57. 
    
58.         /**
    
59.          * 删除指定索引的元素
    
60.          *
    
61.          * @param i
    
62.          *            删除指定位置的元素
    
63.          * @return true 删除成功; false 删除失败
    
64.          */
    
65.         public T delete(int index);
    
66. 
    
67.         /**
    
68.          * 线性表遍历
    
69.          *
    
70.          * @return 返回遍历结果
    
71.          */
    
72.         public String traverse();
    
73. 
    
74.         /**
    
75.          * 插入元素结点.
    
76.          *
    
77.          * @param t
    
78.          *            插入结点
    
79.          * @return true 插入成功 ; false 插入失败
    
80.          */
    
81.         public boolean add(T t);
    
82. }
    

复制代码

实现类如下:

1. /**
   
2. * <p>Title: LinkedLinearList.java</p>
   
3. * <p>Copyright: Copyright (c) 2015</p>
   
4. * @version 1.0
   
5. */
   
6. package com.dt.linearlist;
   
7. 
   
8. public class LinkedLinearList<T> implements ILinearList<T> {
   
9.         private Node<T> header;
   
10.         private Node<T> tailer;
    
11.         private Node<T> pre;
    
12. 
    
13.         private int length;
    
14. 
    
15.         public LinkedLinearList() {
    
16.                 header = new Node<T>();
    
17.                 tailer = header;
    
18.         }
    
19. 
    
20.         /**
    
21.          * 销毁单链表.
    
22.          */
    
23.         @Override
    
24.         public void destoryList() {
    
25.                 Node<T> node = header;
    
26.                 while(header.next != null){
    
27.                         header = header.next;
    
28.                         node.next = null;
    
29.                         node.item = null;
    
30.                         node = header;
    
31.                 }
    
32.                
    
33.                 length = 0;
    
34.         }
    
35. 
    
36.         /**
    
37.          * 单链表是否为空
    
38.          */
    
39.         @Override
    
40.         public boolean isEmpty() {
    
41.                 return length() == 0;
    
42.         }
    
43. 
    
44.         /**
    
45.          * 单链表的长度
    
46.          */
    
47.         @Override
    
48.         public int length() {
    
49.                 System.out.println("length = " + length);
    
50.                 return length;
    
51.         }
    
52. 
    
53.         /**
    
54.          * 获取指定索引出的Node
    
55.          */
    
56.         @Override
    
57.         public T get(int index) {
    
58.                 Node<T> node = getElement(index);
    
59.                 System.out.println(node.item);
    
60.                 return node.item;
    
61.         }
    
62. 
    
63.         /**
    
64.          * 在指定索引位置添加Node
    
65.          */
    
66.         @Override
    
67.         public boolean add(int index, T t) {
    
68.                 if (!checkBounds(index)) {
    
69.                         throw new ArrayIndexOutOfBoundsException(checkBoundsMsg(index));
    
70.                 }
    
71. 
    
72.                 Node<T> node = new Node<T>();
    
73.                 node.item = t;
    
74.                 Node<T> pointer = getElement(index);
    
75. 
    
76.                 pre.next = node;
    
77.                 node.next = pointer;
    
78.                 increaseLength();
    
79.                 return true;
    
80.         }
    
81. 
    
82.         /**
    
83.          * 删除指定位置的索引Node
    
84.          */
    
85.         @Override
    
86.         public T delete(int index) {
    
87.                 Node<T> pointer = getElement(index);
    
88.                 pre.next = pointer.next;
    
89.                 // 剪断pointer.next的对下一个结点的引用;
    
90.                 pointer.next = null;
    
91. 
    
92.                 decreaseLength();
    
93.                 return pointer.item;
    
94.         }
    
95. 
    
96.         /**
    
97.          * 单链表遍历.
    
98.          */
    
99.         @Override
    
100.         public String traverse() {
     
101.                 StringBuffer sb = new StringBuffer();
     
102.                 sb.append("开始遍历单链表");
     
103.                 sb.append("\n");
     
104. 
     
105.                 if (header.next == null) {
     
106.                         sb.append("单链表无元素");
     
107.                         sb.append("\n");
     
108.                         sb.append("结束遍历单链表");
     
109. 
     
110.                         return sb.toString();
     
111.                 }
     
112. 
     
113.                 Node<T> pointer = header.next;
     
114.                 while (pointer != null) {
     
115.                         sb.append(pointer.toString());
     
116.                         sb.append("\n");
     
117.                         pointer = pointer.next;
     
118.                 }
     
119.                 sb.append("结束遍历单链表");
     
120.                 System.out.println(sb.toString());
     
121.                 return sb.toString();
     
122.         }
     
123. 
     
124.         /**
     
125.          * 单链表添加元素.尾结点插入法
     
126.          */
     
127.         @Override
     
128.         public boolean add(T t) {
     
129.                 Node<T> node = new Node<T>();
     
130.                 node.item = t;
     
131.                 tailer.next = node;
     
132.                 tailer = node;
     
133.                 increaseLength();
     
134.                 return true;
     
135.         }
     
136. 
     
137.         // 得到指定位置的索引结点.
     
138.         private Node<T> getElement(int index) {
     
139.                 if (!checkBounds(index)) {
     
140.                         throw new ArrayIndexOutOfBoundsException(checkBoundsMsg(index));
     
141.                 }
     
142. 
     
143.                 int counter = 0;
     
144.                 Node<T> pointer = header.next;
     
145.                 // 删除index的前一个结点
     
146.                 pre = header;
     
147.                 while (pointer != null) {
     
148.                         if (counter == index) {
     
149.                                 break;
     
150.                         }
     
151.                         counter++;
     
152.                         // 未找到对应的索引,继续向下查找
     
153.                         pre = pre.next;
     
154.                         pointer = pointer.next;
     
155.                 }
     
156.                 return pointer;
     
157.         }
     
158. 
     
159.         /*
     
160.          * 添加元素,链表长度增加1
     
161.          */
     
162.         private void increaseLength() {
     
163.                 length++;
     
164.         }
     
165. 
     
166.         /*
     
167.          * 删除元素,链表长度减1
     
168.          */
     
169.         private void decreaseLength() {
     
170.                 length--;
     
171.         }
     
172. 
     
173.         private String checkBoundsMsg(int index) {
     
174.                 if (index >= length) {
     
175.                         return "下标越界   " + " length: " + length + " index: " + index;
     
176.                 }
     
177.                 return null;
     
178.         }
     
179. 
     
180.         /**
     
181.          * 检查指定的索引是否越界
     
182.          *
     
183.          * @param index
     
184.          * @return
     
185.          */
     
186.         private boolean checkBounds(int index) {
     
187.                 return index >= 0 && index < length;
     
188.         }
     
189. 
     
190.         /**
     
191.          * 单链表结点
     
192.          *
     
193.          * @author possible
     
194.          *
     
195.          */
     
196.         private static class Node<T> {
     
197.                 /**
     
198.                  * 下一个结点引用
     
199.                  */
     
200.                 Node<T> next;
     
201. 
     
202.                 /**
     
203.                  * 存储的对象
     
204.                  */
     
205.                 T item;
     
206. 
     
207.                 @Override
     
208.                 public String toString() {
     
209.                         return "Node [" + " item=" + item + "]";
     
210.                 }
     
211.         }
     
212. }
     

复制代码

没有人赞, 我自己默默赞一下吧