图片来自 unsplash

双向链表

上次说到了单向链表 , 我么可以很轻松的从一个元素获取到下一个元素的引用 , 但是 , 如果我们突然有一个要获取上一个元素的需求呢 ? 这相对来说就很难了 , 尽管你可以在使用的时候专门创建一个对变量来指向上一个元素 .

双向链表的节点元素

双向链表的节点其实和单向链表差不多 , 只不过还要添加一个属性来引用最后一个元素 .

private class Node {
    public Item item = null;//元素节点内容
    public Node next = null;//下一个节点的引用
    public Node prev = null;//上一个节点的引用

    public Node(Item item) {
        this.item = item;
    }
}

方法列表

• add(Item item) : 添加一个新元素节点 .
• remove(int index) : 根据索引删除一个元素节点 .
• remove(Item item) : 根据给定得Item对象 , 删除一个元素节点 .
• toString() : 正向遍历输出所有元素节点 .
• reverseToString() : 反向遍历输出所有元素节点 .

代码实现

因为和单向链表差不多 , 只是对于prev要稍作处理 , 所以接不多说了 .

public class DoubleLinkList<Item> {

    /**
     * length : 链表长度
     * head : 链表第一个节点
     * tail : 链表最后一个节点
     */
    private int length = 0;
    private Node head = null;
    private Node tail = null;

    public void add(Item item) {
        Node newNode = new Node(item);
        if (this.length == 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.length++;
    }

    public boolean remove(int index) {
        if (index < 0 || index > this.length) {
            return false;
        }

        Node current = this.head;
        int i = 0;
        while (i <= index) {
            current = current.next;
        }
        current.prev.next = current.next;
        current.next.prev = current.prev;
        this.length--;
        return true;
    }

    public boolean remove(Item item) {
        Node current = this.head;
        while (current.item != item) {
            current = current.next;
            if (current == null) {
                return false;
            }
        }
        current.prev.next = current.next;
        current.next.prev = current.prev;
        this.length--;
        return true;
    }

    public String toString() {

        String str = "";
        Node current = this.head;
        str += current.item;
        while (current.next != null) {
            current = current.next;
            str += current.item;
        }

        return str;
    }

    public String reverseToString() {
        String str = "";
        Node current = this.tail;

        str += current.item;
        while (current.prev != null) {
            current = current.prev;
            str += current.item;
        }

        return str;
    }

    private class Node {
        public Item item = null;
        public Node next = null;
        public Node prev = null;

        public Node(Item item) {
            this.item = item;
        }
    }
}