Java 數(shù)據(jù)結(jié)構(gòu) 雙向鏈表

基本特點(diǎn)

單向鏈表：只有指向下一個(gè)結(jié)點(diǎn)的引用（后驅(qū)）
雙向鏈表：既有指向下一個(gè)結(jié)點(diǎn)的引用（后驅(qū)），也有指向上一個(gè)結(jié)點(diǎn)的引用（前驅(qū)）

優(yōu)點(diǎn)

1. 雙向鏈表在查找元素的時(shí)候，速度比之單向鏈表會(huì)更快
2. 擁有前驅(qū)后驅(qū)，操作更靈活

缺點(diǎn)

1. 增加刪除結(jié)點(diǎn)操作更繁瑣一些
2. 占用的資源更多，數(shù)據(jù)存儲(chǔ)率相比單向鏈表更低（生產(chǎn)中使用單鏈表比雙鏈表更多）

存儲(chǔ)結(jié)構(gòu)

在這里插入圖片描述

Java代碼

package linklist;

/**
 * 雙向鏈表
 * Created by Sheldon on 2019/4/1.
 * Project Name: alstudy.
 * Package Name: linklist.
 */

// 單向鏈表
class NodeTwo{
    Data data;
    NodeTwo pre;
    NodeTwo next;
}

public class LinkListTwo {

    // 頭結(jié)點(diǎn)
    NodeTwo head = null;

    /**
     * 追加結(jié)點(diǎn)
     * @param data
     * @return
     */
    public boolean addNode(Data data){
        NodeTwo temp = head;
        NodeTwo newNode;
        // 創(chuàng)建新結(jié)點(diǎn)對(duì)象
        if ((newNode=new NodeTwo())==null){
            System.out.println("申請(qǐng)內(nèi)存失敗！");
        }else {
            // 保存數(shù)據(jù)
            newNode.data = data;
            if (head==null){
                head = newNode;
                return true;
            }
            // 遍歷數(shù)組，追加數(shù)據(jù)
            while (temp.next!=null){
                temp = temp.next;
            }
            // 通過(guò)遍歷找到最后一個(gè)元素，使其后驅(qū)指向新結(jié)點(diǎn)
            temp.next = newNode;
            // 將新結(jié)點(diǎn)的前驅(qū)指向‘最后一個(gè)元素’
            newNode.pre = temp;
            return true;
        }
        return false;
    }

    /**
     * 查找結(jié)點(diǎn)
     * @param key
     */
    public void findByKey(String key){
        NodeTwo temp = head;
        // 遍歷結(jié)點(diǎn)
        while (temp!=null){
            if (temp.data.key.equals(key)){
                // 打印結(jié)點(diǎn)信息
                System.out.println(temp.data.key+"->"+temp.data.name);
                return;
            }
            temp = temp.next;
        }
        System.out.println("沒(méi)有該結(jié)點(diǎn)");
    }


    /**
     * 刪除結(jié)點(diǎn)
     * @param key
     * @return
     */
    public boolean delNode(String key){
        NodeTwo temp = head;
        while (temp!=null){
            if (temp.data.key.equals(key)){
                // 查看該結(jié)點(diǎn)是否是頭結(jié)點(diǎn)
                if (temp==head){
                    // 如果是頭結(jié)點(diǎn)，將其引用替換成它的后驅(qū)
                    head = temp.next;
                    head.pre = null;
                    return true;
                }else {
                    // 將該結(jié)點(diǎn)的前驅(qū)的‘后驅(qū)引用’指向它的后驅(qū)
                    // 直接temp = temp.next是無(wú)法得到想要的結(jié)果的，因?yàn)槠淝膀?qū)沒(méi)發(fā)生變化
                    temp.pre.next = temp.next;
                    return true;
                }
            }
            temp = temp.next;
        }
        return false;
    }

    /**
     * 顯示所有結(jié)點(diǎn)
     */
    public void showAllList(){
        NodeTwo temp = head;
        while (temp!=null){
            // 打印結(jié)點(diǎn)信息
            System.out.printf(temp.data.key+"->"+temp.data.name+" ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkListTwo list = new LinkListTwo();
        // 插入結(jié)點(diǎn)
        list.addNode(new Data("1","小明"));
        list.addNode(new Data("2","小紅"));
        list.addNode(new Data("3","小綠"));
        list.addNode(new Data("4","小黃"));
        // 查看結(jié)點(diǎn)效果
        list.showAllList();
        // 查找結(jié)點(diǎn)
        list.findByKey("1");
        // 刪除結(jié)點(diǎn)
        list.delNode("2");
        // 再次查看結(jié)點(diǎn)
        list.showAllList();
    }
}

顯示結(jié)果：

在這里插入圖片描述