Node

增加 pre 前驱 指向上一个节点

package _09_Linear.list;

/*节点*/!

public class ListNode {
    Object data;//数据
    ListNode next;//指向下一个节点的指针
    ListNode pre;

    public ListNode(Object data) {//初始化构造器
        this.data = data;
    }
}

DoublLinkedList

其head和tail都是空的 也就是如下定义的first和last
所有元素起于first.next 止于last

其中数据的增加
换四个linked

last.pre.next = newNode;//倒数第二个指向新的
newNode.next = last;//新的尾巴 指向 最后一个
newNode.pre = last.pre;//新的头指向 上次最后一个的前面一个
last.pre = newNode;//最后一个的头 指向新的

在删除 元素后 使得p.next p.pre =null 便于节约资源被CG清理

package _09_Linear.list;

public class DoubleLinkList implements MyList {
    private ListNode first = new ListNode(null);//head
    private ListNode last = new ListNode(null);//tail
    private int size;

    public DoubleLinkList() {//初始化两个 亚元
        first.next = last;
        last.pre = first;
    }

    /**
     * 加到 node：last 之前
     * 维护四条线
     *
     * @param element
     */
    @Override
    public void add(Object element) {
        ListNode newNode = new ListNode(element);

        last.pre.next = newNode;//倒数第二个指向新的
        newNode.next = last;//新的尾巴 指向 最后一个
        newNode.pre = last.pre;//新的头指向 上次最后一个的前面一个
        last.pre = newNode;//最后一个的头 指向新的

        size++;

    }

    @Override
    public void delete(Object element) {
        ListNode p = first.next;
        while (p != last) {//终止于 亚元
            if (p.data.equals(element)) {//当前p 匹配到了
                size--;
                p.pre.next = p.next;
                p.next.pre = p.pre;
            }
            p = p.next;//滑动指向下一个节点
        }
    }

    @Override
    public void delete(int index) {
        if (index < 0 || index >= size) {
            return;//索引超出 [0,size)
        }
        int i = 0;
        ListNode p = first.next;
        while (p != last) {
            if (i == index) {
                size--;
                p.pre.next = p.next;
                p.next.pre = p.pre;
                p.next = null;
                p.pre = null;
                break;
            }
            i++;
            p = p.next;
        }

    }

    @Override
    public void update(int index, Object newElement) {
        if (index < 0 || index >= size) {
            return;//索引超出 [0,size)
        }
        int i = 0;
        ListNode p = first.next;
        while (p != last) {
            if (i == index) {
                p.data = newElement;
                break;
            }
            i++;
            p = p.next;
        }
    }

    @Override
    public boolean contains(Object target) {
        ListNode p = first.next;
        while (p != last) {
            if (p.data.equals(target)) {
                return true;
            }
            p = p.next;
        }
        return false;
    }

    @Override
    public Object at(int index) {
        if (index < 0 && index >= size) {
            return null;
        }
        int i = 0;
        ListNode p = first.next;
        while (p != last) {
            if (i == index) {
                return p.data;
            }
            p = p.next;
            i++;
        }
        return null;
    }

    @Override
    public int indexOf(Object element) {
        ListNode p = first.next;
        int i = 0;
        while (p != last) {
            if (p.data.equals(element)) {
                return i;
            }
            p = p.next;
            i++;
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        ListNode p = first.next;
        while (p != last) {
            sb.append(p.data).append(p.next != last ? "," : "");
            p = p.next;
        }
        sb.append("]");//这么写的原因是 如果为空 就[] 不然写到while 里面 while不判定就gg
        return "DoubleLinkList{" +
                "elements=" + sb.toString() +
                "size=" + size +
                '}';
    }
}

Test

package _09_Linear.list;

import org.junit.Test;

public class DoubleLinkListTest {
    DoubleLinkList list = new DoubleLinkList();


    @Test
    public void add() {
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        System.out.println(list);
    }

    @Test
    public void delete() {
        add();
        System.out.println("deleteTest:");
        list.delete("a");
        System.out.println(list);
        list.delete("e");
        System.out.println(list);
    }

    @Test
    public void delete1() {
        add();
        System.out.println("deleteTestOfIndex:");
        list.delete(1);
        System.out.println(list);
    }

    @Test
    public void update() {
        add();
        list.update(1,'D');
        System.out.println(list);
    }

    @Test
    public void contains() {
        add();
        System.out.println(list.contains("b"));
    }

    @Test
    public void at() {
        add();
        System.out.println(list.at(4));
    }

    @Test
    public void indexOf() {
        add();
        System.out.println(list.indexOf("b"));
    }
}