数据结构基础--线性表

文章来源：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 }

　　所有代码均为本人手工编写，功能经过本人简单测试，如有问题，还请指出，本代码旨在通过练习熟悉线性表的几种实现方式，和其中的复杂度。