线性表--双链表实现方式 (JAVA)

前面一篇文章说明了线性表主要有三种结构：顺序表、单链表、双链表。

其实按照其实现的特点是两种实现方式：1、采用数组式的静态存储空间，即线性表；2、采用链

式的动态存储空间，即是链表。

上一章实现了顺序表，这篇文章用于实现双链表。由于双链表具有的方法比顺序表多。

因此重新定义一个线性表接口：

[java]
package com.kiritor.linklist;

/**
* 线性表接口
* @author Kiritor
* */
public interface LinearTable<T>{
//判空
public boolean isEmpty();
//获取长度
public int getLength();
//返回某个位置的元素
public T getData(int index);
//设置index位置的元素，并返回先前的元素
public T setData(int index,T element);
//插入一个元素，位置没有限定(插入链表尾部)
public boolean addData(T element);
//在指定的位置插入一个元素
public boolean addData(int index,T element);
//删除某个位置的元素，并返回该元素
public T removeData(int index);
//清空线性表
public boolean clearData();
//删除尾部
public boolean removeTail();

}

package com.kiritor.linklist;

/**
* 线性表接口
* @author Kiritor
* */
public interface LinearTable<T>{
//判空
public boolean isEmpty();
//获取长度
public int getLength();
//返回某个位置的元素
public T getData(int index);
//设置index位置的元素，并返回先前的元素
public T setData(int index,T element);
//插入一个元素，位置没有限定(插入链表尾部)
public boolean addData(T element);
//在指定的位置插入一个元素
public boolean addData(int index,T element);
//删除某个位置的元素，并返回该元素
public T removeData(int index);
//清空线性表
public boolean clearData();
//删除尾部
public boolean removeTail();

}
接下来就是实现了

[java]
package com.kiritor.linklist;

/**
* java版双向链表的实现
*
* @author Kiritor
*/
public class DBLinkList<T> implements LinearTable<T> {

    // 指向链表的头结点
    private Node head;
    // 指向链表的尾结点
    private Node tail;
    private int size = 0;// 链表的元素个数

    public DBLinkList() {
        this.head = new Node();
        this.tail = null;
    }

    public DBLinkList(T data) {
        this.head = new Node(null, data, null);
        this.tail = this.head;
        this.size++;
    }

    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return this.size == 0;
    }

    // 获得链表的长度
    public int getLength() {
        return this.size;
    }

    // 获取指定位置结点，下表从0开始
    public Node getNode(int index) {
        if (index < 0 || index > this.size - 1)
            throw new IndexOutOfBoundsException("访问位置非法越界!");
        // 根据index所出的位置决定是从前遍历还是从后遍历
        if (index <= this.size / 2) {// 位置在前半部分，则从头开始搜索
            Node curent = this.head;
            for (int i = 0; i <= this.size / 2 && curent != null; i++, curent = curent.next)
                if (i == index)
                    return curent;
        } else {// 位置在后半部分，则从后开始往前搜索
            Node curent = this.tail;
            for (int i = this.size - 1; i > this.size / 2 && curent != null; i--, curent = curent.pre)
                if (i == index)
                    return curent;
        }
        return null;
    }

    // 获取指定位置的结点元素
    public T getData(int index) {
        return this.getNode(index).data;
    }

    @Override
    public T setData(int index, T element) {
        return null;
    }

    // 在链表的头部插入元素，不指定位置默认在头部插入
    @Override
    public boolean addData(T element) {
        // 前驱引用为null,后继引用为头结点
        Node node = new Node(null, element, this.head);
        this.head.pre = node;// 改变前驱引用
        // 修改链表的头结点
        this.head = node;
        if (tail == null)
            tail = this.head;
        this.size++;
        // System.

补充：软件开发 , Java ,