import java.util.Arrays;public class SequenceList<T> {    private final int DEFAULT_SIZE = 16; //定义一个常量        private int capacity = DEFAULT_SIZE;   //保存数组的容量    private Object[] elementData; //用数组实现    private int size=0; //数组当前元素个数        public SequenceList()  //1.创建一个链表并且初始化    {        elementData = new Object[capacity];    }        public SequenceList(T element)//以一个元素为基础创建链表    {        this();        elementData[0]=element;        size++;    }        public SequenceList(int initSize)  //指定初始容量    {        //最好要先判断一个传进来的参数        //指定的容量是2的n次方        capacity = 1;        while(capacity<initSize)        {            capacity<<=1;        }        elementData = new Object[capacity];    }        public int Length()   //2.获取list的大小    {        return size;    }        public T get(int index)    //3.获取指定索引处的元素    {        //传进来的参数一定要判断其合法性        if(index<0 || index>size-1)        {            throw new IndexOutOfBoundsException("数组下标越界");            }        return (T)elementData[index];    }        public int indexOf(T element) //4.查找指定元素的索引    {        for(int i=0;i<capacity;i++)        {            if(element.equals(elementData[i]))            {                return i;            }        }        return -1;    }        public void insert(T element,int index) //5.在指定位置插入一个元素    {        if(index<0 || index>size)        {            throw new IndexOutOfBoundsException("数组下标越界");            }        //先处理数组长度问题,保证数组长度增加后仍然安全        if((size+1)>capacity)        {            //容量不够了,扩容，把原数组copy到新数组            while(capacity<(size+1))            {                capacity <<=1;            }            elementData = Arrays.copyOf(elementData, capacity); //效率不好        }        //把index处的数组元素后移        System.arraycopy(elementData,index,elementData,index+1,size-index);        elementData[index]=element;        size++;    }    public void insertLast(T element) //6.在尾部新增一个元素    {        insert(element,size);   //注意尾部是size而不是capacity    }    public T remove(int index)  //7.删除指定位置的元素    {        if(index<0 || index>size-1)        {            throw new IndexOutOfBoundsException("线性表索引越界");        }        T oldValue = (T)elementData[index];        int numMoved = size - index - 1; //index后面多少个元素都要前移        if(numMoved>0)        {            System.arraycopy(elementData, index+1, elementData, index, numMoved);        }        elementData[--size] = null;        return oldValue;    }        public T removeLast()  //8.删除尾部的元素    {        return remove(size-1);    }        public boolean empty()   //判断表是否为空    {        return size==0;    }        public void clear()  //清空线性表    {        Arrays.fill(elementData, null);        size=0;    }        public String toString()  //以字符串输出    {        if(size==0)        {            return "[]";        }        else        {            StringBuilder sb = new StringBuilder("[");            for(int i=0;i<size;i++)            {                //取出一个元素加上一个逗号                sb.append(elementData[i].toString()+", ");//逗号+空格            }            //删除最后一个“逗号和空格”，加上"]"  [3,4,5,            int length = sb.length();            return sb.replace(length-2, length, "]").toString();        }    }    }

public class LinkList<T> {    //内部类Node代表节点    private class Node    {        private T data;  //保存节点的数据        private Node next; //指向下一个节点        public Node(){}        public Node(T data, LinkList<T>.Node next)         {            super();            this.data =http://www.mamicode.com/ data;            this.next = next;        }    }    private Node header; //保存该链表的头结点    private Node tail; //保存该链表的尾节点    private int size; //保存该链表的节点数        public LinkList()   //创建空链表    {        header = null;        tail = null;    }    public LinkList(T element)   //以一个元素来初始化链表    {        header = new Node(element,null); //只有一个节点        tail = header;        size++;    }    public int length()   //获取链表的长度    {        return size;    }        public T get(int index)  //根据索引获取某元素的数据    {        if(index<0 || index>size-1)        {            throw new IndexOutOfBoundsException("链表越界");        }        Node current = header;        for(int i=0;current!=null && i<size;i++)        {            if(i == index)            {                return current.data;            }        }        current = current.next;        return null;    }        public int indexOf(T element)  //获取链表中指定元素的索引    {        Node current = header;          for(int i=0;i<size && current!=null;i++ , current=current.next )   //要返回索引所以必须在循环里也写上i        {            if(current.data.equals(element))            {                return i;            }        }         return -1;    }    public void insert(T element,int index) //向线性表的指定索引后新增一个元素    {        if(index <0 || index>size)  //可以向链表的最后添加一个元素        {            throw new IndexOutOfBoundsException("线性表下标越界");        }        if(header == null) //如果还是空链表        {            addAtLast(element);//尾插法        }        else        {            //获取插入的前一个节点            Node pre = header;            for(int i=0;i<index-1;i++)            {                pre=pre.next;            }            pre.next = new Node(element,pre.next); //让新节点只想原来pre.next节点            size++;        }    }        private void addAtLast(T element)  //尾插法--被insert(T，int)调用    {        header = new Node(element,null);        tail = header; //只有一个节点，header和tail都指向它        size++;    }        public void addAtHeader(T element)//头插法    {        //总是以新节点作为头结点        header = new Node(element,header); //不管原来的头结点是否为空        size++;    }        public T delete(int index) //删除链式表指定处的元素    {        if(index<0 || index>size-1)        {            throw new IndexOutOfBoundsException("链表索引错误");        }                //删除头节点有点特殊        Node del = header;        if(index == 0)        {            header = header.next;            del.next=null;  //让原来的头结点的下一个指向null            //del = null;  //让原来的头结点失去引用        }        else        {            Node pre = header;            for(int i =0;i<index-1;i++) //让pre指向index-1节点            {                pre = pre.next;            }            del = pre.next; //del指向了index            pre.next = pre.next.next;            del.next=null; //让需要删除的节点的下一指向指向null                    }        size--;        return del.data;    }        public T deleteLast()   //删除最后一个元素    {        return delete(size-1);    }        public boolean empty() //判断链表是否为空    {        return size ==0;    }        public void clear()  //清空链表    {        //        Node pre =header;        Node current = pre.next;        for(;current!=null;current =current.next)        {            pre.next = null;            pre = current;        }        //pre.next = null;        tail = null;        size = 0;    }        public String toString()     {        if(empty())        {            return "[]";        }        else        {            StringBuilder sb = new StringBuilder("[");            for(Node current = header;current !=null;current=current.next)            {                sb.append(current.data.toString()+", ");            }            int len = sb.length();            return sb.replace(len-2, len, "]").toString();        }    }}

public class DbLinkedList<T> {        private class Node  //内部节点类    {        private T data;        private Node prev;        private Node next;        public Node(){}        public Node(T data, Node prev, DbLinkedList<T>.Node next)         {            super();            this.data =http://www.mamicode.com/ data;            this.prev = prev;            this.next = next;        }    }    private Node header;  //保存该链表的头结点    private Node tail; //保存链表的尾节点    private int size; //包含链表中已包含的节点数        public DbLinkedList()    {        //空链表的header 和 tail都是null        header = null;        tail = null;    }        public DbLinkedList(T element)  //以特定的元素构建链表    {        header = new Node(element,null,null);        //只有一个节点,header,tail都指向该节点        tail = header;        size++;    }        public int length()//返回链表的长度    {        return size;    }        public T get(int index)//获取链式线性表中索引为index处的元素    {        return getNodeByIndex(index).data;    }    private Node getNodeByIndex(int index) //根据索引获取    {        if(index<0 || index>size-1)        {            throw new IndexOutOfBoundsException("线性表下标越界");        }        if(index<=size/2)        {            //header节点开始            Node current = header;            for(int i=0;i<size/2&&current!=null;                    i++,current=current.next)//索引靠前就用            {                if(i==index)                {                    return current;                }            }        }        else        {            //从tail节点开始搜索            Node current = tail;            for(int i=size-1;i>size/2&&current!=null;                    i--,current=current.prev)            {                if(i == index)                {                    return current;                }            }        }        return null;    }        public int indexOf(T element)   //获取指定元素的下标    {        Node current = header;        for(int i=0;i<size && current!=null;i++,current=current.next)        {            if(current.data.equals(element))            {                return i;            }        }        return -1;    }            public void insert(T element,int index)//向指定位置插入一个元素    {        if(index<0 || index> size) //可向链表的最后一个元素后面插入元素        {            throw new IndexOutOfBoundsException("下标越界");        }                if(header==null)        {            addLast(element); //尾插法        }        else        {            //当index为0的时候，也就是在表头插入            if(index==0)            {                addAtHeader(element);            }            else //中间插入            {                Node prev = getNodeByIndex(index-1); //获取插入节点的前一个节点                Node next = prev.next; //获取插入节点                                Node newNode = new Node(element,prev,next);                                prev.next = newNode;                next.prev = newNode;                size++;            }        }    }    public void addLast(T element) //尾插法实现    {        if(header == null)        {            header = new Node(element,null,null);            tail = header;        }        else        {            //找到尾节点            Node newNode = new Node(element,tail,null);            tail.next = newNode;            tail = newNode;        }        size++;    }    public void addAtHeader(T element) //采用头插法    {        //创建新节点的next指向header,并把它作为新的list头        header = new Node(element,null,header);        if(tail == null)        {            tail = header;        }        size++;    }    public T delete(int index)  //删除指定索引的元素    {        if(index<0 || index>size -1)        {            throw new IndexOutOfBoundsException("线性表索引越界");        }        Node del = null;  //用于返回要删除元素的值                if(index==0)  //删除头结点        {            del = header;              header = header.next;   //让head指向原来的header的next             header.prev = null;  //新header的prev指向null        }        else        {            Node prev = getNodeByIndex(index-1); //获取要删除的前一个节点            del = prev.next;   //获取要删除的元素                        //开始处理互相引用            prev.next = del.next;            if(del.next!=null)            {                del.next.prev = prev;            }            del.prev = null;            del.next = null;        }        size--;        return del.data;    }        public T deleteLast() //删除链式线性表中的最后一个元素    {        return delete(size-1);    }        public boolean empty()  //判断是否为空    {        return size==0;    }        public void clear()    {        //前向和后项全部要置为null    }    public String toString()     {        if(empty())        {            return "[]";        }        else        {            StringBuilder sb = new StringBuilder("[");            for(Node current = header;current !=null;current=current.next)            {                sb.append(current.data.toString()+", ");            }            int len = sb.length();            return sb.replace(len-2, len, "]").toString();        }    }    public String reverseToString()    {        if(empty())        {            return "[]";        }        else        {            StringBuilder sb = new StringBuilder("[");            for(Node current = tail;current!=null;current = current.prev)            {                sb.append(current.data.toString()+", ");            }            int len=sb.length();            return sb.replace(len-2,len, "]").toString();        }    }}