第三章线性表1（顺序存储和单链表）

3.1线性表及抽象数据类型

线性表的（linear list）是n个类型相同数据元素的有限序列，n定义线性表的长度，n=0为空表。

线性表中相邻的两个元素不一定存储在连续的内存空间中，除非时用数组实现的。

线性表对应的java的集合（List）

  1 package com.datastructure.chapter03;
  2 
  3 /** 
  4  * @ClassName: List 
  5  * @Description: 线性表对应java中的集合List  共11个方法
  6  * @author 
  7  * @date 2018年3月6日 下午11:17:26 
  8  *  
  9  */
 10 public interface List {
 11 
 12     
 13     /** 
 14      * @Title: getSize 
 15      * @Description: 返回线性表的大小，即数据元素的个数 
 16      * @param @return  
 17      * @return int   
 18      * @throws 
 19      */
 20     public int getSize();
 21     
 22     /** 
 23      * @Title: isEmpty 
 24      * @Description:  线性表为空返回true，否则返回false
 25      * @param @return  
 26      * @return boolean   
 27      * @throws 
 28      */
 29     public boolean isEmpty();
 30     
 31     /** 
 32      * @Title: contains 
 33      * @Description:  判断线性表中是否包含某个元素
 34      * @param @param e
 35      * @param @return  
 36      * @return boolean   
 37      * @throws 
 38      */
 39     public boolean contains(Object e);
 40     
 41     /** 
 42      * @Title: indexOf 
 43      * @Description:  返回数据元素e在线性表中的序号
 44      * @param @param e
 45      * @param @return  
 46      * @return int   
 47      * @throws 
 48      */
 49     public int indexOf(Object e);
 50     
 51     /** 
 52      * @Title: insert 
 53      * @Description:  将数据元素e插入到线性表i号位置
 54      * @param @param i
 55      * @param @param e
 56      * @param @throws Exception  下标越界的异常 
 57      * @return void   
 58      * @throws 
 59      */
 60     public void insert(int i,Object e) throws Exception;
 61     
 62     
 63     /** 
 64      * @Title: insertBefore 
 65      * @Description: 将数据元素e插入到元素obj之前 
 66      * @param @param obj
 67      * @param @param e
 68      * @param @return  
 69      * @return boolean   
 70      * @throws 
 71      */
 72     public boolean insertBefore(Object obj,Object e);
 73     
 74     
 75     /** 
 76      * @Title: insertAfter 
 77      * @Description: 将数据元素e插入到元素obj之后
 78      * @param @param obj
 79      * @param @param e
 80      * @param @return  
 81      * @return boolean   
 82      * @throws 
 83      */
 84     public boolean insertAfter(Object obj,Object e);
 85     
 86     /**
 87      * s
 88      * @Title: remove 
 89      * @Description: 删除序号为i的元素
 90      * @param @param i
 91      * @param @return
 92      * @param @throws Exception 下标越界的异常  
 93      * @return Object   
 94      * @throws
 95      */
 96     public Object remove(int i) throws Exception;
 97     
 98     
 99     /** 
100      * @Title: remove 
101      * @Description:  移除线性表中与e相同元素
102      * @param @param e
103      * @param @return  
104      * @return boolean   
105      * @throws 
106      */
107     public boolean remove(Object e);
108     
109     /** 
110      * @Title: replace 
111      * @Description:  替换表中序号为i的元素，返回原数据元素
112      * @param @param i
113      * @param @param e
114      * @param @return
115      * @param @throws Exception  
116      * @return Object   
117      * @throws 
118      */
119     public Object replace(int i,Object e) throws Exception;
120     
121     /**
122      * 
123      * @Title: get 
124      * @Description:  返回线性表中序号为i的元素
125      * @param @param i
126      * @param @return
127      * @param @throws Exception  
128      * @return Object   
129      * @throws
130      */
131     public Object get(int i) throws Exception;
132     
133     
134     
135     
136 }

View Code

list接口中异常的类：

 1 package com.datastructure.chapter03;
 2 
 3 /** 
 4  * @ClassName: OutOfBoundaryException 
 5  * @Description: 角标越界的异常
 6  * @author 
 7  * @date 2018年3月8日 下午10:52:36 
 8  *  
 9  */
10 @SuppressWarnings("serial")
11 public class OutOfBoundaryException extends RuntimeException {
12     
13     public OutOfBoundaryException(String err){
14         super(err);
15     }
16     
17 }

View Code

由于list接口中的所有元素都是Object，不利于比较；比如：String的compareTo与equal，基本类型的数据用关系运算符进行比较；所以要制定一个比较策略，抽出一个比较的接口

 1 package com.datastructure.chapter03;
 2 
 3 public interface Strategy {
 4     
 5     /** 
 6      * @Title: equal 
 7      * @Description:  判断两个元素是否相等
 8      * @param @param obj1
 9      * @param @param obj2
10      * @param @return  
11      * @return boolean   
12      * @throws 
13      */
14     public boolean equal(Object obj1,Object obj2);
15     
16     
17     
18     /** 
19      * @Title: compare 
20      * @Description:  obj1>obj2 返回1
21      * @param @param obj1
22      * @param @param obj2
23      * @param @return  
24      * @return int   
25      * @throws 
26      */
27     public int compare(Object obj1,Object obj2);
28     
29 }

View Code

比如下面的学生类：

 1 package com.datastructure.chapter03;
 2 
 3 /** 
 4  * @ClassName: Student 
 5  * @Description: 学生类
 6  * @author 
 7  * @date 2018年3月8日 下午11:02:08 
 8  *  
 9  */
10 public class Student {
11     
12     private String sId;
13 
14     public String getsId() {
15         return sId;
16     }
17 
18     public void setsId(String sId) {
19         this.sId = sId;
20     }
21     
22     
23 }

View Code

比较实现类：

 1 package com.datastructure.chapter03;
 2 
 3 /** 
 4  * @ClassName: StudentStrategy 
 5  * @Description: 具体的比较实现类
 6  * @author 
 7  * @date 2018年3月8日 下午11:07:44 
 8  *  
 9  */
10 public class StudentStrategy implements Strategy {
11 
12     @Override
13     public boolean equal(Object obj1, Object obj2) {
14         
15         if(obj1 instanceof Student && obj2 instanceof Student){
16             
17             Student s1 = (Student) obj1;
18             
19             Student s2 = (Student) obj2;
20             
21             return s1.getsId().equals(s2.getsId());
22         }
23         return false;
24     }
25 
26     @Override
27     public int compare(Object obj1, Object obj2) {
28         
29         if(obj1 instanceof Student && obj2 instanceof Student){
30             Student s1 = (Student) obj1;
31             Student s2 = (Student) obj2;
32             return s1.getsId().compareTo(s2.getsId());
33         }else{
34             return obj1.toString().compareTo(obj2.toString());
35         }
36         
37     }
38 
39 }

View Code

3.2 线性表的顺序存储与实现

线性表的顺序存储是用一组地址连续的存储单元依次存储线性表的数据元素。

线性表中序号为i的数据元素的存储地址LOC(a_i)与序号为i+1的数据元素的存储地址LOC（a_i+1）之间的关系为：LOC（a_i+1） = LOC(a_i) + K（每个元素占用K个存储单元）；数组是采用顺序存储的结构。若是线性表中存储的是对象时，数组存放的是对象的引用。

线性表的顺序存储的特点：以数据元素在机内存储地址相邻来表示线性表中数据元素之间的逻辑关系。

线性表的顺讯存储的实例ListArray:

  1 package com.datastructure.chapter03.interfacesImpl;
  2 
  3 import com.datastructure.chapter03.exception.OutOfBoundaryException;
  4 import com.datastructure.chapter03.interfaces.List;
  5 import com.datastructure.chapter03.interfaces.Strategy;
  6 
  7 public class ListArray implements List {
  8 
  9     private final int LEN = 8;// 数组的默认大小
 10 
 11     private Strategy strategy;// 数据元素比较策略
 12 
 13     private int size;
 14 
 15     private Object[] elements;// 数据元素数组
 16 
 17     public ListArray() {
 18         this(new DefaultStrategy());
 19     }
 20 
 21     public ListArray(Strategy strategy) {
 22         this.strategy = strategy;
 23         size = 0;
 24         elements = new Object[LEN];
 25     }
 26 
 27     /*
 28      * (非 Javadoc) <p>Title: getSize</p> <p>Description: 返回线性表的大小，即数据元素的个数</p>
 29      * 
 30      * @return
 31      * 
 32      * @see com.datastructure.chapter03.interfaces.List#getSize()
 33      */
 34     @Override
 35     public int getSize() {
 36         return size;
 37     }
 38 
 39     /*
 40      * (非 Javadoc) <p>Title: isEmpty</p> <p>Description:
 41      * 如果线性表为空返回true，否则返回false</p>
 42      * 
 43      * @return
 44      * 
 45      * @see com.datastructure.chapter03.interfaces.List#isEmpty()
 46      */
 47     @Override
 48     public boolean isEmpty() {
 49         return size == 0;
 50     }
 51 
 52     /*
 53      * (非 Javadoc) <p>Title: contains</p> <p>Description: 判断线性表是否包含数据元素e</p>
 54      * 
 55      * @param e
 56      * 
 57      * @return
 58      * 
 59      * @see
 60      * com.datastructure.chapter03.interfaces.List#contains(java.lang.Object)
 61      */
 62     @Override
 63     public boolean contains(Object e) {
 64 
 65         for (int i = 0; i < size; i++)
 66             if (strategy.equal(e, elements[i]))
 67                 return true;
 68         return false;
 69     }
 70 
 71     /* (非 Javadoc) 
 72      * <p>Title: indexOf</p> 
 73      * <p>Description: 返回数据元素e在线性表中的序号</p> 
 74      * @param e
 75      * @return 
 76      * @see com.datastructure.chapter03.interfaces.List#indexOf(java.lang.Object) 
 77      */
 78     @Override
 79     public int indexOf(Object e) {
 80         for(int i=0;i<size;i++)
 81             if(strategy.equal(e, elements[i]))
 82                 return i;
 83         return -1;
 84     }
 85 
 86     /* (非 Javadoc) 
 87      * <p>Title: insert</p> 
 88      * <p>Description: 将数据元素e插入到线性表中i号位置</p> 
 89      * @param i
 90      * @param e
 91      * @throws OutOfBoundaryException 
 92      * @see com.datastructure.chapter03.interfaces.List#insert(int, java.lang.Object) 
 93      */
 94     @Override
 95     public void insert(int i, Object e) throws OutOfBoundaryException {
 96         if(i<0||i>size)
 97             throw new OutOfBoundaryException("错误，指定的插入序号越界");
 98         
 99         if(size >= elements.length)
100             expandSpace();
101         for(int j=size;j>i;j--)
102             elements[j] = elements[j-1];
103         elements[i] = e; size++;
104         return ;
105     }
106 
107     /** 
108      * @Title: expandSpace 
109      * @Description: 进行数组扩容 
110      * @param   
111      * @return void   
112      * @throws 
113      */
114     private void expandSpace() {
115         Object[] a = new Object[elements.length*2];
116         for(int i=0;i<elements.length;i++)
117             a[i] = elements[i];
118         elements = a;
119     }
120 
121     /* (非 Javadoc) 
122      * <p>Title: insertBefore</p> 
123      * <p>Description: 将数据袁术e插入到元素obj之前</p> 
124      * @param obj
125      * @param e
126      * @return 
127      * @see com.datastructure.chapter03.interfaces.List#insertBefore(java.lang.Object, java.lang.Object) 
128      */
129     @Override
130     public boolean insertBefore(Object obj, Object e) {
131         int i = indexOf(obj);
132         if(i<0)return false;
133         insert(i,e);
134         return true;
135     }
136 
137     /* (非 Javadoc) 
138      * <p>Title: insertAfter</p> 
139      * <p>Description: 插入到元素obj之后</p> 
140      * @param obj
141      * @param e
142      * @return 
143      * @see com.datastructure.chapter03.interfaces.List#insertAfter(java.lang.Object, java.lang.Object) 
144      */
145     @Override
146     public boolean insertAfter(Object obj, Object e) {
147         int i = indexOf(obj);
148         if(i<0)return false;
149         insert(i+1,e);
150         return true;
151     }
152 
153     /* (非 Javadoc) 
154      * <p>Title: remove</p> 
155      * <p>Description: 删除线性表中序号为i的元素，并返回之</p> 
156      * @param i
157      * @return
158      * @throws OutOfBoundaryException 
159      * @see com.datastructure.chapter03.interfaces.List#remove(int) 
160      */
161     @Override
162     public Object remove(int i) throws OutOfBoundaryException {
163         if(i<0 || i>size)
164             throw new OutOfBoundaryException("错误,指定的删除序号越界");
165         Object obj = elements[i];
166         for (int j = i; j < size - 1; j++) 
167             elements[j] = elements[j+1];
168         elements[--size] = null;
169         return obj;
170     }
171 
172     /* (非 Javadoc) 
173      * <p>Title: remove</p> 
174      * <p>Description: 删除线性表中第一个与e相同的元素</p> 
175      * @param e
176      * @return 
177      * @see com.datastructure.chapter03.interfaces.List#remove(java.lang.Object) 
178      */
179     @Override
180     public boolean remove(Object e) {
181         int i = indexOf(e);
182         if(i<0) return false;
183         remove(i);
184         return true;
185     }
186 
187     /* (非 Javadoc) 
188      * <p>Title: replace</p> 
189      * <p>Description: 替换线性表中序号为i的数据元素为e，返回原数据元素</p> 
190      * @param i
191      * @param e
192      * @return
193      * @throws OutOfBoundaryException 
194      * @see com.datastructure.chapter03.interfaces.List#replace(int, java.lang.Object) 
195      */
196     @Override
197     public Object replace(int i, Object e) throws OutOfBoundaryException {
198         if(i<0|| i>=size)
199             throw new OutOfBoundaryException("错误，指定的序号越界");
200         
201         Object obj = elements[i];
202         elements[i] = e;
203         return obj;
204     }
205 
206     /* (非 Javadoc) 
207      * <p>Title: get</p> 
208      * <p>Description: 返回线性表中序号为i的数据元素</p> 
209      * @param i
210      * @return
211      * @throws OutOfBoundaryException 
212      * @see com.datastructure.chapter03.interfaces.List#get(int) 
213      */
214     @Override
215     public Object get(int i) throws OutOfBoundaryException {
216         if(i<0 || i>=size)
217             throw new OutOfBoundaryException("错误，指定的序号越界。");
218         return elements[i];
219     }
220 
221 }

View Code

默认的策略类DefaultStrategy类的实现:

 1 package com.datastructure.chapter03.interfacesImpl;
 2 
 3 import com.datastructure.chapter03.interfaces.Strategy;
 4 
 5 public class DefaultStrategy implements Strategy {
 6 
 7     /* (非 Javadoc) 
 8      * <p>Title: equal</p> 
 9      * <p>Description: 比较的方法(自己写的，不是书上的)</p> 
10      * @param obj1
11      * @param obj2
12      * @return 
13      * @see com.datastructure.chapter03.interfaces.Strategy#equal(java.lang.Object, java.lang.Object) 
14      */
15     @Override
16     public boolean equal(Object obj1, Object obj2) {
17         if (obj1 == null)
18             return obj2 == null;
19         if (obj2 == null)
20             return obj1 == null;
21         if(obj1.equals(obj2))
22             return true;
23         return false;
24     }
25 
26     @Override
27     public int compare(Object obj1, Object obj2) {
28         //不晓得怎么写
29         
30         return 0;
31     }
32 
33 }

View Code

3.3 线性表的链式存储与实现

3.3.1 单链表

链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少由两个域，一个域用于数据的存储，另一个域用于指向其他的单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为节点（node）。

节点的接口Node：

 1 package com.datastructure.chapter03.interfaces;
 2 
 3 public interface Node {
 4     
 5     /** 
 6      * @Title: getData 
 7      * @Description:  获取结点数据域
 8      * @param @return  
 9      * @return Object   
10      * @throws 
11      */
12     public Object getData();
13     
14     
15     /** 
16      * @Title: setData 
17      * @Description:  设置节点数据域
18      * @param @param obj  
19      * @return void   
20      * @throws 
21      */
22     public void setData(Object obj);
23     
24     
25 }

View Code

单链表节点的定义SLNode：

 1 package com.datastructure.chapter03.interfacesImpl;
 2 
 3 import com.datastructure.chapter03.interfaces.Node;
 4 
 5 public class SLNode implements Node {
 6 
 7     
 8     private Object element;
 9     
10     private SLNode next;
11     
12     public SLNode() {
13         this(null,null);
14     }
15     
16     
17     public SLNode(Object ele, SLNode next) {
18         this.element = ele;
19         this.next = next;
20     }
21 
22 
23     @Override
24     public Object getData() {
25         return element;
26     }
27 
28     @Override
29     public void setData(Object obj) {
30         element = obj;
31     }
32 
33 
34     public SLNode getNext() {
35         return next;
36     }
37 
38 
39     public void setNext(SLNode next) {
40         this.next = next;
41     }
42     
43     
44     
45 
46 }

View Code

单链表没有直接前驱，有直接后驱。删除和插入效率较高。

3.3.2 双向链表

双向链表节点的定义DLNode：

 1 package com.datastructure.chapter03.interfacesImpl;
 2 
 3 import com.datastructure.chapter03.interfaces.Node;
 4 
 5 public class DLNode implements Node {
 6 
 7     private Object element;
 8     
 9     private DLNode pre;
10     
11     private DLNode next;
12     
13     
14     public DLNode() {
15         this(null,null,null);
16     }
17     
18     public DLNode(Object ele, DLNode pre, DLNode next) {
19         this.element = ele;
20         this.pre = pre;
21         this.next = next;
22     }
23 
24     public DLNode getPre() {
25         return pre;
26     }
27 
28     public void setPre(DLNode pre) {
29         this.pre = pre;
30     }
31 
32     public DLNode getNext() {
33         return next;
34     }
35 
36     public void setNext(DLNode next) {
37         this.next = next;
38     }
39 
40     @Override
41     public Object getData() {
42         return element;
43     }
44 
45     @Override
46     public void setData(Object obj) {
47         element = obj;
48     }
49 
50 }

View Code

3.3.3线性表的单链表实现

单链表的实现代码：

  1 package com.datastructure.chapter03.interfacesImpl;
  2 
  3 import com.datastructure.chapter03.exception.OutOfBoundaryException;
  4 import com.datastructure.chapter03.interfaces.List;
  5 import com.datastructure.chapter03.interfaces.Strategy;
  6 
  7 /**
  8  * @ClassName: ListSLinked
  9  * @Description: 单链表的实现
 10  * @author
 11  * @date 2018年3月15日 下午7:26:49
 12  * 
 13  */
 14 public class ListSLinked implements List {
 15 
 16     private Strategy strategy;// 数据元素比较策略
 17 
 18     private SLNode head; // 单链表首节点引用
 19 
 20     private int size; // 线性表中数据元素的个数
 21 
 22     public ListSLinked() {
 23         this(new DefaultStrategy());
 24     }
 25 
 26     public ListSLinked(Strategy strategy) {
 27         this.strategy = strategy;
 28         head = new SLNode();// 头结点
 29         size = 0;
 30     }
 31 
 32     /*
 33      * (非 Javadoc) <p>Title: getSize</p> <p>Description: 获得单链表的长度</p>
 34      * 
 35      * @return
 36      * 
 37      * @see com.datastructure.chapter03.interfaces.List#getSize()
 38      */
 39     @Override
 40     public int getSize() {
 41 
 42         return size;
 43     }
 44 
 45     /*
 46      * (非 Javadoc) <p>Title: isEmpty</p> <p>Description:
 47      * 如果线性表为空返回true，否则返回false</p>
 48      * 
 49      * @return
 50      * 
 51      * @see com.datastructure.chapter03.interfaces.List#isEmpty()
 52      */
 53     @Override
 54     public boolean isEmpty() {
 55 
 56         return size == 0;
 57     }
 58 
 59     /*
 60      * (非 Javadoc) <p>Title: contains</p> <p>Description: 判断线性表中是否包含数据元素e</p>
 61      * 
 62      * @param e
 63      * 
 64      * @return
 65      * 
 66      * @see
 67      * com.datastructure.chapter03.interfaces.List#contains(java.lang.Object)
 68      */
 69     @Override
 70     public boolean contains(Object e) {
 71         SLNode p = head.getNext();
 72         while (p != null) {
 73             if (strategy.equal(p.getData(), e))
 74                 return true;// 遇到第一个包含的就返回true
 75             else
 76                 p = p.getNext();// 否则将p的引用下移一位
 77 
 78         }
 79         return false;
 80     }
 81 
 82     /*
 83      * (非 Javadoc) <p>Title: indexOf</p> <p>Description:获得某个元素线性表中的序号 </p>
 84      * 
 85      * @param e
 86      * 
 87      * @return
 88      * 
 89      * @see
 90      * com.datastructure.chapter03.interfaces.List#indexOf(java.lang.Object)
 91      */
 92     @Override
 93     public int indexOf(Object e) {
 94         SLNode p = head.getNext();
 95         int index = 0;
 96         while (p != null)
 97             if (strategy.equal(p.getData(), e))
 98                 return index;
 99             else {
100                 index++;
101                 p = p.getNext();
102             }
103         return -1;
104     }
105 
106     /* (非 Javadoc) 
107      * <p>Title: insert</p> 
108      * <p>Description: </p> 
109      * @param i
110      * @param e
111      * @throws OutOfBoundaryException 
112      * @see com.datastructure.chapter03.interfaces.List#insert(int, java.lang.Object) 
113      */
114     @Override
115     public void insert(int i, Object e) throws OutOfBoundaryException {
116         if (i < 0 || i > size)
117             throw new OutOfBoundaryException("错误，指定的插入序号越界。");
118         SLNode p = getPreNode(i);
119         SLNode q = new SLNode(e,p.getNext());//构造新节点，并且将插入前的前一个节点的后一个节点置于新节点的后面
120         p.setNext(q);//将前一个节点的下一个节点链接到新节点上
121         size++;
122         return ;
123     }
124 
125     /* (非 Javadoc) 
126      * <p>Title: insertBefore</p> 
127      * <p>Description: 插入在某个元素之前</p> 
128      * @param obj
129      * @param e
130      * @return 
131      * @see com.datastructure.chapter03.interfaces.List#insertBefore(java.lang.Object, java.lang.Object) 
132      */
133     @Override
134     public boolean insertBefore(Object obj, Object e) {
135         SLNode p = getPreNode(obj);
136         if(p!=null){
137             SLNode n = new SLNode(e, p.getNext());
138             p.setNext(n);
139             size++;
140             return true;
141         }
142         
143         return false;
144     }
145 
146     
147 
148     /* (非 Javadoc) 
149      * <p>Title: insertAfter</p> 
150      * <p>Description: 在某个元素后面插入一个元素</p> 
151      * @param obj
152      * @param e
153      * @return 
154      * @see com.datastructure.chapter03.interfaces.List#insertAfter(java.lang.Object, java.lang.Object) 
155      */
156     @Override
157     public boolean insertAfter(Object obj, Object e) {
158         SLNode p = head.getNext();
159         while(p!=null){
160             if(strategy.equal(p.getData(), obj)){
161                 SLNode q = new SLNode(e, p.getNext());
162                 p.setNext(q);
163                 size++;
164                 return true;
165             }else
166                 p = p.getNext();
167         }
168         
169         return false;
170     }
171 
172     /* (非 Javadoc) 
173      * <p>Title: remove</p> 
174      * <p>Description: 删除指定位置的数据元素</p> 
175      * @param i
176      * @return
177      * @throws OutOfBoundaryException 
178      * @see com.datastructure.chapter03.interfaces.List#remove(int) 
179      */
180     @Override
181     public Object remove(int i) throws OutOfBoundaryException {
182         
183         if(i<0||i>size)
184             throw new OutOfBoundaryException("错误，指定删除序号越界!");
185         
186         SLNode p = getPreNode(i);
187         Object obj = p.getNext().getData();
188         p.setNext(p.getNext().getNext());
189         size--;
190         return obj;
191     }
192 
193     /* (非 Javadoc) 
194      * <p>Title: remove</p> 
195      * <p>Description: 删除某一个元素</p> 
196      * @param e
197      * @return 
198      * @see com.datastructure.chapter03.interfaces.List#remove(java.lang.Object) 
199      */
200     @Override
201     public boolean remove(Object e) {
202         SLNode p = getPreNode(e);
203         if(p!=null){
204             p.setNext(p.getNext().getNext());
205             size--;
206             return true;
207         }
208         return false;
209     }
210 
211     /* (非 Javadoc) 
212      * <p>Title: replace</p> 
213      * <p>Description: 替换指定位置的数据元素</p> 
214      * @param i
215      * @param e
216      * @return
217      * @throws OutOfBoundaryException 
218      * @see com.datastructure.chapter03.interfaces.List#replace(int, java.lang.Object) 
219      */
220     @Override
221     public Object replace(int i, Object e) throws OutOfBoundaryException {
222         if(i<0||i>size)
223             throw new OutOfBoundaryException("错误，指定的序号越界!");
224         SLNode p = getNode(i);//
225         Object data = p.getData();
226         p.setData(e);
227         return data;
228     }
229 
230     
231 
232     /* (非 Javadoc) 
233      * <p>Title: get</p> 
234      * <p>Description: 获得指定位置的数据元素</p> 
235      * @param i
236      * @return
237      * @throws OutOfBoundaryException 
238      * @see com.datastructure.chapter03.interfaces.List#get(int) 
239      */
240     @Override
241     public Object get(int i) throws OutOfBoundaryException {
242         if(i<0||i>size)
243             throw new OutOfBoundaryException("错误，指定的序号越界!");
244         SLNode p = getNode(i);//
245         return p.getData();
246     }
247 
248     /** 
249      * @Title: getPreNode 
250      * @Description:  获得指定位置的前一个节点
251      * @param @param i
252      * @param @return  
253      * @return SLNode   
254      * @throws 
255      */
256     private SLNode getPreNode(int i) {
257         SLNode p = head;
258         for (; i > 0; i--)
259             p = p.getNext();
260         return p;
261     }
262     
263     
264     /** 
265      * @Title: getPreNode 
266      * @Description:  获得某个数据元素的前一个节点
267      * @param @param obj
268      * @param @return  
269      * @return SLNode   
270      * @throws 
271      */
272     private SLNode getPreNode(Object obj) {
273         SLNode p = head;
274         while(p.getNext()!=null){
275             if(strategy.equal(p.getData(), obj))
276                 return p;
277             else
278                 p = p.getNext();
279         }
280         return null;
281     }
282     
283     /** 
284      * @Title: getNode 
285      * @Description:  获得指定位置的节点
286      * @param @param i
287      * @param @return  
288      * @return SLNode   
289      * @throws 
290      */
291     private SLNode getNode(int i) {
292         SLNode p = head.getNext();
293         for(;i>0;i--) p = p.getNext(); 
294         return p;
295     }
296 
297 }

View Code

getPreNode(Object e)、getPreNode(int i)，这两个防范的平均运行时间T(n)≈n/2。

replace(int i,Object e)、get(int i)算法的平均运行时间T(n)≈n/2。比数组慢

insert(int i,Object e)、remove(int i)，平均运行时间T(n)≈n/2。与使用数组实现的运行时间相同。

insertBefore(Object obj,Object e)、insertAfter(IObject obj,Object e),remove(Object e),平均运行时间T(n)≈n/2<n,要由于使用数组实现的运行时间。

3.4 两种实现的对比

　 3.4.1基于时间的比较

线性表的基本操作查找、插入、删除

　查找：基于序号的查找，数组是随机存储的，线性表的顺序存储可以在常数时间内完成；而在链式存储中由于需要从头结点开始顺着链表才能取得，无法在常数时间内完成，因此顺序存储优于链式存储。查找还有基于元素的查找，而顺序存储和链式存储在这种情况先军事从线性表中序号为0的元素开始查找，因此两种实现性能相同。若是，在线性表的使用中主要操作是查找，那么应当选用顺序存储实现线性表。

插入、删除：基于数据元素的操作，对于数组而言，首先顺序查找定位相应数据元素，然后才能插入，删除，并且在插入、删除郭晨又要移动大量元素；而链表在定位数据元素的基础上，只需要修改指针就可以了，效率要高。基于序号的操作，顺序存储中平均需要移动一半的数据；链式存储中不能直接定位，平均比较一般的元素才能定位。因此，二者，效率相当。但综合起来，链式增删好些。

3.4.2基于空间的比较

当数据较大时，顺序存储的线性表由于动态扩展出的存储空间被大量空闲，利用率不高；而链式不存在这种情况，所以数据量大的时候，宜用链式。

当数元素结构简单，且数据量小的时候，链式由于用额外的空间来表示数据元素之间的逻辑关系。所以开销较大。此时，顺序存储较好。

第三章 线性表1（顺序存储和单链表）

第三章线性表1（顺序存储和单链表）