【数据结构】模拟实现双向链表（1）

1.模拟实现双向链表

LinkedList 底层就是一个双向链表，那我们就来实现一个双向链表

我们首先需要创建一个类来实现这样一个链表：

public class DLinkedList {
}

接下来我们就需要将这个实现链表的过程全部放在 DLinkedList 这个类中

1.1 DLinkedList的内部类

我们知道链表是用结点来存储数据的，并且还是用结点来实现结点与结点之间的链接

那我们现在就需要在 DLinkedList类 中创建一个内部类当做结点类

//结点
private class Node {
    private int val;//数据
    private Node prev;//指向前一个结点
    private Node next;//指向后一个结点
    public Node(int val) {
        this.val = val;
    }
}

data：用来存放数据

prev：用来存储上一个结点的地址，从而达到结点与结点之间的双向的链接

next：用来存储下一个结点的地址，从而达到结点与结点之间的双向的链接

构造方法：每实例化一个结点类时，都需要调用构造方法，来把数据放入数据域

1.2 DLinkedList的成员属性

定义一个结点类型的 head 变量用来记录头结点，还定义了一个结点类型的 tail 变量用来记录尾结点

private Node head;//头结点
private Node tail;//尾结点

1.3 DLinkedList的成员方法

1.3.1 在链表开头插入一个新结点

在链表开头插入一个结点，首先需要根据 data 数据实例化一个结点，然后在判断这个链表是否是空链表，如果是空链表那么这个结点即是第一个结点又是最后结点。如果不是空链表直接让这个结点的后指针域存放 head 结点的地址，让 head 前指针域存放这个结点的地址，然后让 head 等于这个结点，因为这个结点变成了第一个结点

//头插法
public void addFirst(int data) {
    Node tmpNode = new Node(data);
    if (this.head == null) {
        this.head = tmpNode;
        this.tail = tmpNode;
    } else {
        tmpNode.next = this.head;
        this.head.prev = tmpNode;
        this.head = tmpNode;
    }
}