线性表概述

线性表是最基本、最简单、也是最常用的一种数据结构。在线性表中数据元素之间的关系是线性，数据元素可以看成是排列在一条线上或一个环上。

线性表分为静态线性表和动态线性表，常见的有顺序表(静态的)、单向链表(动态的)和双向链表(动态的)。

线性表的操作主要包括：

（1）计算表的长度n。

（2）线性表是否为空

（3）将元素添加到线性表的末尾

（4）获取第i个元素，0≤i < n。

（5）清除线性表

（6）返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1。

（7）返回列表中最后一次出现指定元素的索引，如果列表不包含此元素，则返回 -1。

（8）将新元素插入第i个位置，0≤i < n，使原来的第i，i+1，…，n–1个元素变为第i+1，i+2，…，n个元素。

（9）更改第i个元素

（10）删除第i个元素，0≤i < n，使原来的第i+1，i+2，…，n–1个元素变为第i，i+1，…，n–2个元素

由此，对线性表抽象数据类型定义List接口如下：

模拟List接口

package com.example.code;

public interface MyList {

    /**

     * 将元素添加到线性表的末尾

     */  

    public void add(Object obj);  

      

    /**

     * 清除线性表

     */  

    public void clear();  

    /**

     * 获取i位置的元素

     * @param i

     * @return

     */  

    public Object get(int i);  

    /**

     * 返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1。

     * @param obj

     * @return

     */  

    public int indexOf(Object obj);  

    /**

     * 在i后面插入一个元素e

     * @param i

     * @param obj

     */  

    public void insert(int i, Object obj);  

    /**

     * 判断线性表是否为空

     * @return

     */  

    public boolean isEmpty();  

    /**

     * 回列表中最后出现指定元素的索引，如果列表不包含此元素，则返回 -1。

     * @param obj

     * @return

     */  

    public int lastIndexOf(Object obj);

    /**

     *  移除列表中指定位置的元素

     * @param i

     */  

    public void remove(int i);  

    /**

     *  移除列表中指定的元素

     * @param obj

     */  

    public void remove(Object obj);  

    /**

     * 用指定元素替换列表中指定位置的元素（可选操作）。

     * @param i

     * @param obj

     */  

    public Object set(int i, Object obj);  

    /**

     * 返回线性表的大小

     * @return

     */  

    public int size();  

}

模拟ArrayList实现List接口

package com.example.code;

public class MyArrayList implements MyList {

    private Object[] array;

    private int size;

    

    /**

     * 自定义容量

     * @param initialCapacity

     */  

    public MyArrayList(int initialCapacity){  

        if(initialCapacity<0){  

            try {  

                throw new Exception();  

            } catch (Exception e) {  

                e.printStackTrace();  

            }  

        }  

        array = new Object[initialCapacity];  

    }

    

    //默认容量为10

    public MyArrayList(){  

        this(10);  

    }  

    

    @Override

    public int size() {

        return size;

    }

    

    @Override

    public boolean isEmpty() {

        return size==0;

    }

    /**

     * 数组下标检查

     * @param index

     */  

    private void rangeCheck(int index){  

        if(index<0||index>=size){  

            try {  

                throw new Exception();  

            } catch (Exception e) {  

                e.printStackTrace();  

            }  

        }  

    }

    

    /**

     * 添加一个元素

     * @param obj

     *

     * System提供了一个静态方法arraycopy(),我们可以使用它来实现数组之间的复制。其函数原型是：

     * public static void arraycopy(Object src,int srcPos, Object dest, int destPos, int length)

     * src:源数组;srcPos:源数组要复制的起始位置;dest:目的数组;destPos:目的数组放置的起始位置;length:复制的长度。

     */

    @Override

    public void add(Object obj) {

        //数组扩容和数据的拷贝，重新new一个数组  

        if(size==array.length){

            Object[] newArray = new Object[size*2+1];  

            System.arraycopy(array, 0, newArray, 0, array.length);  

            array = newArray;

        }

        array[size++] = obj;

    }

    @Override

    public void clear() {

        for (int i = 0; i < size; i++)

            array[i] = null;

        size = 0;

        

    }

    /**

     * 通过索引获取元素

     */

    @Override

    public Object get(int i) {

        rangeCheck(i);  

        return array[i];

    }

    @Override

    public int indexOf(Object obj) {

         if (obj==null) {

             for (int i = 0; i < size; i++)

                 if (array[i]==null)

                     return i;

         } else {

             for (int i = 0; i < size; i++)

                 if (obj.equals(array[i]))

                     return i;

         }

         return -1;

    }

    /**

     * 数组扩容

     */  

    private void ensureCapacity(){  

        //数组扩容和数据的拷贝  

        if(size==array.length){  

            Object[] newArray = new Object[size*2+1];  

            System.arraycopy(array, 0, newArray, 0, array.length);   

            array = newArray;  

        }  

    }

    /**

     * 将元素插入对应的位置

     */

    @Override

    public void insert(int i, Object obj) {

        rangeCheck(i);  

        ensureCapacity();  //数组扩容  

        System.arraycopy(array, i, array, i+1, size-i);  

        array[i] = obj;  

        size++;  

    }

    /**

     * 回列表中最后出现指定元素的索引，如果列表不包含此元素，则返回 -1。

     */

    @Override

    public int lastIndexOf(Object obj) {

        if (obj==null) {

            for (int i=size-1; i>=0; i--)

                if (array[i]==null)

                    return i;

        } else {

            for (int i=size-1; i>=0; i--)

                if (obj.equals(array[i]))

                    return i;

        }

        return -1;

    }

     /**

     * 通过索引删除元素

     */  

    @Override

    public void remove(int i){  

        rangeCheck(i);  

          

        int numMoved = size - i - 1;  

        if (numMoved > 0){  

            System.arraycopy(array, i+1, array, i,numMoved);  

        }  

        array[--size] = null;

    }

    /**

     * 删除对应的元素（利用equal判断元素是否一致）

     * @param obj

     */  

    @Override

    public void remove(Object obj) {

        for(int i=0;i<size;i++){  

            //注意：底层调用的equals方法而不是==

            if(get(i).equals(obj)){    

                remove(i);  

            }  

        }  

    }

    /**

     * 设置索引对应的元素

     */

    @Override

    public Object set(int i, Object obj) {

        rangeCheck(i);

        Object oldValue = array[i];

        array[i] = obj;  

        return oldValue;  

        

    }

    

    public static void main(String[] args) {

        MyArrayList list = new MyArrayList();  

        list.add("333");  

        list.add("444");  

        list.add("5");  

        list.add("344433");  

        list.add("333");  

        list.add("333");  

        list.remove("444");

        list.insert(2, "a");

        for (int i = 0; i < list.size(); i++) {  

            System.out.println(list.get(i));   

        }

        System.out.println(list.size);

        System.out.println(list.indexOf("5"));

    }

}

模拟单项循环链表LinkList实现List接口

package com.example.code;

/**

 * 带头结点的链式链表,下标从0开始;

 *

 */

public class MyLinkList implements MyList{

    Node head;  //头结点  

    int size;   //链表的大小  

    public MyLinkList() {  

        head = new Node();  

        size = 0;  

    }  

    public MyLinkList(Object[] datas) {  

        int n = datas.length;  

        head = new Node();  

        Node p = head;  

        for(int i=0; i<n; i++) {  

            p.next = new Node(datas[i]);  

            p = p.next;  

        }  

        size = n;  

    }  

    @Override  

    public void add(Object e) {  

        Node p;  

        if(0 == size) {  

            p = head;  

        } else {  

            p = index(size-1);  

        }  

        p.next = new Node(e);  

        size ++;  

    }  

 

    @Override  

    public void clear() {  

        head.next = null;  

        size = 0;  

    }  

 

    @Override  

    public Object get(int i) {  

        Node p = index(i);  

        return p.data;  

    }  

      

    private Node index(int i) {  

        Node p = null;  

        if(i>=0 && i<size){  

            p = head;  

            for(int j=0; j<=i; j++) {  

                p = p.next;  

            }  

        }   

        return p;  

    }  

 

    @Override  

    public int indexOf(Object e) {  

        Node p = head.next;  

        int i = 0;  

        while(!p.data.equals(e)) {  

            p = p.next;  

            i++;  

        }  

        if(i<size)  

            return i;  

        else   

            return -1;  

    }  

 

    @Override  

    public void insert(int i, Object e) {  

        Node p = index(i);  

        Node p2 = new Node(e);  

        p2.next = p.next;  

        p.next = p2;  

        size ++;  

    }  

 

    @Override  

    public boolean isEmpty() {  

        if(size ==0)  

            return true;  

        else  

            return false;  

    }  

 

    @Override  

    public int lastIndexOf(Object e) {  

        int i = size-1;  

        while(!get(i).equals(e)) {  

            i--;  

        }  

        if(i>=0)  

            return i;  

        else   

            return -1;  

    }  

 

    @Override  

    public void remove(int i) {  

        if(i>=0 && i<size) {  

            Node p = null;  

            if(i == 0)  

                p = head;  

            else {  

                p = index(i-1);  

            }  

            p.next = index(i).next;  

        }  

        size --;  

    }  

 

    @Override  

    public Object set(int i, Object e) {  

        Node p = index(i);  

        p.data = e;  

        return p;

    }  

 

    @Override  

    public int size() {  

        return size;   

    }

    @Override

    public void remove(Object obj) {

        // TODO Auto-generated method stub

        

    }  

}

/**

 * 链表的结点

 *

 */  

class Node{  

    Object data;    //数据元素  

    Node next;      //后驱结点  

    public Node() {  

        this(null);  

    }  

    public Node(Object data) {  

        this.data = data;  

        this.next = null;  

    }  

}

模拟双向循环链表LinkList实现List接口

package com.example.code;

public class MyDoubleLinkList implements MyList{

    DlNode head;    //头结点  

    int size;   //链表的大小  

    public MyDoubleLinkList() {  

        head = new DlNode();  

        head.prior = head;  

        head.next = head;  

        size = 0;  

    }  

    public MyDoubleLinkList(Object[] datas) {  

        int n = datas.length;  

        head = new DlNode();  

        DlNode p = head;  

        DlNode p2 = null;  

        for(int i=0; i<n; i++) {  

            p2 = new DlNode(datas[i]);  

            p.next = p2;  

            p2.prior = p;  

            p = p.next;  

        }  

        p2.next = head;  

        head.prior = p2;   

        size = n;  

    }  

    @Override  

    public void add(Object e) {  

        DlNode p, p2;  

        if(0 == size) {  

            p = head;  

        } else {  

            p = index(size-1);  

        }  

        p2 = new DlNode(e);  

        p.next = p2;  

        p2.prior = p;  

        p2.next = head;  

        head.prior = p2;  

        size ++;  

    }  

 

    @Override  

    public void clear() {  

        head.prior = head;  

        head.next = head;  

        size = 0;  

    }  

 

    @Override  

    public Object get(int i) {  

        DlNode p = index(i);  

        return p.data;  

    }  

      

    private DlNode index(int i) {  

        DlNode p = null;  

        if(i>=0 && i<size){  

            p = head;  

            for(int j=0; j<=i; j++) {  

                p = p.next;  

            }  

        }   

        return p;  

    }  

 

    @Override  

    public int indexOf(Object e) {  

        DlNode p = head.next;  

        int i = 0;  

        while(!p.data.equals(e)) {  

            p = p.next;  

            i++;  

        }  

        if(i<size)  

            return i;  

        else   

            return -1;  

    }  

 

    @Override  

    public void insert(int i, Object e) {  

        DlNode p = index(i);  

        DlNode p2 = new DlNode(e);  

        p2.next = p.next;  

        p2.prior = p;  

        p.next = p2;  

        size ++;  

    }  

 

    @Override  

    public boolean isEmpty() {  

        if(size ==0)  

            return true;  

        else  

            return false;  

    }  

 

    @Override  

    public int lastIndexOf(Object e) {  

        DlNode p = head.prior;  

        int i = size-1;  

        while(!p.data.equals(e)) {  

            p = p.prior;  

            i--;  

        }  

        if(i>=0)  

            return i;  

        else   

            return -1;  

    }  

 

    @Override  

    public void remove(int i) {  

        if(i>=0 && i<size) {  

            DlNode p = null;  

            if(i == 0)  

                p = head;  

            else {  

                p = index(i-1);  

            }  

            DlNode p2 = index(i).next;  

            p.next = p2.next;  

            p2.next.prior = p;  

        }  

        size --;  

    }  

 

    @Override  

    public Object set(int i, Object e) {  

        DlNode p = index(i);  

        p.data = e;  

        return p;

    }  

 

    @Override  

    public int size() {  

        return size;   

    }

    @Override

    public void remove(Object obj) {

        // TODO Auto-generated method stub

        

    }  

}

/**

 * 链表的结点

 *

 */  

class DlNode{  

    Object data;  

    DlNode prior, next;  

    public DlNode() {  

        this(null);  

    }  

    public DlNode(Object data) {  

        this.data = data;   //数据元素  

        this.prior = null;  //前驱结点  

        this.next = null;   //后驱结点  

    }  

} 

 

转载：http://blog.csdn.net/luoweifu/article/details/8505178