資料結構_雙向連結清單的java實作

這篇文章講述的是資料結構部分的雙向連結清單的java實作，如有錯誤或者不當之處，還望各位大神批評指正。

雙向連結清單的特點

• 實體結構不連續邏輯結構連續
• 删除和添加操作友善
• 順序儲存随資料量的增大而增大
• 查詢操作不友善
• 查詢前驅後繼元素比較友善

雙向連結清單的基本操作

1. init:初始化順序表
2. destroy：銷毀資料表
3. clear：清空資料表中的元素
4. length：擷取資料表長度
5. get：擷取索引位置的元素
6. locateElem：定位元素
7. priorElem：擷取元素前驅
8. nextElem：擷取元素後繼
9. put：順序放入元素
10. insert：插入元素
11. replace：替換元素
12. delete：删除元素
13. isEmpty：判斷順序表是否為空
14. print：列印順序表中的元素

雙向連結清單的java實作

package list;

/**
 * ================================資料結構說明：========================================
 * 
 * 名稱：雙向連結清單
 * 
 * 特征：
 *      1. 實體結構不連續邏輯結構連續
 *      2. 删除和添加操作友善
 *      3. 順序儲存随資料量的增大而增大
 *      4. 查詢操作不友善
 *      5. 查詢前驅後繼元素比較友善
 * 
 * 主要方法：
 *      1. init:初始化順序表
 *      2. destroy：銷毀資料表
 *      3. clear：清空資料表中的元素
 *      4. length：擷取資料表長度
 *      5. get：擷取索引位置的元素
 *      6. locateElem：定位元素
 *      7. priorElem：擷取元素前驅
 *      8. nextElem：擷取元素後繼
 *      9. put：順序放入元素
 *      10. insert：插入元素
 *      11. replace：替換元素
 *      12. delete：删除元素
 *      13. isEmpty：判斷順序表是否為空
 *      14. print：列印順序表中的元素
 * 
 * ======================================================================================
*/
/**
 * @author 葉清逸
 * @date 2018年7月24日下午6:53:51
 * @version 1.0
 * @project list
 */
public class DouLinkList implements List {
    /*雙向連結清單的長度*/
    private int LENGTH ;
    /*頭指針*/
    private Element head ;

    /*元素類*/
    private class Element{
        Object data ;
        Element next ;
        Element prior ;
    }
    /**
     * @see list.List#init()
     * @explain init方法:初始化雙向連結清單
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午6:59:22
     */
    @Override
    public void init() {
        head = new Element() ;
        head.data = null ;
        head.next = null ;
        head.prior = null ;

        LENGTH =  ;
    }
    /**
     * @see list.List#destroy()
     * @explain destroy方法:銷毀雙向連結清單
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午7:00:57
     */
    @Override
    public void destroy() {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return ;
        }
        head= null ;
    }
    /**
     * @see list.List#clear()
     * @explain clear方法:清空雙向連結清單
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午7:40:53
     */
    @Override
    public void clear() {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return ;
        }
        head.next = null ;
        head.prior = null ;
    }
    /**
     * @see list.List#length()
     * @explain length方法:擷取雙向連結清單長度
     * @return 連結清單的長度
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午7:03:23
     */
    @Override
    public int length() {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return -;
        }

        return LENGTH ;
    }
    /**
     * @see list.List#get(int)
     * @explain get方法:擷取縮影位置的元素
     * @param index 索引
     * @return
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午7:41:15
     */
    @Override
    public Object get(int index) {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return null;
        }
        /*判斷index是否合法*/
        if(index > LENGTH || index<=){
            System.out.println("錯誤：索引不合法！");
            return null;
        }
        Element p = head.next ;
        /*找到索引位置*/
        for(int i= ; i<index- ; i++){
            p = p.next ;
        }
        return p.data;
    }
    /**
     * @see list.List#locateElem(java.lang.Object)
     * @explain locateElem方法:擷取元素的索引
     * @param elem  元素
     * @return  元素的索引位置,若未找到則傳回-1
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午7:49:42
     */
    @Override
    public int locateElem(Object elem) {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return -;
        }

        int index = - ;
        /*周遊找到元素的位置*/
        Element p = head.next ;
        for(int i= ; i<LENGTH ; i++){
            if(p.data.equals(elem)){
                return i+ ;
            }
            p = p.next ;
        }
        return index ;
    }
    /**
     * @see list.List#priorElem(java.lang.Object)
     * @explain priorElem方法:擷取元素的前驅
     * @param elem 元素
     * @return 元素的前驅
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午7:57:03
     */
    @Override
    public Object priorElem(Object elem) {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return null;
        }

        Element prior = null ;
        /*定位到元素*/
        Element p = head.next ;
        while(p != null){
            if(p.data.equals(elem)){
                break ;
            }
            p = p.next ;
        }
        /*擷取前驅*/
        if(p != null){
            prior = p.prior ;
            return prior.data;
        }else{
            return null ;
        }
    }

    @Override
    public Object nextElem(Object elem) {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return null;
        }
        Element next = null ;
        /*定位到元素*/
        Element p = head.next ;
        while(p != null){
            if(p.data.equals(elem)){
                break ;
            }
            p = p.next ;
        }
        if(p.next != null){
            next = p.next ;
            return next.data;
        }else{
            return null ;
        }
    }
    /**
     * @see list.List#put(java.lang.Object)
     * @explain put方法:添加元素
     * @param elem 要添加的元素
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午7:04:06
     */
    @Override
    public void put(Object elem) {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return ;
        }
        /*申請空間将元素存入*/
        Element e = new Element() ;
        e.data = elem ;
        /*周遊找出要插入的位置*/
        Element p = head ;
        while(p.next != null){
            p = p.next ;
        }
        /*改變指針指向*/
        e.next = p.next ;
        e.prior = p ;
        p.next = e ;

        LENGTH++ ;
    }
    /**
     * @see list.List#insert(int, java.lang.Object)
     * @explain insert方法:在索引位置插入元素
     * @param index 索引
     * @param elem 要插入的元素
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午8:14:43
     */
    @Override
    public void insert(int index, Object elem) {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return ;
        }
        /*判斷index是否合法*/
        if(index > LENGTH || index<=){
            System.out.println("錯誤：索引不合法！");
            return ;
        }
        /*找到索引位置*/
        Element p = head ;
        for(int i= ; i<index- ; i++){
            p = p.next ;
        }
        /*插入元素*/
        Element e = new Element() ;
        e.data = elem ;
        e.next = p.next ;
        e.prior = p ;
        p.next = e ;
        e.next.prior = e ;

        LENGTH++ ;
    }
    /**
     * @see list.List#replace(int, java.lang.Object)
     * @explain replace方法:将索引位置的元素替換為傳入元素
     * @param index 索引位置
     * @param elem 替換的元素
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午9:43:46
     */
    @Override
    public void replace(int index, Object elem) {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return ;
        }
        /*判斷index是否合法*/
        if(index > LENGTH || index<=){
            System.out.println("錯誤：索引不合法！");
            return ;
        }
        /*找到索引位置*/
        Element p = head ;
        for(int i= ; i<index ; i++){
            p = p.next ;
        }
        /*替換元素*/
        p.data = elem ;
    }

    @Override
    public void delete(int index) {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return ;
        }
        /*判斷index是否合法*/
        if(index > LENGTH || index<=){
            System.out.println("錯誤：索引不合法！");
            return ;
        }
        /*找到索引位置*/
        Element p = head ;
        for(int i= ; i<index- ; i++){
            p = p.next ;
        }
        /*删除元素*/
        p.next = p.next.next ;
        p.next.prior = p ;

        LENGTH-- ;
    }
    /**
     * @see list.List#isEmpty()
     * @explain isEmpty方法:判斷連結清單是否為空
     * @return 傳回Boolean類型值，true為空，false為非空
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午9:52:53
     */
    @Override
    public boolean isEmpty() {
        boolean flag = false ;

        /*判斷是否為空*/
        if(head.next == null)
            flag = true ;

        return flag;
    }
    /**
     * @see list.List#print()
     * @explain print方法:列印連結清單，順序通路各個節點
     * @throws 
     * @author 葉清逸
     * @date 2018年7月24日 下午9:55:34
     */
    @Override
    public void print() {
        /*若未初始化輸出異常資訊*/
        if(head == null){
            System.out.println("錯誤：連結清單未初始化！");
            return ;
        }
        /*順序通路各節點*/
        Element p = head.next ;
        while(p != null){
            System.out.print(p.data+" ");
            p = p.next ;
        }
        System.out.println();
    }
    @Override
    public String toString() {
        String str = "DouLinkList:[" ;
        Element p = head.next ;
        while(p != null){
            if(p.next != null){
                str = str + p.data +"," ;
                p = p.next ;
            }else{
                str = str + p.data ;
                p = p.next ;
            }

        }
        str = str+"]" ;
        return str ;
    }

}