【数据结构】模拟实现双向链表_模拟双向链表

你必须非常努力，才能显得毫不费劲 

---

目录

1.模拟实现双向链表 

1.1 DLinkedList的内部类

1.2 DLinkedList的成员属性

1.3 DLinkedList的成员方法

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

1.3.2 在链表结尾插入一个新的结点 

1.3.3 计算结点个数

1.3.4 在链表任意位置插入一个新结点

1.3.5 查找链表中是否有指定的数据

1.3.6 删除第一次出现的指定数据的结点

1.3.7 删除所有指定数据的结点

 1.3.8 打印链表

1.3.9 清除链表

---

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;
    }
}

1.3.2 在链表结尾插入一个新的结点 

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

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

1.3.3 计算结点个数

首先判断这个链表是否为空链表，如果为空直接返回0。否则不为空就遍历这个链表计数有多少个结点，遍历结束后直接返回结点的个数 

注：tail.next 是最后一个结点的下一个结点，当 cur == tail.next 说明链表已经遍历结束了

//结点个数
public int size() {
    if (this.head == null) {
        return 0;
    }
    Node cur = this.head;
    int count = 0;
    while (cur != this.tail.next) {
        count++;
        cur = cur.next;
    }
    return count;
}

1.3.4 在链表任意位置插入一个新结点

首先判断插入的位置是否合法，如果不合法直接返回 false。否则合法在判断插入的位置是否为第一个结点，如果是则为在链表开头插入一个新结点。否则判断插入的位置是否为最后一个结点，如果是则为在链表结尾插入一个新结点。否则就为在链表的中间插入一个新结点，首先需要根据 data 数据实例化一个结点，然后遍历链表找到 index 的位置，让新结点的前指针域存储 index 位置上的前一个结点的地址，让前一个结点的后指针域存储这个新结点的地址，让新结点的后指针域存储 index 位置上结点的地址，index位置上结点的前指针域存储新结点的地址

//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data){
    //判断位置是否合法
    if (index < 0 || index >= size()) {
        return false;
    }
    //判断是否为头插
    if (index == 0) {
        addFirst(data);
        return true;
    }
    //判断是否为尾插
    if (index == size() - 1) {
        addLast(data);
        return true;
    }
    //中间插
    Node tmpNode = new Node(data);
    Node cur = this.head;
    while (index != 0) {
        cur = cur.next;
        index--;
    }
    tmpNode.prev = cur.prev;
    cur.prev.next = tmpNode;
    tmpNode.next = cur;
    cur.prev = tmpNode;
    return true;
}

1.3.5 查找链表中是否有指定的数据

直接将这个链表遍历一遍，如果有直接返回 true，否则返回 false 

//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
    Node cur = this.head;
    while (cur != this.tail.next) {
        if (cur.val != key) {
            cur = cur.next;
        } else {
            return true;
        }
    }
    return false;
}

1.3.6 删除第一次出现的指定数据的结点

首先判断这个链表是否为 null，否则就判断指定数据的结点是否为链表的第一个结点，如果是直接让 head 等于 head.next 。否则就判断指定数据的结点是否为链表的最后一个结点，如果是直接让tail 等于 tail.next。否则就遍历链表找到要删除的结点，让这个要删除的结点前一个结点的后指针域存储这个要删除的结点后一个结点地址，让这个要删除的结点后一个结点的前指针域存储这个要删除结点的前一个结点的地址即可，然后直接 return，因为只删除第一次出现的。否则就没有这个结点

//删除第一次出现关键字为key的节点
public void remove(int key) {
    if (this.head == null) {
        return;
    }
    if (this.head.val == key) {
        this.head = this.head.next;
        return;
    }
    if (this.tail.val == key) {
        this.tail = this.tail.prev;
        return;
    }
    Node cur = this.head;
    while (cur != this.tail.next) {
        if (cur.val == key) {
            cur.prev.next = cur.next;
            cur.next.prev = cur.prev;
            return;
        } else {
            cur = cur.next;
        }
    }
}

1.3.7 删除所有指定数据的结点

首先判断这个链表是否为 null，如果为空直接 return。否则判断链表是否只有一个结点且这个结点是要删除的结点，如果是则 head 和 tail 都是指向的这个结点的，那么直接让 head 和 tail 指向null，即可删除。否则从第二个结点开始遍历，如果遍历到指定数据的结点，让这个要删除的结点前一个结点的后指针域存储这个要删除的结点后一个结点地址，让这个要删除的结点后一个结点的前指针域存储这个要删除结点的前一个结点地址即可，遍历到这个链表倒数第二个结点才会跳出循环，跳出循环后再去判断第一个结点是否是要删除的结点，如果是直接让 head 等于 head.next，然后再去判断最后一个结点是否是要删除的结点，如果是直接让 tail 等于 tail.next

注：如果链表是多个结点，则先删除中间指定数据的结点，然后再去判断第一个结点是否要删除和最后的结点是否要删除 

//删除所有值为key的节点
public void removeAllKey(int key) {
    if (this.head == null) {
        return;
    }
    //判断链表只要一个结点，且这个结点的值等于key
    if (this.head.val == key && this.head.next == null) {
        this.head = null;
        this.tail = null;
        return;
    }
    //删除中间等于key的结点
    Node cur = this.head.next;
    while (cur != this.tail) {
        if (cur.val == key) {
            cur.prev.next = cur.next;
            cur.next.prev = cur.prev;
        }
        cur = cur.next;
    }
    //第一个结点等于key删除
    if (this.head.val == key) {
        this.head = this.head.next;
    }
    //最后一个结点等于key删除
    if (this.tail.val == key) {
        this.tail = this.tail.prev;
    }
}

 1.3.8 打印链表

首先判断这个链表是否为 null，如果是直接打印 null，然后 return。否则把链表遍历一遍，依次打印结点数据域中的数据 

//打印
public void display() {
    if (head == null) {
        System.out.println("null");
        return;
    }
    Node cur = this.head;
    while(cur != this.tail.next) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();
}

1.3.9 清除链表

遍历一遍，依次清空每个结点的前指针域和后指针域，让它们都指向 null 即可，在让 head 等于null，tail 等于null，这样整个链表的每个结点都没有被指向，编译器会直接回收

//清除链表
public void clear() {
    if (this.head == null) {
        return;
    }
    Node cur = this.head;
    while (cur != this.tail.next) {
        Node tmp = cur.next;
        cur.next = null;
        cur.prev = null;
        cur = tmp;
    }
    this.head = null;
    this.tail = null;
}