看动画学算法之Java实现doublyLinkedList

看动画学算法是一种十分有趣的学习方式，Java实现doublyLinkedList正好可以通过该方法进行学习。下面是实现doublyLinkedList的完整攻略。

准备工作

在进行doublyLinkedList的实现之前，需要进行如下准备工作：

1. 确认Java编译器、JUnit测试框架和Maven构建工具是否已经安装好。
2. 创建一个新的Java项目并在其中添加JUnit测试框架和Maven构建工具依赖。
3. 创建一个新的Java类文件来存放doublyLinkedList的实现代码。

实现步骤

1. 定义Node类：Node类是doublyLinkedList的基础元素，节点包含三个重要的属性prev、next和data，分别表示前驱、后继和数据。需要注意的是，Node类需要定义一个构造函数来初始化这些属性。

public class Node<T> {
    public T data;
    public Node<T> prev;
    public Node<T> next;

    public Node(T data, Node<T> prev, Node<T> next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
}

1. 定义LinkedList类：LinkedList类是doublyLinkedList的核心，它包含两个重要的属性head和tail，分别表示链表的头部和尾部。同样需要定义一个构造函数来初始化这些属性。

public class LinkedList<T> {
    public Node<T> head;
    public Node<T> tail;

    public LinkedList() {
        this.head = null;
        this.tail = null;
    }
}

1. 实现addFirst()方法：该方法用于向链表的头部插入一个新的节点。如果链表为空，则新的节点既是头部也是尾部；否则将新节点作为链表的新头部，并更新头部节点的前驱指针。

public void addFirst(T data) {
    if (head == null) {
        head = new Node<>(data, null, null);
        tail = head;
    } else {
        Node<T> newNode = new Node<>(data, null, head);
        head.prev = newNode;
        head = newNode;
    }
}

1. 实现addLast()方法：该方法用于向链表的尾部插入一个新的节点。如果链表为空，则新的节点既是头部也是尾部；否则将新节点作为链表的新尾部，并更新尾部节点的后继指针。

public void addLast(T data) {
    if (tail == null) {
        tail = new Node<>(data, null, null);
        head = tail;
    } else {
        Node<T> newNode = new Node<>(data, tail, null);
        tail.next = newNode;
        tail = newNode;
    }
}

1. 实现removeFirst()方法：该方法用于删除链表的头部节点。如果链表为空则抛出空指针异常，否则将头部节点的后继节点作为新的头部，并更新新头部节点的前驱指针。

public void removeFirst() {
    if (head == null) {
        throw new NullPointerException("LinkedList is empty");
    } else if (head.equals(tail)) {
        head = null;
        tail = null;
    } else {
        head = head.next;
        head.prev = null;
    }
}

1. 实现removeLast()方法：该方法用于删除链表的尾部节点。如果链表为空则抛出空指针异常，否则将尾部节点的前驱节点作为新的尾部，并更新新尾部节点的后继指针。

public void removeLast() {
    if (tail == null) {
        throw new NullPointerException("LinkedList is empty");
    } else if (head.equals(tail)) {
        head = null;
        tail = null;
    } else {
        tail = tail.prev;
        tail.next = null;
    }
}

示例说明

下面两个示例分别演示了doublyLinkedList中的addFirst和removeLast方法的使用方式：

1. 插入一个新的节点到链表头部

LinkedList<String> linkedList = new LinkedList<>();
linkedList.addFirst("hello");
linkedList.addFirst("world");
System.out.println(linkedList.head.data); // world

1. 删除链表中的尾部节点

LinkedList<String> linkedList = new LinkedList<>();
linkedList.addLast("hello");
linkedList.addLast("world");
linkedList.removeLast();
System.out.println(linkedList.tail.data); // hello

通过上述几个步骤可以轻松的实现doublyLinkedList，并且通过JUnit测试框架可以确保其正确性。