数据结构之线性表之顺序表和链表(通过数据结构角度深入理解arrayList和linkedList的特性)

时间:2021-05-03 10:22:00

数据结构广义上说包含两个维度:逻辑结构 、 存储结构

     逻辑结构主要有:一对一:线性表,一对多:树,多对多:图

     存储结构:顺序存储,链式存储,索引存储,散列存储(hashcode)


    对于线性表:逻辑结构上是最简单的一对一的关系 ,存储上可能包含顺序存储和链式存储,具体有:线性表、链表(单链、双链、循环链)、栈、队列


   顺序表:按顺序存储    可以通过指针快速定位

                   优点:可以直接按顺序定位  、添加快、修改快

                  缺点:插入、删除慢,需要移动后续所有

                    

  链表:链式存储         对本身

                   优点:插入、删除快 、添加快

                  缺点:不能按顺序直接定位、修改慢


概念太抽象,举个粒子给大家吃:

java的list接口的两个实现:arrayList 和linkedList 就是这两个存储的很好的代表:

                arrayList采用的是顺序表存存储实现

                 linkedList采用的是链表存储(JDK中是双链表)

照着JDK,通过自己编写List的实现类,成就感不由而生,感觉棒棒哒~~


arrayList实现

              package com.tiger.list;

/** 
 * 自己用数组实现的线性表 
 */  
public class TigerArrayList<E> {  
    Object[] data = null;// 用来保存此队列中内容的数组  
    int current;        // 保存当前为第几个元素的指标  
    int capacity;        // 表示数组大小的指标  
       
    /** 
     * 如果初始化时,未声明大小,则默认为10 
     */  
    public TigerArrayList() {  
        this(10);  
    }  
  
    /** 
     * 初始化线性表,并且声明保存内容的数组大小 
     * @param initalSize 
     */  
    public TigerArrayList(int initalSize) {  
        if (initalSize < 0) {  
            throw new RuntimeException("数组大小错误:" + initalSize);  
        } else {  
            this.data = new Object[initalSize];  
            this.current = 0;  
            capacity = initalSize;  
        }  
    }  
  
    /** 
     * 添加元素的方法 添加前,先确认是否已经满了 
     * @param e 
     * @return 
     */  
    public boolean add(E e) {  
        ensureCapacity(current);// 确认容量  
        this.data[current] = e;  
        current++;  
        return true;  
    }  
  
    /** 
     * 确认系统当前容量是否满足需要,如果满足,则不执行操作 如果不满足,增加容量 
     * @param cur 当前个数 
     */  
    private void ensureCapacity(int cur) {  
        if (cur == capacity) {  
            // 如果达到容量极限,增加10的容量,复制当前数组  
            this.capacity = this.capacity*2;  
            Object[] newdata = new Object[capacity];  
            for (int i = 0; i < cur; i++) {  
                newdata[i] = this.data[i];  
            }  
            this.data = newdata;  
        }  
    }  
  
    /** 
     * 得到指定下标的数据 
     * @param index 
     * @return 
     */  
    public E get(int index) {  
        validateIndex(index);  
        return (E) this.data[index];  
    }  
       
   /** 
    * 返回当前队列大小
    * @return 
    */  
    public int size() {  
        return this.current;  
    }  
  
    /** 
     * 更改指定下标元素的数据为e 
     * @param index  
     * @param e 
     * @return 
     */  
    public boolean set(int index, E e) {  
        validateIndex(index);  
        this.data[index] = e;  
        return true;  
    }  
     
    /** 
     *  验证当前下标是否合法,如果不合法,抛出运行时异常 
     * @param index 下标 
     */  
    private void validateIndex(int index) {  
        if (index < 0 || index > current) {  
            throw new RuntimeException("数组index错误:" + index);  
        }  
    }  
  
    /** 
     * 在指定下标位置处插入数据e 
     * @param index 下标 
     * @param e 需要插入的数据 
     * @return  
     */  
    public boolean insert(int index, E e) {  
        validateIndex(index);  
        Object[] tem = new Object[capacity];// 用一个临时数组作为备份  
        //开始备份数组  
        for (int i = 0; i < current; i++) {  
            if (i < index) {  
                tem[i] = this.data[i];  
            }else if(i==index){  
                tem[i]=e;  
            }else if(i>index){  
                tem[i]=this.data[i-1];  
            }  
        }  
        this.data=tem;  
        return true;  
    }  
     /**  * 删除指定下标出的数据<br>    
      * @param index<br>  
      * @return<br>   
      */
     public boolean delete(int index){
          validateIndex(index);
          Object[] tem = new Object[capacity];// 用一个临时数组作为备份
          //开始备份数组
         for (int i = 0; i < current; i++) { 
                if (i < index) {
                    tem[i] = this.data[i];
                }else if(i==index){
                    tem[i]=this.data[i+1];
                }else if(i>index){
                    tem[i]=this.data[i+1];
                }
            }
          this.data=tem;
          return true;
     }
}  


             linkedList实现


package com.tiger.list;


/** 
 * 自己用链式存储实现的线性表 
 */  
public class TigerLinkedList<E> {  
  
    private Node<E> header = null;// 头结点  
    private Node<E> last = null;// 头结点  
    int size = 0;// 表示数组大小的指标  
  
    public TigerLinkedList() {  
        this.header = new Node<E>();  
        this.last = new Node<E>();  
    }  
  
    public boolean add(E e) {  
        if (size == 0) {  
            header.e = e;  
        } else {  
            // 根据需要添加的内容,封装为结点  
            Node<E> newNode = new Node<E>(e);  
            // 得到当前最后一个结点  
           // Node<E> last = getNode(size-1);  
            // 在最后一个结点后加上新结点  
            last.addNext(newNode);  
            last=newNode;
        }  
        
        size++;// 当前大小自增加1  
        return true;  
    }  
  
    public boolean insert(int index, E e) {  
        Node<E> newNode = new Node<E>(e);  
        // 得到第N个结点  
        Node<E> cNode = getNode(index);  
        newNode.next = cNode.next;  
        cNode.next = newNode;  
        size++;  
        return true;  
    }  
  
    /** 
     * 遍历当前链表,取得当前索引对应的元素 
     *  
     * @return 
     */  
    private Node<E> getNode(int index) {  
        // 先判断索引正确性  
        if (index > size || index < 0) {  
            throw new RuntimeException("索引值有错:" + index);  
        }  
        Node<E> tem = new Node<E>();  
        tem = header;  
        int count = 0;  
        while (count != index) {  
            tem = tem.next;  
            count++;  
        }  
        return tem;  
    }  
  
    /** 
     * 根据索引,取得该索引下的数据 
     *  
     * @param index 
     * @return 
     */  
    public E get(int index) {  
        // 先判断索引正确性  
        if (index >= size || index < 0) {  
            throw new RuntimeException("索引值有错:" + index);  
        }  
        Node<E> tem = new Node<E>();  
        tem = header;  
        int count = 0;  
        while (count != index) {  
            tem = tem.next;  
            count++;  
        }  
        E e = tem.e;  
        return e;  
    }  
  
    public int size() {  
        return size;  
    }  
  
    /** 
     * 设置第N个结点的值 
     *  
     * @param x 
     * @param e 
     * @return 
     */  
    public boolean set(int index, E e) {  
        // 先判断索引正确性  
        if (index > size || index < 0) {  
            throw new RuntimeException("索引值有错:" + index);  
        }  
        Node<E> newNode = new Node<E>(e);  
        // 得到第x个结点  
        Node<E> cNode = getNode(index);  
        cNode.e = e;  
        return true;  
    }  
  
    /** 
     * 用来存放数据的结点型内部类 
     */  
    class Node<e> {  
        private E e;// 结点中存放的数据  
        Node<E> next;// 用来指向该结点的下一个结点 
        
Node() { }  
        Node(E e) {  
            this.e = e;  
        }  
        // 在此结点后加一个结点  
        void addNext(Node<E> node) {  
            next = node;  
        }  
    }  
}  


     测试类:


    package com.tiger.list;


import java.util.Stack;


public class TestMyList {


/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub


TigerArrayList<String> al = new TigerArrayList<String>();  
        TigerLinkedList<String> ll = new TigerLinkedList<String>();  
        Long aBeginTime=System.currentTimeMillis();//记录BeginTime  
        for(int i=0;i<30000;i++){  
            al.add("now"+i);  
        }  
        Long aEndTime=System.currentTimeMillis();//记录EndTime  
        System.out.println("arrylist  add time--->"+(aEndTime-aBeginTime));  
        Long lBeginTime=System.currentTimeMillis();//记录BeginTime  
        for(int i=0;i<30000;i++){  
            ll.add("now"+i);  
        }  
        Long lEndTime=System.currentTimeMillis();//记录EndTime  
        System.out.println("linkedList add time---->"+(lEndTime-lBeginTime));  
          
        //测试JDK提供的ArrayList类和LinkedList类添加30000个数据所需要的世界  
        java.util.ArrayList<String> sal=new java.util.ArrayList<String>();  
        java.util.LinkedList<String> sll=new java.util.LinkedList<String>();  
        Long saBeginTime=System.currentTimeMillis();//记录BeginTime  
        for(int i=0;i<30000;i++){  
            sal.add("now"+i);  
        }  
        Long saEndTime=System.currentTimeMillis();//记录EndTime  
        System.out.println("JDK arrylist  add time--->"+(saEndTime-saBeginTime));  
        Long slBeginTime=System.currentTimeMillis();//记录BeginTime  
        for(int i=0;i<30000;i++){  
            sll.add("now"+i);  
        }  
        Long slEndTime=System.currentTimeMillis();//记录EndTime  
        System.out.println("JDK linkedList add time---->"+(slEndTime-slBeginTime));  
        
        Stack s=new Stack();
    }  


}

   测试结果:  


 arrylist  add time--->24
linkedList add time---->20
JDK arrylist  add time--->10
JDK linkedList add time---->25

 

有没有感觉高大上!欢迎吐槽!