文章来源：http://www.cnblogs.com/V1haoge/p/8276472.html
手动实现的顺序线性表结构，实现了基本的方法，本地简单测试通过，主要用于理解顺序线性表的结构，还实现了简单的数组扩容，有兴趣的朋友可以看看。
1 package dataStructure;
2
3 import java.io.Serializable;
4
5 /**
6 * 顺序线性表
7 *
8 * @author qe259
9 */
10 public class MyArrayList implements Serializable {
11
12 private static final long serialVersionUID = 5162710183439028792L;
13 private Object[] list;//底层用数组实现
14 private static final Integer INITLEBGTH = 10;//默认的初始化数组长度
15 private static final Double INITFACTOR = 0.75;//默认的初始化增长因子
16 private final Double dilatationFactor = 1.5;//默认的初始化扩容因子
17 private Double factor;//增长因子
18 private Integer length;//数组的长度
19 private Integer nowLength;//当前数组包含元素的长度
20
21 public MyArrayList(){
22 this(INITLEBGTH);
23 }
24
25 public MyArrayList(Integer length){
26 this(length,INITFACTOR);
27 }
28
29 public MyArrayList(Integer length,Double factor){
30 this.length = length == null || length == 0 ? INITLEBGTH : length;
31 this.factor = factor == null || factor > 1 || factor <= 0 ? INITFACTOR : factor;
32 list = new Object[length];
33 nowLength = 0;
34 }
35
36 //数组扩容
37 private void dilatation(){
38 Object[] objs = new Object[(int)(length * dilatationFactor)];
39 for(int i =0,j = 0;i<nowLength;i++,j++){
40 objs[j] = list[i];
41 }
42 list = objs;
43 length = objs.length;
44 }
45
46 //添加元素
47 public void add(Object obj){
48 if((double)nowLength/length >= factor){
49 this.dilatation();
50 }
51 list[nowLength]=obj;
52 nowLength++;
53 }
54
55 //查看元素
56 public Object get(Integer index){
57 if(index<0||index>list.length){
58 throw new NullPointerException();
59 }
60 return list[index];
61 }
62
63 //插入元素
64 public void insert(Integer index,Object obj){
65 if((double)nowLength/length >= factor){
66 this.dilatation();
67 }
68 for(int i = nowLength;i>index;i--){
69 list[i]=list[i-1];
70 }
71 list[index]=obj;
72 nowLength++;
73 }
74
75 //移除元素
76 public void remove(Integer index){
77 if(index<0||index>nowLength-1){
78 throw new NullPointerException();
79 }
80 for(int i = index;i < nowLength-1;){
81 list[i]=list[++i];
82 }
83 list[nowLength-1]=null;
84 nowLength--;
85 }
86
87 //移除指定元素
88 public void remove(Object t){
89 for(int i= 0;i<nowLength;i++){
90 if(get(i)==t) {
91 remove(i);
92 }
93 }
94 }
95
96 //清空元素
97 public void clear(){
98 for(int i = 0;i<nowLength;i++){
99 list[i] = null;
100 }
101 nowLength=0;
102 }
103
104 //包含元素
105 public Boolean contains(Object t){
106 for(int i = 0;i<nowLength;i++){
107 if(list[i] == t){
108 return true;
109 }
110 }
111 return false;
112 }
113
114 @Override
115 public String toString() {
116 StringBuffer s = new StringBuffer("MyArrayList[");
117 for(int i = 0;i<nowLength;i++){
118 s.append(list[i].toString()).append(i==nowLength-1?"":",");
119 }
120 return s.append("]").toString();
121 }
122
123 public static void main(String[] args) {
124 MyArrayList list = new MyArrayList();
125 list.add("1");
126 list.add("2");
127 list.add("3");
128 list.add("4");
129 list.add("5");
130 System.out.println(list.toString());
131 System.out.println(list.contains("3"));
132 list.add("6");
133 list.add("2");
134 list.add("5");
135 System.out.println(list.toString());
136 try{
137 list.remove(10);
138 }catch(NullPointerException e){
139 e.printStackTrace();
140 }
141 System.out.println(list.toString());
142 list.remove(2);
143 System.out.println(list.toString());
144 list.remove("2");
145 System.out.println(list.toString());
146 list.insert(3,"100");
147 System.out.println(list.toString());
148 list.clear();
149 System.out.println(list.toString());
150 list.add("1");
151 list.add("2");
152 list.add("3");
153 list.add("4");
154 list.add("5");
155 list.add("1");
156 list.add("2");
157 list.add("3");
158 list.add("4");
159 list.add("5");
160 System.out.println(list.toString());
161 list.add("100");
162 list.add("100");
163 list.insert(0,"10000");
164 System.out.println(list.toString());
165 }
166 }
顺序线性表，底层以数组来实现，是内存上连续排列的一系列数据，其特点是查询和添加元素比较迅速，但是插入元素和移除元素比较慢，需要遍历数组。
手动实现链表形式线性表：
1 package dataStructure;
2
3 import java.io.Serializable;
4 import java.util.Objects;
5
6 /**
7 * 链式线性表
8 *
9 * @author qe259
10 */
11 public class MyLinkedList implements Serializable {
12
13 //节点
14 private static class Node{
15 Object data;
16 Node next;
17 Node(Object data,Node next){
18 this.data = data;
19 this.next = next;
20 }
21 }
22
23 private static final long serialVersionUID = 5162710183435428792L;
24 private Node start;// = new Node(null,null);
25 private Node end;// = new Node(null,null);
26 private Integer length = 0;
27
28 public MyLinkedList(){
29 end = new Node(null,null);
30 start = new Node(null,end);
31 }
32
33 //添加元素
34 public void add(Object data){
35 if(Objects.isNull(data))
36 throw new NullPointerException();
37 Node transitNode = end;
38 end = new Node(data,null);
39 transitNode.next = end;
40 if(length==0){
41 start.next=end;
42 }
43 length++;
44 }
45
46 //查找指定下标元素
47 public Object get(Integer index){
48 if(index<1||index>length)
49 throw new NullPointerException();
50 Integer count = 0;
51 Node circleNode = start;
52 while(circleNode.next != null){
53 circleNode = circleNode.next;
54 count++;
55 if(count == index){
56 return circleNode.data;
57 }
58 }
59 return null;
60 }
61
62 //包含元素
63 public boolean contains(Object data){
64 boolean isExists = false;
65 Node circleNode = start;
66 while(circleNode.next != null){
67 circleNode = circleNode.next;
68 if(circleNode.data == data || circleNode.data.equals(data)){
69 isExists = true;
70 }
71 }
72 return false;
73 }
74
75 //插入元素
76 public void insert(Integer index,Object... objects){
77 if(index <= 0 || index > length)
78 throw new NullPointerException();
79 Node circleNode = start;
80 Integer count = 0;
81 while(circleNode.next != null){
82 if(count==index-1){
83 Node transitNode = circleNode.next;
84 Node oNode = new Node(objects[0],null);
85 circleNode.next = oNode;
86 if(objects.length==1){
87 oNode.next = transitNode;
88 }
89 length++;
90 for(int i = 1;i<objects.length;i++){
91 if(i==objects.length-1){
92 oNode.next = new Node(objects[i],transitNode);
93 }else{
94 Node transitNode1 = new Node(objects[i],null);
95 oNode.next = transitNode1;
96 oNode = transitNode1;
97 }
98 length++;
99 }
100 break;
101 }
102 count++;
103 circleNode = circleNode.next;
104 }
105 }
106
107 //移除指定下标元素
108 public void remove(Integer index){
109 Node circleNode = start;
110 Integer count = 0;
111 if(index == length){
112 while(circleNode.next !=null){
113 count++;
114 circleNode = circleNode.next;
115 if(count==length-1)break;
116 }
117 circleNode.next=null;
118 end = circleNode;
119 length--;
120 return;
121 }
122 while(circleNode.next != null){
123 count++;
124 circleNode = circleNode.next;
125 if(count==index-1){
126 circleNode.next = circleNode.next.next;
127 length--;
128 break;
129 }
130 }
131 }
132
133 //清空列表
134 public void clear(){
135 Node circleNode = start;
136 while(circleNode.next != null){
137 Node transitNode = circleNode.next;
138 circleNode.next = null;
139 circleNode = transitNode;
140 circleNode.data = null;
141 }
142 length = 0;
143 end = new Node(null,null);
144 start = new Node(null,end);
145 }
146
147 @Override
148 public String toString() {
149 Node circleNode = start;
150 StringBuffer str = new StringBuffer("MyLinkedList[");
151 Integer count = 0;
152 while(circleNode.next != null){
153 count++;
154 circleNode=circleNode.next;
155 if(count == length){
156 str.append(circleNode.data.toString()).append("]");
157 }else{
158 str.append(circleNode.data.toString()).append(",");
159 }
160 }
161 return str.toString();
162 }
163
164 public static void main(String[] args) {
165 // TODO Auto-generated method stub
166 MyLinkedList list = new MyLinkedList();
167 list.add("1");
168 list.insert(1,"111");
169 list.add("2");
170 Object o = list.get(2);
171 list.add("3");
172 list.add("4");
173 list.add("5");
174 list.insert(3, "100","200","300");
175 list.add("13321");
176 list.remove(9);
177 list.remove(4);
178 list.add("asd");
179 list.remove(9);
180 System.out.println(list);
181 list.clear();
182 }
183
184 }
下面是静态链表，采用数组方式实现，适用于无指针和类似指针功能语言来实现：
1 package dataStructure;
2
3 import java.io.Serializable;
4
5 public class MyStaticLinkedList implements Serializable {
6
7 private static final long serialVersionUID = 5143210183435428792L;
8
9 //节点
10 public static class Node{
11 Object data;
12 Integer next;
13 Node(Object data,Integer next){
14 this.data=data;
15 this.next=next;
16 }
17 }
18
19 private static Node[] staticList;
20 private static final Integer ListLength = 1000;
21 private Integer length = 0;//链表长度
22 private Integer useMaxLength = 0;//這個值表示的是數組被占用過的最大下標值
23
24 //无参构造器
25 public MyStaticLinkedList(){
26 this(ListLength);
27 }
28
29 //构造器
30 public MyStaticLinkedList(Integer length){
31 staticList = new Node[length];
32 for(int i = 0;i<length;i++){
33 staticList[i] = new Node(null,i+1);
34 }
35 staticList[length-1].next = 0;
36 }
37
38 //添加元素
39 public void add(Object data){
40 staticList[staticList[0].next].data = data;
41 if(useMaxLength == length){
42 staticList[0].next=++staticList[0].next;
43 if(length == 0){
44 staticList[staticList.length-1].next = 1;
45 }
46 if(staticList[0].next>useMaxLength)
47 useMaxLength++;
48 }else if(useMaxLength > length){//數組存在空位，即數組刪除過其中的元素
49 for(int i = 1;i<=useMaxLength;i++){
50 if(staticList[i].data==null){
51 staticList[staticList[0].next].next=i;
52 staticList[0].next=i;
53 break;
54 }
55 }
56 }else
57 throw new IllegalAccessError();
58 length++;
59 }
60
61 //包含元素
62 public Boolean contains(Object data){
63 Boolean isExists = false;
64 for(int i = 1;i<=useMaxLength;i++){//此處使用useMaxLength有取巧之嫌，本應循環鏈表，而非數組，所以此處查詢到的不一定是鏈表中保存的首個該數據
65 if(staticList[i].data==data||staticList[i].data.equals(data)){
66 isExists = true;
67 break;
68 }
69 }
70 return isExists;
71 }
72
73 /**
74 * 插入元素
75 */
76 public void insert(Integer index,Object data){
77 if(index<=0||index>length)
78 throw new NullPointerException();
79 staticList[staticList[0].next].data = data;
80 Node circleNode = staticList[staticList.length-1];
81 Integer oIndex = 0;//插入位置原节点
82 for(int i = 0;i<=length;i++){//循環鏈錶
83 if(i == index-1){//在首位插入数据，其前节点即为数组最后一位
84 oIndex = circleNode.next;
85 circleNode.next = staticList[0].next;
86 staticList[staticList[0].next].next = oIndex;
87 }
88 circleNode = staticList[circleNode.next];
89 }
90 if(index == 1){
91 staticList[staticList.length-1].next = staticList[0].next;
92 }
93 if(staticList[0].next>useMaxLength)
94 useMaxLength++;
95 //circleNode最后保存的是链表的尾节点这个节点和数组首位的下标一致，指向新的空位节点
96 for(int i = 1;i < staticList.length;i++){
97 if(staticList[i].data==null){
98 staticList[0].next = i;
99 circleNode.next = i;
100 break;
101 }
102 }
103 length++;
104 }
105
106 /**
107 * 移除指定下标元素
108 * @param index
109 */
110 public void remove(Integer index){
111 if(index<=0||index>length)
112 throw new NullPointerException();
113 Node circleNode = staticList[staticList.length-1];
114 Integer oIndex = 0;//删除节点的位置
115 for(int i = 0;i <= length;i++){
116 if(i==index-1){
117 oIndex = circleNode.next;
118 staticList[oIndex].data = null;
119 circleNode.next = staticList[oIndex].next;
120 Integer ooIndex = 0;
121 if(staticList[0].next > oIndex){
122 ooIndex = staticList[0].next;
123 staticList[0].next = oIndex;
124 staticList[oIndex].next = ooIndex;
125 }else{
126 ooIndex = staticList[staticList[0].next].next;
127 if(ooIndex > oIndex){
128 staticList[staticList[0].next].next = oIndex;
129 staticList[oIndex].next = ooIndex;
130 }
131 }
132 }
133 if(i == length-1){
134 circleNode.next = staticList[0].next;
135 }
136 circleNode = staticList[circleNode.next];
137 }
138 length--;
139 }
140
141 public void remove(Object data){
142
143 }
144
145 //清空鏈表
146 public void clear(){
147 for(int i = 0;i <= useMaxLength;i++){
148 staticList[i].data = null;
149 staticList[i].next = i + 1;
150 staticList[staticList.length-1].next = 1;
151 }
152 useMaxLength = 0;
153 length = 0;
154 }
155
156 @Override
157 public String toString() {
158 StringBuffer sb = new StringBuffer("MyStaticLinkedList[");
159 Node circleNode = staticList[staticList.length-1];
160 for(int i = 0;i<length;i++){
161 circleNode = staticList[circleNode.next];
162 sb = i==length-1
163 ?sb.append(circleNode.data.toString())
164 :sb.append(circleNode.data.toString()).append(",");
165 }
166 return sb.append("]").toString();
167 }
168
169 //测试
170 public static void main(String[] args){
171 MyStaticLinkedList list = new MyStaticLinkedList(20);
172 list.add("1");
173 list.add("2");
174 list.add("3");
175 list.add("4");
176 list.add("5");
177 list.add("6");
178 list.remove(5);
179 list.remove(1);
180 list.remove(2);
181 list.add("7");
182 System.out.println(list);
183 list.insert(1,"111");
184 list.insert(2,"222");
185 System.out.println(list.contains("333"));
186 System.out.println(list.contains("3"));
187 list.add("2");
188 System.out.println(list);
189 list.clear();
190 }
191
192 }
所有代码均为本人手工编写，功能经过本人简单测试，如有问题，还请指出，本代码旨在通过练习熟悉线性表的几种实现方式，和其中的复杂度。