相較于單鏈表與循環(huán)鏈表，雙向鏈表增加了prior指針
在進(jìn)行增加、插入、刪除時(shí)需要處理兩個(gè)指針
完整的MyDoubleLinkedList類

/**
 * Created by FireFlies on 2018/4/4.
 * 雙向鏈表曹宴，同時(shí)具有兩個(gè)指針next與prior
 * add
 * insert
 * delete操作改變
 */

public class MyDoubleLinkedList {

    public Node header = null;// 頭結(jié)點(diǎn)
    int size = 0;// 表示數(shù)組大小的指標(biāo)

    /**
     * 用來存放數(shù)據(jù)的結(jié)點(diǎn)型內(nèi)部類
     * 一個(gè)結(jié)點(diǎn)：數(shù)據(jù)域與指針域
     */
    class Node {
        Object o;// 結(jié)點(diǎn)中存放的數(shù)據(jù)（數(shù)據(jù)域）
        Node next;// 用來指向該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)（指針域）
        Node prior;//用來指向該結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)（指針域）

        public Node() {}
        public Node(Object o) {
            this.o = o;
        }
    }

    /**
     * 增操作一：直接在末尾增加
     * 思路：
     * 若size為0，則直接為header賦值new Node
     * 若size不為0歉提，獲取鏈表最后一個(gè)節(jié)點(diǎn)笛坦，將此節(jié)點(diǎn)的next賦值為new Node
     * size ++
     */
    public boolean add(Object o) {
        if (size == 0) {
            header = new Node(o);
            header.next = header;
            header.prior = header;
        } else {
            Node temp = this.getNode(size -1);
            Node newNode = new Node(o);
            //四步完成指針替換
            newNode.prior = temp;
            newNode.next = header;
            header.prior = newNode;
            temp.next = newNode;
        }
        size++;// 當(dāng)前大小自增加1
        return true;
    }

    /**
     * 增操作二：指定index增加
     * 思路：
     * 首先驗(yàn)證index有效性能
     * 若為0区转，實(shí)例化newNode，newNode.next賦值為header版扩，header賦值為newNode（三步）废离；
     * 若不為0，實(shí)例化newNode并獲取index-1位置對(duì)應(yīng)的Node temp礁芦，之后進(jìn)行指針替換蜻韭。
     * size++
     */
    public boolean insert(int index, Object o) {
        // 先判斷索引正確性
        validateIndex(index);

        if (index == 0){
            Node newNode = new Node(o);
            newNode.next = header;
            newNode.prior = header.prior;
            header = newNode;
        }else{
            Node newNode = new Node(o);
            Node temp = this.getNode(index-1);

            newNode.next = temp.next;
            newNode.prior = temp;
            temp.next.prior = newNode;
            temp.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * 刪操作一
     * 思路：
     * 先驗(yàn)證index有效性
     * 若index為0，直接將header賦值為header.next
     * 若index不為0柿扣，將index-1處節(jié)點(diǎn)的next賦值為index處節(jié)點(diǎn)的next
     */

    public boolean delete(int index){
        // 先判斷索引正確性
        validateIndex(index);

        if(index == 0){
            header.next.prior = header.prior;
            header = header.next;
        }else{
            this.getNode(index).prior.next = this.getNode(index).next;
            this.getNode(index).next.prior = this.getNode(index).prior;
        }
        size--;
        return true;
    }

    /**
     * 刪操作二：直接刪除元素
     * 思路：直接從0開始遍歷鏈表,類似于查找操作
     * 當(dāng)發(fā)現(xiàn)某次獲取到的數(shù)據(jù)與要?jiǎng)h除數(shù)據(jù)相同肖方，則記錄索引位置，并執(zhí)行delete操作
     */

    public boolean remove(Object o){
        boolean flag = true;
        Node temp = header;
        for(int count = 0;count<size;count++) {
            if (temp.o.equals(o)) {
                this.delete(count);
                flag = false;
            }
            temp = temp.next;
        }
        if(flag){
            System.out.println("Element not found: "+o.toString());
            return false;
        }
        return true;
    }

    /**
     * 改操作
     * 思路：
     * 首先驗(yàn)證index有效性
     * 直接獲取index處節(jié)點(diǎn)temp
     * 取temp的屬性e未状，直接賦值為新的e
     * 設(shè)置第N個(gè)結(jié)點(diǎn)的值
     *
     */
    public boolean set(int index, Object o) {
        // 先判斷索引正確性
        validateIndex(index);
        //Node<E> newNode = new Node<E>(e);
        // 得到第x個(gè)結(jié)點(diǎn)
        Node temp = getNode(index);
        temp.o = o;
        return true;
    }

    /**
     * 查操作：
     * 先驗(yàn)證index有效性
     * 思路：
     * 必須從頭結(jié)點(diǎn)開始查起
     * 實(shí)例化Node對(duì)象temp俯画，并賦值為header，意為從頭結(jié)點(diǎn)開始查起
     * 聲明count計(jì)數(shù)器并從0開始娩践，當(dāng)count活翩！=index烹骨，則temp = temp.next,一直查下去翻伺，計(jì)數(shù)器增1
     * 直到count = index停止查找，取temp.e的值并返回沮焕。
     *
     */
    public Object get(int index) {
        // 先判斷索引正確性
        validateIndex(index);
        Node tem = header;
        int count = 0;
        while (count != index) {
            tem = tem.next;
            count++;
        }
        Object o = tem.o;
        return o;
    }

    /**
     * 查操作：
     * 先驗(yàn)證index有效性
     * 思路：
     * 必須從頭結(jié)點(diǎn)開始查起
     * 實(shí)例化Node對(duì)象temp吨岭，并賦值為header，意為從頭結(jié)點(diǎn)開始查起
     * 聲明count計(jì)數(shù)器并從0開始峦树，當(dāng)count辣辫！=index，則temp = temp.next,一直查下去魁巩，計(jì)數(shù)器增1
     * 直到count = index停止查找急灭，返回temp節(jié)點(diǎn)。
     *
     */
    private Node getNode(int index) {
        // 先判斷索引正確性
        validateIndex(index);
        Node temp = header;
        int count = 0;
        while(count!=index){
            temp = temp.next;
            count++;
        }
        return temp;
    }

    /**
     * 合并操作：
     * 合并兩個(gè)循環(huán)鏈表
     * 思路：
     * 將鏈表1的尾指針指向鏈表2的頭結(jié)點(diǎn)谷遂，鏈表2的尾指針指向鏈表1的頭結(jié)點(diǎn)
     */
    public MyDoubleLinkedList combine(MyDoubleLinkedList anotherList){
        if(this.size()!=0&&anotherList.size()!=0){
            this.getNode(size - 1).next = anotherList.getNode(0);
            anotherList.getNode(anotherList.size() - 1).next = this.getNode(0);
            size += anotherList.size();
        }else if(this.size()==0&&anotherList.size()!=0){
            return anotherList;
        }else if(anotherList.size()==0&&this.size()!=0){
            System.out.println("Your anotherList is empty!");
        }
        return this;
    }


    public int size() {
        return this.size;
    }


    /**
     *  驗(yàn)證當(dāng)前下標(biāo)是否合法葬馋，如果不合法，拋出運(yùn)行時(shí)異常
     */
    private void validateIndex(int index) {
        if (index < 0 || index > size) {
            throw new RuntimeException("數(shù)組index錯(cuò)誤：" + index);
        }
    }

    public void print(){
        System.out.print("[");
        for(int i =0;i<this.size();i++){
            System.out.print(this.get(i).toString() +" ");
        }
        System.out.print("]");
    }

}

測(cè)試類

import org.omg.CORBA._IDLTypeStub;

/**
 * Created by FireFlies on 2018/4/3.
 */
public class MyDoubleLinkedListTest {
    public static void main(String[] args) {
        MyDoubleLinkedList myDoubleLinkedList = new MyDoubleLinkedList();

        //增操作一測(cè)試,添加三個(gè)整數(shù)元素
        System.out.println("\n增操作一測(cè)試：");
        myDoubleLinkedList.add(new Integer(1));
        myDoubleLinkedList.add(new Integer(2));
        myDoubleLinkedList.add(new Integer(3));
        myDoubleLinkedList.print();

        //增操作二測(cè)試肾扰，在第二個(gè)位置增加整數(shù)4
        myDoubleLinkedList.insert(3,new Integer(4));
        myDoubleLinkedList.insert(0,new Integer(0));
        System.out.println("\n增操作二測(cè)試：");
        myDoubleLinkedList.print();

        //刪操作一測(cè)試畴嘶，刪除第一、三個(gè)位置的元素
        myDoubleLinkedList.delete(2);
        myDoubleLinkedList.delete(0);
        System.out.println("\n刪操作一測(cè)試：");
        myDoubleLinkedList.print();

        //刪操作二測(cè)試集晚，刪除元素“4”
        System.out.println("\n刪操作二測(cè)試(刪除元素4)：");
        myDoubleLinkedList.remove(new Integer(4));
        myDoubleLinkedList.print();

        //刪操作二測(cè)試窗悯，刪除元素“6”
        System.out.println("\n刪操作二測(cè)試（刪除元素6）：");
        myDoubleLinkedList.remove(new Integer(6));
        myDoubleLinkedList.print();

        //改操作測(cè)試，將第二個(gè)位置的元素改為整數(shù)5
        myDoubleLinkedList.set(1,new Integer(5));
        System.out.println("\n改操作測(cè)試：");
        myDoubleLinkedList.print();

        //查操作測(cè)試偷拔，取第一個(gè)位置的元素
        System.out.println("\n查操作測(cè)試：");
        System.out.println(myDoubleLinkedList.get(0).toString());

        //合并操作測(cè)試蒋院，合并兩個(gè)循環(huán)鏈表
        System.out.println("\n合并操作測(cè)試：");
        MyDoubleLinkedList anotherList = new MyDoubleLinkedList();
        anotherList.add(7);
        anotherList.add(8);
        anotherList.add(9);
        myDoubleLinkedList.combine(anotherList);
        myDoubleLinkedList.print();
    }
}

測(cè)試結(jié)果

image.png

到現(xiàn)在感覺腦子不太夠用了亏钩。。代碼也不知道有沒有錯(cuò)誤悦污，希望看過的老鐵們多提提意見哈~