双向链表介绍

双向链表是链表的一种，其每个数据节点存在两个指针，分别指向前一个节点和后一个节点，其操作与单向链表类似。本文仅为个人学习的记录，仅供参考。

相关操作介绍

本文主要实现以下操作：

• 链表的生成
• 判断链表是否为空
• 链表的清空

• 节点的插入

  • 头插法
  • 尾插法
• 节点的删除
• 返回第i个结点
• 返回链表的节点个数
• 根据给定值，返回该值在链表出现的第一个位置

Java实现

节点类

package linklist;

public class DualNode {
    public Integer data;
    public DualNode next;
    public DualNode pre;

    public DualNode() {

    }

    public DualNode(Integer data) {
        this.data = data;
        next = null;
        pre = null;
    }

    public DualNode(Integer data, DualNode pre, DualNode next) {
        this.data = data;
        this.pre = pre;
        this.next = next;
    }
}

测试类

package linklist;

public class Test {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        MyDualLinkedList myDualLinkedList = new MyDualLinkedList(arr);
        System.out.println(myDualLinkedList);
        myDualLinkedList.addLastNode(10);
        System.out.println(myDualLinkedList);
        myDualLinkedList.addFirstNode(0);
        System.out.println(myDualLinkedList);
        myDualLinkedList.delNode(6);
        System.out.println(myDualLinkedList);
        System.out.println(myDualLinkedList.getValue(5));
        System.out.println(myDualLinkedList.getNodeCount());
        System.out.println(myDualLinkedList.findNodeIndex(8));
        System.out.println(myDualLinkedList.isNull());
        myDualLinkedList.clear();
        System.out.println(myDualLinkedList.isNull());
    }
}

链表类

package linklist;

public class MyDualLinkedList {
    private DualNode head;//头节点


    public MyDualLinkedList() {
        head = new DualNode();
    }

    /**
     * 通过数组创建链表
     *
     * @param arr 数组
     */
    public MyDualLinkedList(int[] arr) {
        head = new DualNode();
        for (int a : arr) {
            addLastNode(a);
        }
    }

    /**
     * 尾插法添加节点
     *
     * @param value 值
     */
    public void addLastNode(int value) {
        DualNode node = head;
        //遍历链表
        while (node.next != null) {
            node = node.next;
        }
        node.next = new DualNode(value, node, null);//添加节点
    }

    /**
     * 头插法添加节点
     *
     * @param value 值
     */
    public void addFirstNode(int value) {
        DualNode node = head;
        node.next = new DualNode(value, node, node.next);
        node.next.next.pre = node.next;
    }

    /**
     * 判断链表是否为空
     *
     * @return 是否为空
     */
    public boolean isNull() {
        return head.next == null;
    }

    /**
     * 清空链表
     */
    public void clear() {
        head.next = null;
    }

    /**
     * 删除节点
     *
     * @param index 要删除的节点索引
     * @return 是否删除成功
     */
    public boolean delNode(int index) {
        DualNode node = head;
        //当索引不满足条件时直接返回失败
        if (index < 1) {
            return false;
        } else if (index == 1) {
            head.next.next.pre = head;
            head.next = head.next.next;
            return true;
        }
        int i = 0;
        //遍历链表，查找要删除的节点并删除
        while (node.next != null) {
            i++;
            if (i == index) {
                node.next.next.pre = node;
                node.next = node.next.next;
                return true;
            }
            node = node.next;
        }
        return false;
    }

    /**
     * 获取某个节点数据
     *
     * @param index 索引
     * @return 该节点数据，不存在返回null
     */
    public Integer getValue(int index) {
        DualNode node = head.next;
        int i = 0;
        while (node.next != null) {
            i++;
            if (i == index) {
                return node.data;
            }
            node = node.next;
        }
        return null;
    }

    /**
     * 获取节点个数
     *
     * @return 节点个数
     */
    public int getNodeCount() {
        DualNode node = head.next;
        int count = 1;
        while (node.next != null) {
            node = node.next;
            count++;
        }
        return count;
    }

    /**
     * 获取某个值的第一个所在节点索引
     *
     * @param value 值
     * @return 节点索引，不存在返回-1
     */
    public int findNodeIndex(int value) {
        DualNode node = head.next;
        if (node.data == value) {
            return 1;
        }
        int index = 1;
        while (node.next != null) {
            index++;
            node = node.next;
            if (node.data == value) {
                return index;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        if (head.next == null) {
            return "null";
        }
        DualNode node = head.next;
        String str = "";
        while (node.next != null) {
            str += node.data.toString() + ",";
            node = node.next;
        }
        str += node.data.toString();
        return "MyDualLinkedList{" +
                str +
                '}';
    }
}