线性表

类主要方法

1. publicvoiddelete(int index) throws Exception
2. {
3.         //容错性
4.         if(isEmpty()){
5.             thrownewException("顺序表为空，无法删除！");
6.         }
7.         if(index <0|| index > size -1){
8.             thrownewException("参数错误！");
9.         }
10.  
11.         //移动元素（从前往后操作）
12.         for(int j = index; j < size -1; j++)
13.             listArray[j]= listArray[j +1];
14.  
15.         listArray[size -1]= null;      //注意释放内存（避免内存泄漏）
16.         size--;
17. }

1. publicvoid insert(int index,Object obj) throws Exception
2. {
3.         //容错性
4.         if(size == maxSize){
5.             thrownewException("顺序表已满，无法插入！");
6.         }
7.         if(index <0|| index > size){
8.             thrownewException("参数错误！");
9.         }
10.  
11.         //移动元素（从后往前操作）
12.         for(int j = size -1; j >= index; j--)
13.             listArray[j +1]= listArray[j];
14.  
15.         listArray[index]= obj;
16.         size++;
17.  }

1.  //结点类
2.     publicclassNode{
3.         publicObject data;
4.         publicNode next;
5.  
6.         publicNode(Object obj,Node next){
7.             this.data = obj;
8.             this.next = next;
9.         }
10.     }
11.  
12.     Node head;          //记录头结点信息即可（头结点下标为-1）
13.     int size;

1.  //定位
2.     publicNode locate(int index) throws Exception
3.     {
4.         //容错性
5.         if(index <-1|| index > size)
6.             thrownewException("参数错误！");
7.  
8.         //定位到temp指向第index个（index为下标）
9.         Node temp = head;
10.         for(int i =-1; i < index; i++)
11.             if(temp != null)
12.                 temp = temp.next;
13.  
14.         return  temp;
15.     }

1. publicvoiddelete(int index) throws Exception
2.     {
3.         //容错性
4.         if(isEmpty())
5.             thrownewException("链表为空，无法删除！");
6.         if(index <0|| index > size -1)
7.             thrownewException("参数错误！");
8.  
9.         Node temp = locate(index -1);                        //定位到要操作结点的前一个结点对象
10.         temp.next = temp.next.next;
11.         size--;
12.     }

1. publicvoid insert(int index,Object obj) throws Exception
2.     {
3.         //容错性
4.         if(index <0|| index > size )
5.             thrownewException("参数错误！");
6.  
7.         Node temp = locate(index -1);                        //定位到要操作结点的前一个结点对象
8.         Node p =newNode(obj,temp.next);
9.         temp.next = p;
10.         size++;
11.     }

1.  //结点类
2.     publicclassNode{
3.  
4.         publicObject data;
5.         publicNode next;
6.         publicNode prior;
7.  
8.         publicNode(Object obj,Node next,Node prior){
9.             this.data = obj;
10.             this.next = next;
11.             this.prior = prior;
12.         }
13.     }
14.  
15.     Node head;          //记录头结点信息即可（头结点下标为-1）
16.     int size;

1.  publicvoiddelete(int index) throws Exception{
2.  
3.         if(isEmpty())
4.             thrownewException("链表为空，无法删除！");
5.  
6.         if(index <0|| index > size -1)
7.             thrownewException("参数错误！");
8.  
9.         Node temp = locate(index -1);               //定位到要操作结点的前一个结点对象
10.         temp.next = temp.next.next;
11.         if(temp.next != null)                     //当删除到最后一个元素：temp.next == null
12.             temp.next.prior = temp;
13.         size--;
14.     }

1.  publicvoid insert(int index,Object obj) throws Exception{
2.         //容错性
3.         if(index <0|| index > size )
4.             thrownewException("参数错误！");
5.  
6.         Node temp = locate(index -1);               //定位到要操作结点的前一个结点对象
7.         Node p =newNode(obj,temp.next,temp);
8.         temp.next = p;
9.         if(p.next != null)                       //当插入到最后一个位置：p.next == null
10.             p.next.prior = p;
11.         size++;
12.     }

1.  插入删除操作平均移动大约表中一半的元素，对n较大的顺序表效率低。（移动元素涉及内存的写入，消耗较大）
2.  需要预先分配足够大的存储空间：估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。