Java 实现双向链表以及对双链表的基本操作

1、双向链表的概念

  链表是一种比较常见的数据结构，在频繁进行增、删操作时链表效率高于数组，但读取效率不高。链表分为：双向链表，单向链表和循环链表。
  双向链表也叫双链表，不同于单链表只有一个指向下一结点的指针。双链表中拥有两个指针，分别指向当前结点的上一节点和下一节点。

2、示意图

2、代码实现以及功能详解

/**
 * 链表类，元素是以结点的信息存储的
 */
public class MylinkedList<T> {
    /**
     * 结点类，私有的。存放结点的值
     * 以及上一个结点和下一个结点的地址
     */
    private class Node {
        T element;
        Node previous; // 指向该结点的上一个结点
        Node next; // 指向该结点的下一个结点

        Node() {
        }

        // 构造
        Node(T element) {
            this.element = element;
        }
    }

    // 记录第一个结点
    private Node first;
    // 记录最后一个结点
    private Node last;
    // 记录链表中的结点个数
    private int count;


    /**
     * 获取链表中的结点个数
     *
     * @return 结点个数
     */
    public int size() {
        return count;
    }

    /**
     * 根据下标获取对应的结点并返回
     *
     * @param index 需要获取结点的下标
     * @return 下标对应的结点
     */
    private Node getNode(int index) {
        // 根据 index 获取元素值
        if (index < 0 || index >= count) {
            // 如果下标越界，则抛异常
            throw new IndexOutOfBoundsException("列表下标应在范围：[0 , " + count + ") 之间");
        }
        // 从第一个结点开始遍历
        Node node = this.first;
        for (int i = 0; i < index; i++) {
            // 遍历到下标对应的结点
            node = node.next;
        }
        // 返回遍历到的结点
        return node;
    }

    /**
     * 删除一个结点
     *
     * @param node 需要删除的结点
     */
    private void removeNode(Node node) {
        if (count == 1) {
            // 如果这个链表中只有一个结点
            //      那么清空链表即可
            this.first = null;
            this.last = null;
            // 结点个数 -1
            count--;
            return;
        }
        if (node == this.first) {
            // 如果需要删除的是 first 结点
            //      则修改 node 的下一个结点为 first
            this.first = node.next;
            // 将 node 的下一个结点的上一个结点设置为 null
            node.next.previous = null;
        } else if (node == this.last) {
            // 如果需要删除的是 last 结点
            //      则修改 node 的上一个结点为 last
            this.last = node.previous;
            // 将 node 的上一个结点的下一个结点设置为 null
            node.previous.next = null;
        } else {
            // 删除在中间的结点
            // 将 node 的下一个结点的 previous 指向 node 的上一个结点
            node.next.previous = node.previous;
            // 将 node 的上一个结点的 next 指向 node 下一个结点
            node.previous.next = node.next;
        }
        // 移除 node 的全部指向
        node.previous = null;
        node.next = null;
        // 元素个数 -1
        count--;
    }

    /**
     * 在链表后面追加结点
     *
     * @param element 新结点的元素值
     */
    public void add(T element) {
        // 实例化一个 Node 对象
        Node node = new Node(element);
        if (count == 0) {
            // 如果链表中没有任何结点
            //     则新增的元素为首位
            this.first = node;
        } else {
            // 如果链表中已经存在其他结点
            //     则依次往最后一个元素后追加
            this.last.next = node;
            node.previous = this.last;
        }
        this.last = node;
        // 元素个数 +1
        count++;
    }

    /**
     * 根据下标添加结点
     *
     * @param index   需要添加结点的下标
     * @param element 新结点的值
     */
    public void add(int index, T element) {
        // 实例化一个新的结点
        Node newNode = new Node(element);
        if (index == 0) {
            // 添加 first 结点
            //     将 newNode 的 next 指向原来的 first 结点
            newNode.next = this.first;
            // 将原来的 first 的 previous 指向 newNode
            this.first.previous = newNode;
            // 修改 fist 结点为 newNode
            this.first = newNode;
        } else if (index == count) {
            // 添加 last 结点
            //     将原来的 last 的 next 指向 newNode
            this.last.next = newNode;
            // 将 newNode 的 previous 指向原来的 last
            newNode.previous = this.last;
            // 修改 last 结点为 newNode
            this.last = newNode;
        } else {
            // 检查下标并获取下标对应的结点
            Node node = getNode(index);
            // 中间结点的修改
            // 新结点的上一个结点为原下标结点的上一个结点
            newNode.previous = node.previous;
            // 新结点的下一个结点为原下标结点
            newNode.next = node;
            // 修改原结点的上一个结点的 下一个结点为新结点
            node.previous.next = newNode;
            // 修改原结点的上一个结点为新结点
            node.previous = newNode;
        }
        // 元素个数 +1
        count++;
    }

    /**
     * 根据下标删除结点
     *
     * @param index 需要删除结点的下标
     * @return 成功删除的值
     */
    public T remove(int index) {
        // 检查下标并获取结点
        Node node = getNode(index);
        // 删除结点
        removeNode(node);
        // 返回删除的结点值
        return node.element;
    }

    /**
     * 将链表中指定下标为的元素，修改称为新的元素
     *
     * @param index   需要修改的下标
     * @param element 修改后的元素
     * @return 旧的修改前的元素
     */
    public T set(int index, T element) {
        // 验证下标并获取下标对应结点
        Node node = getNode(index);
        T oldElement = node.element;
        // 修改结点元素值
        node.element = element;
        // 返回修改前的旧元素
        return oldElement;
    }

    /**
     * 获取链表中指定下标位的元素
     *
     * @param index 需要获取的下标
     * @return 返回指定元素
     */
    public T get(int index) {
        // 验证下标并获取下标对应结点
        Node node = getNode(index);
        // 获取下标对应的元素值
        return node.element;
    }

    /**
     * 查询链表中某一个元素第一次出现的下标
     *
     * @param element 待查询的元素
     * @return 第一次出现的下标
     */
    public int indexOf(T element) {
        // 获取链表第一个结点
        Node node = this.first;
        // 循环遍历链表结点并进行元素比较
        for (int i = 0; i < size(); i++) {
            if (element.equals(node.element)) {
                // 返回第一次出现的下标
                return i;
            }
            node = node.next;
        }
        // 没找到返回 -1
        return -1;
    }

    /**
     * 判断链表中是否包含指定的元素
     *
     * @param element 待判断的元素
     * @return 判断结果
     */
    public boolean contains(T element) {
        return indexOf(element) != -1;
    }


    /**
     * 删除链表中指定的元素
     *
     * @param element 需要删除的元素
     * @return 是否成功删除
     */
    public boolean remove(T element) {
        // 获取链表第一个结点
        Node node = this.first;
        // 记录删除的元素个数
        int removeCnt = 0;
        // 循环遍历链表结点并进行元素比较
        for (int i = 0; i < size(); i++) {
            if (element.equals(node.element)) {
                // 删除符合要求的元素
                removeNode(node);
                // 计数器 +1
                removeCnt++;
            }
            node = node.next;
        }
        return removeCnt != 0;
    }

    // 如果只删除第一个出现的
    /*
    public boolean remove(T element) {
        int index = indexOf(element);
        if (index == -1) {
            return false;
        }
        remove(index);
        return true;
    }
    */

    /**
     * 清空链表的所有数据
     */
    public void clear() {
        this.first = null;
        this.last = null;
        count = 0;
    }


    @Override
    public String toString() {
        // 实例化一个 StringBuilder 对象
        if (count == 0) {
            // 如果链表为空，直接返回 []
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[ ");
        // 从第一个结点开始循环
        Node node = this.first;
        for (int i = 0; i < size(); i++) {
            // 追加到 StringBuilder 后面
            sb.append(node.element).append(" , ");
            node = node.next;
        }
        sb.replace(sb.length() - 3, sb.length(), " ]");
        return sb.toString();
    }
}

最后

以上就是听话黑裤为你收集整理的Java 实现双向链表以及对双链表的基本操作的全部内容，希望文章能够帮你解决Java 实现双向链表以及对双链表的基本操作所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。