Java学习笔记＜十五＞

package DataStructure_8;

//双向链表--实现双向链表

/**
*双线链表结构
 * 双向链表定义：
 * 双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向直接前驱和直接后继
 *
 */

/**
 *基于双向链表存取的数据
 * @param 
 */
//实现单向链表类的中定义的MyList接口
public class Text3 implements MyList {

    private Node head;      //头结点指针
    private Node tail;      //尾结点指针
    private int size;       //记录元素个数

    //创建节点类（内部类）
    class Node{

        E item;             //记录元素
        Node prev;       //记录链表中前一个节点对象地址
        Node next;       //记录链表中后一个节点对象地址

        public Node(E item, Node prev, Node next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }

    }


    /**
     * 向双向链表中添加元素
     * @param element
     */
    @Override
    public void add(E element) {

        //头结点和尾结点的添加都使用LinkLast()方法
        this.LinkLast(element);

    }

    //为链表中添加头结点的方法
    private void addFirst(E element){

        //将原头结点指针赋给可移动指针
        Node uu=this.head;
        //创建一个新的头结点
        Node node = new Node<>(element,null,uu);
        //为新节点指定头指针
        this.head=node;
        //如果新节点为唯一节点，则新节点也是尾结点
        if (uu==null){
            this.tail=node;
        }else {
            //如果新节点不是唯一节点，将新节点地址赋给原头指针所对应的原头结点的prev
            uu.prev=node;
        }
        this.size++;

    }

    //为链表中添加尾结点的方法
    private void addLast(E element){

        //直接调用LinkLast()方法添加尾结点
        this.LinkLast(element);

    }

    //向双向链表中添加尾结点
    private void LinkLast(E element){

        //将尾结点赋给t
        Node t=this.tail;
        //创建新节点，新节点的前驱节点为尾结点t，后继几点为null
        Node node = new Node<>(element,t,null);      //前驱节点挂接
        //新创建的节点为尾结点
        this.tail=node;
        //如果如果之前的尾结点的前驱节点为空，则新节点就是第一个节点对象，将新节点定为头结点
        if (t==null){
            this.head=node;
            //如果之前尾结点的前驱节点不为空，说明有尾结点，将新节点的地址赋给尾结点的next，（尾结点可能和头结点为一个节点）
        }else{
            t.next=node;
        }
        size++;
    }


    /**
     * 根据索引获取元素
     * @param index
     * @return
     */
    @Override
    public E get(int index) {

        //对index做合法性校验
        this.checkIndex(index);
        //根据index查找节点对象
        Node node = this.getNode(index);
        //返回节点元素
        return node.item;
    }

    //校验index合法性
    private void checkIndex(int index){

        if (!(index >= 0 && index < this.size)){
            throw new IndexOutOfBoundsException("Index "+index+" size "+size);
        }
    }

    //根据index查询并返回元素
    private Node getNode(int index){

        //使用二分法查找
        if (index < (this.size>>1)){
            Node aa=this.head;
            for (int i = 0; i < index; i++) {
                aa=aa.next;
            }
            return aa;
        }else {
            Node aa = this.tail;
            for (int i = (this.size-1); i >= index; i--) {
                aa=aa.prev;
            }
            return aa;
        }
    }

    /**
     * 获取元素个数
     * @return
     */
    @Override
    public int size() {
        return this.size;
    }

    /**
     * 根据指定索引删除元素
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {

        //对index进行合法性校验
        this.checkIndex(index);
        //根据位置获取节点对象
        Node node =this.getNode(index);
        //获取节点对象中的元素
        E item=node.item;
        //判断当前节点是否为头结点
        if (node.prev==null){
            this.head=node.next;
            node.next=null;
            node.item=null;
        }else {
            //当前节点删除后当前节点的前驱节点与后续节点的挂接
            //当前节点的前驱节点的next指向当前节点的next节点（也就是当前节点的后继节点）
            node.prev.next=node.next;
        }
        //判断当前节点是否为尾结点
        if (node.next==null){
            this.tail=node.prev;
        }else {
            //完成当前节点的后继节点的prev与当前节点的前驱节点挂接
            node.next.prev=node.prev;
        }
        //当前节点断掉直接前驱节点的链接
        node.prev=null;
        //当前节点断掉直接后继节点的链接
        node.next=null;
        //将当前节点内元素置空，加速垃圾回收效率
        node.item=null;
        //记录元素个数
        this.size--;
        //返回当前元素
        return node.item;
    }

    public static void main(String[] args) {

        System.out.println("==============测试双向链表类的功能====================");
        Text3 nn=new Text3<>();

        nn.add("a");
        nn.add("b");
        nn.add("c");
        nn.add("d");

        System.out.println(nn.size);

        System.out.println(nn.get(2));

        String kk= nn.remove(2);

        for (int i = 0; i  oo = new Text3<>();

        oo.addFirst("a");
        oo.addLast("A");
        oo.addFirst("B");

        for (int i = 0; i < oo.size; i++) {
            System.out.println(oo.get(i));
        }
    }
}